Carry-lookahead: generate and propagate — adders
exam standardtrading gates for depth
Answer
G column 00000011, P column 00111100, C1 column 00010111
Why this example is worth doing
Rewriting the carry chain in terms of generate and propagate turns a linear ripple into a shallow tree: each carry is computed directly from the inputs instead of waiting for its neighbour. The page derives the two-bit case in full and states the general recurrence, then makes the cost explicit — the gate count grows quadratically while the depth grows logarithmically, which is the fundamental trade in arithmetic circuit design.
Try your own input in the Half adder & full adder. Truth tables, K-maps and circuits for both adders, and the ripple-carry chain.
How the answer is reached
Output table
| A | B | C0 | G | P | C1 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 | 1 |