Combinational Circuits

Why This Matters

A 64-bit ripple-carry adder built from full adders with a 90 ps carry delay has a worst-case carry path near 5.76 ns before wire delay. At 3 GHz, one clock cycle is about 333 ps, so that adder cannot sit alone on one cycle without a different architecture or pipelining.

Combinational circuits are the stateless part of digital computation. Integer addition, address comparison, instruction decoding, multiplexing, and much of a CPU datapath are Boolean functions realized as gates and wires. The same rules also explain why a simulator may show a temporary wrong value for a few picoseconds before the final output settles.

Core Definitions

A combinational circuit can be specified by a truth table, a Boolean expression, a gate-level netlist, or a hardware description language fragment. These are different views of the same object when the netlist is acyclic.

From Gates to Adders

A half-adder adds two one-bit inputs, $a$ and $b$. It produces a sum bit $s$ and carry bit $c$.

The equations are $s = a \oplus b$ and $c = a b$.

a ─────┬──── XOR ─── s
       │
b ─────┘

a ─────┬──── AND ─── c
       │
b ─────┘

A full-adder adds $a$, $b$, and an incoming carry $c_{in}$. It emits $s$ and $c_{out}$.

A useful implementation uses two half-adders and an OR gate:

$s = a \oplus b \oplus c_{in}$

$c_{out} = ab + c_{in}(a \oplus b)$

a ─────┬──── XOR ── x ─── XOR ─── s
       │                 │
b ─────┘                 │
                         │
c_in ────────────────────┘

a ─────┬──── AND ── c1 ──┐
       │                 │
b ─────┘                 OR ─── c_out
                         │
x ─────┬──── AND ── c2 ──┘
       │
c_in ──┘

A ripple-carry adder chains full-adders. For bit $i$, it computes:

$s_i = a_i \oplus b_i \oplus c_i$

$c_{i+1} = a_i b_i + c_i(a_i \oplus b_i)$

Worked 4-bit example, adding $0111_2$ and $0001_2$:

The result is $1000_2$. The carry must travel through all four stages in this input case.

A C version is a useful executable specification:

#include <stdint.h>

uint8_t add4(uint8_t a, uint8_t b) {
    uint8_t carry = 0;
    uint8_t sum = 0;

    for (int i = 0; i < 4; i++) {
        uint8_t ai = (a >> i) & 1;
        uint8_t bi = (b >> i) & 1;
        uint8_t s = ai ^ bi ^ carry;
        uint8_t cout = (ai & bi) | (carry & (ai ^ bi));
        sum |= s << i;
        carry = cout;
    }
    return sum | (carry << 4);
}

For a = 0x7 and b = 0x1, this returns 0x08. For a = 0xF and b = 0x1, it returns 0x10, a five-bit result.

Carry Lookahead as a Prefix Computation

Ripple-carry addition has linear carry depth. Carry-lookahead reduces depth by separating each bit into generate and propagate signals.

For bit $i$:

$g_i = a_i b_i$

$p_i = a_i \oplus b_i$

$c_{i+1} = g_i + p_i c_i$

Here $g_i$ means bit $i$ generates a carry no matter what came in. $p_i$ means bit $i$ passes an incoming carry to the next bit.

For a 4-bit adder:

$c_1 = g_0 + p_0 c_0$

$c_2 = g_1 + p_1 g_0 + p_1 p_0 c_0$

$c_3 = g_2 + p_2 g_1 + p_2 p_1 g_0 + p_2 p_1 p_0 c_0$

$c_4 = g_3 + p_3 g_2 + p_3 p_2 g_1 + p_3 p_2 p_1 g_0 + p_3 p_2 p_1 p_0 c_0$

For $a=0111_2$, $b=0001_2$, and $c_0=0$:

Then $c_1=1$, $c_2=1$, $c_3=1$, and $c_4=0$. The sum bits are $s_i = p_i \oplus c_i$, giving $0000$ for bits 0 through 2 and $1$ for bit 3.

A prefix adder computes combined generate-propagate pairs. For a block from bit $j$ through bit $i$:

$P_{i:j} = p_i p_{i-1} \cdots p_j$

$G_{i:j} = g_i + p_i g_{i-1} + \cdots + p_i p_{i-1} \cdots p_{j+1} g_j$

Then $c_{i+1} = G_{i:0} + P_{i:0}c_0$. A tree can combine adjacent pairs using:

$(G,P) \circ (G',P') = (G + P G', PP')$

This is the same associativity pattern as prefix sums. With a balanced tree, carry depth grows as $O(\log n)$ gate levels instead of $O(n)$. The tradeoff is more gates and more wiring.

Multipliers from Shift and Add

Unsigned binary multiplication decomposes into partial products. Each bit of the multiplier either selects a shifted copy of the multiplicand or selects zero.

Compute $13 \times 11$ using 4-bit inputs:

        1101     13
      x 1011     11
      -----
        1101     bit 0 is 1
       11010     bit 1 is 1, shifted left 1
      000000     bit 2 is 0
     1101000     bit 3 is 1, shifted left 3
     -------
     10001111    143

At the gate level, each partial product bit is an AND:

$pp_{i,j} = a_i b_j$

Then add shifted rows with adders. A direct array multiplier for 4 by 4 bits creates 16 AND gates and a grid of half-adders and full-adders. Its delay is usually dominated by carry propagation through the addition structure, not by the AND gates.

A shift-and-add sequential multiplier reuses one adder across cycles, but that circuit has state and is not purely combinational. A combinational multiplier does all selected shifts and additions in one combinational network, with one final output after the critical path settles.

Comparators and Magnitude Circuits

Equality is the easiest comparator. Two $n$-bit words are equal exactly when every bit pair matches:

$eq = \bigwedge_{i=0}^{n-1} \neg(a_i \oplus b_i)$

For $a=10110100_2$ and $b=10111100_2$, the XOR vector from bit 7 to bit 0 is 00001000, so the equality output is 0.

A magnitude comparator decides $a > b$, $a = b$, or $a < b$. For unsigned numbers, compare from most significant bit downward. At the first differing bit, the word with 1 is larger.

For 4-bit words $a_3a_2a_1a_0$ and $b_3b_2b_1b_0$:

$a>b = a_3\neg b_3 + e_3 a_2\neg b_2 + e_3e_2 a_1\neg b_1 + e_3e_2e_1 a_0\neg b_0$

where $e_i = \neg(a_i \oplus b_i)$.

Worked example, $a=1001_2$ and $b=0111_2$:

The most significant differing bit is bit 3, so $a>b=1$. Lower bits do not matter after bit 3 differs.

Delay, Critical Paths, Fan-Out, and Hazards

In a simple delay model, assign each gate a delay and add delays along paths. Suppose XOR has 70 ps delay, AND has 40 ps, OR has 40 ps, and a full-adder carry is implemented as $ab + c_{in}(a \oplus b)$.

For a carry input reaching $c_{out}$ after $a \oplus b$ is already stable, the path is AND then OR, or 80 ps. If $a$ or $b$ changes and affects carry through XOR, AND, OR, the path is 150 ps. In a 32-bit ripple-carry adder, a worst-case carry propagation estimate using 80 ps per stage is 2.56 ns. A final sum bit may need one more XOR delay, so about 2.63 ns, excluding wire delay and input register delay.

Fan-out changes these numbers. A signal driving one nearby gate input may switch faster than a signal driving 32 gate inputs across a chip. Textbook Boolean algebra treats wires as free. Physical circuits do not.

Hazards are temporary wrong outputs caused by unequal path delays. Consider:

$f = xy + \neg x z$

For $y=1$ and $z=1$, the Boolean function is always 1, no matter what $x$ is. A gate network can still glitch when $x$ changes from 1 to 0.

Assume NOT delay is 20 ps, AND delay is 30 ps, OR delay is 30 ps. Initially $x=1$, so $xy=1$ and $\neg x z=0$. When $x$ falls to 0, the direct path to $xy$ turns off after 30 ps, while the inverted path turns on after 20 ps plus 30 ps, or 50 ps. For about 20 ps, both AND outputs can be 0, so the OR output drops to 0 before returning to 1.

The consensus term $yz$ removes this static-1 hazard:

$f' = xy + \neg xz + yz$

For $y=z=1$, the extra term is 1 during the transition. This does not change the truth table, but it changes transient behavior.

Main Theorem

Common Confusions

Exercises

References

Canonical:

• Charles Petzold, Code: The Hidden Language of Computer Hardware and Software, 2nd ed. (2022), ch. 10-14. Relays, gates, adders, and binary arithmetic.
• David A. Patterson and John L. Hennessy, Computer Organization and Design: The Hardware/Software Interface, 5th ed. (2013), Appendix B. Logic gates, combinational logic, adders, and ALU building blocks.
• J. Clark Scott, But How Do It Know? The Basic Principles of Computers for Everyone (2009), ch. 2-8. Gates, adders, memory contrast, and datapath intuition.
• M. Morris Mano and Michael D. Ciletti, Digital Design, 5th ed. (2013), ch. 3-4. Boolean algebra, gate-level simplification, combinational logic, adders, subtractors, and comparators.
• John F. Wakerly, Digital Design: Principles and Practices, 4th ed. (2006), ch. 4-6. Combinational logic design, timing, hazards, and arithmetic circuits.

Accessible:

• Nand2Tetris, Boolean Arithmetic and Combinational Chips project materials.
• MIT OpenCourseWare, 6.004 Computation Structures, combinational logic and timing lectures.
• Ben Eater, Building an 8-bit breadboard computer, videos on adders and arithmetic logic.

Next Topics

• /computationpath/sequential-circuits
• /computationpath/finite-state-machines
• /computationpath/instruction-decoders
• /computationpath/arithmetic-logic-units
• /topics/boolean-algebra