A decoder takes an $n$-bit input and asserts exactly one of its $2^n$ outputs. A demultiplexer (demux) takes one data line plus an $n$-bit select and routes the data to one of $2^n$ outputs (the others stay at 0). The two circuits share an internal structure — a demux is just a decoder whose data-line gates each output.

2-to-4 Decoder

1-to-4 Demultiplexer

A demux equals a decoder whose output is gated by a data input: $y_i = D \cdot \text{(decode of select)}_i$.

4-to-1 Multiplexer (the inverse of a demux)

A multiplexer reverses the demux: it has $2^n$ data inputs $D_0, D_1, D_2, D_3$, an $n$-bit select, and a single output $y$ which equals whichever data line the select points to. $y = D_{(\text{select})}$.

Three-way comparison (decoder, demultiplexer, multiplexer):

Duality. A demux and a MUX are inverse circuits — connect them back-to-back with the same select, and the data on $D_i$ at the demux input reappears unchanged at the MUX output. This is the basis of time-division multiplexing: many channels share one wire by alternating selects.

Decoder vs MUX. A decoder generates all $2^n$ minterms; a MUX uses minterms internally to select among inputs. Equivalently: a MUX is built from a decoder + AND gates + a big OR. So decoders are the building block; MUXes and demuxes are decoder-based variants — read-direction (MUX, $2^n$→1) vs. write-direction (demux, 1→$2^n$).

Shannon's expansion theorem decomposes any Boolean function on a chosen variable into two simpler "cofactor" pieces. It's the algebraic foundation of MUX-based logic synthesis, BDDs, and recursive function analysis.

Theorem (SOP form):

$f(x_1, x_2, \ldots, x_n) \;=\; \overline{x_1}\cdot f(0, x_2, \ldots, x_n) \;+\; x_1 \cdot f(1, x_2, \ldots, x_n)$

Theorem (POS / dual form):

$f(x_1, x_2, \ldots, x_n) \;=\; \bigl(x_1 + f(0, x_2, \ldots, x_n)\bigr) \cdot \bigl(\overline{x_1} + f(1, x_2, \ldots, x_n)\bigr)$

The two pieces are called the cofactors of $f$ with respect to $x_1$:

$\boxed{\,f \;=\; \overline{x_1}\,f_0 \;+\; x_1\,f_1\,}$

Connection to a 2-to-1 MUX — that's literally MUX2 with select $= x_1$, data inputs $f_0$ and $f_1$:

Recursive application — break a function down to a tree of MUXes:

$f \;=\; \overline{x_1}\bigl[\overline{x_2} f_{00} + x_2 f_{01}\bigr] + x_1\bigl[\overline{x_2} f_{10} + x_2 f_{11}\bigr]$

Each cofactor is itself expanded on the next variable, producing a binary tree with $2^n$ leaves (constants 0 or 1, equal to the truth-table values). This is a binary decision diagram (BDD) before any reduction.

Worked example. $f(w_1, w_2, w_3) = w_1 w_2 + \overline{w_1} w_3$. Expand on $w_1$:

• $f_0 = f|_{w_1 = 0} = (0)\cdot w_2 + (1)\cdot w_3 = w_3$
• $f_1 = f|_{w_1 = 1} = (1)\cdot w_2 + (0)\cdot w_3 = w_2$
• So $f = \overline{w_1}\,w_3 + w_1\,w_2$ — implementable with a 2-to-1 MUX: select $= w_1$, $D_0 = w_3$, $D_1 = w_2$. The original function vanishes into a single MUX with two raw-literal data inputs.

Useful identities & properties:

Where it shows up:

• MUX-based synthesis — implement any Boolean function with a tree of 2-to-1 MUXes by recursive Shannon expansion.
• BDDs / ROBDDs — every node of a BDD is a Shannon-expansion split on one variable. Variable ordering choice = which variable to expand at each level.
• Functional decomposition — to factor $f(x, y, \ldots) = g(h(x, \ldots), y, \ldots)$, examine cofactors and look for repeated patterns.
• Boolean differentiation — $\partial f / \partial x = f_0 \oplus f_1$. A variable is sensitized iff this is true; the basis of test-pattern generation in DFT.
• SAT solvers — DPLL search algorithm performs Shannon expansion on each chosen literal, branching the search tree.

Quick recipe: to express $f$ with a 2-to-1 MUX selected by $x_i$ — compute $f_0$ and $f_1$ by substitution, wire them as the two data inputs, wire $x_i$ as select. To go further (tree of MUXes), expand each cofactor on the next variable. The recursion bottoms out at the constants 0 and 1.

An encoder turns a one-of-$2^n$ one-hot signal into an $n$-bit binary index. A decoder does the reverse: it turns an $n$-bit binary index back into a one-hot signal. Connected back-to-back with the same width, they form an identity on valid one-hot inputs — exactly like a demux/MUX pair, but in the opposite direction.

$\text{one-hot}\;\xrightarrow{\;\text{encoder}\;}\;\text{binary index}\;\xrightarrow{\;\text{decoder}\;}\;\text{one-hot}$

Side-by-side block diagram (4-to-2 encoder → 2-to-4 decoder):

Truth-table round-trip — encoder squeezes 4 wires into 2; decoder expands them back. On valid one-hot inputs the round-trip is identity:

Back-to-back chain with a valid gate — the row in red shows why a plain encoder output is ambiguous: input 0001 and input 0000 both produce y = 00. To distinguish them, the encoder asserts an extra valid bit (= OR of all one-hot inputs), and the decoder uses it as enable so its outputs stay 0000 when no input was asserted:

Where this pair shows up:

• Address compression on a bus. A wide one-hot signal (say 16 device-request lines) is encoded to 4 bits, transmitted across a backplane, then decoded back at the destination. Saves wires and routing area.
• Interrupt vector. Many interrupt-request lines (one-hot) are encoded into a numeric vector index by a priority encoder; the CPU later decodes that index to look up the service routine — same encoder/decoder pair, with priority resolution added.
• Memory-mapped I/O. Address bits travel as a binary index; a chip-select decoder turns them back into one-hot enables for individual peripherals or memory banks.
• Bus arbitration. A priority encoder picks the winning request; a decoder re-asserts the matching grant line back to the requester.

Verilog — minimal back-to-back pair:

module binary_encoder_4to2(input [3:0] W, output reg [1:0] y, output valid);
  assign valid = |W;            // 1 if any input is asserted
  always @(*) case (W)
    4'b0001: y = 2'b00;
    4'b0010: y = 2'b01;
    4'b0100: y = 2'b10;
    4'b1000: y = 2'b11;
    default: y = 2'b00;         // ambiguous without 'valid'
  endcase
endmodule

module dec2to4(input [1:0] W, input En, output reg [3:0] Y);
  always @(*) case ({En, W})
    3'b100: Y = 4'b0001;
    3'b101: Y = 4'b0010;
    3'b110: Y = 4'b0100;
    3'b111: Y = 4'b1000;
    default: Y = 4'b0000;
  endcase
endmodule

module enc_dec_link(input [3:0] W, output [3:0] Y);
  wire [1:0] y;
  wire       valid;
  binary_encoder_4to2 enc(.W(W), .y(y), .valid(valid));
  dec2to4             dec(.W(y), .En(valid), .Y(Y));
endmodule

Footnote on the valid output. A plain (non-priority) encoder cannot tell "no input asserted" from "input 0 asserted" — both produce y = 00. The valid = OR-of-all-inputs bit fixes this: it gates the downstream decoder so the round-trip is correct even when no source line is active. For a priority encoder, valid doubles as the "any request pending" signal feeding the arbiter.

A multiplexer (MUX) picks one of $2^n$ data sources and routes it to a single output. A demultiplexer (DEMUX) does the reverse: it takes one data input and steers it to one of $2^n$ outputs (the rest stay at 0). Connected back-to-back with a shared select, MUX→DEMUX makes a perfect time-division multiplexed (TDM) link: many channels share one wire, alternating in time.

$D_0 \ldots D_{2^n-1}\;\xrightarrow{\;\text{MUX}\;}\;\text{1 wire}\;\xrightarrow{\;\text{DEMUX}\;}\;Y_0 \ldots Y_{2^n-1}$

Side-by-side block diagram (4-to-1 MUX → 1-to-4 DEMUX):

Round-trip table — with the same select on both sides, $Y_i = D_i$ for the selected slot, all other $Y_j = 0$ (the demux floor):

TDM timing — rotate sel through 00 → 01 → 10 → 11 in successive time slots; each source $D_i$ owns the wire for one slot, and the demux drops it onto the matching $Y_i$:

Where this pair shows up:

• Time-division multiplexing (TDM). Multiple low-rate channels share one high-rate wire. The transmitter MUXes; the receiver DEMUXes with the same rotating select. Used in T1/E1 telephony, serial UART framing, I²S audio.
• ADC channel sharing. One physical ADC samples many sensor lines via an analog MUX; the digital side DEMUXes the samples into per-channel buffers.
• Memory bus arbitration. Several masters share one memory data bus through a MUX; the destination registers behave as a DEMUX, capturing the word into the correct latch on the matching cycle.
• Pipeline operand routing. ALUs use a MUX to pick the operand source (register file, immediate, forwarded value); a DEMUX-shaped write-enable network steers the result back to the right register.

Verilog — minimal back-to-back pair:

module mux4to1(input [3:0] D, input [1:0] sel, output reg out);
  always @(*) case (sel)
    2'b00: out = D[0];
    2'b01: out = D[1];
    2'b10: out = D[2];
    2'b11: out = D[3];
  endcase
endmodule

module demux1to4(input in, input [1:0] sel, output reg [3:0] Y);
  always @(*) begin
    Y = 4'b0000;
    case (sel)
      2'b00: Y[0] = in;
      2'b01: Y[1] = in;
      2'b10: Y[2] = in;
      2'b11: Y[3] = in;
    endcase
  end
endmodule

module tdm_link(input [3:0] D, input [1:0] sel, output [3:0] Y);
  wire bus;                              // the shared 1-bit wire
  mux4to1   tx(.D(D),  .sel(sel), .out(bus));
  demux1to4 rx(.in(bus), .sel(sel), .Y(Y));
endmodule

Note. The MUX/DEMUX pair carries data (one wire, value-bearing); the encoder/decoder pair carries an index (binary number, position-bearing). Both pairs are inverse circuits, but they operate on different abstractions: data routing vs. address translation.