By the end of this chapter you should be able to:
- Write the Boolean expression of a \(2^n\)-to-1 multiplexer and relate each product term to one row of the select truth table.
- Assemble a larger multiplexer from smaller modules, either by tree cascading or by using the enable inputs, and count the modules required.
- Explain why a demultiplexer and a decoder with an enable input are the same circuit, and read one data sheet as both.
- Implement any function of \(n\) variables on a \(2^{n-1}\)-line multiplexer by applying one variable to the data inputs, and construct the data-input table.
- Extend the method so that two variables remain, and derive the residue function needed on each data input.
- Compare a multiplexer-based implementation with a minimised gate-level one on gate count, package count and propagation delay.
- Describe parallel-to-serial conversion, function generation and bus multiplexing as applications of the same block.
Every datapath eventually has to answer the same question: of several sources of information arriving at once, which one should be allowed through? A processor register file has to present one of thirty-two registers to the adder; an instrument has to send eight sensor channels down one wire; a display controller has to pick between the counter it is timing and the memory it is reading. Building a separate signal path for each source and switching it with discrete gates works, but it is wasteful, and the same pattern of gates recurs so often that it is worth naming.
That pattern is the multiplexer, and its inverse is the demultiplexer. Both are built from the AND, OR and NOT gates of Part 2 and neither introduces any new idea about logic. What makes them worth a chapter is the second thing a multiplexer turns out to do. Because a \(2^n\)-to-1 multiplexer selects one of \(2^n\) data values according to the value of \(n\) variables, it is already a device that evaluates an arbitrary function of those \(n\) variables — a truth table cast in silicon. With one extra trick it will handle \(n+1\) variables, and this chapter shows how, together with what the technique costs in gates compared with the K-map minimisation of Chapter 8.
1 What a Multiplexer Does
A multiplexer, or data selector, has \(2^n\) data inputs, \(n\) select inputs and a single output. The binary number applied to the select inputs is read as an address, and the data input at that address is copied to the output; the other \(2^n - 1\) are ignored. It is a rotary switch whose position is set electrically rather than by hand, and like a rotary switch it does nothing to the data.
Take the 4-to-1 multiplexer, with data inputs \(I_0\) to \(I_3\) and select inputs \(S_1\) and \(S_0\). Its behaviour is one line of English — \(Y = I_k\) where \(k\) is the number \(S_1S_0\) — and that translates into a sum of four products, one per select combination:
Each product contains one minterm of the select variables as an enabling condition and one data input as the quantity being passed. Only one minterm is 1 at a time, so only one product can be non-zero, and the OR gate simply collects whichever one that is.
The general form follows the same pattern. For \(n\) select variables \(S_{n-1} \dots S_0\),
where \(m_k\) is the \(k\)th minterm of the select variables. This is a two-level AND–OR circuit of exactly the kind Chapter 7 produced from a canonical sum, so a multiplexer costs \(2^n\) AND gates of \(n+1\) inputs, one OR gate of \(2^n\) inputs and \(n\) inverters. An 8-to-1 multiplexer is therefore twelve gates, and a 16-to-1 multiplexer twenty-one — which is why they are bought as single packages rather than built.
| \(E\) | \(S_1\) | \(S_0\) | Output \(Y\) | Product term enabled |
|---|---|---|---|---|
| 1 | × | × | 0 | none — device disabled |
| 0 | 0 | 0 | \(I_0\) | \(S_1'S_0'\) |
| 0 | 0 | 1 | \(I_1\) | \(S_1'S_0\) |
| 0 | 1 | 0 | \(I_2\) | \(S_1S_0'\) |
| 0 | 1 | 1 | \(I_3\) | \(S_1S_0\) |
The enable input \(E\) in the first column is worth dwelling on, because it is what makes multiplexers cascadable. It is usually active-low, written \(\overline{E}\) and drawn with a bubble, and it is ANDed into every product term, so a disabled multiplexer holds its output at 0 whatever the select lines do. The commercial parts follow this scheme: the 74151 is an 8-to-1 multiplexer with an active-low enable and both \(Y\) and \(\overline{Y}\) brought out, the 74153 is a dual 4-to-1 with separate enables and shared select lines, and the 74157 is a quad 2-to-1 used for choosing between two four-bit buses.
Notice from Figure 19.1 that the delay from a data input to the output is two gate levels regardless of \(n\), while the delay from a select input is three, because a select change must first pass through an inverter. Data sheets quote the two separately, and it is usually the select path that sets the limit.
2 Building a Larger Multiplexer from Smaller Ones
Catalogue multiplexers stop at sixteen inputs, so any wider selection has to be assembled. There are two ways of doing it, and they differ in which part of the select word is used where.
The tree method splits the select word. To make a 16-to-1 multiplexer from 4-to-1 modules, group the sixteen inputs into four blocks of four. Four modules in the first rank each reduce one block to a single line, all four driven by the two least significant select bits \(S_1S_0\), which pick the same position within every block. A fifth module in the second rank then chooses between those four lines using the two most significant bits \(S_3S_2\), which say which block was wanted. The two halves of the address are decoded in sequence, exactly as a street name and a house number are.
Counting modules is a matter of counting the lines that have to be reduced. A rank of \(2^k\)-to-1 modules replaces \(2^k\) lines by one, removing \(2^k - 1\) lines each time; reducing \(2^n\) lines to one therefore needs
modules, provided the division is exact — that is, provided \(k\) divides \(n\). For \(n = 4\), \(k = 2\) this gives \(15/3 = 5\) modules in two ranks, and for a 64-to-1 selector from 8-to-1 parts it gives \(63/7 = 9\) modules, again in two ranks.
The enable method keeps all the modules in one rank and uses a decoder instead of a second-rank multiplexer. Each 4-to-1 module receives the low select bits, and the high bits drive a 2-to-4 decoder whose four outputs are the four enables, so exactly one module is awake at any moment. The outputs of the sleeping modules are 0, so a single OR gate — or, in a real board, a common wire if the outputs are open-collector or tri-state — combines them. This costs a decoder and an OR gate rather than a fifth multiplexer, and it has the practical advantage that the shared output node can be driven straight onto a bus.
Thirty-two inputs need five select lines, \(S_4 \dots S_0\). An 8-to-1 module absorbs three of them, so group the inputs into four blocks of eight and give every module the same \(S_2S_1S_0\). Four modules produce four candidate lines, and \(S_4S_3\) must now choose between them.
The formula \(N = (2^5-1)/(2^3-1) = 31/7\) is not an integer, which is the arithmetic saying that the second rank cannot be another 8-to-1 module: three of its inputs would be wasted. Use a 4-to-1 module instead, giving four 8-to-1 parts plus one 4-to-1 part, five packages in two ranks. The alternative is four 8-to-1 modules, a 2-to-4 decoder on \(S_4S_3\) feeding their enables, and a four-input OR gate, which is six packages but keeps the propagation delay to one multiplexer plus one gate rather than two multiplexers.
Delay is why the tree does not scale indefinitely: each rank adds a full multiplexer delay, so a 256-to-1 selector built from 4-to-1 modules is four ranks deep and four times slower than a single part would be. Wide selection at speed is done instead with tri-state buffers on a common bus, as the last section of this chapter describes.
3 The Demultiplexer and Its Identity with the Decoder
A demultiplexer reverses the traffic. It has one data input, \(n\) select inputs and \(2^n\) outputs, and it routes the data to the one output the select word names, holding the rest inactive. If a multiplexer is a many-to-one funnel, a demultiplexer is a one-to-many distributor, and the pair is what allows several signals to share one physical line.
The equations of a 1-to-4 demultiplexer with data input \(D\) are as short as the multiplexer's:
The same four minterms of the select variables appear, but now each one gates \(D\) onto its own output instead of gating its own input onto a shared output. The circuit is four three-input AND gates and two inverters — eleven gates for a 1-to-8 part.
Write those four equations again with \(D\) renamed \(E\) and something becomes obvious. A 2-to-4 decoder with an enable input has outputs \(Y_k = m_k(S_1,S_0)\cdot E\): the very same expressions. A demultiplexer and a decoder with an enable input are one circuit with two names, the difference being only which pin you decide to call the data and which the address. This is not a curiosity of textbook presentation but how the parts are actually sold: the 74138 is labelled a 3-to-8 line decoder/demultiplexer, and the 74154 a 4-to-16 line decoder/demultiplexer, because the manufacturer will not commit to either reading.
Both compute \(Y_k = m_k(\text{select})\cdot(\text{enable})\). Call the enable pin enable and the block decodes an address; call it data and the block distributes a signal. Chapter 18 designed the decoder; nothing new has to be designed here.
The complementary pair is used for time-division multiplexing. Put an 8-to-1 multiplexer at one end of a cable and a 1-to-8 demultiplexer at the other, drive both select inputs from the same three-bit counter, and eight channels travel down one wire in rotation, each reappearing on its own output at the far end. The cost of the saving is bandwidth and synchronism: the line must carry eight times the data rate of one channel, and if the two counters ever disagree by one count every channel is delivered to the wrong destination. Recovering the count at the receiver is the framing problem, and it is why real serial links spend bits on synchronisation patterns.
One point matters in the laboratory: the unselected outputs of a demultiplexer are not floating but actively held at their inactive level, usually HIGH on the active-low outputs of a 74138. Probing one and finding a solid logic 1 is not a fault.
4 Implementing an n-Variable Function on a 2^(n-1)-Line Multiplexer
The direct way of using a multiplexer as a function generator is to give it one select line per variable. A function of four variables goes on a 16-to-1 multiplexer with \(A,B,C,D\) on the select inputs and the sixteen entries of the truth table's output column wired to the sixteen data inputs as constant 0 or 1. It works, it needs no thought at all, and it is extravagant: a 16-to-1 package to implement what four gates might do.
The improvement halves the multiplexer. Put only \(A,B,C\) on the select lines of an 8-to-1 part. Each select combination now addresses one data input but corresponds to two rows of the truth table, the pair sharing those values of \(A,B,C\) and differing in \(D\). Whatever is wired to that input is passed straight through, so it must equal \(F\) on both rows — and only four signals can do that: \(0\), \(1\), \(D\) and \(D'\).
Formally this is Shannon's expansion of \(F\) about the select variables, carried out one step short of the end:
Comparing this with the multiplexer equation \(Y = \sum m_k(S) I_k\) shows that the two are the same statement, with \(I_k = f_k(D)\). The residue \(f_k\) is read straight off the pair of truth-table rows: both 0 gives \(I_k = 0\), both 1 gives 1, \(0\) then \(1\) gives \(D\), and \(1\) then \(0\) gives \(D'\).
In practice the truth table is not even written out. List the minterms in two rows, the upper row holding the minterms with \(D = 0\) and the lower those with \(D = 1\), one column per data input; ring the minterms that are present in the function; and read each column.
Apply \(A,B,C\) to \(S_2S_1S_0\), with \(A\) as the most significant, and leave \(D\) as the data variable. Data input \(I_k\) is addressed by the select word \(ABC = k\), which covers minterms \(2k\) (for \(D=0\)) and \(2k+1\) (for \(D=1\)).
| Data input | \(I_0\) | \(I_1\) | \(I_2\) | \(I_3\) | \(I_4\) | \(I_5\) | \(I_6\) | \(I_7\) |
|---|---|---|---|---|---|---|---|---|
| \(D=0\): minterm | 0 | 2 | 4 | 6 | 8 | 10 | 12 | 14 |
| \(F\) there | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
| \(D=1\): minterm | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 |
| \(F\) there | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| Wire \(I_k\) to | 1 | \(D\) | \(D'\) | 0 | 1 | 0 | 0 | \(D\) |
Column \(I_0\) covers minterms 0 and 1, both present, so \(I_0 = 1\). Column \(I_1\) covers 2 and 3; only 3 is present, and 3 is the \(D = 1\) member, so \(I_1 = D\). Column \(I_2\) covers 4 and 5; only 4 is present, the \(D = 0\) member, so \(I_2 = D'\). Column \(I_3\) covers 6 and 7, neither present, so \(I_3 = 0\). The remaining columns follow in the same way.
The finished circuit is one 74151 and one inverter, wired as in Figure 19.3. Verifying it is a matter of walking the eight columns: for \(ABCD = 0011\) the select word is 001, so \(Y = I_1 = D = 1\), and \(m_3\) is indeed in the list; for \(ABCD = 0111\) the select word is 011, so \(Y = I_3 = 0\), and \(m_7\) is indeed absent.
Two points of procedure. The assignment of variables to select lines is a decision, not a rule: \(A\) is put on \(S_2\) only because that keeps the minterm numbering natural, and a different choice gives a different — sometimes simpler — table. And a don't-care in the function becomes a don't-care in its column, so a column holding one 1 and one \(\times\) may be wired to 1.
5 Holding Back Two Variables: the n−2 Select-Line Method
Nothing stops the same argument being taken one step further. Put only \(n-2\) variables on the select lines, and each data input is addressed by a select combination that now covers four rows of the truth table — the four that share those select values and differ in the two variables held back. The signal wired to that data input must equal \(F\) over all four, so it is a function of two variables, and there are sixteen of those rather than four.
The residue on each input can therefore be any of \(0\), \(1\), \(C\), \(C'\), \(D\), \(D'\), \(CD\), \(C+D\), \(C \oplus D\), \((C \oplus D)'\) and the rest. The constants and single literals cost nothing; the others cost a gate each. The method pays when most columns come out as constants or single literals and only one or two need a gate.
The procedure is unchanged in shape. Divide the sixteen minterms into four groups of four, one per select combination; write out the four-row residue truth table for each group in terms of the two remaining variables; and minimise each residue with a two-variable K-map, which takes a moment because it has only four cells.
Apply \(A,B\) to \(S_1S_0\) and hold back \(C\) and \(D\). Data input \(I_k\) is addressed by \(AB = k\) and covers minterms \(4k\) to \(4k+3\).
| \(AB\) | Minterms covered | \(F\) for \(CD = 00,01,10,11\) | Residue \(I_k\) | Extra gate |
|---|---|---|---|---|
| 00 → \(I_0\) | 0, 1, 2, 3 | 1, 0, 0, 1 | \((C \oplus D)'\) | one XNOR |
| 01 → \(I_1\) | 4, 5, 6, 7 | 0, 0, 0, 0 | \(0\) | none |
| 10 → \(I_2\) | 8, 9, 10, 11 | 1, 1, 1, 1 | \(1\) | none |
| 11 → \(I_3\) | 12, 13, 14, 15 | 0, 1, 1, 1 | \(C + D\) | one OR |
Reading the third column: for \(AB = 00\) the function is 1 when \(CD = 00\) and when \(CD = 11\), which is the pattern of the exclusive-NOR, so \(I_0 = (C \oplus D)'\). For \(AB = 01\) no minterm is present and \(I_1 = 0\); for \(AB = 10\) all four are present and \(I_2 = 1\); for \(AB = 11\) the function is 0 only at \(CD = 00\), so \(I_3 = C + D\).
The circuit is one 4-to-1 multiplexer, one XNOR gate and one OR gate: three packages, or three gate equivalents beyond the multiplexer itself. Checking one line, \(ABCD = 1100\) gives select 11 and \(I_3 = C + D = 0\), so \(F = 0\) and \(m_{12}\) is correctly absent.
The general statement is worth remembering: a \(2^{n-k}\)-to-1 multiplexer implements any \(n\)-variable function if you are willing to build residues of \(k\) variables on its data inputs. With \(k = 0\) the residues are constants and the multiplexer does everything; with \(k = 1\) they are \(0\), \(1\), \(x\) or \(x'\) and cost at most one inverter; with \(k = 2\) they may need a gate apiece. Beyond \(k = 2\) the external logic has grown to the point where the multiplexer is no longer earning its place, and you may as well minimise the whole function on a K-map.
6 Multiplexer Implementation Compared with Gate-Level Design
Having two methods for the same job invites the question of which is cheaper. The honest answer is that it depends on what you are counting, and the two examples already worked make the comparison concrete.
For \(F = \Sigma m(0,1,3,4,8,9,15)\) of Example 19.2, the K-map of Chapter 8 gives the minimal sum
Four product terms of two, three, three and four literals: twelve literals in all. Built directly that is four AND gates, one four-input OR gate and four inverters for \(A', B', C', D'\) — nine gates, spread over three or four 74-series packages. The multiplexer version is one 74151 and one inverter, so it wins on packages by roughly three to one, on wiring by far more, and on design effort completely, since no minimisation was performed at all.
For \(F = \Sigma m(0,3,8,9,10,11,13,14,15)\) of Example 19.3 the minimal sum is
Ten literals: four AND gates, one four-input OR gate and three inverters, eight gates in all. The multiplexer version is a 4-to-1 part plus an XNOR and an OR, which is three packages against three or four — a much narrower margin, because holding two variables back put gates outside the multiplexer again.
Three further considerations decide real cases.
- Predictability. The multiplexer cost depends only on the number of variables, never on which minterms are present. A function of four variables always fits one 74151 and an inverter, whether it has two minterms or fourteen. Gate-level cost, by contrast, varies from one gate to a dozen, and cannot be known until the minimisation is done.
- Change. Rewiring eight data pins is far easier than reworking a gate network, so a design still being modified is much better off on a multiplexer — the same argument Chapter 28 makes at a larger scale for programmable logic.
- Speed and loading. A multiplexer is two or three gate levels from any input to the output, which is the same as a minimised two-level network plus its inverters. There is no speed penalty, but there is a fan-out one: the data variable \(D\) may have to drive several data pins at once.
A single four- or five-variable function is almost always cheaper on a multiplexer. But a multiplexer produces one output, so a block with six outputs needs six of them, whereas a gate-level design can share product terms between outputs — the multiple-output minimisation that Chapter 9 sets up. Count outputs before choosing.
7 Applications: Serialisation, Function Generation and Bus Multiplexing
Parallel-to-serial conversion. Connect the \(n\) select inputs of a \(2^n\)-to-1 multiplexer to a modulo-\(2^n\) counter and the data inputs to the bits of a parallel word. The counter walks the select word through 0 to \(2^n-1\), and the output presents the bits of the word one at a time, most or least significant first depending on how the counter is wired. With an 8-to-1 multiplexer and a counter clocked at 1 MHz each bit occupies 1 µs, a whole word takes 8 µs, and words are delivered at 125 kHz. This is the cheapest serialiser there is, and its limitation is that the parallel word must be held steady for the whole eight clocks; a shift register, which is Chapter 25, captures the word once and then frees the source.
Time-division multiplexing. The same arrangement with a demultiplexer and a matching counter at the far end shares one line between several channels. Four analogue channels each sampled at 8 kHz require the multiplexer to switch at 32 kHz, giving each channel a 31.25 µs time slot. The design questions are all about the slot: it must be long enough for the line to settle and for the receiving circuit to capture the value, and the two counters must be kept in step.
Function generation. This is the use developed in the two preceding sections, and it reappears throughout the rest of the course. A multiplexer with its data inputs tied to fixed levels is a small read-only memory, and the look-up table of an FPGA is literally a small multiplexer whose data inputs are held in configuration cells. Implementing a four-variable function on a 16-to-1 multiplexer is what an FPGA synthesiser does automatically several thousand times, as Chapter 28 explains.
Bus multiplexing and operand selection. Inside a processor, the input of the arithmetic unit must be able to come from any of several registers. Four-bit-wide selection is done with four multiplexers sharing one set of select lines, which is exactly the 74157 quad 2-to-1 or the 74153 dual 4-to-1 in pairs; Chapter 20 uses precisely this arrangement to choose which operation an arithmetic logic unit performs. For wider buses with many sources, the multiplexer is usually replaced by tri-state buffers: each source drives the shared bus through a buffer whose enable comes from a decoder, so the selection network is distributed along the bus instead of being concentrated in one package. The logic is the same — a decoder choosing one of many — but no signal has to be routed to a central point, which on a printed circuit board matters more than gate count.
Data sheets also list analogue multiplexers such as the 4051. They close a CMOS transmission gate between the selected pin and the common pin, so the path is bidirectional and passes a continuous voltage, whereas a logic multiplexer regenerates a two-valued signal and passes it one way only. Connecting a sensor output to a 74151 will not multiplex it — it will threshold it.
8 Summary and Key Results
| Item | Statement | Consequence |
|---|---|---|
| \(2^n\)-to-1 multiplexer | \(Y = \sum_k m_k(S)\,I_k\); \(2^n\) AND gates of \(n+1\) inputs, one OR, \(n\) inverters | Two gate levels from data to output, three from a select input |
| Enable input | ANDed into every product term, so a disabled part outputs 0 | Allows several modules to share one output node when cascading |
| Cascading by tree | \(N = (2^n-1)/(2^k-1)\) modules of size \(2^k\), when \(k\) divides \(n\) | 16-to-1 from 4-to-1 needs 5 modules; 64-to-1 from 8-to-1 needs 9 |
| Demultiplexer | \(Y_k = m_k(S)\cdot D\) — identical to a decoder with enable \(D\) | One part, sold as a decoder/demultiplexer; nothing new to design |
| \(n-1\) select lines | Each data input covers two truth-table rows, so \(I_k \in \{0,1,x,x'\}\) | Any \(n\)-variable function on a \(2^{n-1}\)-to-1 part plus one inverter |
| \(n-2\) select lines | Each data input covers four rows, so \(I_k\) is a function of two variables | Halves the multiplexer again, at the price of a gate on some inputs |
| Multiplexer versus gates | Cost depends on the number of variables, not on which minterms are present | Cheap and predictable for one output; poor value for many outputs |
9 Common Mistakes
In the \(n-1\) method the column for \(I_k\) covers minterms \(2k\) and \(2k+1\) when the held-back variable is the least significant. If the upper minterm alone is present the input is \(x'\), not \(x\), because the upper minterm is the one with \(x = 0\). Getting this the wrong way round complements every affected input and produces a circuit that is wrong on exactly half the rows. Write the two minterm numbers above each column and mark which of them has \(x = 0\) before reading anything off.
Any variable may be applied to the data inputs, and the remaining ones may be assigned to the select lines in any order. Different choices give different data-input tables, and in the \(n-2\) method a good choice can turn a residue that needs a gate into a constant. What is not permitted is being inconsistent: once you have decided that \(A\) drives \(S_2\), every column of the table must be numbered on that basis.
They are driven, not floating. On a 74138 the seven unselected outputs sit at logic 1 and can sink or source current exactly as an active output can. Wiring several demultiplexer outputs together in the hope that only the selected one will matter creates a contention between totem-pole outputs of the kind Chapter 13 warns about. Combine them with a gate, or use open-collector or tri-state parts.
10 Chapter Review
1. Write the output expression of an 8-to-1 multiplexer with an active-low enable \(\overline{E}\), and state how many gates of what size the circuit contains.
With select inputs \(S_2S_1S_0\) and data inputs \(I_0\) to \(I_7\), \(Y = \overline{E}'\sum_{k=0}^{7} m_k(S_2,S_1,S_0)I_k\), or written out, \(Y = E'(S_2'S_1'S_0'I_0 + S_2'S_1'S_0I_1 + \dots + S_2S_1S_0I_7)\) where \(E'\) denotes the enable being active. Each product needs the three select literals, the data input and the enable, so the circuit is eight five-input AND gates, one eight-input OR gate and three inverters for the select complements: twelve gates. Without the enable the AND gates would have four inputs each.
2. How many 4-to-1 multiplexer modules are needed to build a 64-to-1 multiplexer as a tree, and how many ranks deep is it? Compare the delay with a build from 8-to-1 modules.
Each 4-to-1 module absorbs two select bits, and 64-to-1 needs six, so the tree is \(6/2 = 3\) ranks deep. The module count is \((2^6-1)/(2^2-1) = 63/3 = 21\): sixteen in the first rank, four in the second and one in the third. Built from 8-to-1 modules the tree is \(6/3 = 2\) ranks deep and needs \((2^6-1)/(2^3-1) = 63/7 = 9\) modules. The 8-to-1 version is both smaller and faster, because each rank costs a full multiplexer delay: three delays against two. The general lesson is to use the largest module available, since the rank count is \(n/k\).
3. Implement \(F(A,B,C,D) = \Sigma m(1,2,5,7,8,10,11,14)\) on an 8-to-1 multiplexer, with \(A,B,C\) on the select inputs and \(D\) held back. Give the data-input table.
Data input \(I_k\) covers minterms \(2k\) (with \(D=0\)) and \(2k+1\) (with \(D=1\)). Taking the columns in turn: \(I_0\) covers 0 and 1 — only 1 present, the \(D=1\) member, so \(I_0 = D\). \(I_1\) covers 2 and 3 — only 2 present, so \(I_1 = D'\). \(I_2\) covers 4 and 5 — only 5 present, so \(I_2 = D\). \(I_3\) covers 6 and 7 — only 7 present, so \(I_3 = D\). \(I_4\) covers 8 and 9 — only 8 present, so \(I_4 = D'\). \(I_5\) covers 10 and 11 — both present, so \(I_5 = 1\). \(I_6\) covers 12 and 13 — neither present, so \(I_6 = 0\). \(I_7\) covers 14 and 15 — only 14 present, so \(I_7 = D'\). The circuit is one 8-to-1 multiplexer and one inverter. Check: \(ABCD = 1011\) selects \(I_5 = 1\), and \(m_{11}\) is in the list; \(ABCD = 1100\) selects \(I_6 = 0\), and \(m_{12}\) is not.
4. Show that a 1-to-4 demultiplexer and a 2-to-4 decoder with an enable input are the same circuit, and explain why a 74138 can be sold as either.
The demultiplexer with data \(D\) and select \(S_1S_0\) produces \(Y_0 = S_1'S_0'D\), \(Y_1 = S_1'S_0D\), \(Y_2 = S_1S_0'D\), \(Y_3 = S_1S_0D\). The decoder with inputs \(S_1S_0\) and enable \(E\) produces \(Y_k = m_k(S_1,S_0)\cdot E\), which is the same set of four expressions with \(D\) renamed \(E\). Since the equations are identical, so is the gate network — four three-input ANDs and two inverters. The 74138 is a 3-to-8 version of this: apply an address to its three select pins and hold the enable active and it decodes; apply a data stream to the enable and it distributes that stream to whichever output the address names. Nothing inside the package changes; only the designer's intention does.
5. A four-variable function is to be implemented on a 4-to-1 multiplexer with \(A,B\) on the select lines. The four groups of minterms give residues \(1\), \(C'\), \(CD\) and \(0\). Write the function as a sum of minterms and count the gates the multiplexer implementation needs.
Group \(AB=00\) covers minterms 0–3 with residue 1, so all four are present: 0, 1, 2, 3. Group \(AB=01\) covers 4–7 with residue \(C'\), which is true for \(CD = 00\) and \(CD = 01\), giving minterms 4 and 5. Group \(AB=10\) covers 8–11 with residue \(CD\), true only for \(CD = 11\), giving minterm 11. Group \(AB=11\) covers 12–15 with residue 0, contributing nothing. Hence \(F = \Sigma m(0,1,2,3,4,5,11)\). The implementation is one 4-to-1 multiplexer, one inverter for \(C'\) and one two-input AND gate for \(CD\) — the constants 1 and 0 are wired to the supply and ground rails and cost nothing. That is two gates outside the multiplexer, against the gate-level minimum \(F = A'B' + A'C' + B'CD\), which needs three AND gates, a three-input OR gate and inverters for \(A'\), \(B'\) and \(C'\): seven gates.