Every processor adds numbers billions of times per second, and every one of those additions comes down to a tiny circuit that adds just a few bits. In this chapter we design those circuits, the half adder and the full adder, using the procedure from Combinational Circuit Design. Once you have a full adder, you can build an adder of any width, which is what the next chapters do.
Let us start with how you add binary numbers by hand:
carries: 1 1 1
0 1 1 1 (7)
+ 0 0 1 1 (3)
---------
1 0 1 0 (10)
Look at one column. The rightmost column adds just two bits (1 + 1), giving a sum bit 0 and a carry 1. Every other column adds three bits: the two number bits plus the carry from the column on its right. So we need two circuits:
one that adds 2 bits (the half adder), and
one that adds 3 bits (the full adder).
Adding up to three 1-bit values gives at most 3 = 112, so both circuits have exactly two outputs: a sum bit and a carry bit.
Half Adder
A half adder is a combinational circuit that adds two bits A and B and produces a sum bit S and a carry bit C, where 2C + S = A + B.
Truth Table
A | B | C (carry) | S (sum) | Meaning |
|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 + 0 = 0 |
0 | 1 | 0 | 1 | 0 + 1 = 1 |
1 | 0 | 0 | 1 | 1 + 0 = 1 |
1 | 1 | 1 | 0 | 1 + 1 = 102 |
Equations
S = Σm(1, 2) = A′B + AB′ = A ⊕ B
C = Σm(3) = AB
The sum column is exactly the XOR truth table and the carry column is exactly the AND truth table, so the half adder is one XOR gate and one AND gate:
A ──┬──────────┐
│ [XOR]──────── S = A ⊕ B
B ──┼──┬───────┘
│ │
└──┼───────┐
│ [AND]──────── C = AB
└───────┘
Why is it called "half"? Because it has no input for a carry coming from a lower column. It can only be used in the least significant position, or wherever exactly two bits must be added.
Half Adder Using Only NAND Gates
From Universal Gates: NAND & NOR, XOR needs 4 NAND gates. The trick is that the first NAND gate, (AB)′, is reused for the carry: one more NAND acting as an inverter gives AB.
n1 = (A·B)′
n2 = (A·n1)′
n3 = (B·n1)′
S = (n2·n3)′ = A ⊕ B
C = (n1·n1)′ = AB
Total: 5 NAND gates
Half Adder Using Only NOR Gates
n1 = (A + A)′ = A′
n2 = (B + B)′ = B′
C = (n1 + n2)′ = (A′ + B′)′ = AB
n3 = (A + B)′ = A′B′
S = (C + n3)′ = (AB + A′B′)′ = A ⊕ B
Total: 5 NOR gates
Both netlists were checked against the truth table for all inputs. Five is the number usually quoted for both NAND-only and NOR-only half adders.
Full Adder
A full adder is a combinational circuit that adds three bits A, B and Cin (the carry from the previous column) and produces a sum S and a carry Cout, where 2Cout + S = A + B + Cin.
Truth Table
Row | A | B | Cin | Number of 1s | Cout | S |
|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 1 | 1 | 0 | 1 |
2 | 0 | 1 | 0 | 1 | 0 | 1 |
3 | 0 | 1 | 1 | 2 | 1 | 0 |
4 | 1 | 0 | 0 | 1 | 0 | 1 |
5 | 1 | 0 | 1 | 2 | 1 | 0 |
6 | 1 | 1 | 0 | 2 | 1 | 0 |
7 | 1 | 1 | 1 | 3 | 1 | 1 |
The "number of 1s" column is the key to understanding the outputs: the two output bits are simply that count written in binary.
Sum: K-map and Equation
S = Σm(1, 2, 4, 7)
B Cin
A 00 01 11 10
0 | 0 | 1 | 0 | 1 |
1 | 1 | 0 | 1 | 0 |
A checkerboard: no two 1s are adjacent, so the K-map cannot simplify anything and the minimal SOP has four 3-literal terms:
S = A′B′Cin + A′BCin′ + AB′Cin′ + ABCin
A checkerboard pattern is the signature of XOR. S is 1 when an odd number of inputs are 1, which is exactly what a 3-input XOR computes. Algebraically:
S = Cin′(A′B + AB′) + Cin(A′B′ + AB)
= Cin′(A ⊕ B) + Cin(A ⊕ B)′
= (A ⊕ B) ⊕ Cin
= A ⊕ B ⊕ Cin
Carry: K-map and Equation
Cout = Σm(3, 5, 6, 7)
B Cin
A 00 01 11 10
0 | 0 | 0 | 1 | 0 |
1 | 0 | 1 | 1 | 1 |
pair (3,7) → B·Cin pair (5,7) → A·Cin pair (6,7) → AB
Cout = AB + A·Cin + B·Cin
This is the majority function from Combinational Circuit Design: a carry comes out when at least two of the three inputs are 1. That makes sense: two or three 1s add up to 2 or 3, both of which have a 1 in the 2s place.
A Second Form of the Carry
There is another useful way to write Cout. Split on whether A and B are equal:
Cout = AB + Cin·(A ⊕ B)
Proof: Cin(A ⊕ B) = A′B·Cin + AB′·Cin
AB + A′B·Cin + AB′·Cin
= AB + AB·Cin + A′B·Cin + AB·Cin + AB′·Cin (AB = AB + AB·Cin, twice)
= AB + B·Cin(A + A′) + A·Cin(B + B′)
= AB + B·Cin + A·Cin ✓
Read it in words; these two ideas return in the carry look-ahead adder:
AB: the column generates a carry on its own (both bits are 1), whatever Cin is.
Cin(A ⊕ B): exactly one of A, B is 1, so the column propagates the incoming carry to the next column.
Full Adder from Two Half Adders
The two equations S = (A ⊕ B) ⊕ Cin and Cout = AB + Cin(A ⊕ B) describe exactly two half adders and an OR gate:
+---------+ S1 = A⊕B +---------+
A ───────> | |───────────> | |──────────────────> S = A⊕B⊕Cin
| HA1 | | HA2 |
B ───────> | | Cin ────> | |
+---------+ +---------+
│ C1 = AB │ C2 = Cin·(A⊕B)
│ │
└─────────>[ OR ]<──────┘
│
└──────────────────────────────────> Cout
Can C1 and C2 be 1 at the same time? C1 = 1 needs A = B = 1, which makes A ⊕ B = 0 and therefore C2 = 0. They are mutually exclusive, so the OR gate could even be replaced by an XOR gate and the circuit would still be correct. Exam questions like to test this.
Gate Count and Delay
Implementation | Gates | Notes |
|---|---|---|
Two half adders + OR | 2 XOR, 2 AND, 1 OR = 5 | Most common textbook form |
Two-level SOP | S: 4 AND3 + 1 OR4; Cout: 3 AND2 + 1 OR3 (plus inverters) | Fastest (2 levels after inverters), largest |
NAND only | 9 NAND | Two 4-NAND XORs + 1 NAND for Cout |
NOR only | 9 NOR | Two 4-NOR XNORs + 1 NOR for Cout |
The NAND-only version follows directly from the half adder trick: build A ⊕ B with 4 NANDs (n1 = (AB)′ inside), build (A ⊕ B) ⊕ Cin with 4 more (with n5 = ((A ⊕ B)·Cin)′ inside), and then Cout = (n1 · n5)′ = AB + (A ⊕ B)Cin with one more NAND: 9 NAND gates.
Delay (two half adders + OR, each gate counted as 1 unit, all inputs ready at time 0):
S1 = A ⊕ B ready at 1
C1 = AB ready at 1
S = S1 ⊕ Cin ready at 2
C2 = S1 · Cin ready at 2
Cout = C1 + C2 ready at 3
But if Cin arrives late (at time t), S is ready at t + 1 and Cout at t + 2.
That last line is what matters when full adders are chained: in a multi-bit adder, the carry input is almost always the last signal to arrive, so the Cin → Cout delay (2 gate delays here) is repeated once per bit. Ripple-Carry & Carry Look-Ahead Adders builds on exactly this number.
Describing Adders in Verilog
Here is a structural full adder made from two half-adder modules, with a testbench that checks all 8 rows against ordinary arithmetic:
module half_adder (input logic a, b,
output logic s, c);
assign s = a ^ b;
assign c = a & b;
endmodule
module full_adder (input logic a, b, cin,
output logic s, cout);
logic s1, c1, c2;
half_adder ha1 (.a(a), .b(b), .s(s1), .c(c1));
half_adder ha2 (.a(s1), .b(cin), .s(s), .c(c2));
assign cout = c1 | c2;
endmodule
module tb;
logic a, b, cin, s, cout;
full_adder dut (.a(a), .b(b), .cin(cin), .s(s), .cout(cout));
initial begin
$display("a b cin | cout s");
for (int i = 0; i < 8; i++) begin
{a, b, cin} = i; #1;
$display("%b %b %b | %b %b", a, b, cin, cout, s);
if ({cout, s} !== a + b + cin) $display("MISMATCH");
end
end
endmodule
Output (Icarus Verilog with -g2012):
a b cin | cout s
0 0 0 | 0 0
0 0 1 | 0 1
0 1 0 | 0 1
0 1 1 | 1 0
1 0 0 | 0 1
1 0 1 | 1 0
1 1 0 | 1 0
1 1 1 | 1 1
No "MISMATCH" lines were printed, so {Cout, S} equals A + B + Cin in every row. In real projects you would usually just write assign {cout, s} = a + b + cin; and let the synthesis tool pick the gates; the structural version is how you show you understand what those gates are.
Half Adder vs Full Adder
Point | Half adder | Full adder |
|---|---|---|
Inputs | 2 (A, B) | 3 (A, B, Cin) |
Outputs | S, C | S, Cout |
Sum | A ⊕ B | A ⊕ B ⊕ Cin |
Carry | AB | AB + ACin + BCin = AB + Cin(A ⊕ B) |
Basic gates | 1 XOR + 1 AND | 2 XOR + 2 AND + 1 OR |
NAND-only | 5 | 9 |
Accepts a carry in? | No | Yes |
Typical use | LSB of an adder, incrementers, building full adders | Every bit of a multi-bit adder, multipliers |
Where Full Adders Are Used
Multi-bit adders: n full adders chained carry-to-carry add two n-bit numbers (next chapters).
Subtractors: with inverted B and Cin = 1, an adder computes A − B in 2's complement (see Subtractors).
Counting 1s: a full adder outputs, in binary, how many of its 3 inputs are 1. That is why it is also called a 3:2 counter or 3:2 compressor; fast multipliers use trees of them to add many partial products.
Majority and parity: Cout alone is a 3-input majority voter; S alone is a 3-input odd-parity function.
Common Mistakes
Writing S = A + B (OR) for the half adder. The sum is XOR: 1 + 1 gives sum 0, not 1.
Swapping sum and carry. Carry is the AND/majority; sum is the XOR/parity.
Using three half adders for a full adder. It takes two half adders and one OR gate.
Trying to simplify the sum K-map. The checkerboard has no adjacent 1s; recognise it as XOR instead.
Forgetting that C1 and C2 are never both 1. That is why OR and XOR both work for the final gate.
Reporting the full adder delay as one number. State which path: A/B → S, A/B → Cout, or Cin → Cout. The last one dominates in chained adders.
GATE and Interview Questions
Q1. What is the minimum number of 2-input NAND gates needed to build a half adder and a full adder?
Half adder: 5 (4 for the XOR, reusing the first NAND (AB)′ plus one inverter-NAND for AB). Full adder: 9.
Q2. How many half adders and other gates make a full adder?
Two half adders and one OR gate. The OR gate can be replaced by an XOR gate, because the two half-adder carries are never 1 together.
Q3. A full adder has inputs A = 1, B = 0, Cin = 1. Give S and Cout.
Two inputs are 1, so 1 + 0 + 1 = 2 = 102: Cout = 1, S = 0.
Q4. Express the full adder outputs in Σm form.
S = Σm(1, 2, 4, 7) and Cout = Σm(3, 5, 6, 7), with inputs ordered A, B, Cin.
Q5. In a full adder made from two half adders and an OR gate, the XOR, AND and OR gates have delays of 20 ns, 10 ns and 10 ns. All inputs arrive at t = 0. When are S and Cout valid?
S1 = A ⊕ B at 20 ns; S = S1 ⊕ Cin at 20 + 20 = 40 ns. C1 = AB at 10 ns; C2 = S1·Cin at 20 + 10 = 30 ns; Cout = C1 + C2 at 30 + 10 = 40 ns.
Q6. Why is the full adder called a 3:2 counter?
It takes 3 input bits of equal weight and produces a 2-bit binary number (Cout S) equal to how many of them are 1. Trees of such counters (Wallace and Dadda trees) reduce many partial products to two rows in fast multipliers.
Q7. If the Cin input of a full adder is tied to 0, what circuit do you get?
A half adder: S = A ⊕ B ⊕ 0 = A ⊕ B and Cout = AB + 0 + 0 = AB.
Summary
A half adder adds 2 bits: S = A ⊕ B, C = AB. It has no carry input. NAND-only: 5 gates.
A full adder adds 3 bits: S = A ⊕ B ⊕ Cin (odd parity), Cout = AB + ACin + BCin (majority) = AB + Cin(A ⊕ B). NAND-only: 9 gates.
Full adder = 2 half adders + 1 OR gate (an XOR also works, since the two carries are mutually exclusive).
AB is the generate term and A ⊕ B the propagate term: remember them for fast adders.
In chained adders, the Cin → Cout delay of one full adder is the number that matters.
Next: Subtractors, the borrow-based twins of these circuits, and then Ripple-Carry & Carry Look-Ahead Adders.