Digital Design / Module 2: Combinational building blocks
8. Half, full and ripple adders
Build addition out of gates.
See it move
The idea
Addition in hardware works just as it does on paper: add one column, pass the carry to the next. A single column is a full adder.
| Signal | Equation |
|---|---|
| Sum | A ^ B ^ Cin |
| Carry out | AB + Cin(A ^ B) |
The sum bit is the parity of the three inputs. A carry comes out when at least two of them are 1. A half adder has no carry input, so it is just an XOR and an AND.
Ripple-carry
Chain N full adders, with each carry out feeding the next carry in.
module full_adder(input a, b, cin, output s, cout);
assign s = a ^ b ^ cin;
assign cout = (a & b) | (cin & (a ^ b));
endmodule
module add4(input [3:0] a, b, input cin,
output [3:0] s, output cout);
wire [4:0] c;
assign c[0] = cin;
assign cout = c[4];
full_adder fa0(.a(a[0]), .b(b[0]), .cin(c[0]), .s(s[0]), .cout(c[1]));
full_adder fa1(.a(a[1]), .b(b[1]), .cin(c[1]), .s(s[1]), .cout(c[2]));
full_adder fa2(.a(a[2]), .b(b[2]), .cin(c[2]), .s(s[2]), .cout(c[3]));
full_adder fa3(.a(a[3]), .b(b[3]), .cin(c[3]), .s(s[3]), .cout(c[4]));
endmoduleThe limit
The worst case is a carry born at bit 0 that travels all the way to the top, as in 0111 + 0001. Delay therefore grows in proportion to width. Doubling the width doubles the worst-case delay, which becomes a serious problem at 32 or 64 bits.
Common mistake
Thinking that the worst case depends on the values you happened to simulate. Static timing checks the longest structural path, whichever values you tried. A design can pass every simulation and still fail timing because of a carry chain your tests rarely exercised.
Key ideas
- Sum is A xor B xor Cin.
- Carry out is AB + Cin(A xor B).
- Ripple delay grows linearly with width.
Your exercise
Find the bug
This code has one deliberate bug. Read the symptom, then click the line you think is wrong.
The fix
assign cout = (a & b) | (cin & (a ^ b));
Why it failed
A carry comes out when at least two of the three inputs are 1. This line misses a = 0, b = 1, cin = 1, so a carry disappears whenever it should pass through a bit where only b is high. That only shows up for particular values, which is why adders need exhaustive tests.
Interview questions
coreWhat limits a ripple adder?
The carry may have to travel through every bit.
basicWhat is the difference between a half adder and a full adder, in gates?
A half adder adds two bits: sum is A XOR B and carry is A AND B. A full adder also takes a carry in, so sum is the XOR of all three inputs and carry out is 1 when at least two inputs are 1. A full adder can be built from two half adders and an OR gate.
basicA full adder has A = 1, B = 1 and carry in = 1. What are the sum and carry out?
Three ones add up to 3, which is binary 11. So the sum is 1 and the carry out is 1. The sum is the parity of the inputs, and three is odd; the carry is the majority, and all three are high.
coreHow many bits does the sum of two N-bit unsigned numbers need? Check with 4 bits.
N + 1 bits. The largest sum is (2^N - 1) × 2 = 2^(N+1) - 2, which needs one extra bit. For 4 bits, 15 + 15 = 30 = 11110, five bits. The extra bit is the carry out of the top full adder.
coreThe lesson writes carry out as AB + Cin(A XOR B). Show that it equals the majority AB + ACin + BCin.
If A and B are both 1, both forms give 1 from AB. If exactly one of them is 1, A XOR B is 1, so the first form gives Cin, and the majority form also gives Cin because one of ACin or BCin is active. If both are 0, both forms give 0. The XOR version is preferred because A XOR B is already computed for the sum.
coreIn a 32-bit ripple-carry adder, each full adder's carry path takes 50 ps (illustrative). Roughly what is the worst-case delay, and which input pattern causes it?
The worst case is a carry born at bit 0 that has to pass through every stage, about 32 × 50 ps = 1.6 ns, plus a little for the final sum bit. Adding 1 to a value whose low 31 bits are all 1s does it, because every stage propagates. Delay grows in proportion to width.
coreThis line is meant to average two 8-bit unsigned values. With a = 200 and b = 100, it gives 22 instead of 150. Why?
wire [7:0] a, b; wire [7:0] avg = (a + b) >> 1;
Verilog sizes the expression to the widest operand or target, which is 8 bits here, so a + b is computed in 8 bits and the carry is lost: 300 wraps to 44, and 44 >> 1 is 22. Widen before adding, for example ({1'b0, a} + b) >> 1, so the sum has a ninth bit to keep the carry.
advancedA 64-bit ripple adder passes millions of random simulation vectors but fails static timing. Why didn't random tests hit the slow path, and does it matter?
The full-length path needs a carry generated at the bottom and propagated through every bit above it, and each bit propagates with probability one half under random data. A 63-bit propagate run is therefore astronomically unlikely, and typical random sums only ripple a few bits. It matters, because static timing checks the structural worst case, and real data such as counters and address increments does hit long carries.
advancedYou need the sum of three 8-bit unsigned numbers in one cycle. Besides two chained adders, how can it be done, and how wide is the result?
Use a row of full adders as a carry-save stage: each column adds the three bits in that column, producing a sum bit and a carry bit, with no carry passing between columns. That reduces three numbers to two, the sum vector and the carry vector shifted left one place, which a single normal adder then combines. The maximum total is 3 × 255 = 765, so the result needs 10 bits.