Combinational Building Blocks
Designers rarely think in single gates for long. They think in blocks: a multiplexer that chooses, a decoder that selects, an encoder that numbers, a comparator that weighs two numbers. This volume builds each one from gates, shows how a multiplexer or a decoder can build any function, and ends with the decoder that drives every digital clock face.
- How a multiplexer works, and how one can build any function
- Decoders, enables and demultiplexers, and building functions from a decoder
- Encoders, and why a priority encoder is the useful one
- How to compare two binary numbers, bit by bit
- How a seven-segment decoder works, simplified with K-maps and don't cares
- Volumes 02 to 04 of this course: the gates, minterms and K-maps with don't cares.
5.1 Multiplexers
A multiplexer, or mux, is a switch made of gates. Its select inputs choose one of its data inputs and pass it to the output. With the right inputs, a multiplexer can build any function at all.
Designers rarely think in single gates for long. They think in building blocks: small circuits that do one well-known job, drawn as a box. This volume meets the most useful ones. Each is still just gates inside, so everything from Volumes 02 to 04 still applies.
The 2-to-1 multiplexer
A 2-to-1 multiplexer has two data inputs, I0 and I1, and one select input, S. When S is 0 the output copies I0; when S is 1 it copies I1:
| S | I0 | I1 | Y |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
As a formula, each AND term lets one data input through when the select allows it:
Y = S'·I0 + S·I1 on every row: True
The 4-to-1 multiplexer
With two select inputs, S1 and S0, a multiplexer can choose between four data inputs. The select lines are read as a binary number, and that number picks the input:
| S1 | S0 | Y |
|---|---|---|
| 0 | 0 | D0 |
| 0 | 1 | D1 |
| 1 | 0 | D2 |
| 1 | 1 | D3 |
Y = S1'·S0'·D0 + S1'·S0·D1 + S1·S0'·D2 + S1·S0·D3 on every row: True
In general, n select inputs choose between 2n data inputs: an 8-to-1 multiplexer has three select inputs.
Any function from a multiplexer
Here is the clever part. Connect the inputs of a function to the select lines of a multiplexer, and each data input picks one row of the truth table. Set each data input to that row's output, and the multiplexer is the function.
For the majority function from Volume 03, an 8-to-1 multiplexer with A, B and C on its select lines needs its data inputs set to the output column:
D0..D7 = 0 0 0 1 0 1 1 1
A smaller multiplexer works too. Put just A and B on the select lines of a 4-to-1 multiplexer. Each pair of rows with the same A and B then needs a data input of 0, 1, C or C':
| A | B | Y when C = 0 | Y when C = 1 | Data input |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | C |
| 1 | 0 | 0 | 1 | C |
| 1 | 1 | 1 | 1 | 1 |
This is a favourite exam question. With n select lines, and data inputs of 0, 1, the last input or its inverse, a multiplexer builds any function of n + 1 inputs.
A 4-to-1 multiplexer has S1 = 1 and S0 = 0. Which data input reaches the output?
Show the answer
Answer: C. The select lines read as the binary number 10, which is 2, so D2 is passed to the output.
5.2 Decoders and demultiplexers
A decoder turns a binary number into one active line: with n inputs it has 2n outputs, and exactly one of them is 1. OR together the right outputs, and a decoder builds any function.
The 2-to-4 decoder
A 2-to-4 decoder reads its inputs A1 and A0 as a number from 0 to 3, and sets that one output to 1. It usually has an enable input, EN, too: when EN is 0, every output stays 0.
| EN | A1 | A0 | Y0 | Y1 | Y2 | Y3 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 1 |
Each output is one minterm of the inputs: Y2, for instance, is 1 only when A1 = 1 and A0 = 0. So a decoder is a whole row of minterms, ready made.
Any function from a decoder
Because each output is a minterm, ORing together the outputs for the rows where a function is 1 builds that function. The majority function is Σm(3, 5, 6, 7), so it needs outputs 3, 5, 6 and 7 of a 3-to-8 decoder:
majority = Y3 + Y5 + Y6 + Y7 of a 3-to-8 decoder: True
Decoders choose chips
The most common job for a decoder is choosing which chip should answer. A computer's memory is made of several chips; the top bits of an address go into a decoder, and each decoder output enables one chip. Volume 09 builds a memory this way.
The demultiplexer
A demultiplexer does the opposite of a multiplexer: it sends one data input to one of several outputs. A decoder with its enable used as the data input is exactly that. When the data is 1 the chosen output is 1, and when it is 0 every output is 0.
How many outputs does a decoder with 4 inputs have?
Show the answer
Answer: B. Four inputs make 24 = 16 numbers, and a decoder has one output for each number.
5.3 Encoders and priority encoders
An encoder does the reverse of a decoder: it turns one active line into its number. A priority encoder copes with several active lines at once by reporting the highest one.
A simple 4-to-2 encoder assumes exactly one of its inputs I0 to I3 is 1, and outputs that input's number on Y1 and Y0. But what if two keys are pressed at once, or none? A plain encoder gives a wrong answer.
The priority encoder
A priority encoder gives each input a rank: the highest-numbered active input wins. It also has a valid output, V, which is 0 when no input is active at all. In this table, X in an input column means "0 or 1, it makes no difference":
| I0 | I1 | I2 | I3 | Y1 | Y0 | V |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | X | X | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 1 |
| X | 1 | 0 | 0 | 0 | 1 | 1 |
| X | X | 1 | 0 | 1 | 0 | 1 |
| X | X | X | 1 | 1 | 1 | 1 |
Five rows stand for all sixteen input patterns, and the simulator checked every one of them:
this table matches "the highest active input wins" on all 16 input patterns: True
From the table, Y1 is 1 whenever I2 or I3 is active. Y0 is 1 when I3 is active, or when I1 is active and I2 is not:
Y1 = I3 + I2 whenever V = 1: True
Y0 = I3 + I2'·I1 whenever V = 1: True
V = I3 + I2 + I1 + I0
Priority encoders decide which of several interrupt requests a processor serves first, and which key of a keyboard to report.
A 4-to-2 priority encoder has I1 = 1 and I3 = 1, and the other inputs 0. What are Y1 and Y0?
Show the answer
Answer: D. The highest active input wins. I3 is active, so the output is 3, which is 11 in binary: Y1 = 1 and Y0 = 1. I1 is ignored.
5.4 Comparators
A comparator says whether one number is greater than, equal to or less than another. For single bits it is three small gates; for longer numbers, it compares from the most significant bit down.
Comparing two bits
A one-bit comparator has three outputs: G is 1 when A is greater than B, E when they are equal, and L when A is less than B. Exactly one of the three is 1 at any time.
| A | B | G | E | L |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 |
Comparing longer numbers
To compare two numbers, look at the most significant bits first. If they differ, they decide the answer. If they are equal, move on to the next bit down. For two 2-bit numbers A1 A0 and B1 B0:
greater: G = A1·B1' + (A1 ⊙ B1)·A0·B0'
equal: E = (A1 ⊙ B1)·(A0 ⊙ B0)
both right for all 16 pairs of numbers: True
Read the first formula aloud. A is greater if its top bit wins, or if the top bits are equal and its bottom bit wins. Longer comparators follow the same pattern, one bit at a time.
What gate tells you whether two bits are equal?
Show the answer
Answer: A. XNOR gives 1 when its inputs are the same. XOR does the opposite: it gives 1 when they differ.
5.5 Seven-segment display decoders
A seven-segment display draws a digit with seven bars, named a to g. A seven-segment decoder turns a BCD digit into the seven signals that light the right bars - one small function per segment, each simplified with a K-map.
The truth table
Each digit lights a fixed set of segments. As a table, with 1 for a lit segment:
| Digit | a | b | c | d | e | f | g |
|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 2 | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
| 3 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
| 4 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 5 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 6 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 7 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 8 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 9 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
The input is a BCD digit, A B C D, so rows 10 to 15 never happen. They are don't cares, and they make every segment's formula much smaller.
Segment a, with a K-map
Segment a is lit for every digit except 1 and 4. On a map with the don't cares added:
segment a: on for 0 2 3 5 6 7 8 9; a = A + C + B'·D' + B·D
The other six segments work the same way. Here is the simplest formula for each, found by the same search that checks the maps:
segment a: on for 0 2 3 5 6 7 8 9; a = A + C + B'·D' + B·D
segment b: on for 0 1 2 3 4 7 8 9; b = B' + C'·D' + C·D
segment c: on for 0 1 3 4 5 6 7 8 9; c = B + C' + D
segment d: on for 0 2 3 5 6 8 9; d = A + B'·C + B'·D' + C·D' + B·C'·D
segment e: on for 0 2 6 8; e = B'·D' + C·D'
segment f: on for 0 4 5 6 8 9; f = A + B·C' + B·D' + C'·D'
segment g: on for 2 3 4 5 6 8 9; g = A + B'·C + B·C' + C·D' (2 equal answers)
Forgetting whether the display is lit by a 1 or a 0. In a common-cathode display, a segment lights when its input is 1, as in the table above. In a common-anode display, a segment lights when its input is 0, so every output must be inverted. Check which kind you have before you wire it.
Why do rows 10 to 15 help when simplifying a seven-segment decoder?
Show the answer
Answer: C. A BCD digit only goes up to 9, so the patterns for 10 to 15 never arrive. That makes them don't cares, and using them as 1s where it helps makes the groups bigger and the formulas shorter.
What you learned
- A multiplexer passes one of its data inputs to the output; n select lines choose from 2 to the power n inputs.
- A multiplexer can build any function: put the inputs on its select lines and the truth table on its data inputs.
- A decoder turns an n-bit number into one active line out of 2 to the power n; each output is one minterm.
- OR the decoder outputs for the 1 rows of a truth table and you have that function.
- A demultiplexer sends one input to one of several outputs; a decoder with its enable as the data is one.
- A priority encoder reports the highest active input, with a valid output for "none at all".
- A comparator checks the most significant bits first; XNOR tests two bits for equality.
- A seven-segment decoder is seven small functions, and BCD's unused codes make them simpler.
Key words from this volume
Every word below has a plain-English entry in the glossary.
- Multiplexer (mux)
- Building block
- Decoder
- Enable
- Demultiplexer
- Encoder
- Priority encoder
- Comparator
- Seven-segment display
Practice
An XOR from a 2-to-1 multiplexer
Build Y = A ⊕ B from one 2-to-1 multiplexer, using A as the select input.
Show the solution
When A = 0, Y = B; when A = 1, Y = B'. So put B on I0 and B' on I1. The multiplexer's formula then reads Y = A'·B + A·B', which is exactly A ⊕ B.
A decoder for a 3-input function
Which outputs of a 3-to-8 decoder would you OR together to build the three-input XOR, A ⊕ B ⊕ C?
Show the solution
A three-input XOR is 1 when an odd number of inputs are 1: rows 1, 2, 4 and 7, as Volume 03 found. So OR together outputs Y1, Y2, Y4 and Y7.
Which key wins?
A 4-to-2 priority encoder has I0 = 1 and I2 = 1. What are Y1, Y0 and V?
Show the solution
The highest active input is I2, so the output is 2: Y1 = 1 and Y0 = 0. At least one input is active, so V = 1.
Interview corner
Why is a multiplexer called universal?
"How can a multiplexer implement any Boolean function?"
Show the solution
"Connect the function's inputs to the select lines. Each combination of select inputs then chooses one data input, which is one row of the truth table - so tie each data input to that row's output. With 2n data inputs you can do any function of n inputs. With half as many, you can still do any function of n + 1 inputs, by feeding the last input, its inverse, 0 or 1 into the data inputs."
Decoder or demultiplexer?
"What is the difference between a decoder and a demultiplexer?"
Show the solution
"Inside they are the same circuit. A decoder turns a number on its inputs into one active output line. A demultiplexer routes a data signal to one of several outputs, chosen by its select inputs. Take a decoder with an enable, use the enable as the data input and the address inputs as the select, and you have a demultiplexer."
Volume 06 builds the most important block of all: the circuit that adds.