Ok, we left off last time discussing the issues involved in binary arithmetic. Specifically, we discussed subtraction and negative numbers. We watched a Compuphile video about the issues and the Prof. showed us how to use 2’s complement to use negative numbers and addition to complete subtraction. I had asked you to play around with your own ideas on how to implement this in hardware using Logisim to simulate your ideas. I hope you had fun doing that. Here’s my idea for implementing a binary adder that uses two’s complement to do subtraction.
Now this is only one stage of the circuit. What I’ve done is taken a typical full-adder circuit and added an XOR gate to the B input. The other leg of the XOR gate is used to control the inversion of the B input value. Additionally, I’ve also tied the Sub input control bit to an OR gate used to force a carry-in bit into the adder. This has the effect of inverting B to get the 1;s complement and then adding 1 to get the 2’s complement. Only the first bit needs the OR gate for a carry-in. However, every bit in B will need the XOR gate to invert the bit.
Ok, now that we’ve taken care of old business it is time to look at the next stage of our Microprocessor development. The core of any Microprocessor or Micro-controller is it’s Arithmetic Logic Unit. This piece of hardware is responsible for completing arithmetic and logic operations. If a basic logic or arithmetic operation is not implemented in the ALU it is much more difficult to implement that function in the systems built around the microprocessor. There are a few exceptions to that… We’ll discuss some of those later. For now, let’s look at how we might build an ALU for the MiniMips.
If you’ve followed this series so far, I assume you have the basic understanding of the primitive logic operations AND, OR, NOT, and XOR. We need to implement AND, OR, NOT, and XOR as well as Addition and Subtraction in our ALU. The simplest way to do this is to include a hardware circuit for each operation and then complete them in parallel. We can then select the desired operation from the various results. Since our hardware operates in parallel it takes no extra time to implement additional operations in our ALU this way.
So our ALU operations should look something like this:
One thing we haven’t discussed yet is Signal Bus’s. A signal buss is simply a group of conductors with a common implementation theme. For example, our ALU takes two inputs A and B. Each of these inputs contains 16 signal lines, one for each bit in the 16-bit value. We could refer to these signals as the A input Bus and B input Bus. You may have also heard of the Address bus and Data Bus in a computer system. These are just groups of Address or Data signals just like our A and B inputs. A simple way to think of a bus is just to think of them as a bundle of wires all carrying related signals.
Our simple ALU has six operations. It can Add, Subtract, NOT, AND, OR, and XOR our input values. Note that Inverting is only supported on the B input. This was a choice made for our design that helped reduce the number of logic gates needed to implement the design. This is great! We can now do multiple operations on our two input values. But how do we select the results of just a single operation? Well, that’s where multiplexer come in.
A multiplexer can be thought of as a rotary switch that selects one of many input signals:
This image show’s a two pole rotary switch. But let’s just concentrate on the top portion of the image. S1a is the first pole and the center armature or wiper simply rotates to make and break contact with the outer contact points as the user turns the rotor. To allow multiple conductors like our two input values A and B to be selected, these switches are manufactured with many sets of switches stacked on top of each other and connected to a single rotor. This way when the user turns the rotor, all the wipers rotate at the same time. With the switch shown a user can select from 1 of 6 positions. If we used rotary switches in our computer we would have to rotate these switches by hand to the proper positions and at the proper times, just to complete a single operation. Luckily there are solid state implementations of these devices called multiplexers and demultiplexers. A multiplexer simply takes many input values and switches one of them to a single output. A demultiplexer works the other way around. So a multiplexer is a many to one and demultiplexer of a one to many switch. In Logisim you’ll find multiplexers and demultiplexers under the Plexer components.
You may be asking how we tell a mux or demux (multiplexer/demultiplexer) which contacts to use or how each input to select? Well, we have to provide a selection signal. This is just a binary value. Let’s look at a simple four bit to one bit multiplex circuit.
Build the Mux and Demux circuits shown below and see that the input or output is selected buy the two select bits S0 and S1. These are simple 4-to-1 and 1-to-4 circuits that control a single bit. We will need circuits that control 16-bit inputs with as many as 16 selectable inputs.
As you can see, we’ve used a set of AND gates and wired the the selection inputs and their complements to the gates to provide activation of each gate with a specific binary value. This allows only one AND gate to be active at a time. The AND gate outputs are all then fed into a single OR gate. That gate outputs is the signal on the input to the selected AND gate.
To convert the mux into a demux, we only need to tie all the signal inputs together and remove the OR gate. Try this in logisim. Build the two circuits above and tie the output of the mux to the input of the demux. Then tie S1 together on both circuits. Next tie S0 together on both circuits. Now you should be able to select one input on the mux and get the signal out of the same input on the demux.
Now let’s see how we can tie a mux to our ALU so that we can select a single operation from the ALU:
Ok, so here we have our ALU with a few extras. First and foremost is Mux we added to the output. I’ve labeled the select lines for the Mux as OPCODE. If you look at the miring of the mux you’ll notice that I wired the out of the adder to the first two inputs of the mux. I then created a decoder that decodes the value 1 from the four OPCODE bits. The resulting signal is used to tell the Adder/Subtractor to subtract. This allows us to select Addition as 0 and subtraction as 1. Here’s a table of OPCODE values and ALU operations:
|0011||A AND B|
|0100||A OR B|
|0101||A XOR B|
Now you may have noticed that I used a mux with four select inputs. This allows up to 16 operations but I’ve only included six here. We will be adding more operations to our ALU later. Now you may be asking “Where does the values for A, B and OPCODE come from” ? Well, that all depends on our instruction set and how we implement it. We’ll be discussing that soon. For now, try and build an ALU that matches the operation of this one.