Combinational and sequential logic
Combinational circuits compute outputs from current inputs alone; sequential circuits also remember. Together they build every digital system, from calculators to processors.
Combinational circuits
In a combinational circuit, outputs depend only on present inputs, with no memory. Building blocks include multiplexers, which select one of several inputs using select lines; decoders, which activate one of 2^n outputs for an n-bit input; encoders, which do the reverse; and comparators, which test equality or order of binary numbers.
Binary arithmetic circuits
A half adder adds two bits, producing sum = A XOR B and carry = AB. A full adder adds three bits, including an incoming carry. Chaining n full adders forms an n-bit ripple-carry adder, which is simple but slow because carries propagate through every stage; carry-lookahead adders compute carries in parallel. Subtraction uses two's complement: invert the subtrahend and add 1.
Propagation delay
Gates take time to respond, typically picoseconds to nanoseconds. A combinational circuit's critical path, the longest chain of gates from input to output, sets its maximum speed. Briefly incorrect outputs called glitches can appear as signals travel unequal paths, which is why sequential systems sample results only after they settle.
Latches and flip-flops
Sequential circuits store bits using feedback. An SR latch, two cross-coupled NOR or NAND gates, holds a bit set or reset by its inputs. A D flip-flop captures its data input D at the moment the clock rises (edge-triggered) and holds it until the next edge. Flip-flops are the memory elements of registers, counters, and state machines.
Clocks and timing
Synchronous systems use a clock signal so all flip-flops update together. The clock period must exceed the critical path delay plus the flip-flop's setup time, the interval before the clock edge during which data must be stable. A processor clocked at 3 GHz has a period of about 333 picoseconds, so every combinational path between registers must settle within that time.
Registers and counters
A register is a group of flip-flops storing a multi-bit value. Shift registers move bits along one position per clock, converting between serial and parallel data. Counters step through binary sequences on each clock: a 4-bit binary counter counts 0 to 15 and wraps around. Counters divide clock frequencies, count events, and generate timing.
Finite state machines
A finite state machine (FSM) has a set of states stored in flip-flops, logic computing the next state from the current state and inputs, and logic computing outputs. Moore machines' outputs depend only on the state; Mealy machines' outputs also depend on inputs. Traffic lights, vending machines, communication protocols, and processor control units are FSMs.
Worked example
A traffic-light controller with states GREEN, YELLOW, and RED can be encoded in 2 flip-flops (2^2 = 4 codes, one unused): GREEN = 00, YELLOW = 01, RED = 10. A counter times each state; when the timer expires, the next-state logic moves GREEN to YELLOW, YELLOW to RED, and RED to GREEN. As a Moore machine, the lamp outputs depend only on the state bits: green lamp = Q1'Q0'.
Key takeaways
Combinational circuits have no memory: multiplexers, decoders, encoders, and comparators are building blocks. Half adders give sum = A XOR B and carry = AB; full adders chain into ripple-carry adders, sped up by carry lookahead; two's complement handles subtraction. Propagation delay and the critical path limit speed, and glitches occur before outputs settle. Latches and edge-triggered D flip-flops store bits. Clocks synchronise updates; the period must cover critical-path delay plus setup time, about 333 ps at 3 GHz. Registers, shift registers, and counters build on flip-flops. Finite state machines, Moore or Mealy, control sequential behaviour.
Flashcard
Output depends only on present inputs
Check your understanding
What is the main difference between combinational and sequential logic?