Digital design is the refinement of a mathematical function into a physical network whose outputs become valid after a bounded propagation delay. A combinational circuit has no intentional storage: once its inputs have remained stable long enough, its outputs depend only on those inputs. This property distinguishes it from sequential logic, where the circuit’s state records history. The distinction is architectural, not merely terminological: an ALU, decoder, address calculator, and cache tag comparator are combinational components that must produce values within the timing budget of a clocked system.
Boolean functions as specifications
The simplest specification is a Boolean function A truth table lists all input combinations and the required output. A circuit is correct when, for every input row, its stable output equals the specified output. This exhaustive definition is practical for small circuits and becomes the semantic foundation for symbolic simplification, formal equivalence checking, and test generation for larger ones.
The primitive operations are NOT AND and OR NAND and NOR are functionally complete: every Boolean function can be built from either one alone. For example, and Functional completeness is an expressiveness result; it does not imply that a NAND-only implementation is fastest, smallest, or easiest to verify.
Boolean algebra supports local transformations that preserve a function. Important identities include commutativity, associativity, distributivity, identity domination idempotence complement absorption and De Morgan’s laws:
These are equations over truth values, so each transformation can be justified for all inputs. A designer should prefer a proof-preserving transformation to an intuition such as “this gate seems redundant.”
Worked derivation. Simplify where juxtaposition denotes AND and + denotes OR. First factor the first two terms: Therefore Apply absorption in its dual form, which can be verified by distributivity: The original three-product circuit can therefore be implemented by one OR gate after the appropriate inputs are available. The simplification is a theorem about the function, not an approximation.
From truth table to circuit
What property defines a combinational circuit?
Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.
Canonical forms and minimization
Every Boolean function can be written as a sum of products (SOP). For each truth-table row where form a minterm that is 1 only on that row, then OR the minterms. Likewise, a product of sums (POS) uses maxterms for rows where Canonical forms are systematic and easy to derive, but they may contain many literals and gates.
Consider a three-input function that is 1 for inputs 001, 010, and 111. With variables in that order, its SOP is If the function has don’t-care input combinations—states that never occur or whose output does not matter—those rows may be assigned whichever value produces a cheaper implementation. A don’t-care is not permission to ignore a reachable safety-critical state; it is a specification statement that must be defended by the surrounding design.
Karnaugh maps expose adjacent minterms that differ in one variable. Grouping powers of two allows the differing variable to disappear. For larger functions, Quine–McCluskey or binary decision diagrams provide systematic alternatives, while synthesis tools use cost models and technology libraries. “Minimal number of terms” and “minimal delay” are different objectives: factoring may reduce area but add a logic level; duplicating a term may reduce fanout and improve timing.
Equivalent Boolean functions, different hazards
Two circuits have the same steady-state truth table. During a one-bit input change, one briefly pulses its output because paths have unequal delay.
Which evidence distinguishes the implementations?
Multiplexers and decoders
A 2-to-1 multiplexer is the conditional operator of hardware:
When the first product survives and when the second survives and A -to-1 multiplexer can select one of inputs using select bits. Multiplexers are powerful because a data path can be described as “choose this value when the control predicate holds” rather than drawn as a separate circuit for every case.
A decoder performs the inverse-shaped task: input bits activate one of outputs. A 2-to-4 decoder with inputs generates minterms and Decoders construct register-file enables, memory chip selects, instruction subfields, and one-hot state encodings. A one-hot representation uses one state bit per state, increasing storage but often simplifying next-state logic and making illegal-state detection explicit.
Worked construction. Implement a 4-to-1 multiplexer from three 2-to-1 multiplexers. First select between and using and between and using Select those two intermediate results using The first layer has two parallel gates and the second layer one gate, so the data path has two multiplexer delays. A balanced tree is preferable to chaining three selections because its depth is logarithmic in the number of inputs.
Adders and arithmetic structure
The half-adder adds two bits. Its sum is and carry is A full adder adds and carry-in
The carry expression says at least two of the three inputs are 1. It can also be written separating the generate case from the propagate case. Chaining full adders creates a ripple-carry adder. Its area is linear, but the carry may traverse every bit, so worst-case delay is gate stages.
The carry-propagate structure motivates a carry-lookahead adder. Define per bit and Then Expanding gives and so on. Parallel prefix structures compute these equations with lower depth at greater wiring and area cost. This is a recurring architecture trade-off: asymptotic latency improves by investing physical resources and design complexity.
Subtraction uses the identity in two’s complement. A single adder can therefore add either or selected by a control signal, with the same signal supplied as the initial carry-in. The ALU must define flag semantics: zero, negative, carry/borrow, and signed overflow are not interchangeable. A branch instruction that tests unsigned less-than uses a different interpretation from one that tests signed less-than even when both consume the same subtractor outputs.
The full-adder graph implements the derived generate/propagate equations. Each arrow carries a single Boolean value except the explicitly paired input a,b; no unspecified selector or stored state is needed.
Transfer check. For predict every internal wire and both outputs. Then change only to 1: which carry term now establishes the output?
Check generate versus propagateExpandCollapse
For (1,0,1), sum is 0, and carry-out is 1: the input carry propagates. For (1,1,1), sum is 1, and carry-out is 1: the operands generate the carry. Both satisfy
Comparators and predicates
Equality of two -bit words is the AND of bitwise equivalences:
An equality tree reduces delay compared with a serial chain. Unsigned less-than can be determined by the most significant bit at which operands differ. A lexicographic comparator therefore scans from high bits conceptually, although hardware uses a tree or prefix formulation. Signed comparison treats the sign bit specially: a negative operand is less than a nonnegative operand; if signs match, the remaining bits can be compared as an unsigned magnitude under the two’s-complement ordering.
Predicates are often more valuable than numeric results. The ALU’s output may be discarded while its zero or sign condition controls a branch, a memory-protection check, or an instruction exception. The control contract must say whether a comparison is signed, unsigned, exact, masked, or tolerant of invalid encodings.
Timing, hazards, and physical reality
Boolean equivalence describes the stable function, but a physical circuit also has propagation delay. If an output feeds another gate before it has settled, the receiving logic can observe a transient value. The longest input-to-output path is the critical path and bounds the maximum clock frequency when the circuit lies between registers. Gate count is only a rough area proxy; fanout, wire length, loading, and technology-specific delays matter.
Unequal path delays can produce a glitch: an output briefly changes even though the logically correct value before and after the transition is the same. For example, in changing while should leave but the direct and inverted paths may not switch simultaneously, producing a temporary zero. Adding the consensus term yields a hazard-resistant two-level form for this transition, at the cost of an extra product. Whether a glitch matters depends on the receiver: a level-sensitive combinational consumer may ignore it after settling, while an asynchronous control input or clock edge can capture it.
Static timing analysis uses arrival and required times to verify that paths meet setup constraints. The logic designer cannot safely assume zero delay merely because a truth table is correct. Conversely, adding arbitrary “delay gates” is not a robust fix; synthesis may remove them, process variation may change their delay, and the real solution may require registering the signal or changing the protocol.
CMOS and implementation cost
Transistor counts and stage delays in static CMOS:
| Gate type | Complementary pull-up / pull-down topology | Transistor count | Stage delay and characteristics |
|---|---|---|---|
INVERTER | 1 pMOS pull-up, 1 nMOS pull-down | 2 | Single inverting stage; symmetric rise/fall with sized pMOS |
NAND2 | 2 parallel pMOS, 2 series nMOS | 4 | Natural inverting gate; higher electron mobility makes series nMOS fast |
NOR2 | 2 series pMOS, 2 parallel nMOS | 4 | Slower than NAND2 because lower hole mobility requires wider series pMOS |
AND2 | NAND2 stage driving an INVERTER | 6 | Two stages; higher latency and area than native NAND2 |
OR2 | NOR2 stage driving an INVERTER | 6 | Two stages; higher latency and area than native NOR2 |
XOR2 | Complex CMOS gate or transmission gates | 8–12 | High logic depth; forms the delay bottleneck in ripple carry adders |
At the transistor level, complementary CMOS uses networks of p-type and n-type devices to implement logic with low static power in steady states. A NAND gate is naturally efficient: the pull-down network places nMOS devices in series for the AND condition, while the pull-up network is the dual parallel structure. A NOR gate has the opposite topology and often different delay characteristics because series and parallel transistor arrangements load differently.
The same Boolean expression can map to different physical costs. Factoring reduces repeated logic but may increase fanout; a NAND-NAND implementation can exploit the technology’s native gate; a balanced tree reduces depth but increases wiring. Modern synthesis tools optimize against timing, area, power, and testability objectives. Architectural reasoning remains necessary because the tool only optimizes within the constraints and library the designer supplies.
Verification strategy
For a small combinational block, exhaustive simulation covers all inputs. For a 32-bit ALU, exhaustive testing is impossible, so verification combines equivalence checking, constrained random tests, directed corner cases, and compositional proofs. Directed cases should include all-zero and all-one operands, one-hot patterns, sign transitions, carry chains, alternating bits, and illegal control encodings.
An assertion expresses a property such as “if operation is ADD, then result plus a widened carry equals the mathematical sum” or “if select is 0, output equals input A regardless of input B.” Assertions turn the specification into an executable proof obligation. A test that observes only the common path can miss a carry that propagates through every bit or a mode field that selects the wrong input.
Deep Practice
Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.
Exercise 1.2.1: Full Adder Composition from Half Adders
Derive a full-adder circuit from two half-adders. Give the equations for the intermediate carry and prove that the final carry equals
HintExpandCollapse
Express sum and carry-out of the full adder using the intermediate sum and carry signals of two cascaded half adders.
Worked solutionExpandCollapse
The first half-adder computes and the second computes and The final carry is after expanding XOR and absorbing the duplicate term.
Exercise 1.2.2: Karnaugh Map Minimization and Symmetry
Minimize and identify any symmetry. Verify the expression on at least one minterm and one zero row.
HintExpandCollapse
Group adjacent minterms on a 4-variable K-map and look for XOR/XNOR checkerboard patterns involving variables and .
Worked solutionExpandCollapse
The minterms pair by the high-bit and low-bit symmetries. Grouping the four cells where gives equivalently A correct solution may use XOR/XNOR as a primitive or expand it into SOP. Check 0000 (1), 0001 (0), and a paired edge such as 1010 (1).
Exercise 1.2.3: Hierarchical Multiplexer Tree Synthesis
Build an 8-to-1 multiplexer from 2-to-1 multiplexers. Give the number of gates and logic depth for a balanced tree and a serial chain.
HintExpandCollapse
Determine how many 2-to-1 multiplexers are needed to select 1 of 8 inputs, and compare a -depth balanced tree against a serial linear chain.
Worked solutionExpandCollapse
A balanced tree uses seven 2-to-1 multiplexers and depth three. A serial chain also uses seven multiplexers but has depth seven and would require a different select-routing scheme; the balanced tree meets a shorter critical path.
Exercise 1.2.4: Data-Dependent Critical Path in Ripple-Carry Adders
Explain why a ripple-carry adder has a data-dependent delay even though its topology is fixed. Give an input pattern that propagates carry through every bit.
HintExpandCollapse
Find an operand combination where a carry generated at the least significant bit must propagate sequentially through all bit positions.
Worked solutionExpandCollapse
Each full adder waits for the incoming carry. An operand pair such as 01111111 plus 00000001 generates a carry at the low bit and propagates it through all higher positions, exposing the linear chain delay.
Exercise 1.2.5: Signed Two's-Complement Comparator Correctness
A comparator receives signed two’s-complement operands. Prove that comparing sign bits first and magnitudes second yields the correct order, including the minimum negative value.
HintExpandCollapse
Consider how sign bits order opposite-sign operands and how overflow flag modifies the sign flag during subtraction.
Worked solutionExpandCollapse
If signs differ, every negative two’s-complement value is less than every nonnegative value, so the sign bit decides. If signs match, subtracting the common sign weight leaves an ordering by the lower bits; for two negative operands, the lower-bit ordering is reversed relative to unsigned magnitude, which the signed comparator’s subtract/overflow logic accounts for. The minimum value is not negatable in range, so a proof must not assume symmetric magnitude bounds.
Exercise 1.2.6: Static-1 Hazard Detection and Consensus Term Elimination
Construct a transition that can glitch in Why does adding cover the static-1 hazard? What timing assumption makes the term useful?
HintExpandCollapse
Examine what happens when and variable changes state if an inverter propagation delay causes both product terms to momentarily drop to 0.
Worked solutionExpandCollapse
Set and change from 0 to 1. The function should stay 1, but may fall before rises. The consensus term remains 1 throughout, covering the static-1 gap. It helps only when the input transition is single-variable or the timing environment makes the consensus reasoning applicable.
Exercise 1.2.7: Formal Combinational ALU Invariant Assertions
Propose an assertion set for a 4-bit ALU with ADD, SUB, AND, OR, and XOR. Include one property about unused control codes.
HintExpandCollapse
Write algebraic invariants matching outputs to mathematical operations across all opcode modes, and specify defensive defaults for undefined control codes.
Worked solutionExpandCollapse
For each opcode, assert the output equation. For ADD and SUB, use widened arithmetic to relate result, carry, and operands; for bitwise operations assert bitwise equality. For unused codes, specify a safe result and side-effect behavior—such as no write enable—rather than leaving the output unconstrained.