Question 2 of 5: FPGA Architecture, and a 2’s-Complement→Sign-Magnitude Converter

Question 2: FPGA Architecture, and a 2’s-Complement→Sign-Magnitude 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.

(a) A PAL (Programmable Array Logic) has a programmable AND array feeding a fixed OR array, and a PLA (Programmable Logic Array) programs both the AND and OR arrays — but both are still single-level, two-plane SOP structures with a small, fixed pool of macrocells and no routing between cells other than through the fixed I/O pins. An FPGA (Field-Programmable Gate Array) is architecturally different in three ways that make it far more versatile: (1) it is built from a large 2-D array of small, identical Configurable Logic Blocks (each a look-up table + flip-flop, able to realize any function of a few inputs, not just a fixed AND-OR term); (2) it has a rich, programmable interconnect fabric (routing channels and programmable switch matrices) that lets any CLB output reach any other CLB input, so designs are not limited to one pass through a fixed two-level array — arbitrarily deep, arbitrarily large logic and full sequential state machines fit on one device; and (3) it integrates abundant on-chip flip-flops/registers and, on modern devices, dedicated block RAM, multipliers and I/O standards, so an entire digital subsystem (datapath + control + memory) can be realized in one part. A PAL/PLA, by contrast, is sized for a handful of SOP equations and cannot economically hold a large state machine or a memory-based function. This is why FPGAs scale from small glue logic up to entire SoC-class designs, while PAL/PLA remain suited only to small fixed combinational replacement logic.

Given. $C_3C_2C_1C_0$, a 4-bit 2’s-complement code for an integer in $[-8,7]$, restricted by the question to the sub-range $[-7,+7]$ (so the all-magnitude-zero-sign-negative code $1000$, which would encode $-8$ and has no 4-bit sign-magnitude equivalent, never occurs and is a don’t-care).

Find. $M_3M_2M_1M_0$, the 4-bit sign-magnitude equivalent ($M_3$=sign, $M_2M_1M_0$=magnitude), via truth table, K-map SOP, and a minimum-2-input-gate circuit.

Approach. Tabulate all 15 valid codes (minterm 8 = don’t-care), K-map/minimize each output bit directly from the table, then recognize the arithmetic shortcut — sign-magnitude conversion from 2’s complement is exactly "conditionally invert the magnitude bits when negative, then add 1" — which realizes the same four functions with far fewer, more regular gates than the raw SOP.

1. Part (b), Step 1 — K-map each output bit directly. Grouping the 1-cells of each column above (minterm 8 used as a don’t-care wherever it helps a group) gives, by Quine-McCluskey: $$M_3 = C_3 \qquad M_0 = C_0$$ $$M_2 = C_3C_1'C_0' + C_3'C_2 + C_3C_2' \qquad M_1 = C_1C_0' + C_3'C_1 + C_3C_1'C_0$$ $M_3$ and $M_0$ collapse to a single literal (a bare wire, zero gates); $M_2$ and $M_1$ each need 3 product terms — a K-map on 4 variables does not group them into anything smaller, so a literal AND-OR realization of $M_2$ needs roughly 3 AND gates (one of them 3-input) + a 3-input OR, and $M_1$ the same — more than 2-input gates permit without further decomposition.
2. Part (b), Step 2 — recognize the arithmetic structure for the minimum-gate design. Converting 2’s complement to sign-magnitude is exactly: keep the sign bit ($M_3=C_3$); if negative, the magnitude is the 2’s complement of $C_2C_1C_0$ (invert then add 1), and if positive the magnitude is $C_2C_1C_0$ unchanged. Both cases are captured in one uniform rule by XOR-ing each magnitude bit with the sign bit first (conditional invert: $Y_i = C_i\oplus C_3$ is a no-op when $C_3=0$ and a true inversion when $C_3=1$), then rippling $C_3$ itself in as the add-one carry: $$M_0 = Y_0\oplus C_3,\quad c_0=Y_0\cdot C_3,\quad M_1=Y_1\oplus c_0,\quad c_1=Y_1\cdot c_0,\quad M_2=Y_2\oplus c_1$$ This uses 6 XOR + 2 AND = 8 two-input gates total for $M_2,M_1,M_0$ (plus $M_3=C_3$ and, redundantly, $M_0=Y_0\oplus C_3$ collapses to $M_0=C_0$ exactly as the K-map found — both derivations agree).
   Fig. Q2(b) — conditional-complementer (XOR-then-ripple-add) sign-magnitude converter, 8 two-input gates total (plus the free wire $M_3=C_3$).