BitFlow
← Academy·Multiplexers, Decoders and Encoders
ΣCore~40 min

Multiplexers, Decoders and Encoders

The blocks that route and translate data: MUX and DEMUX, decoders, encoders, priority encoders and code converters.

Multiplexers

A multiplexer, or MUX, is a data selector: many inputs, one output, and select lines that choose which input gets through. With n select lines it chooses among 2ⁿ inputs.

Loading the animation…

y = s₁'s₀'d₀ + s₁'s₀d₁ + s₁s₀'d₂ + s₁s₀d₃
A 4:1 MUX: each term is an AND of one input with its select pattern.

Loading the circuit…

A 4:1 MUX as a single part. Click sel to step through the inputs.
  • Turn on only d2. The light comes on only when sel is 2.
  • Press Slow motion and change sel, to see the output follow the new input.
Challenge: 4:1 multiplexer from gates →Turn the equation above into gates, and earn XP.

A MUX can make any function

A MUX is also a programmable logic block, since it's really a look-up table: put the truth table's outputs on the data inputs, and the select lines read them back. FPGAs are built on this idea (Chapter 18).

A 4:1 MUX has two select lines but can handle a 3-variable function. Use two variables as selects. For each select pattern, what's left is a function of the third variable: 0, 1, c or c'.

Worked example: F(a, b, c) = Σm(1, 2, 6, 7) with a 4:1 MUX

Use a and b as select lines. What goes on each data input?

  1. ab = 00 covers minterms 0 and 1. F is 0 then 1, so F = c.
  2. ab = 01 covers minterms 2 and 3. F is 1 then 0, so F = c'.
  3. ab = 10 covers minterms 4 and 5. F is 0 then 0, so F = 0.
  4. ab = 11 covers minterms 6 and 7. F is 1 then 1, so F = 1.

Answer:d₀ = c, d₁ = c', d₂ = 0, d₃ = 1

Loading the circuit…

The worked example, wired up.
  • Set a, b, c to 1, 1, 0, which is minterm 6: the light comes on.
  • Set them to 1, 0, 1, which is minterm 5: it goes off.
Practice

How many 2:1 MUXes make an 8:1 MUX?

Decoders and DEMUX

A decoder does the opposite of an encoder: n input bits light up exactly one of 2ⁿ outputs. It's how a memory chip selects one row, and how a processor picks which unit an instruction uses.

Loading the circuit…

A 2:4 decoder. One light is on at a time.
  • Click code to count from 0 to 3 and watch the light step along.

Each output of a decoder is one minterm. So a decoder plus OR gates can build any function, because a sum of minterms is all you need.

Loading the circuit…

A full adder from a 3:8 decoder and two ORs: sum = Σm(1, 2, 4, 7) and carry = Σm(3, 5, 6, 7).
  • Set abc to 7. Both lights come on, because 1 + 1 + 1 = 11 in binary.

A DEMUX is the same circuit with a different job: it routes one data line to one of many outputs. Tie the data to 1 and it's a decoder, as you saw in the animation.

Practice

How many 3:8 decoders make a 4:16 decoder, ignoring any inverter on the enable?

Encoders and priority encoders

An encoder goes the other way: of 2ⁿ input lines, whichever is on gets turned into its n-bit number. A plain encoder assumes exactly one input is on. If two are on, its output is nonsense.

A priority encoder fixes that: the highest-numbered active input wins, and a valid output says whether any input is active at all. Interrupt controllers work this way, and so do keyboard scanners.

Loading the circuit…

A 4:2 priority encoder.
  • Turn on i1, then i2. The code jumps to 2 and stays there, whatever i1 does.
  • Turn everything off. The code reads 0, the same as if i0 were on, so only valid tells them apart.
Practice

In a 4:2 priority encoder where the highest input wins, inputs i0 and i2 are on. What's the output?

Code converters

Chapter 4 introduced several codes. A code converter is just a combinational circuit from one to another. You design it like anything else: write the truth table, use don't-cares for patterns that can't occur, then minimise each output.

Loading the circuit…

BCD to Excess-3: add 3. Some conversions really are this short.

The one you'll see most often drives a seven-segment display, with one output per segment.

Loading the circuit…

A BCD to seven-segment decoder. Click the number to count from 0 to 9.
  • Past 9 the display goes blank, because this decoder treats 10 to 15 as invalid.
Challenge: BCD to 7-segment →Build the decoder yourself, one segment at a time.

Exam problems on these blocksGATE: fine to skip at first

To turn a 2ⁿ:1 MUX into an (n + 1)-variable function, use the method above. The same idea stacks: with a 2:1 MUX, any function of two variables can be built if you may feed in a variable and its inverse.

FunctionWith one 2:1 MUX, select = a
NOT ad₀ = 1, d₁ = 0
a AND bd₀ = 0, d₁ = b
a OR bd₀ = b, d₁ = 1
a XOR bd₀ = b, d₁ = b'
So a 2:1 MUX is functionally complete, if constants and inverted inputs are available.
Practice · GATE-style

How many select lines does a 32:1 MUX have?

Practice · GATE-style

How many 4:1 MUXes make a 64:1 MUX, in a full tree?

Practice · GATE-style

A 2:1 MUX has select a, d₀ = b and d₁ = b'. What's its output?

Practice · GATE-style

How many 2:4 decoders with enable make a 4:16 decoder?

Was this chapter helpful?