By the end of this chapter you should be able to:
- Derive the gate structure of an \(n\)-to-\(2^n\) decoder and explain why MSI decoders have active-low outputs.
- Use the enable input to cascade decoders into a wider one, and state how the polarity of the enables makes an inverter unnecessary.
- Implement any Boolean function of \(n\) variables with one decoder and one gate per output, and decide when that is cheaper than a gate network.
- State the two conditions under which a simple encoder gives a meaningless answer, and demonstrate each with an input pattern.
- Write the full truth table of an 8-to-3 priority encoder, derive its output equations and verify them.
- Produce the segment truth table of a BCD-to-seven-segment decoder and minimise a segment on a K-map using the six unused codes as don't-cares.
Digital systems keep two kinds of information side by side. Some things are naturally a code — an address, an instruction, a BCD digit — where \(n\) wires carry one of \(2^n\) meanings and every wire matters. Other things are naturally a selection: one chip out of sixteen is being addressed, one key out of eight has been pressed, one lamp is to be lit. A selection wants one wire per possibility, active on its own. Converting between the two representations is what this chapter is about.
Going from code to selection is decoding, and it is the easier direction, because every input code has exactly one meaning. Going the other way is encoding, and it is harder than it looks: the naive circuit misbehaves in two quite different ways, and repairing it produces the priority encoder, which is the part every interrupt controller is built around. The chapter ends with the decoder every laboratory bench has on it — the BCD-to-seven-segment driver — because it is the clearest example in the whole course of don't-care conditions paying for themselves.
1 The n-to-2ⁿ Decoder and the Active-Low Convention
A decoder has \(n\) inputs and \(2^n\) outputs, and it asserts exactly one output for each input combination. Since output \(i\) must be asserted for exactly one input code, output \(i\) is minterm \(m_i\) of the input variables, and the whole design is written down without any minimisation at all. For two inputs:
Four two-input AND gates and two inverters. In general an \(n\)-to-\(2^n\) decoder is \(2^n\) AND gates of \(n\) inputs each, plus \(n\) inverters — 8 gates for 3-to-8, 16 for 4-to-16, 32 for 5-to-32. The gate count doubles with each extra input, which is why decoders beyond five inputs are built by cascading rather than as one block.
Every real MSI decoder, however, gives active-low outputs: the selected line goes to 0 and the other \(2^n - 1\) stay at 1. Replace each AND by a NAND and the same circuit is obtained, as in Figure 18.1. There are three reasons, and they are worth knowing because the convention is not arbitrary.
- The TTL output stage of Chapter 13 sinks far more current than it sources — 16 mA against 400 µA for a standard gate — so a load driven to ground, such as a lamp, a relay driver or a memory chip's \(\overline{CS}\) pin, is better served by a LOW-active output.
- A NAND is the natural gate of the technology. Chapter 10 showed that AND costs a NAND plus an inverter, so active-low outputs are one gate per output cheaper.
- Active-low outputs combine with a single NAND, as Section 3 uses. Wiring several of them together on an open-collector part gives a wired-AND, which is the same thing again.
Two smaller variants recur often enough to have names. A BCD decoder, such as the 7442, is a 4-to-10 decoder: it accepts the ten valid BCD codes and drives ten outputs, and for the six invalid codes 1010 to 1111 it asserts no output at all. It is therefore not quite a 4-to-16 decoder with six pins missing — it also rejects the illegal codes, which is useful. A demultiplexer, the subject of Chapter 19, turns out to be a decoder in which the enable input carries data rather than a fixed level; the two functions are the same circuit used two ways.
2 Enable Inputs and Cascading
Every MSI decoder has one or more enable inputs, and Figure 18.1 shows the cheapest way to fit one: give every gate an extra input carrying \(E\). When \(E = 0\) every NAND has a zero in it, so every output sits at 1 and no line is selected. When \(E = 1\) the decoder behaves exactly as before.
The enable earns its cost twice over. It lets the decoder be switched off while its address inputs are changing, which is what suppresses the decoding glitches Chapter 24 meets in counters — while the address settles, several outputs may momentarily go low as different bits arrive at different times, and holding the enable off until the address is stable removes the problem entirely. More important here, it is the input that lets decoders be cascaded.
Suppose a 4-to-16 decoder is needed and only 3-to-8 parts are to hand. Split the four address bits: \(A_2A_1A_0\) chooses one of eight lines within a half, and \(A_3\) chooses the half. Wire the three low bits to both packages in parallel, and use \(A_3\) to enable one package or the other. The 74138 makes this free by providing enables of both polarities — one active-high input \(G_1\) and two active-low inputs \(\overline{G_{2A}}\) and \(\overline{G_{2B}}\) — so \(A_3\) can drive the active-low enable of one package and the active-high enable of the other without an inverter anywhere. The unused enables are tied to their inactive levels — \(G_1\) high on the package selected by \(A_3 = 0\), and the two \(\overline{G_2}\) pins low on the other.
Exactly one output of the sixteen is low for each of the sixteen input codes, which is the definition of a 4-to-16 decoder, and the spare enables are still free for a system-level chip select. The construction generalises: four 74138s and a 2-to-4 decoder driving their enables give 5-to-32; eight and a 3-to-8 give 6-to-64. Each level of the tree adds one gate delay, so a 6-to-64 decoder built this way settles in the time of two decoders in series rather than sixteen times the time of one.
Without it, a decoder is a fixed block of \(2^n\) minterms. With it, the decoder implements \(E \cdot m_i\), and feeding \(E\) from a higher-order address bit — or from another decoder — turns two small decoders into one large one with no extra logic. This is the same idea that the chip-select pin of a memory device uses in Chapter 26, and it is the reason address decoding in a microprocessor system is almost entirely a matter of wiring enables together.
3 The Decoder as a Minterm Generator
A decoder with \(n\) inputs puts every one of the \(2^n\) minterms of those inputs on a separate wire. Chapter 7 showed that any Boolean function can be written as a sum of minterms, so any function of \(n\) variables can be built from one decoder and one OR gate that collects the minterms in its list. With active-low outputs the collecting gate is a NAND rather than an OR, because by De Morgan's theorem
A NAND gate fed from active-low decoder outputs is an OR gate on the minterms themselves — an application of the bubble-pushing of Chapter 10, and the reason active-low decoders are convenient rather than merely traditional.
The strength of the method is that the decoder is shared. A circuit with several outputs that are all functions of the same variables needs one decoder and one gate per output, however complicated the individual functions are. The full adder of Chapter 16 is the standard demonstration: \(S = \Sigma m(1,2,4,7)\) and \(C_{out} = \Sigma m(3,5,6,7)\) are both functions of \(A\), \(B\) and \(C_{in}\), so one 3-to-8 decoder and two four-input NANDs do the whole job.
Compare the three implementations of the full adder met so far. Built from gates in the two-level form of Chapter 16 it is six gates: two exclusive-ORs and a three-term AND–OR network. Built from a decoder it is one 74138 plus two four-input NAND gates — two packages instead of three, but ten gate equivalents instead of six.
The comparison turns on how many functions share the variables. For one output the decoder is wasteful: \(2^n\) gates are built and most are thrown away. For two outputs, as here, it is roughly a draw and wins on package count. For a circuit with five or six outputs of the same three or four variables — a code converter, a small instruction decoder, the segment driver of Section 6 — it is clearly cheapest, because the expensive part is built once. A useful rule: use a decoder when the number of output functions approaches the number of input variables, and gates otherwise.
One further check is worth making before choosing. If a function has more than \(2^{n-1}\) minterms it is cheaper to collect the minterms of its complement and invert, since fewer decoder outputs then need connecting. A function of four variables with eleven minterms is built from the five minterms of \(F'\) and one inverter rather than from an eleven-input gate.
The method has a natural limit. The decoder grows as \(2^n\), so at six variables it is 64 gates before any function has been formed, and the collecting gates need impossible fan-in. Chapter 19 shows the multiplexer method, which handles the same problem with a part that grows as \(2^{n-1}\) and needs no collecting gate at all, and Chapter 27 shows the ROM, which is nothing but a decoder with a programmable array of collecting gates attached — the same idea, industrialised.
4 Encoders and Their Two Ambiguities
An encoder is the inverse of a decoder: \(2^n\) inputs, \(n\) outputs, and the output is the binary code of whichever input is active. For eight inputs the design follows from asking, for each output bit, which input numbers have a 1 in that position:
Three four-input OR gates, and \(D_0\) is not connected to anything, because the code for input 0 is 000 and needs no gate to produce it. That last observation is the first warning that something is wrong.
This circuit works perfectly on the eight input patterns it was designed for — exactly one input high — and produces nonsense on the other 248. There are two distinct failures, and a usable encoder must fix both.
- Ambiguity one: no input active. With all eight inputs at 0 the outputs are 000, which is also the output when \(D_0\) alone is active. The circuit cannot distinguish \"input 0 is asserted\" from \"nothing is asserted\", and in an interrupt controller those two conditions could hardly be more different.
- Ambiguity two: more than one input active. The gates simply OR the codes together, and the OR of two codes is generally the code of a third input. With \(D_3\) and \(D_5\) both high, \(Y_2 = 1\) from \(D_5\), \(Y_1 = 1\) from \(D_3\) and \(Y_0 = 1\) from both, giving \(Y = 111\) — the circuit reports that \(D_7\) is active, and \(D_7\) is the one input that is not.
The first ambiguity is cured by an extra output. A valid output \(V = D_7 + D_6 + \cdots + D_0\) is 1 whenever any input is asserted, so the pair \((V, Y)\) is unambiguous: \(V = 0\) means \"nothing\", and \(V = 1\) with \(Y = 000\) means \"input 0\". One eight-input OR gate.
The second cannot be cured by adding outputs, because it is not a missing-information problem but a definitional one. When two inputs are asserted there is no correct answer — the encoder has one code to give and two things to report. The only way forward is to define what the circuit should do, and the definition that is nearly always wanted is a priority rule: report the highest-numbered active input and ignore the rest. A circuit built to that rule is a priority encoder, and it is what Section 5 designs. The simple encoder of this section is not manufactured at all; every encoder in the 74 series is a priority encoder, for exactly this reason.
5 The Priority Encoder
The specification is now precise. Output the binary code of the highest-numbered asserted input; assert \(V\) if any input is asserted; when \(V = 0\) the code outputs mean nothing. Writing that as a truth table is where the design becomes easy, because most of the table is don't-cares — once a high-numbered input is known to be 1, everything below it is irrelevant:
| \(D_7\) | \(D_6\) | \(D_5\) | \(D_4\) | \(D_3\) | \(D_2\) | \(D_1\) | \(D_0\) | \(Y_2\) | \(Y_1\) | \(Y_0\) | \(V\) |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | × | × | × | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | × | 0 | 0 | 1 | 1 |
| 0 | 0 | 0 | 0 | 0 | 1 | × | × | 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | 1 | × | × | × | 0 | 1 | 1 | 1 |
| 0 | 0 | 0 | 1 | × | × | × | × | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | × | × | × | × | × | 1 | 0 | 1 | 1 |
| 0 | 1 | × | × | × | × | × | × | 1 | 1 | 0 | 1 |
| 1 | × | × | × | × | × | × | × | 1 | 1 | 1 | 1 |
Nine rows cover all 256 input patterns. The staircase of × entries is the priority rule made visible: everything to the right of the leading 1 is ignored.
Reading the equations off the table is now a matter of collecting the rows in which each output is 1, with the don't-cares left out. \(Y_2 = 1\) on the four rows whose leading 1 is at position 4 or above, and on those rows \(D_7, D_6, D_5, D_4\) is the only column that is ever 1, so
\(Y_1\) is 1 when the leading 1 is at 7, 6, 3 or 2. The first two need no qualification, since nothing outranks them; the second two are valid only if 5 and 4 are both quiet:
\(Y_0\) is 1 when the leading 1 is at 7, 5, 3 or 1, each qualified by the inputs that outrank it and would change the answer:
Evaluating all four expressions against all 256 input patterns confirms that they agree with the priority rule on every one. Note that the qualifying terms are not the same in each equation: \(Y_1\) is spoiled only by \(D_5\) and \(D_4\), while \(Y_0\) is spoiled by \(D_6\), \(D_4\) and \(D_2\) — in each case exactly the higher inputs whose codes have a 0 in that bit position.
Apply \(D_7 \ldots D_0 = \) 00101100, so \(D_5\), \(D_3\) and \(D_2\) are all asserted. The rule says the answer is 5, or \(Y = 101\).
\(Y_2 = D_7+D_6+D_5+D_4 = 0+0+1+0 = 1\). For \(Y_1\), the first two terms are 0; the third is \(D_5'D_4'D_3 = 0 \cdot 1 \cdot 1 = 0\) because \(D_5 = 1\) kills it; the fourth dies the same way. So \(Y_1 = 0\). For \(Y_0\), the first term is 0; the second is \(D_6'D_5 = 1 \cdot 1 = 1\), so \(Y_0 = 1\). The code is 101, and \(V = 1\). The simple encoder of Section 4 would have given \(101 + 011 + 010 = 111\), reporting the one input that is silent.
The 74148 packages this as an eight-input priority encoder with active-low inputs and outputs, plus two extra pins for cascading in the manner of Section 2: an enable input \(\overline{EI}\), and an enable output \(\overline{EO}\) that is asserted only when the package is enabled and none of its inputs is. Feeding \(\overline{EO}\) of the higher-priority package into \(\overline{EI}\) of the next builds a 16-to-4 priority encoder from two packages and a couple of gates: the lower package is allowed to speak only when the upper one has nothing to say, which is the priority rule applied one level up.
6 BCD-to-Seven-Segment Decoding
A seven-segment display is seven light-emitting bars arranged in a figure of eight and lettered \(a\) to \(g\) clockwise from the top, with \(g\) across the middle. The decoder takes a BCD digit on four lines and drives the seven segments so that the digit appears. Despite the name it is not one decoder but seven independent functions of the same four variables — which makes it the case Worked Example 18.1 said the shared-decoder method suits, and also an ideal exercise in don't-cares.
The truth table is written by drawing each digit and noting which bars are lit. Taking \(A\) as the most significant bit (weight 8) down to \(D\) (weight 1), and 1 as \"segment on\":
| Digit | \(ABCD\) | \(a\) | \(b\) | \(c\) | \(d\) | \(e\) | \(f\) | \(g\) |
|---|---|---|---|---|---|---|---|---|
| 0 | 0000 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
| 1 | 0001 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 2 | 0010 | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
| 3 | 0011 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
| 4 | 0100 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 5 | 0101 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 6 | 0110 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 7 | 0111 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 8 | 1000 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 9 | 1001 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
| 10–15 | 1010–1111 | × | × | × | × | × | × | × |
The six codes 1010 to 1111 never occur, because the input is a BCD digit. They are therefore don't-cares, and Chapter 8 showed what to do with those: take each as 1 wherever it enlarges a group of 1s and as 0 otherwise.
Take segment \(a\), which is lit for every digit except 1 and 4, so \(a = \Sigma m(0,2,3,5,6,7,8,9) + d(10,\ldots,15)\). Figure 18.4 plots it.
Four groups cover the map, each of them prime and each of them essential:
- The bottom two rows are all 1 or ×, an octet in which \(B\), \(C\) and \(D\) all change while \(A = 1\): the term is \(A\).
- The two right-hand columns are all 1 or ×, an octet in which \(A\), \(B\) and \(D\) change while \(C = 1\): the term is \(C\).
- Cells 5, 7, 13 and 15 form a quad with \(B = 1\), \(D = 1\): the term is \(BD\). Cells 13 and 15 are don't-cares taken as 1, and without them cells 5 and 7 would only make a pair.
- Cells 0, 2, 8 and 10 are the four corners, adjacent round both edges of the map, with \(B = 0\), \(D = 0\): the term is \(B'D'\).
Six literals and four gates, and substituting the ten valid codes confirms it reproduces the column exactly — 1 for every digit but 1 and 4.
Now force the six unused codes to 0 instead and repeat the minimisation. The corners disappear, the octets shrink to quads, and the best available answer becomes
Still four terms, but eleven literals instead of six, and three of the gates now need three inputs. The don't-cares have saved five literals on one segment out of seven, and the same saving repeats across the others — which is why the assumption that illegal codes never arrive is worth making explicitly rather than by accident.
Minimising the remaining six segments the same way gives:
| Segment | Lit for digits | Minimal expression | Literals |
|---|---|---|---|
| \(a\) | 0, 2, 3, 5, 6, 7, 8, 9 | \(A + C + BD + B'D'\) | 6 |
| \(b\) | 0, 1, 2, 3, 4, 7, 8, 9 | \(B' + CD + C'D'\) | 5 |
| \(c\) | 0, 1, 3, 4, 5, 6, 7, 8, 9 | \(B + C' + D\) | 3 |
| \(d\) | 0, 2, 3, 5, 6, 8, 9 | \(A + B'C + CD' + B'D' + BC'D\) | 10 |
| \(e\) | 0, 2, 6, 8 | \(CD' + B'D'\) | 4 |
| \(f\) | 0, 4, 5, 6, 8, 9 | \(A + BC' + BD' + C'D'\) | 7 |
| \(g\) | 2, 3, 4, 5, 6, 8, 9 | \(A + BC' + B'C + CD'\) | 7 |
Segment \(c\) is the cheapest because it is dark for only one digit, and segment \(d\), lit for a
Segment \(c\) is the cheapest because it is dark for only one digit, and segment \(d\), lit for a scattered set with no useful adjacencies, is the dearest. Building all seven from gates comes to 42 literals in twenty-three gates plus four inverters; building them from a 4-to-16 decoder and seven collecting gates is one decoder and seven gates, which is why the 7447 and 7448 exist as single packages.
common-cathode forms: in the first, all seven anodes are joined to \(V_{CC}\) and a segment lights when its cathode is pulled low, so it needs a decoder with active-low outputs such as the 7447; in the second the common pin goes to ground and an active-high driver such as the 7448 is wanted. Connecting the wrong one lights every segment except the ones you asked for. And each segment needs its own series resistor — typically 220 Ω to 470 Ω at 5 V — because an LED has no useful series resistance of its own and will take whatever current the driver can supply until one or the other fails.Finally, a caution about the don't-cares. They were treated as free, and in the logic they are; but a real chip does something definite for codes 1010 to 1111, and what it does is whatever the minimised equations happen to produce. The 7447 displays a set of partial patterns for those codes rather than blanking, so a fault upstream that puts an illegal code on the bus shows up as a meaningless glyph rather than a dark display. If a blank is wanted the part provides a separate ripple-blanking input, which is a deliberate control rather than an accident of the minimisation.
7 Summary and Key Results
| Block | What it does | Design notes |
|---|---|---|
| \(n\)-to-\(2^n\) decoder | Asserts the one output whose number matches the input code | Output \(i\) is minterm \(m_i\); \(2^n\) gates of \(n\) inputs plus \(n\) inverters |
| Active-low outputs | Selected line goes to 0, the rest stay at 1 | NAND instead of AND: one gate cheaper, and TTL sinks far more current than it sources |
| Enable input | Extra input on every gate; \(E = 0\) deselects all outputs | Suppresses decoding glitches, and is what makes cascading possible |
| Cascading | Low address bits to all packages, high bits to the enables | Two 74138s give 4-to-16; four plus a 2-to-4 give 5-to-32 |
| Decoder as minterm generator | \(F = (m_a' m_b' m_c')'\) with one NAND per function | Worth it when several functions share the same input variables |
| Simple encoder | \(Y_2 = D_4+D_5+D_6+D_7\), and so on | Unusable: no output distinguishes "input 0" from "nothing", and two active inputs OR their codes |
| Priority encoder | \(Y_1 = D_7 + D_6 + D_5'D_4'D_3 + D_5'D_4'D_2\) | Reports the highest active input; needs a valid flag \(V\); the 74148 cascades through \(\overline{EO}\) |
| BCD-to-seven-segment | \(a = A + C + BD + B'D'\) | Six literals with the unused codes as don't-cares, eleven without |
8 Common Mistakes
Every 74-series decoder asserts its selected output by pulling it low, so a lamp wired between the output and ground is on for fifteen codes out of sixteen and off for the one that was wanted. The same slip in a logic design collects decoder outputs with an OR gate, which by De Morgan's theorem produces the NAND of the minterms instead of their OR. Active-low outputs must be collected with a NAND.
A plain encoder is correct only when exactly one input is asserted, and nothing in the circuit enforces that. With \(D_3\) and \(D_5\) both high its three OR gates deliver \(011 + 101 = 111\), reporting input 7. Because the fault needs two simultaneous inputs it survives every single-input test and appears in service as an occasional wrong answer. Any application in which two inputs can be asserted at once — keypads, interrupt lines, alarm inputs — needs a priority encoder and a valid output.
The six unused BCD codes halve the literal count of the seven-segment decoder, so leaving them out of the map is expensive. The opposite error costs just as much: a loop drawn round a block containing only don't-cares creates a term that turns a segment on for a code that never occurs, adding a gate that can never do anything useful. A don't-care earns its place only by making a group of genuine 1s larger.
9 Chapter Review
1. Design a 3-to-8 decoder with an active-high enable and active-low outputs. How many gates does it need, and what is the delay from a change of address to a settled output?
Each output is one four-input NAND fed by the enable and by one combination of \(A_2\), \(A_1\), \(A_0\) in true or complemented form: \(\overline{Y_i} = (E \cdot m_i)'\). That is eight NAND gates plus three inverters, eleven gates in all. The delay is one inverter level followed by one NAND level, \(2\Delta = 20\) ns with the model of Chapter 16 — and it does not grow with \(n\), because the decoder is always two levels deep however many inputs it has. What grows with \(n\) is the gate count, as \(2^n\), and the fan-in, as \(n+1\).
2. Implement \(F(A,B,C) = \Sigma m(0,3,5,6)\) with a 3-to-8 decoder, and say what the circuit computes.
Connect \(A\), \(B\) and \(C\) to the decoder's address inputs and take the four active-low outputs \(\overline{m_0}\), \(\overline{m_3}\), \(\overline{m_5}\) and \(\overline{m_6}\) into a four-input NAND. By De Morgan's theorem the NAND output is \(m_0 + m_3 + m_5 + m_6\), which is \(F\). The function itself is the exclusive-NOR of the three variables: those four minterms are exactly the codes with an even number of 1s, so \(F = (A \oplus B \oplus C)'\) and the circuit is a three-bit even-parity detector. Built directly it would be two exclusive-OR gates and an inverter, three gates against a decoder and a NAND — a good illustration of Worked Example 18.1's rule that a single output rarely justifies the decoder.
3. An 8-to-3 priority encoder is presented with \(D_7 \ldots D_0 = \)
00010110. What are \(Y_2Y_1Y_0\) and \(V\), and what would a simple encoder produce?The asserted inputs are \(D_4\), \(D_2\) and \(D_1\); the highest is \(D_4\), so the priority encoder gives \(Y = 100\) with \(V = 1\). Checking against the equations: \(Y_2 = D_7+D_6+D_5+D_4 = 1\); \(Y_1 = D_7 + D_6 + D_5'D_4'D_3 + D_5'D_4'D_2\), and the last two terms both contain \(D_4' = 0\), so \(Y_1 = 0\); \(Y_0 = D_7 + D_6'D_5 + D_6'D_4'D_3 + D_6'D_4'D_2'D_1\), and again every term with a chance of being 1 contains \(D_4'\), so \(Y_0 = 0\). A simple encoder would OR the three codes \(100\), \(010\) and \(001\) to give \(111\), reporting \(D_7\).
4. Minimise segment \(e\) of the seven-segment decoder with and without don't-cares, and explain the difference in the answers.
Segment \(e\) is lit only for 0, 2, 6 and 8, so \(e = \Sigma m(0,2,6,8) + d(10,\ldots,15)\). With the don't-cares, cells 0, 2, 8 and 10 are the four corners, giving \(B'D'\), and cells 2, 6, 10 and 14 form the column pair with \(C = 1\), \(D = 0\), giving \(CD'\); both are essential and together they cover all four 1s, so \(e = B'D' + CD'\) — four literals, three gates. Forcing 10 to 15 to 0 removes cells 10 and 14 from the map, so the corners shrink to the pair \(\{0, 8\}\) giving \(B'C'D'\), the column pair shrinks to \(\{2, 6\}\) giving \(A'CD'\), and \(e = B'C'D' + A'CD'\) — six literals and two three-input gates. Both answers behave identically on the ten codes that occur; they differ only on the six that do not, and the cheaper one is cheaper precisely because it does not care what happens there.
5. A system needs a 32-line select driven by a 5-bit address. Compare building it from a single 5-to-32 decoder with building it from 74138s, in gates, packages and delay.
As one block it is thirty-two five-input NAND gates plus five inverters, thirty-seven gates, two levels deep and therefore \(2\Delta = 20\) ns. As 74138s it is four packages for the thirty-two outputs plus a 2-to-4 decoder driving their enables, so five packages; the address splits as \(A_4A_3\) to the small decoder and \(A_2A_1A_0\) to all four 74138s in parallel. The delay is now two decoders in series, \(4\Delta = 40\) ns, since a 74138 cannot start deciding until its enable is valid. The gate count is similar, but the cascaded version is built from parts that exist, needs no five-input gates, and leaves the second enable of every 74138 free for a board-level chip select — which is why address decoders in real systems are almost always built this way.