A student writes:
Dr. Patt,
During the review session tonight, I asked about the carry look-ahead
adder material. You asked me to send you a reminder to put together some
supplemental material on that topic.
Best Regards,
<<name withheld to protect the inquisitive one>>
Thank you for reminding me.
Recall that addition can be carried out by table look up, which is fast but
requires a huge amount of storage or by an algorithm that adds each column,
digit by digit, from right to left, which takes much less logic but is also
much slower.
You recall the example I gave early in the course:
12 359
+ 9 + 497
----- -------
I asked you to write the two answers down, Then I asked in the first case
(answer = 21), what did you write first, the 2 or the 1. Then I asked in the
second case (answer = 856), what did you write first, the 8 or the 6.
Most people write the 2 of 21 first, but the 6 of 856. Why? Because the
first ADD is done by table lookup from your memory, and the second ADD is
done by an algorithm that works its way through the digits, from right to left.
What is the point? The point is that there is nothing intrinsically time
varying about addition. We introduce the notion of time by our algorithm
which each step of the way, propagates the carry from right to left. We use
this algorithm because the storage cost of total table look up is far too
excessive.
Question: Is there anything we can do that is halfway -- that is not as
expensive as table lookup for large integers, but does not require the
inordinate cost of propagating the carry 32 steps, for example, as is done
in doing a 32 bit ADD. Answer: Lookahead Carry Generation.
It works as follows:
We will use the following example to illustrate the points (we will use
16 bits in the interest of saving me energy):
A: 0011011101011000
B: 0100100110101010
----------------
We will call the MSB bit 15, and LSB bit 0.
Step 1: Break up the word in pieces. The usual size of a piece is four
bits, but that is arbitrary.
0011 0111 0101 1000
0100 1001 1010 1010
We would like to be able to perform these four adds (each ADD operates
on 4-bit pieces) simultaneously. We can't do this since we can not
add A4 and B4 until we know the carry out of bit 3, for example.
Question: is there any way to generate the carry out of bit 3 quickly.
Answer: Step 2.
Step 2: Examine the two four bit values in each "piece." Is there a
carry out of that piece? That is out of bit 3, out of bit 7, and out
of bit 11.
There are three cases.
If the sum of the A part and the B part is greater than
15 (i.e., 1111), then there is a carry out of the piece.
We say the piece GENERATES a carry. G=1
If the sum of the A part and the B part is less than 15,
then there is no carry out of the piece, even if there is
a carry into the piece. We say the piece DOES NOT GENERATE
a carry. G=0
If the sum of the A part and the B part is exactly 15, then
there is a carry out of the piece ONLY IF there is a carry
into the piece. We say the piece PROPAGATES a carry. P=1.
We provide logic to produce the G,P signals for each piece.
Step 3: We provide an additional piece of logic, called a Lookahead
Carry Generator that takes as input the G,P of each piece and produces
the carry out of bits 3, 7, and 11.
Note that carry out of bit 3 is 1 if G from first piece is 1.
Note that carry out of bit 7 is 1 if G from second piece is 1, or
if P from second piece is 1 and G from first piece is 1.
Note that carry out of bit 11 is 1 if G from third piece is 1, or
if P from third piece is 1 and G from second piece is 1, or if
P from third piece is 1 and P from second piece is 1 and G from
first piece is 1.
Thus, a simple combinational logic circuit, having G,P from each piece,
can, in two levels of logic, produce the carries necessary for each piece.
Step 4: Do the ADD in each piece concurrently, using the corresponding
carry out bits produced by the Lookahead Carry Generator.
Summary. We have reduced the time to add from the time it takes to
propagate the carry 16 steps to:
the time it takes to generate P,G for each case (concurrently),
say, four steps -- if you do it by propagating the carry, +
the time it takes for the Lookahead Carry Generator to produce
the carries needed by each piece, +
the time it takes to perform each piece of the ADD (again,
concurrently) using the carry information provided by the
Lookahead Carry Generator. Again, four steps.
4 + 2 (for the logic of the Lookahead Carry Generator) + 4 much less than
16. So, we win. We could gain more for larger size data types by breaking
into more pieces, and having a little more complicated Lookahead Carry
Generator.
OK?
Yale Patt