Multiplexers, Decoders & Comparators

Not every combinational circuit does arithmetic. This page covers the other major family of standard building blocks — ones concerned with routing, selecting, and comparing signals rather than computing on them. Between these and the adder from the previous page, you have the vocabulary to describe the vast majority of any real combinational datapath.

Multiplexers (MUX)

A multiplexer selects one of several data inputs and routes it to a single output, based on a binary select signal. A 2-to-1 MUX — two data inputs, one select line — is the simplest case:

S | Out
0 | I0
1 | I1

Out = I0·S' + I1·S

Generalizing: an n-to-1 MUX needs log₂(n) select lines, and its output is a sum of n product terms, each one gating a single data input with the unique combination of select-line values (complemented or not) that picks it out — the same minterm-construction idea from SOP forms in Boolean Algebra & Logic Gates, just with data inputs instead of constant 1s.

Building larger functions out of a MUX is a genuinely useful trick, not just a routing device: because a 2ⁿ-to-1 MUX has one dedicated input line per possible combination of its n select lines, wiring the outputs of an n-variable truth table directly onto those data inputs implements any n-variable Boolean function with no gates at all beyond the MUX itself — a technique that shows up constantly in FPGA lookup tables (LUTs), which are, at their core, exactly this.

Wide MUXes are usually built by cascading narrower ones, not fabricated flat. An 8-to-1 MUX, for example, is commonly assembled from two 4-to-1 MUXes (each handling half the data inputs on the low two select lines) feeding a final 2-to-1 MUX whose single select line is the most significant select bit, choosing between the two 4-to-1 outputs. The same tree pattern extends to arbitrarily wide MUXes: split the data inputs across smaller MUX stages driven by the low-order select bits, then merge stage outputs with one further layer of MUXes driven by the remaining high-order select bit(s).

Demultiplexers (DEMUX)

A demultiplexer is the MUX's mirror image: one data input, routed to one of several outputs based on a select signal, with every unselected output held at 0.

S | Out0 Out1
0 |  In    0
1 |   0   In

DEMUXes see less standalone use than MUXes in practice, but they're the structural basis for the decoder covered next — a decoder is essentially a DEMUX with its single data input tied permanently to 1.

Decoders

A decoder takes an n-bit binary input and asserts exactly one of 2ⁿ output lines — the one whose index matches the input value — with every other output held at 0. A 2-to-4 decoder:

A1 A0 | Y0 Y1 Y2 Y3
 0  0 |  1  0  0  0
 0  1 |  0  1  0  0
 1  0 |  0  0  1  0
 1  1 |  0  0  0  1

Y0 = A1'A0'   Y1 = A1'A0   Y2 = A1A0'   Y3 = A1A0

Each output is exactly one minterm of the inputs — a decoder is, structurally, nothing but a minterm generator, one AND gate per output. That's precisely why a decoder plus an external OR gate can implement any SOP expression directly (OR together the decoder outputs corresponding to the function's 1-rows) — the same MUX-as-universal-function idea from above, approached from the opposite direction. Decoders' most common real use, though, is address decoding: selecting exactly one memory chip, one register, or one peripheral out of many, based on an address value.

Real decoder chips also add an enable input: the decoder only asserts an output at all while enable is active, and holds every output at 0 (or inactive) otherwise, regardless of the address lines. This does double duty. First, it makes a plain decoder usable as a DEMUX: tie the decoder's enable pin to the DEMUX's data signal instead of a constant 1, and whichever output line the address selects now simply follows that data signal, while every unselected output stays inactive — exactly the DEMUX behavior from above. Second, it lets smaller decoders cascade into a larger one: a 4-to-16 decoder can be built from four 2-to-4 decoders whose enables are each driven by one output of an additional 2-to-4 decoder decoding the two most-significant address bits — only the one sub-decoder whose enable is asserted produces any active output, and the other three stay entirely silent.

Encoders

An encoder is the decoder's inverse: exactly one of 2ⁿ input lines is asserted, and the circuit outputs the n-bit binary index of which one.

I0 I1 I2 I3 | A1 A0
 1  0  0  0 |  0  0
 0  1  0  0 |  0  1
 0  0  1  0 |  1  0
 0  0  0  1 |  1  1

A plain encoder has an unstated but load-bearing assumption: exactly one input is ever high at a time — its truth table simply has no defined behavior if two inputs are asserted simultaneously (or none are). A priority encoder removes that fragility by explicitly defining a priority order — if multiple inputs are asserted, it outputs the index of the highest-priority one and ignores the rest — which is why priority encoders, not plain encoders, are what actually show up in real designs like interrupt controllers, where multiple request lines being active simultaneously is an entirely normal condition the circuit has to handle correctly, not an edge case to assume away.

Magnitude comparators

A magnitude comparator takes two multi-bit values, A and B, and produces three outputs: A>B, A=B, A<B. For single bits:

A B | A>B A=B A<B
0 0 |  0   1   0
0 1 |  0   0   1
1 0 |  1   0   0
1 1 |  0   1   0

A=B = A'B' + AB = (A⊕B)'      A>B = AB'      A<B = A'B

Note that A=B is just XNOR — the "same" gate, the mirror of the XOR "differ" gate that's shown up repeatedly through this section. For multi-bit comparison, the standard structure works from the most significant bit down: if the MSBs already decide the comparison (one is 1 and the other 0), the result is final; only if the MSBs are equal does the comparison need to fall through to the next-most-significant bit pair, cascading down to the least significant bit if every higher pair ties. This is exactly the same "compare left to right, fall through only on a tie" logic you'd use comparing two decimal numbers digit by digit, and it's why multi-bit comparators are built as a cascade of identical single-bit-comparison-plus-cascade-input stages rather than one large flat truth table.

What's next

Every circuit on this page and the previous one is stateless — feed the same inputs twice, get the same outputs twice, with no memory of anything in between. The next section introduces circuits that break that rule on purpose: sequential logic, starting with the latch and flip-flop, the building blocks that let a digital circuit remember.