At the very least, most people expect computers to do some kind of arithmetic computation, and thus, most people expect computers to add.
We're going to construct combinational logic circuits that perform binary addition. The first question you should ask when adding binary numbers, given all the time we've spent talking about representation is "what representation are we talking about"?
Clearly the choice of representation is going to affect how we perform the addition. Certain representations allow us to add in the way we add base ten numbers.
What is a Full Adder?
A Full Adder is a combinational circuit that performs the arithmetic sum of three input bits. It consists of three inputs and two outputs. Three of the input variables can be defined as A, B, Cin and the two output variables can be defined as S, Cout. The two input variables that we defined earlier A and B represents the two significant bits to be added. The third input Cin represents the carry bit. We have to use two digits because the arithmetic sum of the three binary digits needs two digits. The two outputs represents S for sum and Cout for carry.
For designing a full adder circuit, two half adder circuits and an OR gate is required. It is the simplest way to design a full adder circuit. For this two XOR gates, two AND gates, one OR gate is required.
Full Adders
Full Adders
The logic table for a full adder is slightly more complicated
than the tables we have used before, because now we have
3 input bits. It looks like this:
than the tables we have used before, because now we have
3 input bits. It looks like this:
| |||||||||||||||||||||||||||||||||||||||||||||
There are many different ways that you might implement this table. I am going to present one method here that has the benefit of being easy to understand. If you look at the Q bit, you can see that the top 4 bits are behaving like an XOR gate with respect to A and B, while the bottom 4 bits are behaving like an XNOR gate with respect to A and B. Similarly, the top 4 bits of CO are behaving like an AND gate with respect to A and B, and the bottom 4 bits behave like an OR gate. Taking those facts, the following circuit implements a full adder:
This definitely is not
the most efficient way to implement a full adder, but it is extremely easy to
understand and trace through the logic using this method. If you are so
inclined, see what you can do to implement this logic with fewer gates.
Now we have a piece of
functionality called a "full adder." What a computer engineer then
does is "black-box" it so that he or she can stop worrying about the
details of the component. A black box for a full adder would look
like this:
In this diagram the
carry-out from each bit feeds directly into the carry-in of the next bit over.
A 0 is hard-wired into the initial carry-in bit. If you input two 4-bit numbers
on the A and B lines, you will get the 4-bit sum out on the Q lines, plus 1
additional bit for the final carry-out. You can see that this chain can extend
as far as you like, through 8, 16 or 32 bits if desired.
The 4-bit adder we just
created is called a ripple-carry adder. It gets that name because the
carry bits "ripple" from one adder to the next. This implementation
has the advantage of simplicity but the disadvantage of speed problems. In a
real circuit, gates take time to switch states (the time is on the order of
nanoseconds, but in high-speed computers nanoseconds matter). So 32-bit or
64-bit ripple-carry adders might take 100 to 200 nanoseconds to settle into
their final sum because of carry ripple. For this reason, engineers have
created more advanced adders called carry-lookahead adders. The
number of gates required to implement carry-lookahead is large, but the
settling time for the adder is much better.http://computer.howstuffworks.com/boolean3.htm
Building Blocks: Full Adders
The problem with a half-adder is that there it doesn't handle carries. When you look at the left column of the addition
1 0
1 1 0
+ 0 1 1
-----------
(1) 0 0 1
you see that you add three bits. Half adders only add two bits.
We need a circuit that can add three bits. That circuit is called a full adder.
Here are the characteristics of a full adder.
- Data inputs: 3 (call them x, y, and cin, for carry in)
- Outputs: 2 (call them s, for sum, and cout, for carry out)
Notice we now need to make a distinction whether the carry is an input (cin) or an output (cout). Carry in's in column i are due to carry outs from column i - 1 (assuming we number columns right to left, starting at column 0 at the least significant bit).
Here's a truth table for full adders.
| Row | x | y | cin | cout | s |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 1 |
| 2 | 0 | 1 | 0 | 0 | 1 |
| 3 | 0 | 1 | 1 | 1 | 0 |
| 4 | 1 | 0 | 0 | 0 | 1 |
| 5 | 1 | 0 | 1 | 1 | 0 |
| 6 | 1 | 1 | 0 | 1 | 0 |
| 7 | 1 | 1 | 1 | 1 | 1 |
Ripple Carry Adders
Once you have half adders and full adders, you can now construct ripple carry adders.
A ripple carry adder allows you to add two k-bit numbers. We use the half adders and full adders and add them a column at a time.
Let's put the adder together one step at a time.
Before Adding
Adding Column 0
We add x0 to y0, to produce z0.
Adding Column 1
In column 1, We add x1 to y1 and c1 and, to produce z1, and c2, where ci is the carry-in for column i and ci + 1 is the carry-out of column i.
Adding Column 2
In column 2, We add x2 to y2 and c2 and, to produce z2, and c3.
Using Only Full Adders
We don't really need to use the half adder. We could replace the half adder with a full adder, with a hardwired 0 for the carry in.
