Multiplexers, decoders and encoders

Some circuits do not calculate: they choose and route. Processors are full of them.

Multiplexer (MUX)

A multiplexer has 2ⁿ data inputs, n select inputs and one output. The select bits, read as a binary number, say which data input reaches the output: a digital switch. A 4-to-1 MUX with data D0 to D3 and select S1 S0 computes

Y = S1'S0'·D0 + S1'S0·D1 + S1S0'·D2 + S1S0·D3

Each AND term is "open" for exactly one select value. A processor uses multiplexers to pick which register goes to the adder, or whether the next instruction address is "the next one" or a jump target.

def mux4(d, s1, s0):
    # The gate version of a 4-to-1 multiplexer.
    return ((1 - s1) & (1 - s0) & d[0]) | ((1 - s1) & s0 & d[1]) | (s1 & (1 - s0) & d[2]) | (s1 & s0 & d[3])

data = [1, 0, 0, 1]
for s in range(4):
    print("select", format(s, "02b"), "-> output", mux4(data, s >> 1, s & 1), " (the same as data[" + str(s) + "] =", str(data[s]) + ")")

majority = [0, 0, 0, 1, 0, 1, 1, 1]     # an 8-to-1 MUX holding a truth table
a, b, c = 1, 0, 1
print("majority(1, 0, 1) =", majority[a * 4 + b * 2 + c])

Any function from a MUX: connect the select inputs to the function's variables and each data input to that row's output (0 or 1). An 8-to-1 MUX is then a 3-input function, with no simplification needed: it is a lookup table, exactly how FPGAs implement logic.

A demultiplexer does the reverse: one input is sent to one of 2ⁿ outputs, chosen by the select bits.

Decoder and encoder

A decoder turns an n-bit number into 2ⁿ outputs, exactly one of which is 1 (one-hot). It picks one memory chip, one register or one row of memory from an address. Since each output is one minterm, a decoder plus an OR gate implements any sum of minterms.

An encoder does the reverse: 2ⁿ inputs, one of which is 1, become its n-bit number. A priority encoder allows several 1s and reports the highest one, for example to find which of several devices asking for attention is most urgent.

def decoder(bits):
    n = int(bits, 2)
    return [1 if k == n else 0 for k in range(2 ** len(bits))]

def priority_encoder(inputs):
    for k in range(len(inputs) - 1, -1, -1):    # the highest 1 wins
        if inputs[k]:
            return format(k, "03b")
    return "none"

print("decoder(101):", decoder("101"))
print("priority encoder, inputs 3 and 6 on:", priority_encoder([0, 0, 0, 1, 0, 0, 1, 0]))

Mark lesson complete