3.1 Combinational Logic

This chapter temporarily sets software abstractions aside and examines how AND, OR, and NOT gates combine into arithmetic and control circuits. CPU instructions can execute only because these circuits work together under timing constraints.

The previous two chapters explained the bit-level representation of data. This chapter feeds bits into logical networks and observes how outputs are determined solely by the current inputs; the next section introduces flip-flops, clocks, and state.

How Software Operations Become Circuits

A circuit diagram shows input pins, output pins, gates, and connections. A C + operator cannot do the wiring for them. Adding two binary numbers is implemented through logic gates, interconnections, and electrical timing.

Digital circuits do not claim that physical voltage levels are strictly 0 or 1. Instead, they define that inputs below a certain threshold are interpreted as logic 0, above another threshold as logic 1, and values in between are not guaranteed to be interpreted at all. The exact thresholds depend on the specific logic family and manufacturing process; logic design operates first on this abstract model.

MOS transistors behave more like voltage-controlled devices than ideal mechanical switches. CMOS combines transistor networks into logic gates, which are then assembled into standard cells, wiring, and storage elements to form a processor. Not every transistor flips on every clock edge; dynamic power consumption varies with actual switching activity.

Six Common Logical Relations

For single-bit inputs A and B:

A	B	AND	OR	XOR	NAND	NOR
0	0	0	0	0	1	1
0	1	0	1	1	1	0
1	0	0	1	1	1	0
1	1	1	1	0	0	0

NOT requires only a single input: NOT 0 = 1, NOT 1 = 0. A truth table exhaustively enumerates all input combinations, thus fully defining any finite-input Boolean function.

In C, &&, ||, and ! are logical operators that return a value normalized to 0 or 1, with the first two performing short-circuit evaluation; &, |, ^, and ~ are bitwise operators. When simulating single-bit logic gates in C, normalize inputs first. These function fragments map zero to 0 and every nonzero integer to 1; mixing logical and bitwise operators without that convention can produce incorrect results.

static int bit(int value) {
    return value != 0;
}

static int gate_and(int left, int right) {
    return bit(left) & bit(right);
}

static int gate_xor(int left, int right) {
    return bit(left) ^ bit(right);
}

These functions describe the logical relationships of logic gates, but they do not imply that a typical C compiler arranges transistors in the order of function calls. Actual hardware design languages describe concurrent connections, and synthesis tools map those designs to specific target cell libraries.

Why NAND Can Independently Realize Any Boolean Logic

A gate set is said to be functionally complete if it can construct any Boolean function. Using only NAND gates, we can implement NOT, AND, and OR operations:

NOT A     = NAND(A, A)
A AND B   = NAND(NAND(A, B), NAND(A, B))
A OR B    = NAND(NAND(A, A), NAND(B, B))

Since NOT, AND, and OR are sufficient to express any finite Boolean function (such as through disjunctive normal form) NAND alone is functionally complete. NOR gates exhibit the same property.

This is a conclusion about logical expressiveness, not an indication that all chips exclusively use NAND gates. In practice, implementation must balance factors like delay, area, power consumption, fanout, and routing. Gate libraries typically include a variety of gates and more complex combinational units.

Boolean Algebra Helps Us Eliminate Unnecessary Logic

Common identities include:

A AND B = B AND A
A OR (B OR C) = (A OR B) OR C
A AND (B OR C) = (A AND B) OR (A AND C)

NOT (A AND B) = (NOT A) OR (NOT B)
NOT (A OR B) = (NOT A) AND (NOT B)

A OR (A AND B) = A
A AND (A OR B) = A

Equivalent expressions may have different gate counts, but "fewer gates" doesn't always mean better performance. Logic depth, shared subexpressions, fanout, and physical routing all affect the critical path. Synthesis tools can perform large-scale simplifications; however, designers must still understand equivalence in order to interpret the results and apply correct constraints.

Karnaugh maps are well-suited for manually simplifying a small number of variables. When dealing with many variables, algorithmic simplification and synthesis tools are more practical. Regardless of the method used, the first step is to ensure the truth table accurately represents the desired functionality.

Combinational Logic Has No Internal State

The output of a combinational circuit is determined by its current inputs. A common abstract model is written as:

output = F(input)

"Current" does not mean a physical instant. After an input changes, the signal must propagate through gates and wires, and the output may temporarily pass through intermediate values before settling to a stable state. Propagation delay, rise/fall times, and loading are determined by the specific implementation.

The distinction between combinational and sequential logic lies in whether the circuit retains state, not in whether there is delay. Real-world combinational gates also exhibit delay.

From Half Adder to Full Adder

A half adder computes the sum of inputs A and B, producing a sum output S and a carry output C:

S = A XOR B
C = A AND B

When a carry-in from the previous bit position (denoted as Cin) is also considered, the full adder operates as follows:

P    = A XOR B
S    = P XOR Cin
Cout = (A AND B) OR (P AND Cin)

Examining each of the eight possible input combinations reveals that S is the parity bit of the number of 1s among the three inputs, and Cout indicates that at least two of the inputs are 1.

By feeding the carry-out (Cout) of bit position i into the carry-in (Cin) of bit position i+1, a ripple-carry adder is formed. Each bit can compute its partial result in parallel, but the final output from higher bits must wait for the carry to propagate through the chain. As the bit width increases, the worst-case carry path length also grows.

Advanced structures such as carry-lookahead and prefix adders use generate and propagate signals to compute carry information in parallel, trading increased hardware and routing complexity for shorter logic depth. The specific architecture adopted in modern processors varies depending on timing, area, and power constraints; there is no single "fastest" adder design.

Exhaustive Model Checking of an 8-Bit Adder

This C17 reference model simulates eight connected stages. carry_out returns the ninth bit, and only the low bit of carry_in is used. Save it as ripple_adder.c, compile with cc -std=c17 -Wall -Wextra -Werror ripple_adder.c -o ripple_adder, and run ./ripple_adder. The software loop does not model physical timing.

#include <assert.h>
#include <stdint.h>

struct Add8Result {
    uint8_t sum;
    uint8_t carry_out;
};

static struct Add8Result ripple_add8(uint8_t left, uint8_t right,
                                     uint8_t carry_in) {
    struct Add8Result result = {0, 0};
    uint8_t carry = (uint8_t)(carry_in & UINT8_C(1));

    for (unsigned int position = 0; position < 8U; position++) {
        uint8_t a = (uint8_t)((left >> position) & UINT8_C(1));
        uint8_t b = (uint8_t)((right >> position) & UINT8_C(1));
        uint8_t propagate = (uint8_t)(a ^ b);
        uint8_t sum_bit = (uint8_t)(propagate ^ carry);

        carry = (uint8_t)((a & b) | (propagate & carry));
        result.sum |= (uint8_t)(sum_bit << position);
    }

    result.carry_out = carry;
    return result;
}

int main(void) {
    for (unsigned int left = 0; left <= UINT8_MAX; left++) {
        for (unsigned int right = 0; right <= UINT8_MAX; right++) {
            for (unsigned int carry = 0; carry <= 1U; carry++) {
                struct Add8Result actual =
                    ripple_add8((uint8_t)left, (uint8_t)right,
                                (uint8_t)carry);
                unsigned int expected = left + right + carry;

                assert(actual.sum == (uint8_t)expected);
                assert(actual.carry_out == (uint8_t)(expected >> 8));
            }
        }
    }
    return 0;
}

This test covers 131,072 input combinations, checking both sum and carry_out against the wider integer result. Exhaustive testing is effective for inputs with fewer bits; larger modules are better validated using formal verification, random testing, and coverage metrics.

The Same Carry Chain Can Also Perform Subtraction

For n-bit modular arithmetic:

A - B = A + (NOT B) + 1  (mod 2^n)

Thus, the control signal Sub can simultaneously enable two operations:

B'[i] = B[i] XOR Sub
Cin   = Sub

When Sub is 0, the circuit computes A + B; when Sub is 1, it computes A + NOT(B) + 1. This reuses the same addition path.

However, carry out, borrow, and signed overflow are distinct concepts. In the case of n-bit two's complement addition, signed overflow can be detected by either the XOR of the carry input and carry output at the most significant bit, or by examining the relationship between the signs of the operands and the result. For example, 4-bit 1111 + 0001 = 0000 produces an unsigned carry but no signed overflow: in two’s complement it means -1 + 1 = 0. Conversely, 0111 + 0001 = 1000 overflows the signed range without a carry. For the n-bit subtraction path A + NOT(B) + 1, unsigned borrow is the inverse of the final carry. Check the ISA’s flag names and polarity; carry is not a universal “result too large” flag.

MUX Selects Data, Decoder Chooses One Path

A 2-to-1 multiplexer outputs either input A or B based on the select bit S:

Y = (NOT S AND A) OR (S AND B)

Wider multiplexers apply the same select signal in parallel to each bit. Additional inputs can be implemented using tree structures or pre-existing building blocks in the library. Multiplexers are commonly used to select ALU inputs, write-back sources, or the next program counter value.

An n-to-2^n decoder maps an n-bit input to a one-hot output. A 3-to-8 decoder activates only output 5 (numbered from zero, so the sixth output) when the input is 101. Real memory systems also include row/column selection, chip select, address mapping, timing control, and analog circuitry; "the address goes into the decoder and reads DRAM" is merely the most basic abstraction layer.

An encoder performs the reverse mapping. If multiple inputs may be active simultaneously, the standard encoder input constraints no longer hold; priority encoders or explicit error handling are required.

A Small ALU Is Multiple Results Plus a Selector

A simplified 8-bit ALU can compute AND, OR, XOR, and ADD operations in parallel, then use an operation code to select the output:

and_result = A AND B
or_result  = A OR B
xor_result = A XOR B
add_result = A + B
result     = MUX(op, and_result, or_result, xor_result, add_result)

"Parallel computation" refers to a structural possibility, not a requirement that every design must continuously switch through all paths. Techniques like clock gating, operand isolation, and shared resource reuse can significantly affect power consumption and area. A single ADD instruction in the ISA does not mean that data must pass through a fixed single-cycle circuit; the microarchitecture can instead pipeline, reuse, or distribute across multiple execution units.

Delay Can Cause Glitches

Consider Y = (A AND B) OR ((NOT A) AND C). When B=C=1 and A transitions from 1 to 0, the ideal Boolean function should remain at 1. However, if the two paths have different delays, the outputs of the two AND gates might momentarily both go to 0, causing a glitch at output Y. This is known as a static-1 hazard.

A synchronous data path may still work if the output remains stable throughout the receiving flip-flop’s setup/hold window. Disappearing just before the nominal sampling instant is insufficient. But if the output drives asynchronous control signals, clocks, or external interfaces, it can lead to serious errors. Here, adding the consensus term B AND C preserves the Boolean function and removes the static-1 hazard when only A changes. Other cases may require reencoding, registering the output, or specialized clock-domain design. Each method has conditions; the ideal truth table alone cannot establish timing correctness.

Build and Check Combinational Paths

1. Implement XOR using only NAND gates and verify the result with a four-row truth table.
2. List an eight-row truth table for a full adder and derive the sum-of-products expression for each output.
3. Manually compute the carry propagation step-by-step for 1011₂ + 0110₂ and explain the fifth-bit carry.
4. Design a selection tree for a 4-to-1 MUX and indicate how many levels of 2-to-1 MUXes are required in the worst case.
5. Provide test cases for a 4-bit adder/subtractor, one for unsigned carry/borrow and one for two’s complement overflow.
6. Identify an input transition that causes a static hazard and draw the arrival times along two paths.

Let the Result Be Remembered in the Next Cycle

Combinational logic can compute, but it does not automatically retain the value from the previous cycle. The processor requires a program counter, pipeline registers, and control state. The next lesson will introduce latches, flip-flops, and synchronous sequencing, and will explain why setup time, hold time, and metastability cannot be simply summarized as "the clock is the heartbeat."