Digital Logic Toolkit — Half adder & full adder
Half adder and full adder: truth tables, K-maps and circuits
Truth tables, K-maps and circuits for both adders, and the ripple-carry chain.
The half adder
Half adder truth table
| k | A | B | S | C |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 |
| 2 | 1 | 0 | 1 | 0 |
| 3 | 1 | 1 | 0 | 1 |
S = Σm(1, 2) · C = Σm(3). Two gates: one XOR and one AND.
Half adder sum, S = A ⊕ B
IEC 60617-12:1997 is a paid standard and its per-symbol dimensions are not public. These rectangular symbols follow the published module-grid construction (module M = 6.5 units, so 4M = 26 matches the IEEE body height; line width M/10; qualifying symbol top-centre; connection pitch 2M; negation circle radius M/2 tangent outside the outline). The shapes and qualifying symbols are standard; the exact metrics are our construction, not a quotation.
Circuit description
Logic gate schematic. 2 inputs: A and B. 1 gate: 1 XOR. The output S is driven by an XOR gate. The longest signal path passes through 1 gate.
g0 = XOR(A, B)= A ⊕ B
1 gates1 levels to this outputVerified against the truth table
Half adder carry, C = A · B
IEC 60617-12:1997 is a paid standard and its per-symbol dimensions are not public. These rectangular symbols follow the published module-grid construction (module M = 6.5 units, so 4M = 26 matches the IEEE body height; line width M/10; qualifying symbol top-centre; connection pitch 2M; negation circle radius M/2 tangent outside the outline). The shapes and qualifying symbols are standard; the exact metrics are our construction, not a quotation.
Circuit description
Logic gate schematic. 2 inputs: A and B. 1 gate: 1 AND. The output C is driven by an AND gate. The longest signal path passes through 1 gate.
g0 = AND(A, B)= A · B
1 gates1 levels to this outputVerified against the truth table
The full adder
Full adder truth table
| k | A | B | Cin | S | Cout |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 |
| 2 | 0 | 1 | 0 | 1 | 0 |
| 3 | 0 | 1 | 1 | 0 | 1 |
| 4 | 1 | 0 | 0 | 1 | 0 |
| 5 | 1 | 0 | 1 | 0 | 1 |
| 6 | 1 | 1 | 0 | 0 | 1 |
| 7 | 1 | 1 | 1 | 1 | 1 |
S = Σm(1, 2, 4, 7) · Cout = Σm(3, 5, 6, 7).
The sum K-map is a checkerboard
Σm(1, 2, 4, 7) has no two adjacent 1-cells, so no group is bigger than one cell and the minimal sum of products is the whole four-term expression A′B′Cin + A′BCin′ + AB′Cin′ + ABCin — four terms, twelve literals. The K-map does not help here. The compact answer S = A ⊕ B ⊕ Cin comes from recognising the parity pattern, not from grouping, and this is one of the few places where “the K-map gives the minimal SOP” is misleading.The carry K-map does help
Σm(3, 5, 6, 7) groups into three pairs, giving Cout = A · B + A · Cin + B · Cin — three terms, six literals, and the unique minimal sum of products. The alternative form Cout = A·B + (A ⊕ B)·Cin is equivalent but not minimal in literal count; it is what two half adders produce, and it is the form that leads to generate and propagate.Full adder sum, S = A ⊕ B ⊕ Cin
IEC 60617-12:1997 is a paid standard and its per-symbol dimensions are not public. These rectangular symbols follow the published module-grid construction (module M = 6.5 units, so 4M = 26 matches the IEEE body height; line width M/10; qualifying symbol top-centre; connection pitch 2M; negation circle radius M/2 tangent outside the outline). The shapes and qualifying symbols are standard; the exact metrics are our construction, not a quotation.
Circuit description
Logic gate schematic. 3 inputs: A, B and Cin. 1 gate: 1 XOR. The output S is driven by an XOR gate. The longest signal path passes through 1 gate.
g0 = XOR(A, B, Cin)= A ⊕ B ⊕ Cin
1 gates1 levels to this outputVerified against the truth table
Full adder carry, Cout = A·B + A·Cin + B·Cin
IEC 60617-12:1997 is a paid standard and its per-symbol dimensions are not public. These rectangular symbols follow the published module-grid construction (module M = 6.5 units, so 4M = 26 matches the IEEE body height; line width M/10; qualifying symbol top-centre; connection pitch 2M; negation circle radius M/2 tangent outside the outline). The shapes and qualifying symbols are standard; the exact metrics are our construction, not a quotation.
Circuit description
Logic gate schematic. 3 inputs: A, B and Cin. 4 gates: 3 AND and 1 OR. The output Cout is driven by an OR gate. The longest signal path passes through 2 gates. 3 junction dots mark where a signal fans out to more than one gate.
g0 = AND(A, B)= A · Bg1 = AND(A, Cin)= A · Cing2 = AND(B, Cin)= B · Cing3 = OR(g0, g1, g2)= A · B + A · Cin + B · Cin
4 gates2 levels to this outputVerified against the truth table
Nine-NAND full adder: the sum output
IEC 60617-12:1997 is a paid standard and its per-symbol dimensions are not public. These rectangular symbols follow the published module-grid construction (module M = 6.5 units, so 4M = 26 matches the IEEE body height; line width M/10; qualifying symbol top-centre; connection pitch 2M; negation circle radius M/2 tangent outside the outline). The shapes and qualifying symbols are standard; the exact metrics are our construction, not a quotation.
Circuit description
Logic gate schematic. 3 inputs: A, B and Cin. 9 gates: 9 NAND. The output S is driven by a NAND gate. The longest signal path passes through 6 gates. 8 junction dots mark where a signal fans out to more than one gate.
n1 = NAND(A, B)= A ↑ Bn2 = NAND(A, n1)= A ↑ (A ↑ B)n3 = NAND(B, n1)= B ↑ (A ↑ B)n4 = NAND(n2, n3)= A ↑ (A ↑ B) ↑ (B ↑ (A ↑ B))n5 = NAND(n4, Cin)= A ↑ (A ↑ B) ↑ (B ↑ (A ↑ B)) ↑ Cinn6 = NAND(n4, n5)= A ↑ (A ↑ B) ↑ (B ↑ (A ↑ B)) ↑ (A ↑ (A ↑ B) ↑ (B ↑ (A ↑ B)) ↑ Cin)n7 = NAND(Cin, n5)= Cin ↑ (A ↑ (A ↑ B) ↑ (B ↑ (A ↑ B)) ↑ Cin)S = NAND(n6, n7)= A ↑ (A ↑ B) ↑ (B ↑ (A ↑ B)) ↑ (A ↑ (A ↑ B) ↑ (B ↑ (A ↑ B)) ↑ Cin) ↑ (Cin ↑ (A ↑ (A ↑ B) ↑ (B ↑ (A ↑ B)) ↑ Cin))Cout = NAND(n5, n1)= A ↑ (A ↑ B) ↑ (B ↑ (A ↑ B)) ↑ Cin ↑ (A ↑ B)
9 gates6 levels to this outputVerified against the truth table
Nine-NAND full adder: the carry output
IEC 60617-12:1997 is a paid standard and its per-symbol dimensions are not public. These rectangular symbols follow the published module-grid construction (module M = 6.5 units, so 4M = 26 matches the IEEE body height; line width M/10; qualifying symbol top-centre; connection pitch 2M; negation circle radius M/2 tangent outside the outline). The shapes and qualifying symbols are standard; the exact metrics are our construction, not a quotation.
Circuit description
Logic gate schematic. 3 inputs: A, B and Cin. 9 gates: 9 NAND. The output Cout is driven by a NAND gate. The longest signal path passes through 6 gates. 8 junction dots mark where a signal fans out to more than one gate.
n1 = NAND(A, B)= A ↑ Bn2 = NAND(A, n1)= A ↑ (A ↑ B)n3 = NAND(B, n1)= B ↑ (A ↑ B)n4 = NAND(n2, n3)= A ↑ (A ↑ B) ↑ (B ↑ (A ↑ B))n5 = NAND(n4, Cin)= A ↑ (A ↑ B) ↑ (B ↑ (A ↑ B)) ↑ Cinn6 = NAND(n4, n5)= A ↑ (A ↑ B) ↑ (B ↑ (A ↑ B)) ↑ (A ↑ (A ↑ B) ↑ (B ↑ (A ↑ B)) ↑ Cin)n7 = NAND(Cin, n5)= Cin ↑ (A ↑ (A ↑ B) ↑ (B ↑ (A ↑ B)) ↑ Cin)S = NAND(n6, n7)= A ↑ (A ↑ B) ↑ (B ↑ (A ↑ B)) ↑ (A ↑ (A ↑ B) ↑ (B ↑ (A ↑ B)) ↑ Cin) ↑ (Cin ↑ (A ↑ (A ↑ B) ↑ (B ↑ (A ↑ B)) ↑ Cin))Cout = NAND(n5, n1)= A ↑ (A ↑ B) ↑ (B ↑ (A ↑ B)) ↑ Cin ↑ (A ↑ B)
9 gates5 levels to this outputVerified against the truth table
The ripple-carry chain
Four-bit ripple carry: 1011 + 0110
| Stage | Aᵢ | Bᵢ | Cᵢ | Sᵢ | Cᵢ₊₁ |
|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 |
| 2 | 0 | 1 | 1 | 0 | 1 |
| 3 | 1 | 0 | 1 | 0 | 1 |
Sum 0001, carry out 1 — 11 + 6 = 17 = 10001₂. The four-bit result on its own is wrong; the true answer needs five bits, which is exactly what the carry out is telling you.
Notation used on this page
- Positive logic
- 1 = HIGH = asserted, 0 = LOW = deasserted. An active-low signal is written with an overbar in figures and a trailing _n in copyable text, for example CLR_n.
- Operators
- · AND (also written by juxtaposition, AB) · + OR · ′ complement (postfix; an overbar in figures) · ⊕ XOR · ⊙ XNOR · ↑ NAND (Sheffer stroke) · ↓ NOR (Peirce arrow).
- Precedence, highest first
- ( ) then ′ then · (including juxtaposition) then ⊕ and ⊙ then ↑ and ↓ then +. The parser echoes the fully parenthesised reading back, and warns without blocking when ⊕, ↑ or ↓ appears un-parenthesised beside · or +, because textbooks disagree there.
- Truth-table row order
- Binary counting order from all-zeros to all-ones. The first-listed variable is the most significant bit. Row index k is the integer value of the input vector, and the row is labelled mₖ.
- Minterms and maxterms
- Σm(…) lists the rows where F = 1. ΠM(…) lists the rows where F = 0. Mᵢ complements a variable wherever bit i is 1 — the opposite way round from mᵢ.
- Symbol standards
- IEEE means ANSI/IEEE Std 91-1984 with its 91a-1991 supplement — the distinctive shapes. IEC means IEC 60617-12 — the rectangular shapes with a qualifying symbol. The header toggle switches every figure on the page between them.
- Symbol-set toggle
- Both symbol standards are in this page’s HTML. The toggle in the header chooses which one is drawn, before the first frame is painted, and it changes nothing else on the page — not a truth table, not a gate count, not an answer.
The carry chain
Ripple carry and its 2n + 1 delay
Stage i cannot settle until stage i−1 has produced its carry. With the two-level carry expression the critical path is two gate delays per stage, so an n-bit ripple-carry adder settles in 2n + 1 gate delays — the extra one for the final sum XOR. For n = 32 that is 65 gate delays, which is why ripple carry is taught and then abandoned.
Generate and propagate
Gᵢ = Aᵢ · Bᵢ — this stage generates a carry whatever arrives. Pᵢ = Aᵢ ⊕ Bᵢ — this stage propagates an incoming carry. Then Cᵢ₊₁ = Gᵢ + Pᵢ·Cᵢ and Sᵢ = Pᵢ ⊕ Cᵢ.
Pᵢ = Aᵢ + Bᵢ also works for the carry equation — the two differ only on the row where both inputs are 1, and there G already forces the carry — but XOR is used because the same signal is the sum term.
Carry lookahead
- C₁ = G₀ + P₀C₀
- C₂ = G₁ + P₁G₀ + P₁P₀C₀
- C₃ = G₂ + P₂G₁ + P₂P₁G₀ + P₂P₁P₀C₀
- C₄ = G₃ + P₃G₂ + P₃P₂G₁ + P₃P₂P₁G₀ + P₃P₂P₁P₀C₀
Expanding the recurrence flattens the chain to two levels. The cost is fan-in: a four-bit lookahead block needs a five-input OR and AND gates of up to five inputs, and the fan-in grows linearly, which is why real designs cascade four-bit blocks with a block generate G* = G₃ + P₃G₂ + P₃P₂G₁ + P₃P₂P₁G₀ and a block propagate P* = P₃P₂P₁P₀.
Overflow, unsigned and signed
For unsigned operands the final carry out is the overflow flag: in the worked chain above the four-bit result 0001 is wrong on its own and the carry out says so.
For two’s-complement operands overflow is V = Cₙ ⊕ Cₙ₋₁ — the carry into the sign bit differing from the carry out of it. Worked: 0111 + 0001 = 1000 with carry out 0. The carry into the sign bit is 1 and the carry out of it is 0, so V = 1: +7 + 1 gives −8, which is wrong, and the flag says so.
Three ways to build a full adder
Two half adders and an OR. The first half adder produces s₁ = A ⊕ B and c₁ = A · B; the second adds the carry in, giving S = s₁ ⊕ Cin and c₂ = s₁ · Cin; and Cout = c₁ + c₂. Five gates — two XOR, two AND, one OR — in three levels.
Two-level sum of products from the K-map. The carry map gives the minimal three-term form directly. The sum map does not help, as the checkerboard note above explains.
Nine NAND gates. The elegant part is the carry: n1 = (A·B)′ and n5 = ((A ⊕ B)·Cin)′ are already the complements of the two product terms, so a single extra NAND performs the OR by De Morgan — NAND(n5, n1) = (A ⊕ B)·Cin + A·B = Cout.
Why two depth numbers
The level counts printed under each drawing are measured from that netlist to that output, counting every gate including the inverters made by tying a NAND’s inputs together. Published figures for the nine-NAND adder often quote a smaller number by not counting those, so the convention is stated rather than assumed.Adders in real parts
The 74HC283 is a four-bit binary full adder with fast internal carry; the 74182 is a carry-lookahead generator meant to sit above four of them. A modern CPU adder is neither: it is a parallel-prefix structure — Kogge–Stone, Brent–Kung and their relatives — which is the same carry recurrence solved with a different tree.
Subtraction with the same adder
A − B = A + B′ + 1. XOR every bit of B with a mode bit and feed the same mode bit into C₀: with the mode bit at 0 the adder adds, and with it at 1 every bit of B is complemented and the extra 1 arrives as the carry in, which is exactly the two’s complement of B. One circuit does both operations, and that is the fifth thing XOR is for.
Start from a worked example
Worked examples
- Half adder, A = 1, B = 1intro1 + 1 = 10 in binary
- Half adder, full truth tableintrotwo outputs, four rows
- Full adder, A = 1, B = 1, Cin = 1core1 + 1 + 1 = 11
- Full adder, carry-out K-mapcorethe majority function, three terms
- 4-bit ripple-carry: 1011 + 0110corecarry out of the top bit
- Carry-lookahead: generate and propagateexamtrading gates for depth
- Subtraction by two's complement: 1011 − 0110examone adder does both operations
- BCD adder: 25 + 48 with the +6 correctionedge casewhen binary addition is not decimal addition
Sources
- C. E. Shannon, “A Symbolic Analysis of Relay and Switching Circuits,” Transactions of the AIEE, vol. 57, pp. 713–723, 1938.
- A. W. Burks, H. H. Goldstine and J. von Neumann, Preliminary Discussion of the Logical Design of an Electronic Computing Instrument, Institute for Advanced Study, Princeton, 1946.
- A. Weinberger and J. L. Smith, “A One-Microsecond Adder Using One-Megacycle Circuitry,” IRE Transactions on Electronic Computers, vol. EC-5, no. 2, pp. 65–73, June 1956 — the origin of carry lookahead.
- M. Karnaugh, “The Map Method for Synthesis of Combinational Logic Circuits,” Transactions of the AIEE, Part I, vol. 72, no. 5, pp. 593–599, 1953.
- ANSI/IEEE Std 91-1984 with IEEE Std 91a-1991, IEEE Standard Graphic Symbols for Logic Functions.
- IEC 60617-12:1997, Graphical symbols for diagrams — Part 12: Binary logic elements. (Paid standard; see the construction note beside every rectangular symbol.)