22-Elec-A4 Digital Systems and Computers · December 2013

Question 3 of 6: Four-Output Combinational Circuit and PLD Choice

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Notes on this paper

Paper format. National Exams, December 2013 — 07-Elec-A4 Digital Systems & Computers. Three hours, closed book (one approved Casio or Sharp calculator). Six questions are printed; any five constitute a complete exam and every question is worth 12 marks, with the per-part split printed in the marking scheme on page 1 (Q1 and Q5 are 3+3+3+3; Q2 is 4+4+4; Q3 and Q6 are 6+6; Q4 is 8+2+2). An excitation table for the RS/JK/T/D flip-flops and a table of 22 basic Boolean identities are supplied on the last page. All six questions are solved below, because this set is a study resource rather than a timed sitting.

Reference texts.

M. M. Mano and M. D. Ciletti, Digital Design: With an Introduction to the Verilog HDL, VHDL, and SystemVerilog, 6th ed. — Boolean algebra and K-maps (Ch. 2–3), combinational MSI design with multiplexers and decoders (Ch. 4), synchronous sequential logic and flip-flop excitation (Ch. 5), registers and counters (Ch. 6), memory and programmable logic (Ch. 7).
J. F. Wakerly, Digital Design: Principles and Practices, 5th ed. — canonical forms, minimisation and timing hazards (Ch. 3–4), PLD architectures (Ch. 5), counters (Ch. 8).
C. Hamacher, Z. Vranesic, S. Zaky and N. Manjikian, Computer Organization and Embedded Systems, 6th ed. — bus structure and I/O (Ch. 3), polling versus interrupts (§3.2), serial interfaces (§3.5), memory system organisation and chip-select decoding (Ch. 8).

Notation used throughout. A prime and an overbar both denote complement: $\overline{A}$ in the mathematics, A′ in the figures, where SVG text cannot carry an overbar. The variable order in every K-map is the order printed in the question, with the leftmost variable as the most significant bit, so minterm and maxterm indices match the question's numbering exactly.

Question 3: Four-Output Combinational Circuit and PLD 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. A three-input, four-output truth table with inputs $X$, $Y$, $Z$ ($X$ most significant) and outputs $A$, $B$, $C$, $D$:

$X$	$Y$	$Z$	$A$	$B$	$C$	$D$
0	0	0	0	1	1	0
0	0	1	1	0	0	0
0	1	0	0	0	1	1
0	1	1	1	1	1	1
1	0	0	1	0	1	1
1	0	1	0	1	0	1
1	1	0	0	1	1	0
1	1	1	1	1	0	1

Reading each output column as a minterm list gives

$$A = \sum m(1,3,4,7), \quad B = \sum m(0,3,5,6,7), \quad C = \sum m(0,2,3,4,6), \quad D = \sum m(2,3,4,5,7)$$

Find. A minimum two-level SoP expression for each output, and a justified choice between a PAL and a PLA for the four-output implementation.

Approach. Minimise each output independently on its own three-variable K-map, then count the distinct product terms across all four outputs and compare that against the number of term instances: the gap between the two is precisely the saving a PLA's programmable OR array can capture and a PAL's fixed OR array cannot.

(a) Simplified expressions (6 marks)

@@q3_A@@

Figure 3.1 — output $A$. Minterm 4 is isolated (none of 0, 5 or 6 is a one), so it must be covered by a full three-literal product.

@@q3_B@@

Figure 3.2 — output $B$. Minterm 7 lies in three different pairs; each of those pairs is essential for a different neighbour, so all three are kept.

@@q3_C@@

Figure 3.3 — output $C$. The whole $Z=0$ column pair forms one group of four, leaving only minterm 3 to pick up.

@@q3_D@@

Figure 3.4 — output $D$. Minterms 2 and 4 each force a pair; either $YZ$ or $XZ$ then covers minterm 7.

Output $A = \sum m(1,3,4,7)$. Minterm 1 pairs only with 3 (giving $\overline{X}Z$) and minterm 7 pairs only with 3 (giving $YZ$); both are therefore essential. Minterm 4 has no one-valued neighbour at all, so it stands alone: $$A = \overline{X}Z + YZ + X\overline{Y}\,\overline{Z} \qquad (3\ \text{terms})$$
Output $B = \sum m(0,3,5,6,7)$. Minterm 0 is isolated. Minterms 3, 5 and 6 each pair only with 7, forcing the three pairs $YZ$, $XZ$ and $XY$ — the majority function — and every one of them is essential: $$B = \overline{X}\,\overline{Y}\,\overline{Z} + XY + XZ + YZ \qquad (4\ \text{terms})$$
Output $C = \sum m(0,2,3,4,6)$. The four cells with $Z=0$ are all ones, giving the single-literal term $\overline{Z}$; only minterm 3 remains, and it pairs with 2 to give $\overline{X}Y$: $$C = \overline{Z} + \overline{X}Y \qquad (2\ \text{terms})$$
Output $D = \sum m(2,3,4,5,7)$. Minterm 2 pairs only with 3 ($\overline{X}Y$) and minterm 4 only with 5 ($X\overline{Y}$); those two are essential and together cover 2, 3, 4 and 5. Minterm 7 is then covered by either $YZ$ or $XZ$ — the solution is not unique, and we take $$D = \overline{X}Y + X\overline{Y} + YZ = (X \oplus Y) + YZ \qquad (3\ \text{terms})$$

An exhaustive search over all implicant combinations confirms that no cover with fewer terms exists for any of the four outputs, so the term counts 3, 4, 2 and 3 — twelve term instances in total — are genuinely minimal. Boxing the set:

$$\boxed{\;\begin{aligned} A &= \overline{X}Z + YZ + X\overline{Y}\,\overline{Z} \\ B &= \overline{X}\,\overline{Y}\,\overline{Z} + XY + XZ + YZ \\ C &= \overline{Z} + \overline{X}Y \\ D &= \overline{X}Y + X\overline{Y} + YZ \end{aligned}\;}$$

(b) PAL or PLA, with justification (6 marks)

Count distinct product terms versus term instances. The twelve term instances above are drawn from only nine distinct products, because $YZ$ appears in $A$, $B$ and $D$, and $\overline{X}Y$ appears in $C$ and $D$: $$\{\,\overline{X}Z,\ YZ,\ X\overline{Y}\,\overline{Z},\ \overline{X}\,\overline{Y}\,\overline{Z},\ XZ,\ XY,\ \overline{Z},\ \overline{X}Y,\ X\overline{Y}\,\}$$
Size each architecture. A PLA has both arrays programmable, so one AND row can drive any number of OR sums: 9 AND rows and a $9 \times 4$ OR array carry the whole design. A PAL has a fixed OR array in which each output owns a private, fixed allocation of product terms; a shared term must be generated separately for every output that uses it. Since the widest output needs four products, the smallest standard part is a four-product-per-output device, giving $4 \times 4 = \mathbf{16}$ AND rows, of which twelve are used and four wasted.
Choose and justify. The PLA is the better fit: $$\boxed{\text{PLA: 9 AND rows} \;\lt\; \text{PAL: 16 AND rows (12 needed, } YZ \text{ replicated three times)}}$$ The design has genuine, repeated term sharing across outputs, which is exactly the situation the programmable OR array exists to exploit; it also leaves the design free to grow an output past four products without changing part. The honest counter-argument, which should be stated, is that a PAL is faster (one fixed array instead of two programmable ones), cheaper and easier to program, so on a four-output problem this small a designer with a 16-product PAL already in stock would reasonably use it. The marks are for recognising the sharing and quantifying it, not for a dogmatic answer.

Figure 3.5 — the PLA programming map. Every dot is a programmed connection in the OR array; the row $YZ$ feeding three outputs at once is the saving a PAL cannot make.

Output	Minimum SoP	Products
$A$	$\overline{X}Z + YZ + X\overline{Y}\,\overline{Z}$	3
$B$	$\overline{X}\,\overline{Y}\,\overline{Z} + XY + XZ + YZ$	4
$C$	$\overline{Z} + \overline{X}Y$	2
$D$	$\overline{X}Y + X\overline{Y} + YZ$	3
Term instances / distinct terms		12 / 9
Choice		PLA (9 AND rows vs 16 for a PAL)

Topic. Multiple-output two-level minimisation and the architectural difference between PAL and PLA.

Key relations. PLA cost $\approx$ number of distinct product terms; PAL cost $\approx$ (products per output) $\times$ (number of outputs), independent of sharing; a term is shareable exactly when it is an implicant of more than one output.

Why this works. A PLA programs both the AND array (which literals form each product) and the OR array (which products form each sum), so a product term is a resource in a common pool. A PAL fixes the OR array at manufacture: output $k$ is hard-wired to a specific block of AND rows and can never borrow a neighbour's. Sharing therefore has value in a PLA and none in a PAL, and the whole decision reduces to comparing the distinct-term count against the worst-case per-output count. That fixed OR array is not merely a limitation — removing one level of programmable interconnect is what makes a PAL faster and cheaper, which is why PALs and their descendants, not PLAs, dominated the market. Note also that strict per-output minimisation is not always optimal for a PLA: deliberately using a non-minimal cover for one output can sometimes let it share a term already present, cutting the distinct-term count further.

Common pitfall. Minimising the four outputs in isolation and then reporting the term count as twelve, without noticing that $YZ$ and $\overline{X}Y$ recur — the whole point of the question is the difference between 12 instances and 9 distinct terms. A second trap is output $D$, where two equally minimal covers exist; choosing $YZ$ rather than $XZ$ is worth a remark, since $YZ$ is already needed by $A$ and $B$ and so costs a PLA nothing at all, whereas $XZ$ would push the distinct count to ten.

Source. Mano & Ciletti, Digital Design, 6th ed., §7.5–7.7 (programmable logic: PROM, PAL, PLA); Wakerly, 5th ed., §5.3.

← Question 2 Next: Question 4 →

\(X\)	\(Y\)	\(Z\)	\(A\)	\(B\)	\(C\)	\(D\)
0	0	0	0	1	1	0
0	0	1	1	0	0	0
0	1	0	0	0	1	1
0	1	1	1	1	1	1
1	0	0	1	0	1	1
1	0	1	0	1	0	1
1	1	0	0	1	1	0
1	1	1	1	1	0	1

Output	Minimum SoP	Products
\(A\)	\(\overline{X}Z + YZ + X\overline{Y}\,\overline{Z}\)	3
\(B\)	\(\overline{X}\,\overline{Y}\,\overline{Z} + XY + XZ + YZ\)	4
\(C\)	\(\overline{Z} + \overline{X}Y\)	2
\(D\)	\(\overline{X}Y + X\overline{Y} + YZ\)	3
Term instances / distinct terms		12 / 9
Choice		PLA (9 AND rows vs 16 for a PAL)