Multiplexers, decoders and comparators
Three more circuits that are nothing but truth tables: pick an input, light one line, compare two numbers.
Three circuits, one idea
Adders do arithmetic. The circuits in this lesson do something humbler: they choose, they point, and they compare. They turn up everywhere inside a computer, and the point of meeting them together is to notice that none of them is new. Each one is a truth table, and a truth table is something you already know how to turn into gates.
The multiplexer: a switchboard
Imagine an old telephone switchboard. Several lines come in, one line goes out, and an operator connects one of the incoming lines to the outgoing one. A multiplexer, or mux, is that switchboard made of gates. It has several data inputs, one output, and a few extra inputs called select lines. The select lines carry a binary number, the select code, and that number says which data input is connected to the output. Everything else is ignored.
The smallest one picks between two inputs, a and b, with one select line s. When s is 0 the output copies a; when s is 1 it copies b. As an expression that is (¬s ∧ a) ∨ (s ∧ b): the select line enables one of two AND gates and an OR merges them. Try it:
Two select lines make four codes, 00 to 11, so they can pick among four inputs. One way to build that is a tree of three 2-to-1 muxes: s0 picks between d0 and d1 and, separately, between d2 and d3, then s1 picks between those two results. The widget below is wired that way.
Worked example. A 4-to-1 mux has s1 = 1 and s0 = 0. Which input reaches the output?
Read the select lines as a binary number with s1 as the top bit: 10, which is 2. So the output copies d2, whatever d0, d1 and d3 are doing. In the tree, s0 = 0 picks d0 from the first pair and d2 from the second, and s1 = 1 picks the second pair's result, which is d2.
Common mistake: reading the select lines in the wrong order
s1 s0 = 10 selects input 2, not input 1. The select lines are a binary number, and s1 is the twos column. Muxes are also easy to confuse with decoders: a mux has many data inputs and one output, a decoder has no data inputs at all and many outputs.
The decoder: one line per code
A decoder takes a binary number in and raises exactly one of its outputs, the one whose number matches. A 2-to-4 decoder has two inputs and four outputs, y0 to y3. Input 00 lights y0, 01 lights y1, 10 lights y2 and 11 lights y3, and the other three stay low. Because exactly one output is ever high, this way of writing a number is called one-hot. Each output is a single AND gate, with each input used as it is or inverted: y0 is ¬a ∧ ¬b, y1 is ¬a ∧ b, y2 is a ∧ ¬b and y3 is a ∧ b.
Decoders are how a memory chip turns an address into "this row, not the others", and in the next lesson a close cousin turns a digit into the bars of a display.
The comparator: equal, less, greater
A comparator takes two numbers and says how they stand: equal, or which one is bigger. For single bits it has three outputs, and exactly one of them is high at any time. Equal is 1 when a and b match, which is XOR inverted, the XNOR gate. Greater is 1 only when a is 1 and b is 0, a ∧ ¬b. Less is the mirror image, ¬a ∧ b.
For longer numbers, compare from the top bit down. If the top bits differ, they decide, and the rest is ignored. If they are equal, move down one bit and ask again. In gates that is a chain of one bit comparators where each stage only gets a say when every stage above it reported equal.
Worked example. Compare A = 10 and B = 01 (two bits each).
Top bits first: A has 1, B has 0. They differ, and A's is the 1, so A is greater. The bottom bits never need looking at. In decimal, that is 2 against 1.
Why?: why are these 'just truth tables'?
Every circuit here has outputs that depend only on the inputs at that moment, with no memory. Stage 4 showed that any such behaviour can be written as a truth table and any truth table can be built from AND, OR and NOT. So a mux, a decoder and a comparator are not new kinds of thing; they are common tables that were worth giving names to, because designers reach for them constantly.
What to remember
- A multiplexer passes one of its data inputs to its output, chosen by the select code; n select lines pick among 2n inputs.
- A decoder raises exactly one output, the one numbered by its input: a one-hot code.
- A comparator says equal, greater or less; for several bits, compare from the top bit down.
- All three are ordinary truth tables, built from the gates you already have.
Check yourself
Get 5 right in a row and the lesson is done. A wrong answer costs the run, not the lesson.
A 2-to-4 decoder has inputs a (the top bit) and b, and outputs y0 to y3. With a = 1 and b = 0, which output is high?
a b = 10
Already know this? and come back to the quiz any time.