Carry-Lookahead Adder
Adding two binary numbers is easy one column at a time, and that is the problem. Column three cannot finish until column two says whether anything carried, and column two is waiting on column one. So the answer is correct only once the carry has walked the whole width, and the walk is the cost. Weinberger and Smith worked out in 1956 how to stop waiting: every bit can say, from its own two inputs alone, whether it will MAKE a carry or merely PASS one on, and from those two facts every carry in the adder can be built at once. Nothing here is timed. What an adder costs is the number of gates a signal must cross in turn, and that is a property of the wiring rather than of the machine running this page.
New to how an adder waits? Start here
Adding two binary numbers is easy per column: the two bits and whatever carried in, giving a sum bit and a carry out. The trouble is that last part. Column three cannot finish until column two tells it whether anything carried, and column two is waiting on column one.
So a straightforward adder is a queue. Its answer is correct the moment the carry has walked all the way from the bottom to the top, and that walk is what costs time. Nothing here is timed in seconds: the cost is the NUMBER of gates a signal must pass through in turn, which is a property of the wiring and the same on any hardware.
Everything is a switch
Underneath all of it is one part: a switch that is either on or off, and that can be operated by another switch rather than by a finger. That is the whole of the hardware vocabulary. AND is two switches in a row, so both must be on. OR is two side by side, so either will do. NOT turns the answer around.
There is nothing else in the box. Adding, remembering, choosing and counting are all arrangements of those three, and the machines in this topic are those arrangements, in the order somebody had to think of them.
The machine for this idea on its own is Flip-Flop, if you would rather press it than read about it.
Machines here that come first: The Adder.
The carry has to get all the way to the top
1 One bit at a time, each waiting for the carry out of the bit below it
Two numbers, and the carry walking up from the bottom. Every bit waits for the one beneath it, which is what the depth on the right is counting.
| bit | a | b | carry in | sum | carry out |
|---|
2 Generate and propagate worked out for every bit at once, from the inputs alone
The same two numbers, read differently. Each bit answers two questions from its own inputs, without knowing anything about its neighbours: does it MAKE a carry, and would it PASS one on.
| bit | a | b | generate | propagate |
|---|
3 Group carries built from those, so no bit waits for the one beneath it
A carry expanded all the way down to the inputs needs a gate with one input per bit, and past a handful those do not exist. So the lookahead is built in groups, and the depth that results grows with the logarithm of the width rather than staying flat.
| width | ripple | lookahead | deeper by |
|---|
4 The delay counted in gate levels for both designs, and the gates each one costs
What the depth was bought with. The lookahead is never cheaper in gates, at any width, and a page that showed only the win would be selling something.
| width | ripple | lookahead | costlier by |
|---|
| claim | held | measured |
|---|---|---|
| both adders agree with plain integer addition on 1000 pairs across every width | yes | sum and carry-out both, from a fixed seed so a failure repeats |
| the ripple's depth grows by two gates for every bit added | yes | 4:9, 8:17, 16:33, 32:65, 64:129 |
| the lookahead's depth grows with the logarithm of the width, not the width | yes | 4:4, 8:6, 16:6, 32:8, 64:8 at fan-in 4 |
| and it is bought with more gates at every width, never fewer | yes | 4: 20 to 23; 8: 40 to 57; 16: 80 to 103; 32: 160 to 217; 64: 320 to 423 |
| fan-in is bounded at 4, so this is not the flat depth a textbook draws | yes | a carry expanded to the inputs at 64 bits would need a 64-input gate. Those do not exist, so the lookahead is done in groups and the depth is logarithmic rather than constant |
| the all-ones-plus-one case makes the carry cross every bit, and both still agree | yes | bit zero generates, because it is 1 + 1, and every bit above it merely propagates. That is what makes it the worst case: ONE carry created at the bottom and passed the whole way up. The first version of this line said no bit generates, which the page's own table contradicts |
| the depths are derived from the structure, because JavaScript has no gates | yes | the carries above are computed by an ordinary loop -- the VALUES are the same however they are worked out, which is why the sums can be checked against integer addition. The DEPTH cannot be observed here at all, so it is counted from the wiring the two designs describe. Nothing on this page is timed, and a millisecond figure in a browser would be measuring JavaScript rather than an adder. |
| the gate counts are a model at fan-in 4, not a netlist | yes | five gates per bit for the ripple, and for the lookahead two per bit for generate and propagate, 11 per group, and one XOR per bit for the sum. A real cell library would differ; what survives any library is that the lookahead costs more gates and less depth, which is the trade the page is about. |
What is real here, and what is not
Nothing here is timed
A millisecond figure measured in a browser would be measuring JavaScript, not an adder. What an adder costs is the number of gates a signal has to cross one after another before the answer is stable, and that number comes from the wiring. So the depths on this page are counted from the structure the two designs describe, and the page says so rather than implying it watched a clock.
The carries are computed by an ordinary loop
The VALUES are the same however they are worked out, which is exactly why the sums can be checked against plain integer addition and are. What cannot be reproduced in JavaScript is the simultaneity: a real lookahead computes those carries in parallel and this page computes them in sequence. The depth figure is a claim about the circuit, not about the loop above it.
Fan-in is bounded at four, and that changes the answer
Many explanations draw the carry expanded all the way to the inputs and report a constant depth of three gates at any width. That circuit is not buildable: at 64 bits it needs a 64-input gate. Bounding fan-in at four puts the lookahead into a tree of groups, and the depth becomes logarithmic rather than constant. The figure this page prints is the buildable one.
The gate counts are a model, not a netlist
Five gates per bit for the ripple; for the lookahead, two per bit for generate and propagate, eleven per group, and one exclusive-or per bit for the sum. A real cell library would give different numbers. What survives any library is the direction: the lookahead costs more gates and less depth, and that trade is the subject.
1956, not 1958
This machine sat on the planned list with 1958 against it. The paper is Weinberger and Smith, IRE Transactions on Electronic Computers EC-5(2), pages 65 to 73, June 1956. The date was checked before the page was written, which is the only reason the error did not ship.
Sources
- A. Weinberger and J. L. Smith, A One-Microsecond Adder Using One-Megacycle Circuitry, IRE Transactions on Electronic Computers EC-5(2):65-73, June 1956 — the paper this machine is about, and the source of the date correction above.
- The Adder, on this site — the ripple this one is measured against, one bit at a time.
- Logical Art, the studio this belongs to.