Question 2 of 5: PAL vs. FPGA, PAL16L8 Implementation and FPGA Logic Blocks

Question 2: PAL vs. FPGA, PAL16L8 Implementation and FPGA Logic Blocks (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. $F(a,b,c,d)=\sum m(0,2,4,6,7,9,11,13)$, no don't-cares; a PAL16L8 device (programmable AND array, fixed OR array, active-low output buffer per the appendix data sheet) is available for part (b).

Find. (a) The principal PAL-vs-FPGA architectural differences; (b) a PAL16L8 fuse map realizing $F$; (c) the main components of one FPGA logic block (ALM/CLB), with a block diagram.

Approach. Minimize $F$ by K-map to its minimal sum-of-products, map each product term onto one AND-array row of the PAL16L8, and sum them with the fixed OR array. For (c), describe and sketch the standard LUT+flip-flop+mux+carry-chain structure common to Altera ALMs and Xilinx CLB slices.

1. Part (a) — PAL vs. FPGA. A PAL (Programmable Array Logic) has a programmable AND array feeding a fixed OR array: fuses select which literals enter each product term, but the OR-array wiring that sums product terms into an output pin is fixed at fabrication, capping the product terms and total gate count per output. A PAL is one-time (fuse) or electrically reprogrammable (GAL), purely combinational-plus-simple-macrocell, with no internal routing fabric — cheap, low-power and fast for small "glue logic." An FPGA (Field-Programmable Gate Array) instead contains thousands to millions of small look-up-table (LUT) based logic cells with embedded flip-flops, block RAM and a rich programmable interconnect fabric, configured (typically from external SRAM, so reconfigurable at every power-up) to realize arbitrarily large combinational and sequential designs, including full processors. FPGAs cost and consume more but scale to orders of magnitude more logic than a PAL/GAL and support in-system reconfiguration.
2. Part (b) — minimize $F$ by K-map. Grouping the 8 minterms $\{0,2,4,6,7,9,11,13\}$ on the 4-variable K-map gives the minimal sum-of-products $$F = \overline{a}\,\overline{d} \;+\; a d \overline{b} \;+\; a d \overline{c} \;+\; b c\overline{a}.$$
3. Part (b) — program the PAL16L8. $F$ has 4 product terms, so 4 rows of the AND array are fused active at the literal columns $\{\overline a,\overline d\}$, $\{a,d,\overline b\}$, $\{a,d,\overline c\}$ and $\{b,c,\overline a\}$ respectively (every other crosspoint on those rows left blown/open), and every other product-term row feeding this output is left unprogrammed (logic 0). The fixed OR array sums the 4 fused rows. As in Question 1's device, the PAL16L8's output macrocells are active-low, so the physical output pin delivers $\overline F$; an external inverter (or programming the complementary term set) recovers $F$ itself.

4. Part (c) — ALM/CLB components. The basic reconfigurable logic block common to Altera's Adaptive Logic Module and Xilinx's Configurable Logic Block slice has four elements: (i) one or more small look-up tables (LUTs), typically 4- to 6-input, which can realize any Boolean function of their inputs by storing the truth table in fast SRAM cells addressed by the inputs; (ii) a flip-flop (or pair) per output, so the block can register the LUT's combinational result for synchronous designs; (iii) a small multiplexer network that selects between the raw (combinational) LUT output and the registered flip-flop output, and that can also split a larger LUT into two smaller independent functions; and (iv) a dedicated, hard-wired carry chain connecting adjacent blocks, which lets multi-bit adders/comparators/counters ripple a carry from block to block at very high speed without consuming the general-purpose programmable routing fabric. Thousands of these blocks, wired together by the FPGA's programmable interconnect, build arbitrarily large designs.