Question 2 of 6: Multiplexer and decoder realisations (12 marks)

Question 2: Multiplexer and decoder realisations (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. Two three-variable functions for parts (a) and (b): $f_1 = \sum m(1,4,6)$ with don't-cares at $ABC = 011$ and $111$ (that is, $d(3,7)$), and $f_2 = \prod M(0,1,2,5)$. Three further functions for part (c), specified in mixed notation. In every part A is the most significant variable.

Find. An 8:1 multiplexer realisation of $f_1$ and $f_2$; a 4:1 multiplexer realisation of each; and a single 3:8 decoder feeding three OR gates that produces all three part-(c) functions simultaneously, with every decoder input specified.

Approach. Convert every function to a common minterm list first. An 8:1 multiplexer with the three variables on its select lines is then a direct read-out of the truth table, a 4:1 multiplexer requires collapsing the table in pairs to residues in the left-over variable, and a decoder plus OR gates is a canonical sum-of-minterms realisation.

1. Put both part-(a) functions on a common footing. The maxterm form is converted by complementing the index set: a function given as $\prod M(\cdot)$ is 0 at exactly those indices, so $$f_2 = \prod M(0,1,2,5) = \sum m(3,4,6,7)$$ while $f_1 = \sum m(1,4,6)$ with $d(3,7)$ is already in minterm form.

(a) 8:1 multiplexer realisation (4 marks)

With A, B, C driving the three select inputs ($A$ most significant), data input $I_i$ is selected exactly when the input combination is minterm i. Each data input is therefore tied directly to the function's value at that minterm — logic 0, logic 1, or left as a don't-care that may be tied either way.

For $f_1$, inputs $I_3$ and $I_7$ are the don't-cares; tying both to 0 gives the smallest wiring, and tying them to 1 is equally valid. No external gates are required for either function.

(b) 4:1 multiplexer realisation (4 marks)

1. Choose the select variables and form the residues. Put A and B on the two select lines and leave C as the data variable. Each select combination now addresses a pair of minterms, and the data input must equal the function restricted to that pair, expressed in C: $$I_{AB} = f(A,B,C)\big|_{A,B \text{ fixed}} \in \{0,\;1,\;C,\;\overline{C}\}$$
2. Reduce $f_1$ pair by pair. For $AB = 00$ the pair is $(m_0, m_1) = (0, 1)$, which is C. For $AB = 01$ it is $(m_2, m_3) = (0, \times)$; taking the don't-care as 0 gives the constant 0. For $AB = 10$ it is $(m_4, m_5) = (1, 0)$, which is $\overline{C}$. For $AB = 11$ it is $(m_6, m_7) = (1, \times)$; taking the don't-care as 1 gives the constant 1. Hence $$f_1:\quad \boxed{I_0 = C,\; I_1 = 0,\; I_2 = \overline{C},\; I_3 = 1}$$
3. Reduce $f_2$ the same way. With no don't-cares the pairs are $(m_0,m_1) = (0,0)$, $(m_2,m_3) = (0,1)$, $(m_4,m_5) = (1,0)$ and $(m_6,m_7) = (1,1)$, giving $$f_2:\quad \boxed{I_0 = 0,\; I_1 = C,\; I_2 = \overline{C},\; I_3 = 1}$$

Only one inverter is needed in each circuit, to generate $\overline{C}$; both functions happen to require it, so a single inverter can be shared if the two multiplexers sit on the same chip.

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

1. Specify the decoder inputs. The decoder's three address inputs take the three variables directly, most significant first: $$A_2 = A,\qquad A_1 = B,\qquad A_0 = C$$ An active-high 3:8 decoder then asserts output $D_i$ exactly when the input combination is minterm i, so $D_i \equiv m_i$ and any function can be formed by ORing its minterms.
2. Convert each function to a minterm list. For the first, De Morgan gives $\overline{B + C} = \overline{B}\,\overline{C}$, so $$f_1 = A\overline{B}\,\overline{C} = m_4$$ The second is already in minterm form, $f_2 = \sum m(0,3,4)$. For the third, $ABC = m_7$, and $B\overline{C}$ covers both $\overline{A}B\overline{C} = m_2$ and $AB\overline{C} = m_6$, so $$f_3 = \sum m(2,6,7)$$
3. Wire the OR gates. Collecting the three lists, $$\boxed{f_1 = D_4}\qquad \boxed{f_2 = D_0 + D_3 + D_4}\qquad \boxed{f_3 = D_2 + D_6 + D_7}$$ Six of the eight decoder outputs are used; $D_1$ and $D_5$ are left unconnected. Output $D_4$ is the only one that feeds two gates, because $m_4$ belongs to both $f_1$ and $f_2$ — the decoder's fan-out is what makes sharing free here.

Strictly, $f_1$ needs no OR gate at all, since it is a single minterm and could be taken straight off $D_4$. The question asks for three OR gates, so the gate is shown with its single input connected; in a real design it would be replaced by a direct wire or a buffer. Had the decoder been the more common active-low type, each OR gate would be replaced by a NAND gate, since $\overline{\overline{m_i} \cdot \overline{m_j}} = m_i + m_j$.