The ripple carry adder
Chain one full adder per bit, carry out into carry in, and you can add numbers of any width. It is the simplest adder there is, the one inside this site's calculator example, and the reason the carry lookahead adder was invented.
The cell: a full adder
Adding two binary numbers by hand, each column takes three bits: one from each number and a carry from the column to the right. It produces a sum bit and a carry to the left. A full adder is that one column as a circuit, and its truth table is just the eight ways three bits can add up to 0, 1, 2 or 3:
| A | B | Cin | Sum | Cout | Total |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 2 |
| 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 2 |
| 1 | 1 | 0 | 0 | 1 | 2 |
| 1 | 1 | 1 | 1 | 1 | 3 |
Sum = A ⊻ B ⊻ Cin
Cout = AB ∨ Cin(A ⊻ B)
The sum is 1 when an odd number of inputs are 1, which is XOR. The carry is 1 when at least two are, which is the majority function; writing it with the shared A ⊻ B is what lets a full adder be built from two half adders and an OR gate.
Chaining them: the 4-bit adder
Put four full adders side by side. Bit 0 of each number goes into the first, with the carry in; its carry out goes into the second along with bit 1 of each number; and so on up the word. The four sum bits are the answer and the final carry out is a fifth bit, worth 16, for when the answer does not fit. Set the numbers below and follow the carries along the chain.
| bit 4 | bit 3 | bit 2 | bit 1 | bit 0 | Value | |
|---|---|---|---|---|---|---|
| carry | 1 | 1 | 1 | 0 | 0 | Cin = 0 |
| A | 11 | |||||
| B | + | + 6 | ||||
| Sum | 1 | 0 | 0 | 0 | 1 | = 17 |
11 + 6 = 17. That needs five bits: the four sum bits read 1, and the carry out of bit 3 is the fifth bit, worth 16. Each carry in the top row is produced by the column to its right and consumed by the column beneath it; the rightmost one is the carry in, the leftmost the carry out. Click a bit of A or B to flip it.
The circuit
The same four full adders as gates, drawn by the circuit generator from the sum and carry expressions with each carry written in terms of the one before it. Each full adder is two XORs, two ANDs and an OR, 20 gates in all, and the wires follow the numbers set above: green is 1, red is 0.
Open it in the circuit generator to export it as SVG, PNG, Verilog or VHDL, or see the calculator example, which is a 4-bit adder with a display on the end.
Why the carry makes it slow
Nothing in column 3 can finish until it knows its carry in, which comes from column 2, which is waiting on column 1, which is waiting on column 0. In the worst case, adding 1 to 1111, a single carry ripples through every column before the top sum bit and the carry out are right. Each column adds about two gate delays to that path, an AND and an OR, so the delay grows in step with the width. In the diagram above the longest path from an input to the carry out is 9 two-input gates deep for 4 bits, and every extra bit adds two more.
The other columns are not slow, only the carry chain is, and that observation is the whole idea behind the carry lookahead adder: compute every carry directly, so nothing waits.
Carry lookahead
Look at a single column. It generates a carry when both its inputs are 1, whatever comes in from below: G = A ∧ B. It propagates an incoming carry when exactly one input is 1: P = A ⊻ B. So each carry is ci+1 = Gi ∨ Pici, and substituting each carry into the next unrolls the chain into a sum of products that mentions only G, P and the carry in:
- c1 = G0 + P0c0
- c2 = G1 + P1G0 + P1P0c0
- c3 = G2 + P2G1 + P2P1G0 + P2P1P0c0
- c4 = G3 + P3G2 + P3P2G1 + P3P2P1G0 + P3P2P1P0c0
Every one of those is an AND row feeding a single OR, two gate levels deep, after the one level that makes G and P. The carry into the top column no longer waits on the columns below it; it is computed at the same moment as all the others. That is the lookahead: three gate levels whatever the width, provided the gates can be made wide enough, instead of two more per bit.
The cost is gates, and wider ones. For 4 bits the lookahead unit needs 10 AND gates and 4 OR gates, counting each product as one gate however many inputs it has, on top of the 4 generate ANDs, 4 propagate XORs and 4 sum XORs, 26 in all against 20 for the ripple version, and the last OR has 5 inputs. Past four bits the fan-in gets out of hand, so real designs build 4-bit lookahead blocks and then look ahead across the blocks, which is what the classic 74182 lookahead generator chip does.
| Width | Ripple carry: gate levels to the carry out | Carry lookahead: gate levels |
|---|---|---|
| 4 bits | 9 | 3 |
| 8 bits | 17 | 3 |
| 16 bits | 33 | 3 |
| 32 bits | 65 | 3 |
| 64 bits | 129 | 3 |
Two levels per column for ripple carry, the AND-OR of each carry stage, plus the XOR that feeds the first one; three for a flat lookahead unit with gates as wide as needed. A blocked lookahead adder sits between the two.
The lookahead carries are checked against the ripple carries on every one of the 512 possible inputs by the test suite, so the equations above are the ones that work, not the ones that look right. Draw the lookahead adder to see how much wider it is.
Subtraction with the same adder
An adder subtracts if you feed it the two's complement of the second number: invert every bit of B and set the carry in to 1. A row of XOR gates does the inverting, with a control line as their second input that is also wired to the carry in, so one signal switches the circuit between A + B and A − B. That is why a processor's arithmetic unit has an adder and no separate subtractor.
Build one
Make a full adder from two XORs, two ANDs and an OR, turn it into a custom node, and place four of them in a row. Wire each carry out to the next carry in, toggles to the inputs and displays to the sums, and add 1 to 1111 to watch the carry ripple.
Step 4 of the learning path builds the full adder and points at the calculator example, which chains four of them and puts a seven-segment display on the end.
Questions about adders
What is a ripple carry adder?
A circuit that adds two binary numbers by chaining one full adder per bit, with the carry out of each column wired into the carry in of the next. It is called ripple carry because a carry generated in the lowest column has to pass through every column above it before the top bit is right, rippling along the chain the way a carry does in pencil and paper addition.
How does a 4-bit adder work?
Four full adders in a row. The first takes bit 0 of each number and the carry in, and produces bit 0 of the sum and a carry. That carry goes into the second full adder with bit 1 of each number, and so on. After the fourth column the sum is the four sum bits, and the last carry out is a fifth bit that says the answer did not fit in four.
What is the difference between a half adder and a full adder?
A half adder adds two bits and gives a sum and a carry out, but has no carry in, so it can only be the first column of an adder. A full adder adds three bits, the two operand bits and the carry from the column below, which is what lets it be chained. A full adder is two half adders with their carries ORed together.
Why is a ripple carry adder slow?
Because the carry into each column depends on the carry out of the one before, the worst case, adding 1 to a number that is all 1s, has to wait for the carry to pass through every column in turn. Each column adds about two gate delays, so a 32 bit ripple carry adder has a carry path around 64 gates long, and the whole adder is only as fast as that path.
What is a carry lookahead adder?
An adder that computes every carry directly from the inputs instead of waiting for the one below. Each column produces a generate signal, G = A AND B, meaning it makes a carry on its own, and a propagate signal, P = A XOR B, meaning it passes an incoming carry along. Every carry is then a sum of products of those signals, two gate levels deep after the level that makes G and P, however wide the word is, at the cost of many more gates and wider ones.
How do you subtract with an adder?
Invert every bit of the number being subtracted and set the carry in to 1. That adds its two's complement, which is the same as subtracting it. One row of XOR gates with a shared control input does the inverting and doubles as the carry in, so a single adder serves for both operations.
What does the carry out of the last column mean?
For unsigned numbers it is the fifth bit of the answer: 1 means the true sum is too big for the width. For two's complement numbers it is discarded, and overflow is detected differently, by comparing the carry into the top bit with the carry out of it: if they differ, the result has the wrong sign.