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

Question 2 of 6: Multiplexer and Decoder Implementations

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 2: Multiplexer and Decoder Implementations (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. Three-variable functions with $A$ the most significant variable:

Function	Specification	Minterms where the function is 1
$f_1$ (parts a, b)	$\sum m_i(0,5,6,7)$	0, 5, 6, 7
$f_2$ (parts a, b)	$\prod M_i(0,3,6)$ with $d(4,7)$	1, 2, 5 (4 and 7 are don't cares)
$f_1$ (part c)	$\sum m_i(5,6,7)$	5, 6, 7
$f_2$ (part c)	$\overline{A}(B+\overline{C})$	0, 2, 3
$f_3$ (part c)	$\overline{A}C + A\overline{B}\,\overline{C}$	1, 3, 4

Find. The data-input pattern for an 8:1 multiplexer, the residue functions for a 4:1 multiplexer, and the decoder-output-to-OR-gate wiring, in each case with every input explicitly specified.

Approach. An $n$-select multiplexer is a direct hardware realisation of the canonical minterm expansion, so with all three variables on the selects the truth-table column is the answer; dropping to two selects forces the third variable into the data inputs as a per-pair residue. A decoder plus OR gates is the same idea split across two chips: the decoder generates every minterm and the OR gate sums the ones the function needs.

(a) 8:1 multiplexers (4 marks)

Resolve the specification of $f_2$ first. The maxterm list makes $f_2=0$ at 0, 3 and 6, so $f_2=1$ at 1, 2, 4, 5 and 7 — but 4 and 7 are then declared don't cares, which removes them from both lists. The care-set is therefore $f_2 = \sum m_i(1,2,5) + d(4,7)$.
Apply the selects and read off the data inputs. With $S_2S_1S_0 = ABC$, data input $I_k$ is steered to the output exactly when $ABC$ equals the binary value of $k$, so $I_k = f(m_k)$. No design work is needed at all — the truth-table column is the programming: $$f_1:\ I_0\ldots I_7 = 1,0,0,0,0,1,1,1 \qquad f_2:\ I_0\ldots I_7 = 0,1,1,0,\text{X},1,0,\text{X}$$ where X may be tied to either logic level; tying a don't care to ground is usual so that an unintended selection produces a defined, quiet output.

Figure 2.1 — $f_1$ on an 8:1 multiplexer. Because all three variables drive the selects, the eight data inputs are literally the truth-table column of $f_1$.

Figure 2.2 — $f_2$ on an 8:1 multiplexer. $I_4$ and $I_7$ are the two don't-care combinations and may be tied high or low.

(b) 4:1 multiplexers (4 marks)

Choose the select variables and form the residues. Put $A$ and $B$ on $S_1S_0$ and let $C$ become a data-input variable. Each of the four select codes selects one data input, which must then supply the function's behaviour over the pair of minterms sharing that $AB$ value. Comparing $f(AB0)$ with $f(AB1)$ gives one of only four possible residues: $0$, $1$, $C$ or $\overline{C}$.
Tabulate $f_1$. For $AB=00$ the pair $(m_0,m_1)=(1,0)$, which is $\overline{C}$; $AB=01$ gives $(m_2,m_3)=(0,0)=0$; $AB=10$ gives $(m_4,m_5)=(0,1)=C$; $AB=11$ gives $(m_6,m_7)=(1,1)=1$: $$\boxed{\,f_1:\ I_0=\overline{C},\ I_1=0,\ I_2=C,\ I_3=1\,}$$
Tabulate $f_2$, using the don't cares to simplify. $AB=00$ gives $(0,1)=C$ and $AB=01$ gives $(1,0)=\overline{C}$. For $AB=10$ the pair is $(\text{X},1)$: taking the don't care $m_4=1$ makes the residue the constant 1 rather than $C$, saving an input connection. For $AB=11$ the pair is $(0,\text{X})$: taking $m_7=0$ makes it the constant 0. Hence $$\boxed{\,f_2:\ I_0=C,\ I_1=\overline{C},\ I_2=1,\ I_3=0\,}$$ Both choices are legitimate precisely because the exam declared those combinations to be of no concern; a different assignment would give $I_2=C$ and $I_3=C$, which is also correct but needs two more connections to $C$.

Figure 2.3 — $f_1$ on a 4:1 multiplexer, with $C$ and $\overline{C}$ supplied as data.

Figure 2.4 — $f_2$ on a 4:1 multiplexer. Resolving the don't cares as $m_4=1$ and $m_7=0$ turns two of the four residues into constants.

(c) One 3:8 decoder and three OR gates (4 marks)

Specify the decoder inputs. The decoder inputs are the three function variables in significance order: $A \to S_2$, $B \to S_1$, $C \to S_0$. Output $D_k$ then asserts (active high) for exactly the input combination $ABC = k$, so $D_k = m_k$.
Expand each function into its minterm list. $f_1$ is already in minterm form. For $f_2 = \overline{A}(B+\overline{C}) = \overline{A}B + \overline{A}\,\overline{C}$: the first product covers $m_2,m_3$ and the second $m_0,m_2$, giving $\{0,2,3\}$. For $f_3 = \overline{A}C + A\overline{B}\,\overline{C}$: the first product covers $m_1,m_3$ and the second the single cell $m_4$, giving $\{1,3,4\}$.
Wire one OR gate per function. Each OR gate simply sums the decoder outputs named by that minterm list: $$\boxed{\,f_1 = D_5+D_6+D_7, \qquad f_2 = D_0+D_2+D_3, \qquad f_3 = D_1+D_3+D_4\,}$$ Every gate is a three-input OR, and $D_3$ fans out to two gates — the decoder generates each minterm once and it may be shared freely.

Figure 2.5 — one active-high 3-to-8 decoder driving three OR gates. A dot marks a connection; $D_3$ feeds both $f_2$ and $f_3$.

Part	Device	Programming
(a) i	8:1 MUX, selects $ABC$	$I_0\ldots I_7 = 1,0,0,0,0,1,1,1$
(a) ii	8:1 MUX, selects $ABC$	$I_0\ldots I_7 = 0,1,1,0,\text{X},1,0,\text{X}$
(b) $f_1$	4:1 MUX, selects $AB$	$I_0=\overline{C},\ I_1=0,\ I_2=C,\ I_3=1$
(b) $f_2$	4:1 MUX, selects $AB$	$I_0=C,\ I_1=\overline{C},\ I_2=1,\ I_3=0$
(c)	3:8 decoder, inputs $A\to S_2,\ B\to S_1,\ C\to S_0$	$f_1=D_5{+}D_6{+}D_7$; $f_2=D_0{+}D_2{+}D_3$; $f_3=D_1{+}D_3{+}D_4$

Topic. MSI realisation of combinational logic: multiplexers as universal function generators and decoders as minterm generators.

Key relations. A $2^n$:1 multiplexer with all $n$ variables on the selects realises any $n$-variable function with $I_k = f(m_k)$; with only $n-1$ variables on the selects the data inputs become residues drawn from $\{0,1,X_{n-1},\overline{X}_{n-1}\}$ (Shannon expansion $f = \overline{X}f|_{X=0} + Xf|_{X=1}$); an active-high $n$:$2^n$ decoder produces $D_k = m_k$, so $f = \sum_{k \in \text{on-set}} D_k$.

Why this works. All three implementations are the same identity dressed differently. The canonical sum-of-minterms says any function is the OR of the minterms in its on-set; a decoder builds all $2^n$ minterms and lets an OR gate pick, while a multiplexer builds the selection and the OR together, using the data input to say whether each minterm is wanted. Halving the select count folds the residual variable out of the selection tree and into the data path by Shannon expansion, which is why exactly four residues are possible — a one-variable function has only four values. The decoder approach shines when several functions of the same variables are needed at once, because the expensive part (minterm generation) is shared, which is the same economic argument that reappears in the PLA of Question 3.

Common pitfall. The single most common error here is mishandling the don't cares: a candidate converts $\prod M_i(0,3,6)$ to $\sum m_i(1,2,4,5,7)$ and then forgets to strike out 4 and 7, losing the free simplification in part (b). The second is inverting the select-order convention, wiring $A$ to $S_0$ instead of $S_2$, which permutes the data inputs and silently implements a different function. Finally, when the decoder is active low (as many 74-series parts are), the OR gates must be replaced by NAND gates — always state which polarity has been assumed.

Source. Mano & Ciletti, Digital Design, 6th ed., §4.9–4.11 (decoders, encoders, multiplexers and Boolean-function implementation); Wakerly, 5th ed., §6.1–6.2.

← Question 1 Next: Question 3 →

Function	Specification	Minterms where the function is 1
\(f_1\) (parts a, b)	\(\sum m_i(0,5,6,7)\)	0, 5, 6, 7
\(f_2\) (parts a, b)	\(\prod M_i(0,3,6)\) with \(d(4,7)\)	1, 2, 5 (4 and 7 are don't cares)
\(f_1\) (part c)	\(\sum m_i(5,6,7)\)	5, 6, 7
\(f_2\) (part c)	\(\overline{A}(B+\overline{C})\)	0, 2, 3
\(f_3\) (part c)	\(\overline{A}C + A\overline{B}\,\overline{C}\)	1, 3, 4

Part	Device	Programming
(a) i	8:1 MUX, selects \(ABC\)	\(I_0\ldots I_7 = 1,0,0,0,0,1,1,1\)
(a) ii	8:1 MUX, selects \(ABC\)	\(I_0\ldots I_7 = 0,1,1,0,\text{X},1,0,\text{X}\)
(b) \(f_1\)	4:1 MUX, selects \(AB\)	\(I_0=\overline{C},\ I_1=0,\ I_2=C,\ I_3=1\)
(b) \(f_2\)	4:1 MUX, selects \(AB\)	\(I_0=C,\ I_1=\overline{C},\ I_2=1,\ I_3=0\)
(c)	3:8 decoder, inputs \(A\to S_2,\ B\to S_1,\ C\to S_0\)	\(f_1=D_5{+}D_6{+}D_7\); \(f_2=D_0{+}D_2{+}D_3\); \(f_3=D_1{+}D_3{+}D_4\)