Question 3 of 6: K-map minimisation and PAL/PLA implementation

Question 3: K-map minimisation and PAL/PLA implementation [6+6 = 12]

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. The 8-row truth table:

Find. Minimal SOP for $A,B,C,D$, and the more suitable programmable-logic family for implementing all four simultaneously.

Approach. Plot each output on its own 3-variable K-map (rows $X{=}0/1$, columns $YZ$ in Gray-code order $00,01,11,10$), group adjacent 1s into the largest possible pairs/quads, then compare the resulting product terms across all four outputs to decide between PAL and PLA.

(a) K-map minimisation.

1. K-map for $A$. Minterms $\Sigma(1,3,4,7)$, i.e. rows $XYZ{=}001,011,100,111$. Groups: $\{001,011\}\Rightarrow \bar XZ$; $\{011,111\}\Rightarrow YZ$; $\{100\}$ stands alone $\Rightarrow X\bar Y\bar Z$ (no adjacent 1 to pair with). $$A=YZ+\bar XZ+X\bar Y\bar Z.$$
2. K-map for $B$. Minterms $\Sigma(0,3,5,6,7)$. Groups: $\{000\}$ alone $\Rightarrow \bar X\bar Y\bar Z$; $\{011,111\}\Rightarrow YZ$; $\{101,111\}\Rightarrow XZ$; $\{110,111\}\Rightarrow XY$. $$B=XY+XZ+YZ+\bar X\bar Y\bar Z.$$
3. K-map for $C$. Minterms $\Sigma(0,2,3,4,6)$. Groups: $\{000,010,100,110\}\Rightarrow \bar Z$ (quad, all four $Z{=}0$ rows); $\{010,011\}\Rightarrow \bar XY$. $$C=\bar Z+\bar XY.$$
4. K-map for $D$. Minterms $\Sigma(2,3,4,5,7)$. Groups: $\{011,111\}\Rightarrow YZ$; $\{100,101\}\Rightarrow X\bar Y$; $\{010,011\}\Rightarrow \bar XY$. $$D=YZ+X\bar Y+\bar XY.$$

(b) PAL vs PLA. Collecting the distinct product terms actually needed: $A$ uses $\{YZ,\bar XZ,X\bar Y\bar Z\}$; $B$ uses $\{XY,XZ,YZ,\bar X\bar Y\bar Z\}$; $C$ uses $\{\bar Z,\bar XY\}$; $D$ uses $\{YZ,X\bar Y,\bar XY\}$. Two terms recur across outputs: $YZ$ (needed by $A$, $B$ and $D$) and $\bar XY$ (needed by $C$ and $D$). That is 12 term-uses collapsing to 9 distinct AND-plane rows.

A PAL has a programmable AND array but a fixed OR array — each output OR-gate is wired to its own dedicated block of AND rows, so a term shared between two outputs must be generated twice (once per output's private AND rows), i.e. a PAL implementation would need all 12 term-uses as separate AND gates. A PLA has both arrays programmable, so any one AND-plane row can be routed to any number of OR-gates: the 9 unique product terms above are generated once each and shared, giving a $9\times4$ PLA array (9 AND rows $\times$ 3 input literals, feeding 4 programmable OR gates) instead of 12 dedicated AND gates. $$\boxed{\text{PLA is the better choice here} - \text{term sharing ($YZ$, $\bar XY$) cuts the AND-plane from 12 to 9 rows.}}$$