Half Adders, Full Adders and Ripple Carry
Add two bits, then three, then N, and watch the carry travel from bit to bit.
You Will Be Able To
- Build a half adder and a full adder, and give their equations.
- Build a full adder from two half adders and an OR gate.
- Chain full adders into a ripple-carry adder.
- Find the input change that makes the carry cross every bit, and its delay.
- Lesson
- G4.5
- Time
- 25 min
- Runs on
- Your browser
- Check
- 5 questions
A display shows the sum of a counter and an offset. While the carry travels, the sum passes through values that are never true. A circuit that samples it too early reads one of them.
- Cycle 0
One gate delay after the change, bit 0 of the sum falls. The sum reads fe, which is wrong.
- Cycle 3
Every two gate delays the carry moves up one bit and clears one more sum bit.
- Cycle 7
At time 15 all eight sum bits are 0, but the carry out is still 0.
- Cycle 8
At time 16 the carry out rises. Only now is 1_00000000 correct.
The lines printed by the lab below, measured on Icarus with one time unit per gate.
The Half Adder
Adding two bits gives a result from 0 to 2, which needs two bits. The low bit is the sum s and the high bit is the carry c. This block is a half adder.
From the table, s = a ⊕ b and c = a·b. One XOR gate and one AND gate.
It is "half" because it has no carry input. It can add the lowest bits of two numbers, but no higher bit.
The Full Adder
A full adder adds three bits: a, b and the carry in ci. The result is 0 to 3, so it still fits in two bits, s and co.
The sum is 1 when an odd number of inputs are 1: s = a ⊕ b ⊕ ci. The carry is 1 when at least two are 1. That is the majority function: co = a·b + a·ci + b·ci.
A full adder is also two half adders and an OR gate. The first adds a and b. The second adds ci to that sum. A carry can come from either half adder, never from both, so an OR joins them.
- I/O
- Datapath
- Data
- a = 1, b = 0, ci = 1
The first half adder gives p = 1 and no carry.
Follow the calls, values and waits
- data p = 1: Half adder 1 → Half adder 2
- data g = 0: Half adder 1 → OR
- Add the carry in
The second half adder adds ci = 1 to p = 1: sum 0 and carry t = 1.
Follow the calls, values and waits
- data s = 0: Half adder 2 → s
- data t = 1: Half adder 2 → OR
- One carry out
The OR passes t, so co = 1. 1 + 0 + 1 = 2 = binary 10.
Read the diagram as text
- a, b: two bits
- ci: carry in
- Half adder 1: sum p, carry g
- Half adder 2: sum s, carry t
- OR: co = g + t
- s: sum
- a, b → Half adder 1: a, b
- Half adder 1 → Half adder 2: p
- ci → Half adder 2: ci
- Half adder 1 → OR: g
- Half adder 2 → OR: t
- Half adder 2 → s: s
p = a ⊕ b is also called the propagate signal, and g = a·b the generate signal. Lesson G4.6 builds on both.
Ripple Carry
To add N-bit numbers, chain N full adders. The carry out of bit i is the carry in of bit i + 1. Bit 0 takes the adder's carry in, and the last carry out is the top bit of the result.
The carry ripples: each stage waits for the one below. That is why this adder is small and slow.
The Worst Case Grows with the Width
The slowest input change is one that makes a carry born in bit 0 travel through every bit. Adding 1 to all ones does it: every bit propagates.
| Width N | Gates | Carry in changes | a0 changes | b0 changes |
|---|---|---|---|---|
| 4 | 20 | 8 | 8 | 8 |
| 8 | 40 | 16 | 16 | 16 |
| 16 | 80 | 32 | 32 | 32 |
| 32 | 160 | 64 | 64 | 64 |
Gate delays until the carry out settles, measured in Icarus with the lab's full adder and one time unit per gate. Every bit propagates in each test.
The delay is 2N gate delays: two per bit, for every width tested. Doubling the width doubles the delay. A 64-bit ripple adder would need 128.
In this model each gate takes one unit, whatever its fan-in. A real three-input gate is slower than a two-input one, so treat these counts as structure, not as picoseconds.
Asked in interviews
What are the sum and carry equations of a full adder?
s = a ⊕ b ⊕ ci, and co = ab + a·ci + b·ci, the majority of the three inputs. Written with propagate and generate: co = g + p·ci, with g = ab and p = a ⊕ b.
Why is a ripple-carry adder slow?
Each carry depends on the carry below it, so the worst case passes through every stage. The delay grows linearly with the width.
Which input change gives the worst delay?
One that makes a carry start at bit 0 and travel to the top: for example adding 1 to all ones. Every middle bit must propagate.
Try It
The bench changes b from 00 to 01 while a is ff. Each printed line is one change of the outputs. The carry clears one sum bit every two gate delays, and the carry out rises at 16.
Change the bench to add 7f + 01. Predict the time of the last line before you run: the carry now stops at bit 7.
Tie c[0] to 1'b1 in place of ci and run. Every result is now one too large: ff + 01 gives 1_00000001.
t=1 co=0 s=11111110 t=3 co=0 s=11111100 t=5 co=0 s=11111000 t=7 co=0 s=11110000 t=9 co=0 s=11100000 t=11 co=0 s=11000000 t=13 co=0 s=10000000 t=15 co=0 s=00000000 t=16 co=1 s=00000000 ff + 01 = 1_00000000Read included file: tb.sv
// tb.sv: one input change, then every change of the outputs with its time (read-only).
module tb;
logic [7:0] a, b;
logic ci;
wire [7:0] s;
wire co;
time t0;
bit watch = 0;
add8 dut (.a(a), .b(b), .ci(ci), .s(s), .co(co));
always @(s or co) if (watch) $display("t=%0d co=%b s=%b", $time - t0, co, s);
initial begin
a = 8'hFF; b = 8'h00; ci = 1'b0;
#40; // let everything settle
t0 = $time; watch = 1;
b = 8'h01; // ff + 01: the carry must cross all 8 bits
#40;
$display("ff + 01 = %b_%b", co, s);
end
endmodule
Check Yourself
Common Mistakes
Wrong Wire the carry chain with an index off by one, or in the wrong direction.
A carry must leave each stage toward the bit above. A loop or a backward chain leaves some carry net with two drivers or none, and the sums turn to x.
Fix Draw the chain before you write the loop. Then check both ends: the carry into bit 0 and the carry out of the top bit.
Wrong Forget the carry in of bit 0.
An unconnected input is z, and the whole sum can turn to x. A carry in tied to 1 adds 1 to every result.
Fix Drive c[0] from the adder's carry-in port, or tie it to 0 for a plain add.
Wrong Read the sum before the carry has crossed the adder.
In the lab, the sum of ff + 01 passes through seven wrong values before it settles, 16 gate delays later.
Fix Give the adder its full worst-case delay before you sample the sum.
Wrong Make the result as wide as the inputs.
Two N-bit numbers can add up to N + 1 bits. The carry out is the top bit of the result.
Fix Keep the carry out, or make the sum one bit wider.
Remember
- Half adder: s = a ⊕ b, c = ab. Full adder: s = a ⊕ b ⊕ ci, co = majority(a, b, ci).
- A full adder is two half adders and an OR gate.
- A ripple-carry adder chains N full adders through their carries.
- Its worst case sends a carry from bit 0 to the top: 2N gate delays in the lab's model.
- Keep the carry out: N-bit inputs give an N + 1-bit sum.