Combinational design methodology — Half Adder, Full Adder, Parallel Binary Adder, Half & Full Subtractor, BCD (8421) Adder, Excess-3 Adder, and the 2’s Complement Adder/Subtractor — with truth tables, Boolean expressions, K-map derivations, and IC references.
📐 Combinational Design Methodology
A combinational circuit is a network of logic gates where the outputs depend only on the current inputs — there is no memory, no feedback. The design follows a fixed five-step process:
Figure 1 — The five-step combinational circuit design process. Each step is mandatory; skipping K-map minimization leads to unnecessarily complex gate networks.
Combinational circuits do not have memory elements — the same inputs always produce the same outputs. This is in contrast to sequential circuits (covered in DE-08 through DE-10) which include flip-flops and whose outputs depend on both current inputs and past history.
➕ Half Adder
A half adder adds two single binary digits A and B simultaneously, producing a Sum and a Carry output. It is called “half” because it cannot accept a carry-in from a previous column — that limitation is resolved by the full adder.
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 Expressions
S = A·B̄ + Ā·B = A ⊕ B
C = A · B
Sum = XOR of inputs Carry = AND of inputs
Figure 2 — Half adder implementations. Method 1 (XOR+AND) uses 2 gates. Method 2 uses 5 NAND gates — useful when only NAND gates are available in a design (universal gate implementation). A further optimisation reduces this to 5 NAND gates from the initial 7-gate derivation.
Key identity: S = A ⊕ B (XOR). The XOR gate is the natural building block for all adder circuits — every adder and subtractor at the bit level relies on XOR for the sum/difference output.
➕ Full Adder
A full adder adds three bits — augend A₁, addend B₁, and carry-in C₀ from the previous column — producing a Sum S₁ and carry-out C₁. It is the fundamental building block of all multi-bit binary adders.
A₁
B₁
C₀ (carry-in)
Sum S₁
Carry-out C₁
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
Boolean Expressions (derived from K-map)
K-map derivation — Sum S₁ and Carry C₁
S₁From K-map: no adjacent pairs simplify — S₁ = A₁⊕B₁⊕C₀ (XOR of all three inputs)
Expand S₁Let S = A₁⊕B₁ (half adder sum). Then S₁ = S⊕C₀ = S·C̄₀ + S̄·C₀
C₁From K-map: C₁ = A₁·B₁ + B₁·C₀ + A₁·C₀
Factorise C₁= A₁·B₁ + (A₁⊕B₁)·C₀ = C + S·C₀ where C = A₁·B₁ (half adder carry)
S₁ = A₁ ⊕ B₁ ⊕ C₀ C₁ = A₁·B₁ + (A₁⊕B₁)·C₀
Figure 3 — Full adder built from two half adders and one OR gate. HA1 adds A₁ and B₁ to get intermediate sum S and carry C. HA2 adds S and carry-in C₀ to get final sum S₁ and intermediate carry C′. The OR gate combines both carries: C₁ = C + C′.
Full Adder = 2 Half Adders + 1 OR gate. This structure is important — it shows that a full adder is built hierarchically from simpler units. In practice, ICs implement the full adder directly in optimised gate-level logic (9 NAND gates), not as two separate HA ICs.
🔗 Parallel Binary Adder & ICs
To add two n-bit binary numbers, n full adders are chained so that the carry-out of each stage feeds the carry-in of the next. This is called a ripple-carry adder — the carry “ripples” through from LSB to MSB. The main disadvantage is propagation delay: with n stages, the total delay is n × single-FA delay.
Figure 4 — 4-bit ripple-carry adder. Carry-in C₀ = 0 for the LSB stage. Each carry-out feeds directly into the next stage’s carry-in. The output is the 4-bit sum S₃S₂S₁S₀ plus a potential carry-out C₄ (overflow bit).
Available ICs: 74LS82 2-bit full adder | 74C83 4-bit parallel adder with carry look-ahead. Chain two 74C83s for 8-bit addition.
➖ Half Subtractor
A half subtractor subtracts one binary digit Y₀ (subtrahend) from another X₀ (minuend), producing a Difference D₀ and a Borrow B₀. Like the half adder, it cannot accept a borrow-in from a previous stage.
Truth Table
X₀
Y₀
Diff D₀
Borrow B₀
0
0
0
0
0
1
1
1
1
0
1
0
1
1
0
0
Boolean Expressions
D₀ = X₀·Ȳ₀ + X̄₀·Y₀ = X₀ ⊕ Y₀
B₀ = X̄₀ · Y₀
Difference = XOR (same as sum!) Borrow = NOT(X₀) AND Y₀
Half adder vs half subtractor. The Difference expression D₀ = X₀⊕Y₀ is identical to the Sum expression S = A⊕B. The only difference is the Borrow: B₀ = X̄₀·Y₀, while the Carry is C = A·B. To convert a half adder to a half subtractor, add one NOT gate on the A/X input feeding the AND gate.
➖ Full Subtractor
A full subtractor subtracts subtrahend Y₁ and borrow-in B₀ from minuend X₁, producing Difference D₁ and borrow-out B₁. Three inputs, two outputs.
X₁
Y₁
B₀ (borrow-in)
Diff D₁
Borrow B₁
0
0
0
0
0
0
0
1
1
1
0
1
0
1
1
0
1
1
0
1
1
0
0
1
0
1
0
1
0
0
1
1
0
0
0
1
1
1
1
1
Derivation — D₁ and B₁ expressions
D₁From truth table — 1s at rows 1,2,4,7 → D₁ = X₁⊕Y₁⊕B₀ (same XOR pattern as full adder sum)
Just as the full adder is two half adders + OR gate, the full subtractor = two half subtractors + OR gate. The structural pattern is identical; only the borrow generation differs from carry generation.
🔟 BCD (8421) Adder
A BCD adder adds two decimal digits in BCD format. Because BCD only uses codes 0000–1001 (0–9), the sum from a normal binary adder may land in the illegal range 1010–1111 (10–15). When this happens, add 0110 (6 decimal) to skip over the six illegal codes and produce the correct BCD result with a carry.
Figure 5 — BCD addition correction logic. The correction term X detects when the binary sum exceeds 9. X is computed from the sum bits and drives a second 4-bit adder that adds 0110 when required. ICs: two 74LS83 (4-bit parallel adders) + correction gates implement a full one-digit BCD adder.
Carry detect formula: X = S₄ + S₃·S₂ + S₃·S₁ — this Boolean expression is true for all invalid sums (10–15) and for sums that generate a carry (≥16). It drives the second adder stage that adds the 0110 correction automatically in hardware.
3️⃣ Excess-3 (XS-3) Adder
The Excess-3 adder exploits the self-complementing property of XS-3 code. Recall from DE-02 that in XS-3 each digit is BCD + 3. After binary addition of two XS-3 digits:
If carry-out S₄ = 1 (sum > 9): add 0011 to the incorrect sum to restore XS-3 encoding and propagate the carry.
If carry-out S₄ = 0 (sum ≤ 9): subtract 0011 from the sum (add its 1’s complement 1100 + end-around carry) to restore XS-3 encoding.
Unified correction. In hardware, both cases can be handled by a single rule: add S₄·S̄₄·S̄₄·S̄₄ in each position — effectively, when S₄=1 add 0011, and when S₄=0 add 1100 (plus the end-around carry). The circuit uses one adder stage with controlled inputs driven by the carry bit S₄.
± 2’s Complement Adder/Subtractor
The most elegant design: a single circuit that performs both addition and subtraction using a SUB control signal and XOR gates. This is the circuit used inside every ALU.
Figure 6 — 2’s complement adder/subtractor. When SUB=0, XOR gates pass B bits unchanged and C₀=0 — normal addition. When SUB=1, XOR gates invert B bits (1’s complement) and C₀=1 (via the carry-in connection) adds 1 — giving the 2’s complement of B. Result: A−B = A+(2’s complement of B).
SUB signal
XOR behaviour
Carry-in C₀
Result
0 (Add)
B ⊕ 0 = B (pass through)
0
A + B
1 (Subtract)
B ⊕ 1 = B̄ (invert = 1’s complement)
1 (via SUB)
A + B̄ + 1 = A + (2’s comp of B) = A − B
Overflow detection. The final carry C₄ serves as the overflow bit for the adder and as the sign bit indicator for the subtractor. If the result of a signed operation overflows the available bit width, C₄ ≠ carry into the MSB — hardware detectors check this condition to flag arithmetic overflow.
📋 Quick Reference
Circuit
Inputs
Key Expressions
IC / Notes
Half Adder
A, B
S = A⊕B C = A·B
XOR + AND = 2 gates; or 5 NAND gates
Full Adder
A, B, Cᵢₙ
S = A⊕B⊕Cᵢₙ Cₒᵤₜ = A·B + (A⊕B)·Cᵢₙ
2 HA + OR; or 9 NAND; IC 74LS82
Parallel Adder
n-bit A, B
n FAs in series; carry ripples LSB→MSB
IC 74C83 (4-bit); chain for 8-bit
Half Subtractor
X, Y
D = X⊕Y B = X̄·Y
Same as HA + one NOT on X input
Full Subtractor
X, Y, Bᵢₙ
D = X⊕Y⊕Bᵢₙ Bₒᵤₜ = X̄·Y + (X⊕Y)·Bᵢₙ
2 Half Subtractors + OR gate
BCD Adder
4-bit BCD × 2
Add 0110 if sum > 9 or carry out; X = S₄ + S₃·S₂ + S₃·S₁