K-map minimization and PAL/PLA choice: 22-Elec-A4 Digital Systems and Computers, December 2018, Q3

Question 3: K-map minimization and PAL/PLA choice (12 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. Four output functions of $X,Y,Z$: $A=\Sigma m(1,3,4,7)$, $B=\Sigma m(0,3,5,6,7)$, $C=\Sigma m(0,2,3,4,6)$, $D=\Sigma m(2,3,4,5,7)$ (minterm index $m=4X+2Y+Z$).

Find. A minimal SoP for each output and a reasoned PAL-vs-PLA choice.

Approach. Plot each output on its own 3-variable K-map, take the largest legal groups, then count how many distinct product terms the four functions need versus how many term instances a per-output (PAL) array would replicate.

Output A. Groups $\overline{X}Z$ (m1,m3), $YZ$ (m3,m7) and the isolated $X\overline{Y}\,\overline{Z}$ (m4): $$A=\overline{X}Z+YZ+X\overline{Y}\,\overline{Z}.$$
K-map for $A$.
Output B. The three majority pairs $XY,XZ,YZ$ cover m3,m5,m6,m7 and the isolated $\overline{X}\,\overline{Y}\,\overline{Z}$ covers m0: $$B=XY+XZ+YZ+\overline{X}\,\overline{Y}\,\overline{Z}.$$
K-map for $B$ (majority of $X,Y,Z$ plus the all-zero cell).
Output C. The whole $Z=0$ column is 1 (m0,m2,m4,m6), and $\overline{X}Y$ picks up m3: $$\boxed{C=\overline{Z}+\overline{X}Y.}$$
K-map for $C$.
Output D. $\overline{X}Y$ (m2,m3), $X\overline{Y}$ (m4,m5) and $XZ$ (m5,m7): $$D=\overline{X}Y+X\overline{Y}+XZ.$$
K-map for $D$.
(b) PAL vs PLA. The four expressions use $3+4+2+3=12$ product-term instances, but only $9$ are distinct because $YZ$ is shared by $A,B$; $XZ$ by $B,D$; and $\overline{X}Y$ by $C,D$. A PLA has a single programmable AND array that can share those three terms across outputs, needing only $\boxed{9}$ product lines; a PAL gives each output its own fixed AND group (no sharing), so it would spend $12$ terms and must also budget the widest output ($B$, 4 terms) per group. With three genuinely shared terms, the PLA is the more economical choice here.

Question 3 — minimized outputs
Output	Minimal SoP	Terms
$A$	$\overline{X}Z+YZ+X\overline{Y}\,\overline{Z}$	3
$B$	$XY+XZ+YZ+\overline{X}\,\overline{Y}\,\overline{Z}$	4
$C$	$\overline{Z}+\overline{X}Y$	2
$D$	$\overline{X}Y+X\overline{Y}+XZ$	3
Device	PLA — 9 shared product terms vs 12 for a PAL	—

Topic. Multi-output K-map minimization and programmable-logic selection.

Key relations. SoP minimization; PLA = programmable AND + programmable OR (terms shareable); PAL = programmable AND + fixed OR (terms dedicated per output).

Why this works. The device decision is quantitative: count distinct product terms against term instances. Sharing only helps if the same product appears in more than one output, which is exactly what a PLA's fully programmable OR array exploits; a PAL cannot, so it pays for every repeated term. Here the sharing (3 terms) is real, so the PLA wins on array size.

Common pitfall. Minimising each output in isolation and missing shared terms, or defaulting to "PAL is faster/cheaper" without counting — the justification, not the verdict, carries the marks.

Source. Mano & Ciletti, Digital Design, §3.5 (K-maps) and §7.7–7.8 (PLA, PAL).

Question 3 of 6: K-map minimization and PAL/PLA choice

Question 3: K-map minimization and PAL/PLA choice (12 marks)