Question 3 of 5: 4-Bit Negative-Magnitude → 2’s-Complement Converter

Question 3: 4-Bit Negative-Magnitude → 2’s-Complement Converter (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 4-bit magnitude $A_3A_2A_1A_0$ of a negative number (16 possible input codes, 0000–1111).

Find. (a) The complete truth table for the 4-bit output $B_3B_2B_1B_0=$ the 2’s complement of $A$. (b) Minimized K-map SOP for each $B_i$. (c) A minimum-gate combinational realization.

Approach. $B=(16-A)\bmod16$ (with $B=0000$ when $A=0000$). Tabulate all 16 rows, K-map each output bit, then recognize the standard "copy-until-first-1,-then-complement" structure of a 2’s complementer, which realizes all four outputs with only XOR/OR gates — fewer gates than a literal SOP implementation.

1. Part (a) — truth table.

   Truth table — $A_3A_2A_1A_0 \to B_3B_2B_1B_0$ (2’s complement of the 4-bit magnitude)

   A (dec, A3A2A1A0)	B3 B2 B1 B0
   0 (0000)	0000
   1 (0001)	1111
   2 (0010)	1110
   3 (0011)	1101
   4 (0100)	1100
   5 (0101)	1011
   6 (0110)	1010
   7 (0111)	1001
   8 (1000)	1000
   9 (1001)	0111
   10 (1010)	0110
   11 (1011)	0101
   12 (1100)	0100
   13 (1101)	0011
   14 (1110)	0010
   15 (1111)	0001

2. Part (b) — K-map simplification. Grouping the 1-cells of each output column on its own K-map (verified against all 16 rows above) gives $$B_0 = A_0$$ $$B_1 = \overline{A_0}A_1 + A_0\overline{A_1}$$ $$B_2 = \overline{A_0}\,\overline{A_1}A_2 + A_0\overline{A_2} + A_1\overline{A_2}$$ $$\boxed{B_3 = \overline{A_0}\,\overline{A_1}\,\overline{A_2}A_3 + (A_0+A_1+A_2)\overline{A_3}}$$ Each output's K-map groups fall out of the same recurring pattern: bit $i$ is copied unchanged while every bit below it is still 0, and complemented from the first 1 onward — exactly the manual "copy, then complement" rule for negating a binary number.
3. Part (c) — minimum-gate implementation. The K-map SOP equations above are more compactly (and equivalently) written using the same underlying "copy-until-first-1, complement-after" rule as $$B_0=A_0,\quad B_1=A_1\oplus A_0,\quad B_2=A_2\oplus(A_0+A_1),\quad B_3=A_3\oplus(A_0+A_1+A_2)$$ — identical truth tables to Part (b) but realized with only 2 OR2 gates (cascaded to build the running $A_0+A_1+A_2$ term) and 3 XOR2 gates, versus the far larger literal AND/OR gate count a direct SOP build of $B_2,B_3$ would need. $B_0$ is a direct wire, no gate at all.
   Fig. Q3(c) — minimum-gate 2’s complementer: $B_0=A_0$ (wire), $B_1=A_1\oplus A_0$, $B_2=A_2\oplus(A_0+A_1)$, $B_3=A_3\oplus(A_0+A_1+A_2)$ — 2 OR2 + 3 XOR2 gates total.