Combinational Building Blocks

Lessons 1 and 2 built the equations; this lesson builds the small combinational parts those equations get assembled into. Muxes, decoders, priority encoders, and comparators show up inside almost every datapath this course goes on to build — a mux selecting which value a register loads, a decoder turning an opcode into one-hot control signals, a priority encoder arbitrating between simultaneous requests. Each one is worth knowing both as a Verilog idiom and as a specific, recognizable shape in a synthesized netlist.

Reading time: about 8 minutes.

3.1 Mux trees: from 2:1 up to 8:1

A 2:1 multiplexer is the smallest useful building block in this lesson, and every wider mux in this section is built from it, directly or conceptually. A single select bit chooses between two inputs:

module mux2 #(
    parameter WIDTH = 8
) (
    input  wire [WIDTH-1:0] a,
    input  wire [WIDTH-1:0] b,
    input  wire             sel,
    output wire [WIDTH-1:0] y
);
    assign y = sel ? b : a;
endmodule

An 8:1 mux needs three select bits and can be written two ways that describe the identical function. The first builds a literal tree: four 2:1 muxes decide between pairs using sel[0], two more decide between those results using sel[1], and one final mux picks between the last two using sel[2] — three levels of 2:1 muxes for eight inputs, matching log2(8) = 3.

The second way writes the same 8:1 function as a single case statement over the full select value, with no mux2 instances at all:

case (sel)
    3'd0: out = in0;  3'd1: out = in1;
    3'd2: out = in2;  3'd3: out = in3;
    3'd4: out = in4;  3'd5: out = in5;
    3'd6: out = in6;  3'd7: out = in7;
endcase

Both describe the identical truth table, and both are correct, but they do not necessarily produce the same netlist. Yosys, for example, turns the 8-way case into a parallel select (a decode of sel ANDed with each input and ORed together, with no 2:1 mux cells at all), while the explicit tree maps to 2:1 mux cells. Choose the form for readability, and check the synthesized netlist when structure or timing matters, since the choice between writing the tree explicitly and writing a case is a readability decision first, not a performance one. The explicit tree is worth knowing because it is how a mux actually gets built physically, and because some wide, irregular select logic cannot be expressed cleanly as a single flat case and has to be built up from smaller muxes by hand.

Simulating the tree-built 8:1 mux (WIDTH = 4, exercising every one of the eight select values) confirms it reproduces the expected input exactly for every selection:

MUX OK sel=0 -> out=0
MUX OK sel=3 -> out=3
MUX OK sel=7 -> out=7
ALL TESTS PASSED

3.2 Decoders

A decoder turns a binary address into a one-hot output: exactly one output bit set, chosen by the address, every other bit 0. An ADDR_W-bit address decodes to 2^ADDR_W outputs, and the whole function is a single shift:

module decoder #(
    parameter ADDR_W = 3
) (
    input  wire [ADDR_W-1:0]      addr,
    output wire [(1<<ADDR_W)-1:0] onehot
);
    assign onehot = {{((1<<ADDR_W)-1){1'b0}}, 1'b1} << addr;
endmodule

A decoder is, structurally, the mirror image of the mux tree from section 3.1: a mux tree takes many data inputs and one select input and narrows to one data output; a decoder takes one address input and widens to many one-hot outputs. The two show up together constantly — a decoder picking which register in a file gets written, a mux picking which register's value gets read back out — and an interviewer who asks for one is very often checking whether a candidate also understands the other.

3.3 Priority encoders

A priority encoder is the inverse direction of a decoder with a twist: given a bus of request bits where more than one bit can be set at once, it reports the index of the highest-priority set bit, plus a valid flag for the case where no bit is set at all. The width-parameterized version scans from bit 0 upward and lets the last match in the loop win, so the highest-indexed set bit is the one reported:

module prio_enc #(
    parameter WIDTH = 8,
    parameter IDX_W = 3
) (
    input  wire [WIDTH-1:0] req,
    output reg  [IDX_W-1:0] grant_idx,
    output reg              valid
);
    integer i;
    always @(*) begin
        valid     = |req;
        grant_idx = {IDX_W{1'b0}};
        for (i = 0; i < WIDTH; i = i + 1) begin
            if (req[i])
                grant_idx = i[IDX_W-1:0];
        end
    end
endmodule

Two synthesis points are worth knowing cold. First, valid and every bit of grant_idx are assigned on every path through the always block before the loop runs, which is what keeps this combinational and latch-free — an unassigned branch in an always @(*) block is the single most common cause of an accidentally inferred latch, and it is worth checking for explicitly every time a combinational block is written. Second, the for loop is unrolled entirely at synthesis time into WIDTH parallel comparisons feeding a chain of muxes; no actual loop or counter exists in the resulting hardware. Verified against every one of the 256 possible 8-bit request patterns, the encoder reports the correct highest-priority index and valid flag in every case:

PE OK across all 256 request patterns
ALL TESTS PASSED

3.4 Magnitude comparators

A magnitude comparator reports whether one bus is greater than, equal to, or less than another, and in Verilog it is simply the relational operators applied to vectors:

module comparator #(
    parameter WIDTH = 8
) (
    input  wire [WIDTH-1:0] a,
    input  wire [WIDTH-1:0] b,
    output wire             gt,
    output wire             eq,
    output wire             lt
);
    assign gt = (a > b);
    assign eq = (a == b);
    assign lt = (a < b);
endmodule

Under the hood this synthesizes to essentially one subtractor (a - b) whose borrow, the carry out of the subtraction, gives a < b for these unsigned operands, not three unrelated comparison circuits. Looking at the difference's top bit would be wrong here: with 8-bit operands, 200 - 10 = 190 has its top bit set even though a > b. eq can also be built cheaply as a bitwise XNOR of a and b that is then AND-reduced, &(a ~^ b), which some synthesis tools prefer because it avoids building unneeded subtractor logic when only equality is actually used downstream. Writing the three comparisons as plain relational operators, as above, leaves that choice to the synthesis tool rather than committing to one structure by hand.

3.5 Interview questions

How many levels does a binary mux tree need for N inputs? log2(N) levels of 2:1 muxes — three levels for 8:1, four for 16:1 — because each level halves the number of candidates still in play.

Does writing a mux as a case statement instead of an explicit tree of 2:1 muxes change what gets synthesized? The function is identical, but the netlist can differ. Yosys, for example, synthesizes an 8-way case as a parallel decode-and-OR select with no 2:1 mux cells, while an explicit tree maps to 2:1 muxes. Pick the form for readability, and check the netlist if structure or timing matters.

How is a priority encoder different from a decoder? A decoder takes one binary address and produces many one-hot outputs. A priority encoder takes many request bits, which can be set simultaneously, and produces one index — the highest-priority request — plus a valid flag for the no-requests case. They move in opposite directions between a single index and a wide one-hot-like bus.

What is the most common way a combinational priority encoder accidentally infers a latch? Leaving a signal unassigned on some path through the always @(*) block — for instance, forgetting to give grant_idx a default value before the loop, so that when req is all zero, no branch assigns it and the synthesis tool has to add storage to hold the previous value.

What hardware does a > b on two vectors actually synthesize to? Essentially a subtractor. For unsigned operands the borrow out of a - b gives a < b, and a zero check on the difference gives equality; the difference's top bit is not a valid sign for unsigned values. For signed operands the sign bit must be corrected for overflow.