Question 1 of 5: FPGA/PLD Architecture & Sign-Magnitude to 2’s-Complement Converter

Question 1: FPGA/PLD Architecture & Sign-Magnitude to 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.

Part (a). A PAL/PLA is a fixed two-level AND–OR structure: the AND (product-term) array is fuse- or antifuse-programmable, but the OR array is wired at fabrication, so every output sums a small, fixed set of product terms — cheap and fast, but limited fan-in per output, no routing flexibility, and no sequential resources beyond an optional output flip-flop. An FPGA replaces this with a fine-grained array of small look-up-table (LUT) based logic cells, each paired with its own flip-flop, connected through a rich, field-programmable interconnect fabric. Three features make it versatile where a PLD is not: (1) arbitrary combinational functions per cell — a LUT realizes any function of its (typically 4–6) inputs, not just a sum of fixed-width product terms; (2) a programmable routing fabric that lets thousands of cells be wired into deep, wide, pipelined datapaths, whereas a PLD's AND/OR arrays cannot be chained beyond their own output register; (3) per-cell registers plus embedded blocks (block RAM, multipliers/DSP slices, sometimes hard processor cores) that let an FPGA hold large state machines, memories and arithmetic units on one device — capacity a PLA/PAL, sized for a handful of equations, cannot approach.

Approach (part b). Sign-magnitude splits the word into a sign bit a₃ and a 3-bit magnitude a₂a₁a₀ (0–7). For a₃=0 the 2’s-complement value equals the magnitude unchanged. For a₃=1 the standard 2’s-complement rule applies to the sign-extended magnitude: invert every bit, then add 1. Building the circuit as “conditionally invert, then ripple-increment” (rather than deriving four independent 4-variable K-maps from scratch) is what drives the gate count to the minimum.

1. Truth table by inspection. For a₃=0, Z = 0 a₂ a₁ a₀ (pass-through — a positive value's 2’s-complement form is itself). For a₃=1, Z is the 4-bit 2’s complement of the sign-extended magnitude 0 a₂ a₁ a₀: invert all four bits, then add 1. Conditional inversion of bit i is exactly c_i = a_i ⊕ a₃ (passes a_i through unchanged when a₃=0, inverts it when a₃=1) — and the sign-extension bit inverts to c₃ = 0 ⊕ a₃ = a₃. Adding 1 is then an ordinary ripple carry with carry-in tied to a₃ (so the +1 only fires when a₃=1): $$Z_0 = c_0 \oplus a_3,\quad carry_0 = c_0 \cdot a_3$$ $$Z_1 = c_1 \oplus carry_0,\quad carry_1 = c_1 \cdot carry_0$$ $$Z_2 = c_2 \oplus carry_1,\quad carry_2 = c_2 \cdot carry_1$$ $$Z_3 = c_3 \oplus carry_2 = a_3 \oplus carry_2$$ This was brute-force checked against the direct arithmetic definition of Z for all 16 (a₃,a₂,a₁,a₀) combinations — it matches exactly.
2. Simplify Z₀ first (K-map not even needed). Substituting c₀=a₀⊕a₃: $$Z_0 = (a_0 \oplus a_3) \oplus a_3 = a_0$$ since XOR-ing twice by the same signal cancels. $$\boxed{Z_0 = a_0}$$ — a direct wire, no gate at all. This makes sense physically: the least-significant bit of a 2’s-complement negation is always unchanged (invert-then-+1 always returns the LSB to its original value).
3. Z₁ — K-map view confirms a 2-gate result. carry₀ = c₀·a₃ = (a₀⊕a₃)·a₃ = a₀·a₃ (since a₃·a₃=a₃ and the a₃=0 rows of the XOR vanish under the AND). So $$Z_1 = c_1 \oplus carry_0 = (a_1 \oplus a_3) \oplus (a_0 \cdot a_3)$$ Plotting Z₁ on a 4-variable K-map (a₃,a₂,a₁,a₀) shows the 1-cells split cleanly along this same grouping — no further reduction is possible since Z₁ depends on all of a₃,a₁,a₀ and no larger adjacent group exists. $$\boxed{Z_1 = a_1 \oplus (a_3 \cdot a_0)}$$ realized as 1 AND + 1 XOR (2 gates).
4. Z₂ and Z₃ — continue the ripple. carry₁ = c₁·carry₀, so $$Z_2 = c_2 \oplus carry_1 = (a_2\oplus a_3)\oplus\big[(a_1\oplus a_3)\cdot(a_0\cdot a_3)\big]$$ (1 AND + 1 XOR beyond the shared carry chain). carry₂ = c₂·carry₁ is zero unless a₃=1 AND a₂=a₁=a₀=0 (the a₃=1,magnitude=0 row, i.e. −0), so $$Z_3 = a_3 \oplus carry_2 = a_3\cdot(a_2+a_1+a_0)$$ which matches the K-map directly: Z₃=1 exactly on the eight cells a₃=1 with at least one magnitude bit set. $$\boxed{Z_3 = a_3\cdot(a_2+a_1+a_0),\quad Z_2 = c_2\oplus carry_1}$$
5. Gate count. 3 XOR gates build c₀,c₁,c₂ from a₃ and each magnitude bit; the ripple chain adds 3 AND (carry₀,carry₁,carry₂) + 3 XOR (Z₁,Z₂,Z₃); Z₀ needs none. $$\boxed{9\text{ two-input gates total}}$$