Question 1 of 5: Code Comparison, Gray-to-Binary Conversion and NAND Synthesis

Question 1: Code Comparison, Gray-to-Binary Conversion and NAND Synthesis (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. Two 4-bit codes are to be compared (BCD, natural 8-4-2-1 binary-coded-decimal; and Gray, the reflected unit-distance code), and a 4-bit Gray-to-Binary converter is to be designed, minimized by K-map, then re-implemented using 2-input NAND gates only.

Find. (a) The principal advantages/disadvantages of BCD versus Gray code; (b) the minimized Boolean expressions and minimum-gate circuit for $B_3B_2B_1B_0$ from $G_3G_2G_1G_0$; (c) the same converter built from 2-input NAND gates only.

Approach. Part (a) is a direct code-property comparison. For (b)/(c), build the 16-row Gray-to-Binary truth table, K-map each output bit, recognize the resulting checkerboard pattern as the standard ripple-XOR identity, then replace each XOR with its 4-NAND equivalent for part (c).

1. Part (a) — BCD. Advantages: each 4-bit group maps directly onto one decimal digit, so BCD is easy to display (seven-segment decoders), easy for humans to read off an instrument, and simplifies decimal I/O (keypads, decimal arithmetic units). Disadvantages: BCD is not weight-efficient — only 10 of the 16 four-bit combinations (0000–1001) are valid, wasting 6 codes (1010–1111) and requiring illegal-code detection; a straight binary adder produces wrong results on BCD operands whenever a digit sum exceeds 9, so BCD arithmetic needs extra correction logic (add-6 correction); and consecutive decimal values can differ in several bits at once (e.g. 3→4 is $0011\to0100$, 3 bits change), which is undesirable wherever multi-bit transition glitches matter.
2. Part (a) — Gray code. Advantages: Gray code is a unit-distance code — exactly one bit changes between any two consecutive values — which eliminates the transient multi-bit "race" states that plague binary counters/encoders in asynchronous or electromechanical systems (shaft-angle encoders, low-glitch counters) and is why Gray code is the standard choice for Karnaugh-map cell ordering. Disadvantages: Gray code has no direct arithmetic meaning (successive codes are not simple binary weights), so it cannot be added/subtracted or compared for magnitude directly — it must first be converted to binary — and it has no direct correspondence to decimal digits, so it is unsuited to human-readable decimal display.
3. Part (b) — build the 16-row truth table and K-map each bit. Tabulating $B_3B_2B_1B_0$ against every $G_3G_2G_1G_0$ combination and grouping each output on its own 4-variable K-map gives a checkerboard (no two adjacent 1-cells share an edge) for $B_2,B_1,B_0$ — the signature of an XOR relationship, not a reducible sum-of-products — while $B_3$ is simply a direct copy of $G_3$: $$B_3=G_3,\qquad B_2=G_3\oplus G_2,\qquad B_1=B_2\oplus G_1,\qquad \boxed{B_0=B_1\oplus G_0.}$$
4. Part (b) — minimum-gate realization. Because $B_3$ needs no gate at all and each remaining bit is one 2-input XOR of the previous result with the next Gray bit, the whole 4-bit converter needs only 3 XOR gates — fewer than any 2-level AND-OR sum-of-products the raw K-map grouping would give, since the checkerboard pattern cannot be covered by adjacent-cell groups.

5. Part (c) — NAND-only realization. A 2-input XOR $y=x_1\oplus x_2$ is built from exactly 4 two-input NAND gates: $n_1=\overline{x_1x_2}$; $n_2=\overline{x_1n_1}$; $n_3=\overline{x_2n_1}$; $y=\overline{n_2n_3}$. Substituting this 4-NAND block for each of the 3 XOR gates in part (b), with the same cascade topology ($B_3=G_3$ direct, then the two chained taps), gives $3\times4=\boxed{12}$ two-input NAND gates in total — the minimum for this converter, since a single NAND-only 2-level SOP realization of the checkerboard functions would need substantially more gates than the multi-level XOR-tree structure.