Logic Gates - Building an ALU

1 Introduction

The goal of this tutorial is to understand the basics of building complex circuit from simple AND, OR, NOT and XOR logical gates. (We have studied in class the functionalities of the corresponding bitwise operators.) This tutorial will teach you how to build an Arithmetic Logic Unit (ALU) from scratch, using these simple logic gates and other components. Read each tutorial step carefully and complete the activities listed in each step.
The ALU will take in two 32-bit values, and 2 control lines. Depending on the value of the control lines, the output will be the addition, subtraction, bitwise AND or bitwise OR of the inputs. Schematically, here is what we want to build:
Note! This is an interface for the ALU: what goes in, what comes out. It also shows the ALU as an abstraction: you can't see how it works, but you do know what it does.
Also note that there are three status outputs as well as the main result: is the result zero, was there a carry, and did the operation result in an overflow?
Note: just a reminder on the difference between a carry and an overflow:
- Carry: was there a carry in the most-significant bit which we could not output in the given number of bits (32 bits, above)?
- Overflow: does the sign of the output differ from the inputs, indicating (for example) that a sum of two positive numbers has overflowed and is now a negative result?
Some of the data and control lines are shown with a slash and a number like 32.
This indicates that the line is actually 32 lines in parallel, e.g. the result is 32-bits wide. If you don't see a slash in the diagrams below, you can assume that the line is only 1-bit wide.

1.1 Basic Components

We are going to use four logic gates: AND, OR, NOT and XOR. You should Below are the icons for each, and their truth table. (We have already seen the truth tables in class.)
We are going to use another component, the multiplexor. The job of the multiplexor is to choose one of several inputs, based on a control line, and send the chosen input to the output.
This multiplexor above is a 1-bit wide 2-way multiplexor: 2 inputs, 1 bit wide each. If you add extra control lines, you can choose more inputs: 2 control lines is used in a 4-way multiplexor, 3 control lines in an 8-way multiplexor etc.
And by using multiple multiplexors in parallel, you can make N-bit wide multiplexors.
I'm not going to show you the internals of the multiplexor. You should, however, know that it can be easily built with the 4 logic gates above.

1.2 Bitwise AND

Bitwise AND is very useful, for example to calculate an IP network's identity:
- 131.245.7.18 AND 255.255.255.0 => 131.245.7.0
Building the logic to do 32-bit AND on two inputs is easy: as each bit is independent, we just need 32 AND gates in parallel.
Note the interface diagram on the right. Each time we build a larger component, we are going to hide it behind an interface.

What To Do

Download the digital logic circuit simulator Logisim. Make sure you select the correct binary for your platform.
Run Logisim and and go through the tutorial available under the Help menu. Cover the Beginner's section first, then the Subcircuits and the Wire bundle section. You will need to use a splitter wire in your ALU implementation. The interface is simple and intuitive.
Here is a 4-bit ALU implemented in Logisim: ALU4.circ. Download this file and make a copy of it called ALU6.circ. (You will need the original ALU4.circ in later steps.) Open ALU6.circ in Logisim, then double-click on the 4-bit AND component in the left drop-down menu. The 4-bit AND circuit should open up for you. Select the Hand icon in the top-left of the Logisim window, then click on the data inputs to change their values. Make sure that the AND component works as expected.
Extend the AND component to work with 6-bit values instead of 4 bits.

1.3 Bitwise OR

32-bit bitwise OR is just as easy as bitwise AND, we just need 32 OR gates in parallel.

What To Do

Make a copy of your current ALU4.circ version, in case you need to revert to it later.
Open the 4-bit OR circuit by double-clicking on it in the left drop-down menu. Select the Hand icon in the top-left of the Logisim window, then click on the data inputs to change their values. Make sure that the OR component works as expected.
Extend the OR component to work with 6-bit values instead of 4 bits.

1.4 Addition

Addition isn't going to be so easy.
We saw previously that we have to add bits, and this may produce a carry. Columns further up need to accept a carry as input, along with two inputs, and produce the 1-bit output and another carry for the next column up.
The component which will perform a 1-bit ADD, receiving a carry in and producing a 1-bit output and a carry out is called a full adder. Its interface looks like the following:
Internally, here is what a full adder looks like, just 5 logic gates.
The truth table for the full adder is:

Cin A B Result Cout

0 0 0 0 0

0 0 1 1 0

0 1 0 1 0

0 1 1 0 1

1 0 0 1 0

1 0 1 0 1

1 1 0 0 1

1 1 1 1 1
At some point sit down, try some inputs, and convince yourself that the logic works as advertised!
To make a 32-bit full adder, we simply have to string 32 of these 1-bit full adders together.
Except for the least-significant adder, each one is going to receive its carry from the one below and pass up its own carry to the one above.
For the most significant bit, if the carry is a 1, then we ran out of bits to store the result.
When the final carry output is 1, this indicates that the result was too big to fit into 32 bits.
I'm going to delay showing you the interface diagram for the 32-bit full adder, because we can modify it to also do subtraction.

1.5 Subtraction

We could build a completely separate component, a 32-bit subtractor, once we work out how to build a 1-bit subtractor.
Fortunately, we can simplify things a bit.
According to the rules of maths: 3-2=3+(-2).
If we could negate one of the inputs, we could use the existing 32-bit full adder.
We have already learned how to negate a twos complement binary integer: invert every bit in the number, then add 1.
Putting all of the above together, we can say:
A - B = A + (-B) = A + ~B + 1
Inverting every bit is easy: we can use a NOT gate for each bit in B.
But now we need to do A + ~B + 1. How can we do this?
We are going to use a very clever trick.
- Set the initial carry-in to 1 instead of 0, thus adding an extra 1 to the sum.
- And instead of using NOT gates, we will use XOR gates.
If we are doing addition (Control=0), then one arm of the XOR gates is zero, and the B bits go into the adders unchanged, and the carry-in is zero.
If we are doing subtraction (Control=1), then one arm of the XOR gates is one. This inverts all of the B bits before they get to the adders. As well, the carry-in is now 1, so we achieve the result of doing A - B = A + ~B + 1!
Overall, we end up with this unit which can do addition and subtraction:
If the operation bit is 0, we pass in B and perform A+B. If the operation bit is 1, we invert B and do A + ~B + 1.
We can now distinguish between data lines (which pass data around) and control lines (which control the actions of the components).
The data lines are also known as datapaths.
The Operation line above is a control line, as it controls the action being performed. But note, it is also used as a 1-value for the carry-in, so it is also a piece of data!

1.6 Overflow Output

We've seen that a carry occurs when the final addition or subtraction is too big to fit into 32 bits.
A related mathematical output is overflow. This indicates that the sign of the maths result differs from the sign of the two inputs.
Imagine we were using 4-bit numbers: you do 7 + 7 and get the result -2!
Why? Because 7 (0111) + 7 (0111) = 1110, which in 4-bit twos-complement is -2.
Overflow occurs when the size of the inputs is such that there is a carry which changes the most-significant sign bit.
The ALU will always output both carry and overflow, but both only makes sense when the operation is add or subtract.
When we are doing the logical operations (AND and OR), the values on the carry and overflow outputs have no meaning.
As overflow is only maths related, this should be implemented in the ADD/SUBTRACT unit.
The logic is follows: when adding, if the sign of the two inputs is the same, but the result sign is different, then we have an overflow.
The boolean expression is [~a31]·[~b31]·result31+a31·b31·[~result31].
We have to do this only for addition, so we take the b31 value after the XOR gate, i.e. just as it goes into the most-significant adder.

1.7 Negative Output

When is the result negative? When its most-significant bit is 1.
We can wire this bit directly out of the ALU, so that it indicates if the result is negative.

1.8 Zero Output

One thing left to do is to provide the zero output: is the result zero?
This is only true if all of the bits of the result are zero. We can do this for the logical and the maths units.
To do this, we can use a 32-bit OR gate followed by a 1-bit NOT gate:
The OR gate outputs a 0 only if all input bits are 0. If any input bit is a 1, the OR's output is a 1.
The NOT gate simply inverts this, giving the result:
- if any result bit is on, the output is 0, i.e. not zero.
- if all result bits are off, the output is 1, i.e. zero.

What To Do

Make a copy of your current ALU4.circ version, in case you need to revert to it later.
Open the 4-bit Adder/Subtracter circuit by double-clicking on it in the left drop-down menu. Select the Hand icon in the top-left of the Logisim window, then click on the data inputs to change their values. Note that when the 1-bit Add/Sub control is 0 the circuit performs addition, otherwise it performs subtraction.
Extend the Adder/Subtracter cicrcuit to work with 6-bit values instead of 4 bits.

1.9 Putting It All Together

We are getting close to being able to build the full ALU.
We now have three main units:
- a 32-bit bitwise AND unit,
- a 32-bit bitwise OR unit, and
- a 32-bit ADD/SUBTRACT unit with a control line.
- the logic to output carry, overflow, zero and negative.
We can pass the inputs A and B to all three units, and perform all three operations in parallel:
But, we need to choose which of the three results we want, based on the two control lines coming into the ALU. We would like:

c₁ c₀ Result

0 0 A AND B

0 1 A OR B

1 0 A + B

1 1 A - B
How do we control which of the four operations actually becomes the result? With multiplexors again.
When c₀=0, the ANDORresult is A AND B, and the ADDSUBresult is A + B.
When c₀=1, the ANDORresult is A OR B, and the ADDSUBresult is A - B.
Now we just have to choose between these two results, and that is done with the second multiplexor, which chooses either the bitwise logic result or the maths result.

1.10 Finally

To finish off, we can draw the three components, the multiplexors and the zero logic, to reveal the final 32-bit ALU.
The dotted line shows the interface to the ALU.

What To Do

Make a copy of your current ALU4.circ version, in case you need to revert to it later.
Open the main ALU circuit by double-clicking on it in the left drop-down menu. It is designed to operate on 4 bits, so you can test it only in the original ALU4.circ version.
Open the original ALU4.circ file and try out some additions, subtractions, ANDs and ORs, and satisfy yourself that the ALU works as advertised.
Extend the ALU to work with 6-bit values instead of 4 bits.
See if you can put in some input values which cause an oveflow.
Turn in printed copies of your ALU (showing an overflow) and all its subcircuits.

1.12 Conclusion

That's about all we can cover in terms of ALU design in this subject.
Obviously, real ALUs perform many more operations, and use many performance optimizations.
This is just a taste of ALU design, but you should now understand that:
- an ALU is just a collection of logic components;
- the logic components can be made from ordinary logic gates;
- data can flow in parallel to multiple units;
- everything operates in parallel: several units can produce output internally;
- control logic, via multiplexors, chooses which output to use as the result.

Acknowledgement. This tutorial has been developed by Dr. Warren Toomey, and slightly modified by Dr. Mirela Damian.

Cin	A	B	Result	Cout

0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

c₁	c₀	Result

0	0	A AND B
0	1	A OR B
1	0	A + B
1	1	A - B