Combinational Building Blocks

Chapter 1 showed that any truth table can be built from NOT, AND and OR gates. In practice, digital designers rarely think in single gates. They think in a handful of standard building blocks, each with a clear job: choose one of several signals, recognise a code, compare two numbers, add them. This chapter derives each of those blocks from its truth table, then looks at two practical questions: how to make the logic smaller (Karnaugh maps), and how long it takes for the answer to appear (propagation delay).

All blocks here are combinational: the outputs depend only on the current inputs. When an input changes, the outputs change shortly afterwards and there is no memory of the past. That "shortly afterwards" turns out to be the most important number in FPGA design, so keep it in mind.

A multiplexer (mux) is a digitally controlled switch. A 2:1 mux has two data inputs \(d_0, d_1\), one select input \(s\) and one output: if \(s = 0\) the output copies \(d_0\), otherwise \(d_1\). Writing a product term for each case gives

A 4:1 mux needs two select bits \(s_1 s_0\), read as a binary number 0–3, and has one product term per data input. Each term contains the minterm of the select code that picks it:

In general a \(2^k\):1 mux needs \(k\) select bits. Multiplexers are everywhere in hardware: choosing which register feeds an adder, which source drives a bus, which value is shown on the LEDs (the first_lights design of Chapter 14 ends in a mux controlled by a switch).

A decoder turns a \(k\)-bit binary code into \(2^k\) separate wires, exactly one of which is 1. This is called a one-hot output. Output \(i\) is simply the minterm of code \(i\): for a 2-to-4 decoder, \(y_0 = \overline{a_1}\,\overline{a_0}\), \(y_1 = \overline{a_1}\,a_0\), \(y_2 = a_1\,\overline{a_0}\), \(y_3 = a_1\,a_0\). Decoders select one memory word out of many, one device on a bus, or one digit of a display. Often an enable input is ANDed into every output so that all outputs can be forced to 0.

An encoder does the reverse: from \(2^k\) input wires it produces the \(k\)-bit index of the one that is active. A plain encoder assumes only one input is 1 at a time. A priority encoder handles any input pattern by reporting the highest-numbered active input, plus a valid flag for the case where none is active. For 4 inputs:

Here x means "either value", which compresses 16 rows into 5. Reading the table: \(q_1 = r_3 + r_2\), \(q_0 = r_3 + \overline{r_2}\,r_1\), \(\text{valid} = r_3 + r_2 + r_1 + r_0\). Priority encoders arbitrate between several requests, for example deciding which of several interrupt sources is served first.

Two bits are equal exactly when their XOR is 0, that is when their XNOR is 1. Two \(n\)-bit words are equal when every pair of bits is equal, so an equality comparator is \(n\) XNOR gates followed by one wide AND:

A magnitude comparator (\(A > B\)) works like comparing two decimal numbers by eye: scan from the most significant digit; the first position where they differ decides. For unsigned numbers, \(A > B\) if at some position \(i\) we have \(a_i = 1,\ b_i = 0\) and all higher bits are equal:

In practice, as Section 6 shows, hardware usually computes \(A - B\) with an adder and looks at the sign or the carry: \(A \ge B\) (unsigned) exactly when the subtraction produces a carry out. Comparing against a constant is cheaper still: count == 9 is just a single AND of the counter bits, some of them inverted.

Adding two single bits \(a + b\) gives a result from 0 to 2, which needs two bits: a sum bit \(s\) (weight 1) and a carry bit \(c\) (weight 2). The truth table reveals two gates you already know:

This is called a half adder because it is only half of what we need. To add multi-bit numbers, each column must also add the carry coming in from the column to its right, exactly like the "carry the one" of school arithmetic. A full adder adds three bits \(a, b, c_\text{in}\), and its result 0–3 still fits in two bits:

The sum is 1 when an odd number of inputs is 1, which is a chain of XORs. The carry is 1 when at least two of the three inputs are 1: it is the majority function from Chapter 1.

The second form of the carry has a useful reading. The column generates a carry by itself when \(g = ab = 1\), and it propagates an incoming carry when \(p = a \oplus b = 1\)(exactly one of \(a, b\) is 1, so adding \(c_\text{in}\) overflows the column). The two forms agree on all eight rows; the difference is the case \(a = b = 1\), already covered by \(g\). Note that \(p\) also appears in the sum, \(s = p \oplus c_\text{in}\), so one XOR gate serves both. A full adder is therefore two half adders plus an OR gate.

To add two \(N\)-bit numbers, put \(N\) full adders side by side and connect each carry out to the next carry in. This is a ripple-carry adder. It is small (one full adder per bit) and obviously correct, because it is long addition done in hardware.

Its weakness is speed. Each gate needs a small time to respond, its propagation delay (Section 8). The sum bit \(s_{N-1}\) is not final until \(c_{N-1}\) is, and \(c_{N-1}\) may depend on every bit below it. The worst case is something like \(0\text{x}FF + 0\text{x}01\), where every column propagates and a carry born in bit 0 must travel all the way to the top. Counting gate delays in our full adder (with \(c_\text{in} = 0\)): \(p, g\) are ready after 1 delay, \(c_1 = g_0\) after 2, each further carry needs an AND and an OR (+2), and the last sum one XOR (+1):

The program below simulates the adder gate by gate, every gate with one unit of delay. Watch each sum bit flip to 1 and then back to 0 as the carry passes: these temporary wrong values are called glitches. The histogram shows that most input changes settle quickly, but a synchronous circuit (Chapter 3) must always wait for the worst case.

The same adder also subtracts. Since \(-B = \overline{B} + 1\) in two's complement (Chapter 1), feed it \(\overline{B}\) instead of \(B\) and set \(c_\text{in} = 1\): \(A - B = A + \overline{B} + 1\). A row of XOR gates controlled by a single sub signal (\(b_i \oplus \text{sub}\), with \(c_\text{in} = \text{sub}\)) turns the adder into an adder/subtractor.

Simplifying sum-of-products expressions with algebra (as for the majority function in Chapter 1) works, but it depends on spotting the right steps. A Karnaugh map (K-map) makes the steps visible. It is the truth table redrawn as a grid, with the rows and columns ordered in Gray code (00, 01, 11, 10) so that any two neighbouring cells differ in exactly one variable. The left and right edges are also neighbours, and so are the top and bottom.

Why it works: two adjacent 1-cells differ in one variable \(x\), so their minterms combine as \(P\,x + P\,\overline{x} = P\) and the variable disappears. A rectangle of \(2^k\) cells removes \(k\) variables. The recipe:

1. Fill in the 1s from the truth table.
2. Cover every 1 with rectangles of size 1, 2, 4, 8… cells, as large as possible (wrap-around allowed). Overlap is fine.
3. Use as few rectangles as possible.
4. Each rectangle becomes one product term: keep only the variables that are constant across it.

Example: \(F(a,b,c,d) = \sum m(0,1,2,5,8,9,10)\), where \(\sum m(\ldots)\) lists the rows (minterm numbers, \(8a + 4b + 2c + d\)) where \(F = 1\). The direct sum of products has seven 4-input terms.

Read each group by asking which variables do not change inside it. In the corner group, \(a\) and \(c\) take both values while \(b = 0\) and \(d = 0\) throughout, giving \(\overline{b}\,\overline{d}\). Cells you do not care about (input codes that can never occur) can be marked x and treated as 1 or 0, whichever makes groups larger.

K-maps are practical up to four or five variables. You will not use them to design FPGA logic, because the synthesis tools minimise far better and, in an FPGA, any function of up to six inputs costs one LUT regardless of how simple it is. They are still the best way to understand what minimisation does, and they show up whenever you reason about a small piece of control logic by hand.

A real gate does not respond instantly. After an input changes, the output stays at its old value for a short time, may wobble, and then settles. Two numbers describe this:

• The propagation delay \(t_{pd}\): the longest time from an input change until the output is guaranteed to be stable at its new value.
• The contamination delay \(t_{cd}\): the shortest time from an input change until the output might start to change. Before that, the old value is still guaranteed.

For a whole combinational circuit, add up the delays along each path from an input to an output. The path with the largest total is the critical path; it sets the circuit's \(t_{pd}\). The shortest path sets its \(t_{cd}\):

In the ripple-carry adder the critical path is the carry chain: from \(a_0\) through every carry to \(s_{N-1}\). Between \(t_{cd}\) and \(t_{pd}\) the outputs may glitch, as the simulation showed. In an FPGA, delay comes as much from the programmable wiring between LUTs as from the LUTs themselves: on the order of 0.1 ns per LUT, and several times that per routing hop (Chapter 5).

Here are the 4:1 multiplexer and the full adder written in Verilog and VHDL, followed by a 4-bit ripple-carry adder built from four full adders. The syntax is the subject of Part III (Chapters 7–9); for now, compare each line with the equations above. The mux is the sum-of-products equation of Section 2, the full adder is the \(s\) and \(c_\text{out}\) equations of Section 5, and the ripple adder wires the carries together as in the figure of Section 6.

// 4:1 multiplexer: the select code s picks one of four data inputs.
// Sum-of-products form, one product term per input.
module mux4 (
    input  wire [3:0] d,     // data inputs d[0]..d[3]
    input  wire [1:0] s,     // select
    output wire       y
);
    assign y = (d[0] & ~s[1] & ~s[0])
             | (d[1] & ~s[1] &  s[0])
             | (d[2] &  s[1] & ~s[0])
             | (d[3] &  s[1] &  s[0]);
endmodule

-- 4:1 multiplexer: the select code s picks one of four data inputs.
-- Sum-of-products form, one product term per input.
library ieee;
use ieee.std_logic_1164.all;

entity mux4 is
    port (
        d : in  std_logic_vector(3 downto 0);   -- data inputs d(0)..d(3)
        s : in  std_logic_vector(1 downto 0);   -- select
        y : out std_logic
    );
end entity;

architecture sop of mux4 is
begin
    y <= (d(0) and not s(1) and not s(0))
      or (d(1) and not s(1) and     s(0))
      or (d(2) and     s(1) and not s(0))
      or (d(3) and     s(1) and     s(0));
end architecture;

// One-bit full adder: a + b + cin = 2*cout + sum
module full_adder (
    input  wire a,
    input  wire b,
    input  wire cin,
    output wire sum,
    output wire cout
);
    assign sum  = a ^ b ^ cin;                  // odd number of 1s
    assign cout = (a & b) | (cin & (a ^ b));    // generate, or propagate a carry
endmodule

-- One-bit full adder: a + b + cin = 2*cout + sum
library ieee;
use ieee.std_logic_1164.all;

entity full_adder is
    port (
        a    : in  std_logic;
        b    : in  std_logic;
        cin  : in  std_logic;
        sum  : out std_logic;
        cout : out std_logic
    );
end entity;

architecture rtl of full_adder is
begin
    sum  <= a xor b xor cin;                     -- odd number of 1s
    cout <= (a and b) or (cin and (a xor b));    -- generate, or propagate a carry
end architecture;

// 4-bit ripple-carry adder: four full adders, each carry feeding the next.
module ripple4 (
    input  wire [3:0] a,
    input  wire [3:0] b,
    input  wire       cin,
    output wire [3:0] sum,
    output wire       cout
);
    wire c1, c2, c3;

    full_adder fa0 (.a(a[0]), .b(b[0]), .cin(cin), .sum(sum[0]), .cout(c1));
    full_adder fa1 (.a(a[1]), .b(b[1]), .cin(c1),  .sum(sum[1]), .cout(c2));
    full_adder fa2 (.a(a[2]), .b(b[2]), .cin(c2),  .sum(sum[2]), .cout(c3));
    full_adder fa3 (.a(a[3]), .b(b[3]), .cin(c3),  .sum(sum[3]), .cout(cout));
endmodule

-- 4-bit ripple-carry adder: four full adders, each carry feeding the next.
library ieee;
use ieee.std_logic_1164.all;

entity ripple4 is
    port (
        a    : in  std_logic_vector(3 downto 0);
        b    : in  std_logic_vector(3 downto 0);
        cin  : in  std_logic;
        sum  : out std_logic_vector(3 downto 0);
        cout : out std_logic
    );
end entity;

architecture structural of ripple4 is
    signal c1, c2, c3 : std_logic;
begin
    fa0 : entity work.full_adder port map (a => a(0), b => b(0), cin => cin, sum => sum(0), cout => c1);
    fa1 : entity work.full_adder port map (a => a(1), b => b(1), cin => c1,  sum => sum(1), cout => c2);
    fa2 : entity work.full_adder port map (a => a(2), b => b(2), cin => c2,  sum => sum(2), cout => c3);
    fa3 : entity work.full_adder port map (a => a(3), b => b(3), cin => c3,  sum => sum(3), cout => cout);
end architecture;

A testbench (Chapter 10) applied all 512 combinations of \(a, b, c_\text{in}\) to ripple4 and all 64 combinations of data and select to mux4, comparing each result with ordinary arithmetic. Both the Verilog and the VHDL version print PASS: 512 additions and 64 mux selections correct. In real designs you will simply write a + b; the synthesiser builds the adder on the FPGA's carry chain.