Adders
An adder is the combinational circuit that performs binary addition. It is the first genuinely useful circuit you can design with the tools from the previous lessons, and it sits at the heart of every ALU.
1. Half Adder
Adds two bits and produces a sum and a carry. It cannot accept a carry from a previous stage — hence "half".
Truth table
| A | B | Sum (S) | Carry (C) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Boolean equations
S = A'B + AB' = A ⊕ B
C = A . BGate implementation
Cost: 1 XOR + 1 AND. Using NAND only: 5 NAND gates.
Limitation: cannot be cascaded. To add multi-bit numbers you must accept a carry in.
2. Full Adder
Adds three bits: A, B and a carry-in from the previous stage.
Truth table
| A | B | Cin | Sum (S) | Cout |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
S = Σm(1, 2, 4, 7)
Cout = Σm(3, 5, 6, 7)K-map for Sum
B Cin
00 01 11 10
+------+------+------+------+
A=0 | 0 | 1 | 0 | 1 |
| (0) | (1) | (3) | (2) |
+------+------+------+------+
A=1 | 1 | 0 | 1 | 0 |
| (4) | (5) | (7) | (6) |
+------+------+------+------+
No two 1s are adjacent -> NO simplification possible.
S = A'B'Cin + A'BCin' + AB'Cin' + ABCin
= A ⊕ B ⊕ Cin (the checkerboard pattern always means XOR)K-map for Carry-out
B Cin
00 01 11 10
+------+------+------+------+
A=0 | 0 | 0 | 1 | 0 |
+------+------+------+------+
A=1 | 0 | 1 | 1 | 1 |
+------+------+------+------+
Group m3, m7 -> B.Cin
Group m5, m7 -> A.Cin
Group m6, m7 -> A.B
Cout = AB + B.Cin + A.CinAlternative form of Cout (used in the two-half-adder construction)
Cout = AB + Cin(A ⊕ B)
Proof: Cin(A ⊕ B) = Cin(A'B + AB') = A'B.Cin + AB'.Cin
AB + A'B.Cin + AB'.Cin
= AB(1) + BCin(A' + A) ... expand AB into AB(Cin + Cin'):
= ABCin + ABCin' + A'BCin + AB'Cin
= Σm(7, 6, 3, 5) ✓ same as the K-map3. Full Adder from Two Half Adders
HA1: S1 = A ⊕ B C1 = A . B
HA2: S = S1 ⊕ Cin C2 = S1 . Cin
Then: Cout = C1 + C2 = AB + (A ⊕ B).Cin
Total gates: 2 XOR + 2 AND + 1 OR = 5 gates
Using NAND only: 9 NAND gates4. Worked Verification
Add A = 1, B = 1, Cin = 1 (decimal 1 + 1 + 1 = 3 = binary 11)
S1 = 1 ⊕ 1 = 0
C1 = 1 . 1 = 1
S = 0 ⊕ 1 = 1
C2 = 0 . 1 = 0
Cout = 1 + 0 = 1
Result: Cout S = 1 1 = 3 decimal ✓5. Propagation Delay
Assume each gate has delay t.
| Circuit | Sum delay | Carry delay |
|---|---|---|
| Half adder | 1t (XOR) | 1t (AND) |
| Full adder (two-level SOP) | 2t | 2t |
| Full adder (two half adders) | 2t (XOR → XOR) | 3t (XOR → AND → OR) |
The carry path is the critical path — this single fact drives the entire design of fast adders in the next lesson.
6. Half Adder vs Full Adder
| Basis | Half Adder | Full Adder |
|---|---|---|
| Inputs | 2 (A, B) | 3 (A, B, Cin) |
| Outputs | 2 (S, C) | 2 (S, Cout) |
| Handles carry-in? | No | Yes |
| Cascadable? | No | Yes |
| Gates | 1 XOR + 1 AND | 2 XOR + 2 AND + 1 OR |
| NAND-only count | 5 | 9 |
| Used for | LSB position only | All positions of a parallel adder |
| Equations | S = A⊕B, C = AB | S = A⊕B⊕Cin, Cout = AB + Cin(A⊕B) |
7. The Adder as a Building Block
A full adder can also be viewed as a "1-bit counter of ones":
it counts how many of its three inputs are 1,
and outputs that count in 2 bits (Cout, Sum).
000 -> 00 (0) 011 -> 01 wait, 0+1+1 = 2 -> Cout=1, S=0 -> "10" = 2 ✓
111 -> Cout=1, S=1 -> "11" = 3 ✓This viewpoint explains why full adders are used inside multipliers as "3:2 compressors".
The next lesson does subtraction — and then shows the trick that lets one circuit do both.