Search Knowledge

© 2026 LIBREUNI PROJECT

Computer Architecture/Representation and digital state
Page 2 of 20

Logic and Combinational Circuits

Boolean algebra, gates, multiplexers, decoders, and arithmetic circuits.

Lesson briefRepresentation and digital state · 9 h · 3 outcomes

Required knowledge

  • Programming in a systems language
  • Binary arithmetic and basic digital logic

Learning outcomes

  • Construct Boolean specifications, canonical forms, multiplexers, decoders, adders, and comparators from truth conditions.
  • Analyze propagation delay, hazards, fan-in, and resource sharing in a combinational datapath.
  • Verify a circuit with exhaustive small cases, adversarial vectors, and a stated invariant.

Assessment target

Given a truth table and timing budget, synthesize a circuit, derive its output and critical path, then identify an input or hazard that falsifies a naive implementation.

Scope boundary

  • RTL implementation and electrical device physics are reduced to the abstractions needed to reason about a modern processor.

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 f:{0,1}n→{0,1}mf:\{0,1\}^n\to\{0,1\}^m A truth table lists all 2n2^n 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 ¬x\lnot x AND x∧yx\land y and OR x∨yx\lor y NAND and NOR are functionally complete: every Boolean function can be built from either one alone. For example, ¬x=xNAND⁡x\lnot x=x\operatorname{NAND}x x∧y=¬(xNAND⁡y)x\land y=\lnot(x\operatorname{NAND}y) and x∨y=(¬x)NAND⁡(¬y)x\lor y=(\lnot x)\operatorname{NAND}(\lnot y) 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 x∧1=xx\land1=x x∨0=xx\lor0=x domination x∧0=0x\land0=0 x∨1=1x\lor1=1 idempotence x∧x=xx\land x=x complement x∧¬x=0x\land\lnot x=0 absorption x∨(x∧y)=xx\lor(x\land y)=x and De Morgan’s laws:

¬(x∧y)=¬x∨¬y,¬(x∨y)=¬x∧¬y.\lnot(x\land y)=\lnot x\lor\lnot y, \qquad \lnot(x\lor y)=\lnot x\land\lnot y.

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 F=xy+xyˉ+xˉyF=xy+x\bar y+\bar x y where juxtaposition denotes AND and + denotes OR. First factor the first two terms: xy+xyˉ=x(y+yˉ)=xxy+x\bar y=x(y+\bar y)=x Therefore F=x+xˉyF=x+\bar x y Apply absorption in its dual form, x+xˉy=x+yx+\bar x y=x+y which can be verified by distributivity: (x+xˉ)(x+y)=1⋅(x+y)=x+y(x+\bar x)(x+y)=1\cdot(x+y)=x+y 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

0 / 4 answered

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.

1
Its output changes only when a clock edge captures new state
2
Its stable output depends only on the current input values
3
Its internal storage retains every previous input value indefinitely
4
Its gates cannot be composed with any other combinational network

Canonical forms and minimization

Every Boolean function can be written as a sum of products (SOP). For each truth-table row where F=1F=1 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 F=0F=0 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 a,b,ca,b,c in that order, its SOP is aˉbˉc+aˉbcˉ+abc\bar a\bar b c+\bar a b\bar c+abc 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:

M(s,a,b)=sˉa∨sb.M(s,a,b)=\bar s a\lor sb.

When s=0s=0 the first product survives and M=aM=a when s=1s=1 the second survives and M=bM=b A 2k2^k-to-1 multiplexer can select one of 2k2^k inputs using kk 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: kk input bits activate one of 2k2^k outputs. A 2-to-4 decoder with inputs a,ba,b generates minterms aˉbˉ\bar a\bar b aˉb\bar a b abˉa\bar b and abab 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 d0d_0 and d1d_1 using s0s_0 and between d2d_2 and d3d_3 using s0s_0 Select those two intermediate results using s1s_1 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 s=a⊕bs=a\oplus b and carry is c=abc=ab A full adder adds aa bb and carry-in cinc_{in}

s=a⊕b⊕cin,cout=ab+acin+bcin.s=a\oplus b\oplus c_{in}, \qquad c_{out}=ab+ac_{in}+bc_{in}.

The carry expression says at least two of the three inputs are 1. It can also be written ab+cin(a⊕b)ab+c_{in}(a\oplus b) separating the generate case from the propagate case. Chaining ww full adders creates a ripple-carry adder. Its area is linear, but the carry may traverse every bit, so worst-case delay is O(w)O(w) gate stages.

The carry-propagate structure motivates a carry-lookahead adder. Define per bit gi=aibig_i=a_ib_i and pi=ai⊕bip_i=a_i\oplus b_i Then ci+1=gi+picic_{i+1}=g_i+p_ic_i Expanding gives c2=g1+p1g0+p1p0c0c_2=g_1+p_1g_0+p_1p_0c_0 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 a−b=a+¬b+1a-b=a+\lnot b+1 in two’s complement. A single adder can therefore add either bb or ¬b\lnot b 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.

Code
rectangle "inputs a,b" as AB
rectangle "carry-in" as C
rectangle "p = a XOR b" as P
rectangle "g = a AND b" as G
rectangle "q = p AND carry-in" as Q
rectangle "sum = p XOR carry-in" as S
rectangle "carry-out = g OR q" as K
AB --> P : a,b
AB --> G : a,b
P --> Q : p
C --> Q : carry-in
P --> S : p
C --> S : carry-in
G --> K : g
Q --> K : q
inputs a,bcarry-inp = a XOR bg = a AND bq = p AND carry-insum = p XOR carry-incarry-out = g OR qa,ba,bpcarry-inpcarry-ingq

Transfer check. For (a,b,cin)=(1,0,1)(a,b,c_{in})=(1,0,1) predict every internal wire and both outputs. Then change only bb to 1: which carry term now establishes the output?

Check generate versus propagateExpand

For (1,0,1), p=1p=1 g=0g=0 q=1q=1 sum is 0, and carry-out is 1: the input carry propagates. For (1,1,1), p=0p=0 g=1g=1 q=0q=0 sum is 1, and carry-out is 1: the operands generate the carry. Both satisfy a+b+cin=s+2couta+b+c_{in}=s+2c_{out}

Comparators and predicates

Equality of two ww-bit words is the AND of bitwise equivalences:

eq(a,b)=⋀i=0w−1¬(ai⊕bi).eq(a,b)=\bigwedge_{i=0}^{w-1}\lnot(a_i\oplus b_i).

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 F=ab+aˉcF=ab+\bar ac changing aa while b=c=1b=c=1 should leave F=1F=1 but the direct and inverted paths may not switch simultaneously, producing a temporary zero. Adding the consensus term bcbc 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 typeComplementary pull-up / pull-down topologyTransistor countStage delay and characteristics
INVERTER1 pMOS pull-up, 1 nMOS pull-down2Single inverting stage; symmetric rise/fall with sized pMOS
NAND22 parallel pMOS, 2 series nMOS4Natural inverting gate; higher electron mobility makes series nMOS fast
NOR22 series pMOS, 2 parallel nMOS4Slower than NAND2 because lower hole mobility requires wider series pMOS
AND2NAND2 stage driving an INVERTER6Two stages; higher latency and area than native NAND2
OR2NOR2 stage driving an INVERTER6Two stages; higher latency and area than native NOR2
XOR2Complex CMOS gate or transmission gates8–12High 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.

Section Exercises

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

Verificationapplication

Derive a full-adder circuit from two half-adders. Give the equations for the intermediate carry and prove that the final carry equals ab+acin+bcinab+ac_{in}+bc_{in}

HintExpand

Express sum and carry-out of the full adder using the intermediate sum and carry signals of two cascaded half adders.

Worked solutionExpand

The first half-adder computes x=a⊕bx=a\oplus b and g=abg=ab the second computes s=x⊕cins=x\oplus c_{in} and h=xcinh=xc_{in} The final carry is g+h=ab+cin(a⊕b)=ab+acin+bcing+h=ab+c_{in}(a\oplus b)=ab+ac_{in}+bc_{in} after expanding XOR and absorbing the duplicate term.

Exercise 1.2.2: Karnaugh Map Minimization and Symmetry

Constructionapplication

Minimize F(a,b,c,d)=Σm(0,2,5,7,8,10,13,15)F(a,b,c,d)=\Sigma m(0,2,5,7,8,10,13,15) and identify any symmetry. Verify the expression on at least one minterm and one zero row.

HintExpand

Group adjacent minterms on a 4-variable K-map and look for XOR/XNOR checkerboard patterns involving variables bb and dd.

Worked solutionExpand

The minterms pair by the high-bit and low-bit symmetries. Grouping the four cells where b⊕d=0b\oplus d=0 gives bˉdˉ+bd\bar b\bar d+bd equivalently F=b⊕d‾F=\overline{b\oplus d} 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

Constructionapplication

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.

HintExpand

Determine how many 2-to-1 multiplexers are needed to select 1 of 8 inputs, and compare a log⁡2(8)\log_2(8)-depth balanced tree against a serial linear chain.

Worked solutionExpand

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

Descriptiontransfer

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.

HintExpand

Find an operand combination where a carry generated at the least significant bit must propagate sequentially through all NN bit positions.

Worked solutionExpand

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

Prooftransfer

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.

HintExpand

Consider how sign bits order opposite-sign operands and how overflow flag VV modifies the sign flag NN during subtraction.

Worked solutionExpand

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

Verificationtransfer

Construct a transition that can glitch in ab+aˉcab+\bar ac Why does adding bcbc cover the static-1 hazard? What timing assumption makes the term useful?

HintExpand

Examine what happens when b=c=1b=c=1 and variable aa changes state if an inverter propagation delay causes both product terms to momentarily drop to 0.

Worked solutionExpand

Set b=c=1b=c=1 and change aa from 0 to 1. The function should stay 1, but abab may fall before aˉc\bar ac rises. The consensus term bcbc 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

Formalisationsynthesis

Propose an assertion set for a 4-bit ALU with ADD, SUB, AND, OR, and XOR. Include one property about unused control codes.

HintExpand

Write algebraic invariants matching outputs to mathematical operations across all opcode modes, and specify defensive defaults for undefined control codes.

Worked solutionExpand

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.

References & Further Reading