PAL Implementation of Two Functions: 25-Comp-A2 Digital Systems Design, December 2018, Q2

Question 2: PAL Implementation of Two 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. A PAL with six input lines $a,a',b,b',c,c'$, six programmable AND (product-term) columns $P_1$–$P_6$, and two fixed 3-input OR gates producing $F1$ (from $P_1,P_2,P_3$) and $F2$ (from $P_4,P_5,P_6$).

Find. Which fuses to keep intact (dot) on each of the six product-term columns so the OR-plane outputs realize $F1=a'b+ab'+c$ and $F2=a'b'c'+abc'+a'bc$ exactly as given.

Approach. Both expressions are already minimal sum-of-products, so no Boolean simplification is needed — each of the six literal product terms is assigned to one AND column, with a fuse dot kept only on the input lines that literal term actually uses (an unconnected AND input floats to logic 1 and does not constrain the product, which is exactly "don't include this literal").

Assign $F1$'s three terms to columns $P_1$–$P_3$ (first OR gate). $F1=a'b+ab'+c$ has three product terms, one literal pattern each: $$P_1=a'b,\qquad P_2=ab',\qquad P_3=\boxed{c}$$ $P_1$ keeps dots on $a'$ and $b$ only; $P_2$ keeps dots on $a$ and $b'$ only; $P_3$ keeps a single dot on $c$ (a one-literal product term uses only one input line, and the AND gate's other four unconnected inputs float to 1 and drop out of the product).
Assign $F2$'s three terms to columns $P_4$–$P_6$ (second OR gate). $F2=a'b'c'+abc'+a'bc$ has three 3-literal minterm-style terms: $$P_4=a'b'c',\qquad P_5=abc',\qquad P_6=\boxed{a'bc}$$ $P_4$ keeps dots on $a',b',c'$; $P_5$ keeps dots on $a,b,c'$; $P_6$ keeps dots on $a',b,c$ — three dots each, one per literal in the term.
Wire the OR plane (fixed, no programming needed). $P_1,P_2,P_3$ feed the first OR gate, giving $F1=P_1+P_2+P_3=a'b+ab'+c$; $P_4,P_5,P_6$ feed the second OR gate, giving $F2=P_4+P_5+P_6=a'b'c'+abc'+a'bc$ — the OR-plane connections are fixed silicon (not fuse-programmed) on a PAL, so the entire implementation is captured by the eighteen dots above.

Fig. Q2 — PAL fuse map: columns $P_1$-$P_3$ (dots on $a',b$; $a,b'$; $c$) feed the OR gate producing $F1$; columns $P_4$-$P_6$ (dots on $a',b',c'$; $a,b,c'$; $a',b,c$) feed the OR gate producing $F2$. Every AND input line without a dot floats to logic 1 and drops out of that product term.

Final Results — Question 2
Column	Product term	Dotted (kept) fuses	Feeds
$P_1$	$a'b$	$a'$, $b$	$F1$
$P_2$	$ab'$	$a$, $b'$	$F1$
$P_3$	$c$	$c$	$F1$
$P_4$	$a'b'c'$	$a'$, $b'$, $c'$	$F2$
$P_5$	$abc'$	$a$, $b$, $c'$	$F2$
$P_6$	$a'bc$	$a'$, $b$, $c$	$F2$

Topic: Programmable Array Logic (PAL) — a programmable AND plane feeding a fixed OR plane.

Key relations: PAL structure $=$ programmable AND array $+$ fixed OR array (the reverse of a PLA, which programs both planes); each AND column implements one product term; an AND input left unconnected (fuse blown, per this convention "no dot") floats to 1 and is excluded from that product.

Why this works: Because the target expressions are already in minimal sum-of-products form, mapping the PAL is a direct one-term-per-column translation with zero Boolean algebra required — the entire design effort is in correctly reading off which literals each term contains, exactly the intended teaching point of a PAL-mapping question.

Common pitfall: Trying to share one product-term column between $F1$ and $F2$ — on a PAL each AND column drives only ONE fixed OR gate, so a term common to both outputs (there is none here) would still need to be programmed twice, once per column feeding each OR gate.

Source: Mano & Ciletti, Digital Design, Programmable Logic Devices (PAL/PLA).

Question 2 of 6: PAL Implementation of Two Functions

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