PAL Implementation of Two Sum-of-Products Functions: 25-Comp-A2 Digital Systems Design, May 2016, Q2

Question 2: PAL Implementation of Two Sum-of-Products Functions (20 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 3-variable Boolean functions already in sum-of-products form, and a PAL (Programmable Array Logic) device offering three inputs $a,b,c$ (each buffered to its true and complement line), a programmable AND array, and two fixed-OR output structures.

Find. The product-term (AND-gate) connections that realize $F_1$ and $F_2$ on the PAL's two OR outputs.

Approach. A PAL's AND array is fully programmable (any subset of the $2n$ true/complement input lines can feed any AND gate) while its OR array is fixed, wired in groups of a set size to each output — so implementation is simply: assign one AND gate per product term already present in the SOP expression, connect only the literals that term needs (leaving the rest of that AND gate's inputs unconnected, which floats them to the gate's identity value), and let the fixed OR sum the assigned group.

Part 1 — buffer the three inputs to true/complement pairs. Each PAL input cell provides both a variable and its complement to the vertical bit-lines of the AND array: $a,\bar a,\ b,\bar b,\ c,\bar c$ — six lines total, available to every AND gate's programmable fuse matrix.
Part 2 — one AND gate per product term of $F_1$. $F_1$ already has exactly three SOP terms, matching the three AND gates wired into the first fixed-OR group: $$P_1=\bar a b,\qquad P_2=a\bar b,\qquad P_3=c$$ $P_1$ connects only the $\bar a$ and $b$ lines (its third input left unconnected); $P_2$ connects only $a$ and $\bar b$; $P_3$ connects only $c$ (its other two inputs unconnected). The fixed OR then gives $$F_1=\boxed{P_1+P_2+P_3=\bar ab+a\bar b+c}$$ exactly reproducing the given expression — no minimization was needed since it was already in minimal SOP form.
Part 3 — one AND gate per product term of $F_2$. $F_2$ likewise has exactly three SOP terms, assigned to the second group of three AND gates: $$P_4=\bar a\bar b\bar c,\qquad P_5=ab\bar c,\qquad P_6=\bar abc$$ each fully wired (all three literals connected, since every term here has three literals). The second fixed OR gives $$F_2=\boxed{P_4+P_5+P_6=\bar a\bar b\bar c+ab\bar c+\bar abc}$$
Part 4 — confirm fan-in and fuse count. Every AND gate here uses at most 3 of its available inputs (the PAL's own input count), so no product term overflows the array; a total of $2+2+1+3+3+3=14$ literal connections ("fuses left intact") realize both functions, well within a standard PAL's per-gate fan-in.

Fig. Q2 — PAL AND-OR array: six product-term AND gates ($P_1$-$P_3$ feed the $F_1$ OR, $P_4$-$P_6$ feed the $F_2$ OR); dashed lines mark the fuse connections actually left intact per term, all other AND-gate inputs unconnected.

Final Results — Question 2
Output	Product terms (AND gates)	Realized function
$F_1$	$P_1=\bar ab,\ P_2=a\bar b,\ P_3=c$	$F_1=\bar ab+a\bar b+c$
$F_2$	$P_4=\bar a\bar b\bar c,\ P_5=ab\bar c,\ P_6=\bar abc$	$F_2=\bar a\bar b\bar c+ab\bar c+\bar abc$

Topic: Programmable Array Logic (PAL): fixed-OR, programmable-AND SOP realization.

Key relations: PAL input cell $\to$ true+complement bit-lines; one AND gate per SOP product term, connecting only that term's literals; fixed groups of AND-gate outputs summed by a dedicated OR gate per output pin.

Why this works: Because the OR array is hard-wired (unlike a PLA, which also has a programmable OR array), a PAL realizes any function directly in SOP form simply by blowing the fuses for each term's literals — no further factoring is required as long as the function's term count does not exceed the number of AND gates wired to that output.

Common pitfall: Leaving an unused AND-gate input un-programmed in a way that ties it to a fixed 0/1 rather than genuinely disconnecting it — on a real PAL, an unprogrammed (unblown) input is left at its default (typically floating high inside the array, contributing nothing to that AND's result), which is exactly what makes a 1- or 2-literal term work on a gate sized for more inputs.

Source: Mano & Ciletti, Digital Design, Programmable logic devices (PAL/PLA) implementation of combinational functions.

Question 2 of 6: PAL Implementation of Two Sum-of-Products Functions

Question 2: PAL Implementation of Two Sum-of-Products Functions (20 marks)