Question 3 of 5: Number Representation, Flip-Flop Identification & Boolean Minimization

Question 3: Number Representation, Flip-Flop Identification & Boolean 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.

Given. (a) N = 10,000 (decimal, to be negated); a 1-bit full adder is to be built from AND/OR/XOR gates only. (b) the 4-row excitation table above. (c) F(w,x,y,z) = Σm(0,2,3,5,6,9,13).

Find. (a) the minimum bit-width and 2’s-complement pattern for −10,000, and the minimum AND/OR/XOR gate count for a full adder; (b) which flip-flop type the table describes; (c)(i) a Boolean-algebra-simplified SOP for F, (ii) F realized in minimum 2-input NAND gates.

Approach. (a) An n-bit 2’s-complement word represents down to −2ⁿ⁻¹, so the minimum n satisfies 2ⁿ⁻¹ ≥ 10,000; the pattern itself is 2ⁿ − 10,000. The full adder is built from the standard Sum/Carry identities. (b) Match the table’s four rows against the standard SR/JK/D/T excitation tables. (c) Group the 7 minterms on a 4-variable K-map, then convert the resulting SOP to NAND-NAND via double negation.

1. Part (a), bullet 1 — minimum bits. Need 2ⁿ⁻¹ ≥ 10,000. 2¹³=8,192 is too small; 2¹⁴=16,384 clears it, so n−1=14. $$\boxed{n = 15 \text{ bits (minimum)}}$$ The 2’s complement pattern is 2¹⁵ − 10,000 = 32,768 − 10,000 = 22,768, which in 15-bit binary is $$\boxed{(-10{,}000)_{10} = 101100011110000_2}$$.
2. Part (a), bullet 2 — full-adder gate count. The standard identities are $$Sum = A \oplus B \oplus C_{in}, \qquad C_{out} = A\cdot B + C_{in}\cdot(A\oplus B)$$ Computing the shared term A⊕B once and reusing it for both Sum and C_out gives: 1 XOR for (A⊕B), 1 XOR for Sum = (A⊕B)⊕C_in, 1 AND for A·B, 1 AND for C_in·(A⊕B), 1 OR to combine the two AND terms. $$\boxed{5 \text{ gates: 2 XOR + 2 AND + 1 OR (minimum with AND/OR/XOR only)}}$$ brute-force verified against the reference truth table for all 8 input rows.
3. Part (b) — identify the flip-flop. Reading each row as “to drive Qn→Qn+1, inputs A,B must be…”: 0→0 needs A=0,B=x; 0→1 needs A=1,B=0; 1→0 needs A=0,B=1; 1→1 needs A=x,B=0. This is exactly the textbook SR excitation table with A playing the role of Set and B the role of Reset (S=A produces a 1, R=B produces a 0, and both are don’t-care exactly when they are not needed to force the transition). Substituting into the SR characteristic equation Q⁺ = S + R′·Q_n reproduces every row of the table. $$\boxed{\text{SR-type flip-flop: } A=S \text{ (Set)},\ B=R \text{ (Reset)}}$$
4. Part (c)(i) — simplify F. Plotting minterms 0,2,3,5,6,9,13 of F(w,x,y,z) on a K-map and grouping every pair of adjacent 1-cells (each group of 2 removes one variable; no group of 4 exists here) gives five essential prime implicants: minterms 0 and 2 share w′x′z′; 2 and 3 share w′x′y; 2 and 6 share w′yz′; 5 and 13 share xy′z; 9 and 13 share wy′z (minterm 13 is covered twice, which is fine — it is not a required essential term by itself). $$\boxed{F = w'x'z' + w'x'y + w'yz' + xy'z + wy'z}$$ verified against all 16 rows of the truth table by brute force.
5. Part (c)(ii) — minimum-NAND realization. Every term above is a 3-literal product, so each is built by a single 3-input NAND gate whose output is the term’s complement; a final 5-input NAND recombines the five term-NANDs, which by double negation equals the OR of the five terms — i.e. F itself. Four of the variables (w, x, y, z) are each needed in complemented form by at least one term, so four 1-input NAND gates (tied-input inverters) are added up front. $$\boxed{4 \text{ inverters} + 5\times\text{3-input NAND} + 1\times\text{5-input NAND} = 10 \text{ NAND gates}}$$ verified for all 16 input rows (Fig. Q3c).