Combinational Logic

Part of Boolean Logic and Gates

Circuits whose outputs depend only on current inputs, with no memory or state — the foundation of arithmetic and data routing.

Why This Matters

Combinational logic circuits are the workhorses of digital design. An adder, a comparator, a multiplexer, a decoder — all are combinational circuits. They receive inputs, compute a result, and produce outputs with no memory of previous states. The output is a pure function of the current inputs.

This memoryless property makes combinational circuits predictable and testable. Given a fixed set of inputs, the output is always the same. You can verify behavior exhaustively by testing every input combination. For a circuit with four inputs, that is only 16 test cases.

Understanding combinational design gives you the ability to build the arithmetic and data-routing blocks that form the core of a CPU: the ALU, the instruction decoder, the register file address logic. These blocks can be constructed from discrete gates even before you have access to microcontrollers or programmable logic.

Analysis: Reading a Combinational Circuit

To analyze a combinational circuit, trace the signal from inputs to outputs, applying the Boolean operation at each gate.

Start at the inputs and label each wire with its value. Then evaluate each gate whose inputs are all known. Propagate known values forward until all outputs are determined.

For example, consider a circuit with inputs A, B, C:

• Gate 1: X = A AND B
• Gate 2: Y = X OR C
• Gate 3: Z = NOT Y

For inputs A=1, B=0, C=1:

• X = 1 AND 0 = 0
• Y = 0 OR 1 = 1
• Z = NOT 1 = 0

To build the complete truth table, repeat this for all eight input combinations (2^3 = 8 for three inputs). If the circuit has n inputs, you must evaluate 2^n rows.

This process is called circuit simulation by hand. When building circuits from discrete components, verifying the truth table experimentally confirms the circuit works correctly — connect the inputs to switches and the outputs to LEDs, then test all input combinations.

Synthesis: Building a Circuit from a Truth Table

Given a desired truth table, construct the circuit using a systematic method.

Step 1: Identify rows where the output is 1. Step 2: Write a minterm (AND term) for each such row. A minterm includes each input: the input as-is if it is 1 in that row, inverted if it is 0. Step 3: OR all minterms together to get the sum-of-products (SOP) expression. Step 4: Simplify using Boolean laws or a Karnaugh map. Step 5: Draw the gate circuit.

Example: design a circuit with output 1 when exactly two of three inputs (A, B, C) are 1.

Output-1 rows: A=0,B=1,C=1 | A=1,B=0,C=1 | A=1,B=1,C=0

Minterms: (NOT-A AND B AND C), (A AND NOT-B AND C), (A AND B AND NOT-C)

SOP: F = (NOT-A·B·C) + (A·NOT-B·C) + (A·B·NOT-C)

This expression can be implemented directly: three AND gates feeding an OR gate. Each AND gate has three inputs (one possibly inverted).

Common Combinational Building Blocks

Half adder: adds two 1-bit numbers. Sum = A XOR B, Carry = A AND B. Two gates.

Full adder: adds two bits plus a carry-in. Sum = A XOR B XOR Cin, Cout = (A AND B) OR (Cin AND (A XOR B)). Can cascade to add multi-bit numbers.

Ripple-carry adder: chain of full adders where the carry-out of each stage feeds the carry-in of the next. To add two 8-bit numbers, cascade eight full adders. The carry “ripples” through — the final sum is not valid until the carry has propagated through all stages.

Comparator: determines if A > B, A = B, or A < B. Equality is checked bit-by-bit with XNOR gates. A AND-reduction of all XNOR outputs gives overall equality.

Decoder: takes an n-bit input and activates exactly one of 2^n output lines. A 2-to-4 decoder has 2 input bits and 4 outputs; output line k is active when the binary input equals k. Implemented with AND gates and inverters.

Multiplexer (mux): selects one of several inputs and routes it to the output. A 4-to-1 mux has 4 data inputs, 2 select inputs, and 1 output. The select inputs are decoded to enable one of four transmission paths.

Propagation Delay and Hazards

Real gates are not instantaneous. Each gate introduces a small propagation delay — the time between an input change and the corresponding output change. For discrete transistor gates, this might be tens of nanoseconds; for modern CMOS, a few picoseconds.

In a combinational circuit, the longest path from any input to any output through a chain of gates determines the critical path delay. The circuit’s outputs are not valid until this delay has elapsed after any input change.

Glitches (or hazards) occur when outputs briefly take incorrect values during input transitions. If two paths with different delays both feed an OR gate, the faster path may deactivate before the slower path activates, producing a brief 0 output even though the steady-state output should be 1. Glitches are usually harmless in combinational circuits since the output stabilizes before it is sampled, but they can cause problems when feeding memory elements (latches, flip-flops) that are sensitive to transitions.

Testing a Combinational Circuit

Exhaustive testing of all input combinations is straightforward for small circuits. For three inputs, build a test fixture with three switches and verify all eight input combinations against the expected truth table.

For larger circuits (8+ inputs), exhaustive testing becomes impractical (2^8 = 256 cases). Use structured test patterns instead:

• All zeros and all ones: catch stuck-at faults on buses
• Walking ones/zeros: test individual signal paths
• Critical minterms: test input combinations near output transitions

When a circuit produces wrong output, systematically probe intermediate nodes to isolate the fault to a single gate or connection.