Question 2 of 5: Adders, BCD, and NAND-Gate Minimization

Question 2: Adders, BCD, and NAND-Gate Minimization (25 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Part (a) — ripple-carry vs. carry-look-ahead. A ripple-carry adder chains $n$ full adders so that the carry-out of stage $i$ feeds directly into the carry-in of stage $i{+}1$; every stage must wait for the true, settled carry from the previous stage before its own sum and carry are valid, so the carry "ripples" through the chain one full-adder delay at a time. A carry-look-ahead adder instead computes each stage's carry-out directly from the original input bits (using per-bit generate $g_i = A_iB_i$ and propagate $p_i = A_i \oplus B_i$ signals combined in a two-level AND-OR carry network), so every carry is available after only a small, fixed number of gate delays regardless of $n$. The ripple-carry adder is slower because its worst-case delay grows linearly with the number of bits, $t_{ripple} \approx n \cdot t_{FA}$ (e.g. a carry generated in bit 0 must physically propagate through every one of the $n{-}1$ remaining full adders before the final sum is valid), whereas the carry-look-ahead adder's delay stays roughly constant (a small, bounded number of AND/OR levels) because every carry is derived independently and directly from the inputs rather than waiting on its neighbour.

Part (a) — BCD of (17,000)₁₀. In 8421 BCD each decimal digit is encoded independently in its own 4-bit nibble; grouping 17000 digit-by-digit (1, 7, 0, 0, 0):

This is justified because BCD is a weighted, per-digit code (not a pure binary conversion): each of the five decimal digits 1,7,0,0,0 is replaced by its own 4-bit binary value (0–9 only, never using codes 1010–1111), giving a 20-bit result. (For contrast, plain unsigned binary would need only $\lceil\log_2 17001\rceil = 15$ bits, but would not preserve individual decimal-digit boundaries the way BCD does — BCD trades density for direct decimal-digit addressability, which is why it is used in seven-segment displays and decimal arithmetic hardware.)

Part (b) — Given. A 4-bit ripple-carry adder built from AND, OR and XOR gates only (any number of inputs allowed).

Find. The total gate count.

Approach. Count the gates in one full adder using the standard two-level XOR/AND-OR realization, then multiply by 4 (one full adder per bit, chained by carry).

1. Gate count per full adder. $$\text{Sum} = A \oplus B \oplus C_{in} \;\; (\text{2 XOR gates: } X_1=A\oplus B,\ S = X_1 \oplus C_{in})$$ $$\text{Cout} = AB + C_{in}\cdot X_1 \;\; (\text{2 AND gates + 1 OR gate})$$ so each full adder needs $2$ XOR $+ 2$ AND $+ 1$ OR $= \boxed{5\text{ gates}}$.
2. Scale to 4 bits. A ripple-carry adder chains 4 identical full adders (carry-out of bit $i$ → carry-in of bit $i{+}1$), so the total is $4 \times 5 = \boxed{20\text{ gates}}$: 8 XOR + 8 AND + 4 OR.

Part (c) — Given. $F(w,x,y,z) = \Sigma m(0,2,3,5,6,13)$.

Find. A minimum-NAND-gate realization, via K-map simplification.

3. K-map (wx / yz).

   wx / yz	00	01	11	10
   00	1	0	1	1
   01	0	1	0	0
   11	0	1	0	0
   10	0	0	0	0

   Minterms 0,2 (wx=00, yz=00/10) group as $w'x'z'$; minterms 2,3 (wx=00, yz=10/11) group as $w'x'y$; minterms 2,6 (yz=10, wx=00/01) group as $w'yz'$; minterm 13 (wxyz=1101) has no adjacent minterm in the list other than through the pair with minterm 5 (wxyz=0101, differing only in $w$), giving $xy'z$. Each of minterms 0, 3, and 6 appears in only ONE of these groups (no alternative pairing exists for them), so all four groups are essential prime implicants — none can be dropped. $$\boxed{F = w'x'z' + w'x'y + w'yz' + xy'z}$$
4. NAND-NAND realization. Each 3-literal product term is built directly as a single 3-input NAND gate (its output is already the term's complement); the four term-outputs are then combined by a single 4-input NAND gate, which by De Morgan gives exactly the OR of the four true terms: $$F = \overline{\overline{T_1}\cdot\overline{T_2}\cdot\overline{T_3}\cdot\overline{T_4}} = T_1+T_2+T_3+T_4$$ Total: $4$ (3-input NAND) $+ 1$ (4-input NAND) $= \boxed{5\text{ NAND gates}}$.