Decoders, Encoders, Multiplexers

Why This Matters

A 32-register integer register file needs a 5-to-32 decoder to choose exactly one destination register on write. The same datapath usually needs a 32-to-1 multiplexer, or a tree of smaller multiplexers, to choose which register value reaches an ALU input.

These circuits are the addressing and routing fabric beneath instruction execution. A memory address does not magically find a byte cell. A decoder turns address bits into one-hot select lines; multiplexers and tri-state gates move one selected value without mixing it with thirty-one others.

Core Definitions

Decoders Turn Binary Indices into One-Hot Wires

A decoder implements equality tests against all possible input values. For a 3-to-8 decoder with input bits a2 a1 a0, the active output is indexed by the unsigned value 4*a2 + 2*a1 + a0.

The Boolean equations are products of literals. For the 3-to-8 decoder:

y0 = ~a2 & ~a1 & ~a0
y1 = ~a2 & ~a1 &  a0
y2 = ~a2 &  a1 & ~a0
y3 = ~a2 &  a1 &  a0
y4 =  a2 & ~a1 & ~a0
y5 =  a2 & ~a1 &  a0
y6 =  a2 &  a1 & ~a0
y7 =  a2 &  a1 &  a0

For input 101, only y5 is true:

a2=1, a1=0, a0=1

y5 = 1 & ~0 & 1 = 1
y4 = 1 & ~0 & ~1 = 0
y7 = 1 &  0 & 1 = 0

The one-hot property can be written as two invariants. First, at least one output is high. Second, no two different outputs are high.

Decoders are often built with an enable input. If enable=0, all outputs are inactive. If enable=1, the normal one-hot property holds.

enable=0, address=101 -> y7...y0 = 00000000
enable=1, address=101 -> y7...y0 = 00100000

That enable pin matters when composing larger decoders from smaller ones. A 4-to-16 decoder can be built from two 3-to-8 decoders. The high address bit enables the upper or lower half, and the low three bits choose within that half.

Multiplexers Select One Data Input

A 4-to-1 mux has four data inputs, two select inputs, and one output.

Its Boolean equation is a sum of gated inputs:

This equation is a decoder followed by AND gates and one OR gate. The select bits create a one-hot mask, and that mask passes exactly one data input.

A mux can also be written as code:

#include <stdint.h>

uint8_t mux4(uint8_t d0, uint8_t d1, uint8_t d2, uint8_t d3, uint8_t sel) {
    switch (sel & 3) {
        case 0: return d0;
        case 1: return d1;
        case 2: return d2;
        default: return d3;
    }
}

For bit-level hardware, the same selection happens in parallel for every bit of a word. A 32-bit 4-to-1 mux is 32 copies of the 1-bit mux sharing the same s1 s0 select wires.

Worked byte example:

d0 = 0x3C = 00111100
d1 = 0xA5 = 10100101
d2 = 0x17 = 00010111
d3 = 0xE0 = 11100000
sel = 2  = 10

out = d2 = 0x17 = 00010111

A mux tree reduces fan-in. An 8-to-1 mux can be built as two 4-to-1 muxes feeding one 2-to-1 mux. Select bits s1 s0 choose within each group, and s2 chooses the lower or upper group. Delay grows with the number of tree levels, roughly $O(\log k)$ for $k$ inputs in a balanced tree.

Demultiplexers Route One Input Outward

A demux is the mirror image of a mux for control flow. One input enters; the select field chooses which output receives it.

For a 1-to-4 demux:

y0 = input & ~s1 & ~s0
y1 = input & ~s1 &  s0
y2 = input &  s1 & ~s0
y3 = input &  s1 &  s0

If input=1 and s1 s0 = 10, then y2=1 and the rest are 0. If input=0, every output is 0 regardless of the select bits.

Demuxes appear in write paths. A write-data bus carries the value. A decoder or demux-derived write-enable vector chooses which storage element captures it on the clock edge.

Example with four 8-bit registers:

write_data = 0xB6 = 10110110
write_reg  = 2    = 10
write_en   = 1

decoder output w3...w0 = 0100

before:
R0=0x11 R1=0x22 R2=0x33 R3=0x44

after rising clock edge:
R0=0x11 R1=0x22 R2=0xB6 R3=0x44

The data value was physically present near every register input. Only register 2 had its write-enable asserted, so only register 2 changed state.

Priority Encoders Compress Requests

A plain encoder is the inverse of a decoder only when exactly one input is active. Real machines often receive multiple requests at once: interrupt lines, cache miss responses, DMA channels, or issue queue entries. A priority encoder resolves the conflict by choosing one active index.

Assume input vector r7...r0, with r7 highest priority. The output is (valid, index).

A compact behavioral model is:

#include <stdint.h>

struct enc_result {
    uint8_t valid;
    uint8_t index;
};

struct enc_result prienc8(uint8_t r) {
    for (int i = 7; i >= 0; --i) {
        if ((r >> i) & 1) {
            return (struct enc_result){1, (uint8_t)i};
        }
    }
    return (struct enc_result){0, 0}; // index ignored when valid=0
}

For r = 0b00100011, the loop sees bits 7 and 6 as 0, bit 5 as 1, and returns (valid=1, index=5). The lower active bits 1 and 0 do not affect the result.

Interrupt controllers use this pattern. If a timer interrupt and a disk interrupt arrive in the same cycle, the priority encoder chooses the configured higher-priority request and exposes its vector number to the control logic.

Address Decoding for Register Files and ROMs

A register file read port is often modeled as an array read, but the hardware is a selection network. For 32 registers, a 5-bit read address selects one of 32 stored words. The read side can be implemented as a 32-to-1 mux per output bit. The write side uses a 5-to-32 decoder for write enables.

Consider 8 registers of 1 byte each:

address bits: a2 a1 a0
read address: 011
register contents:
R0=0x40  R1=0x41  R2=0x42  R3=0x43
R4=0x44  R5=0x45  R6=0x46  R7=0x47

decoder one-hot y7...y0 = 00001000
read data = R3 = 0x43 = 01000011

A ROM uses the same selection idea. If a ROM has 64 bytes, a 6-bit address selects one of 64 byte locations. A small 16-byte ROM can be drawn as a decoder plus fixed wiring:

addr = 0x0A = 1010
16-word decoder output y15...y0 = 0000010000000000
ROM[0x0A] = 0x6D = 01101101

Byte lane selection adds another layer. A 32-bit word memory with byte addresses uses low address bits to choose a byte inside the word, while higher bits choose the row.

byte address = 0x00000013 = binary ...0001 0011
word index   = address >> 2 = 0x00000004
byte lane    = address & 3  = 3

word at index 4 = 0xA1B2C3D4
little-endian bytes by lane:
lane 0 = 0xD4
lane 1 = 0xC3
lane 2 = 0xB2
lane 3 = 0xA1

selected byte = 0xA1

The row decoder selects word index 4. A 4-to-1 byte mux selects lane 3.

One-Bit ALU Selection with a Mux

A simple 1-bit ALU can compute several candidate results in parallel, then use a mux to choose the operation result. For inputs a, b, and carry-in cin, define:

and_out = a & b
or_out  = a | b
xor_out = a ^ b
sum_out = a ^ b ^ cin
cout    = (a & b) | (a & cin) | (b & cin)

The operation select chooses which candidate becomes result.

#include <stdint.h>

uint8_t alu1(uint8_t a, uint8_t b, uint8_t cin, uint8_t op, uint8_t *cout) {
    a &= 1; b &= 1; cin &= 1; op &= 3;

    uint8_t candidates[4];
    candidates[0] = a & b;          // 00: AND
    candidates[1] = a | b;          // 01: OR
    candidates[2] = a ^ b;          // 10: XOR
    candidates[3] = a ^ b ^ cin;    // 11: SUM

    *cout = (a & b) | (a & cin) | (b & cin);
    return candidates[op];
}

Worked case:

a=1, b=1, cin=0
AND=1, OR=1, XOR=0, SUM=0, cout=1

op=00 -> result=1
op=10 -> result=0
op=11 -> result=0, carry-out=1

A 32-bit ALU replicates this slice 32 times. The mux select wires are shared by all bit positions, while the carry chain connects cout from bit i to cin of bit i+1 for addition.

Tri-State Buffers and Shared Buses

A shared bus is a set of wires driven by several possible sources. A tri-state buffer lets a device connect to the bus only when its enable is active.

For a single bus wire:

enable=0 -> output=Z
enable=1 -> output=input

Z is high impedance, not logic 0. If all drivers are Z, the bus value is not a valid driven 0 or 1 unless there is a pull-up, pull-down, or keeper circuit. If two drivers are enabled and disagree, the circuit has contention.

Example with four 8-bit registers sharing one bus:

R0=0x12, R1=0x34, R2=0x56, R3=0x78
select source = R2
decoder enables e3...e0 = 0100

R0 driver: Z
R1 driver: Z
R2 driver: 0x56 = 01010110
R3 driver: Z

bus = 0x56

Bad enable pattern:

e3...e0 = 0110
R1 drives 0x34 = 00110100
R2 drives 0x56 = 01010110

bit positions 6, 5, 1 differ
bus contention occurs

Inside many modern chips, synthesis tools replace internal tri-state buses with mux networks, but the logical constraint remains: exactly one source should drive a shared value at a time.

Main Theorem

Example: implement majority(a,b,c), which is 1 when at least two inputs are 1. Use a b c as select bits.

When abc=110, the mux selects d6, so the output is 1.

Common Confusions

Exercises

References

Canonical:

• Charles Petzold, Code: The Hidden Language of Computer Hardware and Software, 2nd ed. (2022), ch. 10-14 — relay logic, binary addition, memory, and selection circuits
• David A. Patterson and John L. Hennessy, Computer Organization and Design: The Hardware/Software Interface, 5th ed. (2013), Appendix B — combinational logic, decoders, multiplexers, and ALU construction
• J. Clark Scott, But How Do It Know? The Basic Principles of Computers for Everyone (2009), ch. 3-8 — gates, buses, registers, and CPU datapath routing
• M. Morris Mano and Michael D. Ciletti, Digital Design, 5th ed. (2013), ch. 4 ; combinational logic circuits including decoders, encoders, multiplexers, and demultiplexers
• David Money Harris and Sarah L. Harris, Digital Design and Computer Architecture, 2nd ed. (2012), ch. 2.8-2.10 and ch. 5.2 ; combinational building blocks, tri-state buffers, and datapath components

Accessible:

• Noam Nisan and Shimon Schocken, The Elements of Computing Systems, 2nd ed. (2021), ch. 1-3 ; hands-on construction of muxes, demuxes, adders, registers, and memory
• MIT OpenCourseWare, 6.004 Computation Structures, combinational logic and digital abstraction notes ; worked gate-level examples of decoders and multiplexers
• University of Washington CSE 370 lecture notes, combinational logic modules ; compact truth tables and circuit diagrams for muxes, decoders, and encoders

Next Topics

• /computationpath/adders-and-arithmetic-logic
• /computationpath/registers-and-clocked-state
• /computationpath/memory-addressing
• /computationpath/cpu-datapath-control