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