Sequential Logic and Finite-State Machines

Introduction

Combinational circuits produce outputs determined only by present inputs. Sequential circuits additionally retain state, so their behavior depends on both present inputs and prior events. This memory enables registers, counters, communication controllers, processors, traffic controllers, and digital timing systems.

Sequential systems are classified as synchronous when state changes are coordinated by a clock and asynchronous when state may change directly in response to inputs. Synchronous design is generally easier to verify, but it still requires rigorous treatment of setup time, hold time, clock skew, metastability, reset behavior, and clock-domain crossings. Asynchronous design can offer low latency and low dynamic power, but races and hazards make its design more demanding.

Learning Objectives

After studying this chapter, students should be able to:

• explain the operation of latches and edge-triggered flip-flops;
• select and derive excitation equations for SR, D, JK, and T storage elements;
• design registers, synchronous counters, ripple counters, and timing circuits;
• evaluate setup, hold, propagation-delay, skew, and clock-frequency constraints;
• explain metastability and design practical synchronizers;
• formulate, encode, implement, and verify Moore and Mealy finite-state machines;
• design a complete traffic-light and pedestrian-control FSM;
• derive latch excitation equations for a fundamental-mode asynchronous system;
• identify races, static hazards, dynamic hazards, and unsafe clocking practices.

1. State, Feedback, and Memory

A sequential circuit contains feedback that preserves information. Its mathematical model is

where Q is the present-state vector, Q⁺ is the next-state vector, X is the input vector, and Z is the output vector. In a Moore machine, outputs depend only on state: Z=G(Q). In a Mealy machine, outputs may depend on both state and inputs: Z=G(Q,X).

A bistable element has two stable states representing binary 0 and 1. A latch is level-sensitive: it may respond throughout an enable level. A flip-flop is normally edge-triggered: it samples its input around a clock transition.

2. Latches and Flip-Flops

2.1 SR latch

For an active-high NOR SR latch, input S sets the output and R resets it.

For valid input combinations, its characteristic equation is

The condition SR=0 is essential; the equation must not be applied to the forbidden case.

2.2 Gated D latch

A D latch removes the normal SR ambiguity by generating complementary set and reset actions. When enable E=1, it is transparent; when E=0, it holds its state:

Long transparency windows can permit data to propagate through several latches. Carefully designed two-phase latch systems prevent such unintended race-through.

2.3 Edge-triggered flip-flops

The D flip-flop has the characteristic equation

The JK flip-flop generalizes the SR element:

When J=K=1, it toggles rather than entering a forbidden state. The T flip-flop obeys

and toggles when T=1.

2.4 Excitation requirements

Excitation tables specify the inputs required to obtain a desired transition. Here, X means “don’t care.”

D flip-flops are particularly convenient because each required input is simply the corresponding next-state equation.

3. Registers and Request Storage

A register is a group of flip-flops sharing control signals. Common forms include parallel-load registers, shift registers, serial-to-parallel converters, and universal shift registers.

For a register bit with load enable L,

where X is the new data bit. This implements a clock enable using data-path logic rather than gating the clock.

Sticky request register with clear priority

A sticky request bit remains set after observing a synchronized pulse P_sync. Let C be an active-high synchronous clear. If clear must have priority over setting, the correct next-state equation is

Thus, C=1 forces R⁺=0 even if P_sync=1. The superficially similar expression P_sync+R\overline{C} is incorrect for clear priority because a simultaneous pulse would still set the register.

An asynchronous reset acts independently of the clock and must normally be asserted reliably and released synchronously. Unsynchronized reset release can violate recovery or removal time and cause different flip-flops to leave reset on different clock cycles.

4. Counters and Digital Timing Circuits

4.1 Ripple counters

In a ripple counter, one flip-flop clocks the next. Each stage divides frequency by two, but transition delays accumulate. If each stage has maximum clock-to-output delay t_CQ, an approximate worst-case settling time for an n-stage chain is nt_CQ. This approximation assumes similar stages and neglects additional decoding delay.

Decoded ripple-counter outputs can glitch while intermediate states ripple through the chain. Ripple counters are therefore suitable mainly for simple frequency division or applications that tolerate settling intervals.

4.2 Synchronous binary counters

All flip-flops in a synchronous counter share one clock. For an up-counter with enable E, T-input equations are

Bit i toggles when all lower-order bits are 1. For D flip-flops,

A modulus-M counter requires at least

flip-flops. If M is not a power of two, unused states must be assigned safe recovery transitions rather than treated carelessly as unreachable.

4.3 Timing circuits

Counters can generate periodic events by counting known clock cycles. With clock frequency f_clk and terminal count N, an event generated every N cycles has period and frequency

These equations assume one event per complete count interval. A square-wave output obtained from a toggling terminal-count flip-flop has a full-wave period of 2N/f_clk.

Clock enables are preferable to internally generated clocks in FPGA and many ASIC designs because enable logic preserves the characterized global clock network. Mechanical switches should be debounced before being interpreted as single digital events.

5. Timing Constraints in Synchronous Systems

A register-to-register path contains a launching flip-flop, combinational logic, and a receiving flip-flop.

Figure: Data and clock paths governing setup and hold constraints.

Let t_skew=t_capture-t_launch, so positive skew means the capture clock arrives later. Ignoring jitter and uncertainty, setup requires

Positive skew helps setup under this sign convention. Hold requires

Positive skew hurts hold. In practice, static timing tools include clock uncertainty, jitter, on-chip variation, and separate early/late clock models. A conservative hand calculation may add an adverse setup-skew allowance s:

Worked timing example

Suppose t_CQ,max=0.18\ ns, t_comb,max=4.10\ ns, t_setup=0.35\ ns, and worst adverse setup uncertainty is s=0.25\ ns. Then

Therefore,

For hold analysis, let t_CQ,min=0.12\ ns, t_comb,min=0.20\ ns, t_hold=0.10\ ns, and positive skew be 0.25\ ns. The data path provides 0.32\ ns, while the requirement is 0.35\ ns. The path fails by 0.03\ ns and needs at least that much additional minimum delay, subject to implementation margin.

Setup failures are normally corrected by reducing combinational delay, pipelining, reducing frequency, or improving clock distribution. Hold failures are corrected by adding minimum data-path delay or adjusting clock distribution—not by lowering the clock frequency.

6. Metastability and Clock-Domain Crossing

A flip-flop can become metastable when its input changes within the setup-and-hold aperture. Its output may temporarily remain between valid logic levels or resolve later than normal. Metastability cannot be eliminated completely; its probability can only be reduced.

A commonly used empirical model for mean time between observable synchronizer failures is

where T_res is available resolution time, \tau and C are technology-dependent fitted parameters, f_clk is destination clock frequency, and f_data is asynchronous transition rate. This is not a universal physical constant; designers must use parameters supplied or characterized for the relevant technology.

A two-flip-flop synchronizer is appropriate for a single slowly changing level. It is not automatically safe for a narrow pulse or a multi-bit bus. Pulses may require stretching, toggling, or request–acknowledge handshakes. Multi-bit values commonly use Gray-coded counters, asynchronous FIFOs, or protocols that hold data stable while a synchronized control signal crosses the boundary.

7. Synchronous Finite-State Machine Design

A disciplined FSM procedure is:

1. Write behavioral requirements and assumptions.
2. Identify inputs, outputs, reset state, and exceptional conditions.
3. Define states by distinguishable future behavior.
4. Construct a complete state-transition/output table.
5. Select Moore or Mealy outputs.
6. Assign binary, one-hot, Gray, or safe encodings.
7. Derive next-state and output equations.
8. Verify unreachable states, reset behavior, and timing constraints.
9. Simulate normal, boundary, and illegal scenarios.

Moore outputs are usually more stable because they depend on registered state. Mealy machines may respond within the current cycle and use fewer states, but input glitches can propagate to outputs unless inputs and outputs are registered appropriately.

8. Detailed Application: Traffic and Pedestrian Controller

This illustrative case models a two-road intersection. North–south (NS) and east–west (EW) green indications must never be active simultaneously. A pedestrian WALK interval is permitted only while both roads show red.

Background and specification

Input T is a one-clock timer-complete pulse. A synchronized pedestrian pulse sets request register R. Eight states are used so that every 3-bit encoding has defined behavior. State 111 provides a recovery/all-red interval. The request is cleared with priority when the controller enters WALK.

Complete transition table

Figure: Complete state progression; the omitted visual self-loop arrows are stated explicitly in the caption and transition table.

Next-state equations

Let I₀ through I₇ be one-hot decoded indicators of binary states 000 through 111. With D flip-flops Q₂,Q₁,Q₀, direct equations derived from the complete table are

For example, I₅=Q₂\overline{Q₁}Q₀. The other indicators follow from their respective codes. These equations are not necessarily minimum-area forms, but they are complete and directly auditable.

The Moore output equations are

The request-clear condition is asserted on the transition from AR2 to WALK:

and the clear-priority request equation is

Safety analysis and outcome

The encoding and output equations ensure that NS green is true only in NG and EW green only in EG; therefore, both cannot be active simultaneously for any registered state. WALK is true only in state 110, where both red equations evaluate to 1. A practical safety controller should additionally detect contradictory lamp-current feedback, use watchdog supervision, define startup behavior, and satisfy applicable transportation standards.

Learning points: complete FSM design requires more than a state sketch. The designer must specify every state, transition, encoding, output equation, reset condition, request-storage rule, and illegal-condition response.

9. Asynchronous Sequential Systems

An asynchronous sequential circuit has no global state clock. The following example uses fundamental-mode assumptions: only one external input changes at a time, and another external change is not allowed until the circuit reaches a stable state.

Four-state handshake controller

Let x be a request and a an acknowledgement. Use Gray-assigned states:

Only one state bit changes on every permitted transition, eliminating critical state races for this sequence. Let output y=q₀, so the outgoing request is active in states B and C.

Using active-high SR latches, excitation terms derived directly from the required state changes are

To verify the derivation, in state A=00 with x=1, only S₀ is asserted, producing B=01. In B=01 with a=1, only S₁ is asserted, producing C=11. In C=11 with x=0, only R₀ is asserted, producing D=10. In D=10 with a=0, only R₁ is asserted, restoring A=00.

Race and hazard verification

For each latch, set and reset cannot be asserted simultaneously: S₀ requires q₁q₀=00, whereas R₀ requires 11; S₁ requires 01, whereas R₁ requires 10. Each excitation is a single product term, so its two-level realization has no static-1 hazard caused by reconvergent product terms. Output y=q₀ is taken directly from a latch and has no combinational decoding hazard.

The Gray sequence ensures that only one state variable is intended to change, so unequal latch delays cannot select an unintended intermediate binary state. Nevertheless, this verification depends on the fundamental-mode input protocol, adequate latch pulse width, monotonic input transitions, and bounded physical delays. Essential hazards can still arise if feedback reaches different internal paths in an unsafe order; post-layout delay analysis or speed-independent synthesis is required for high-assurance implementations.

10. Races, Hazards, and Implementation Discipline

A race occurs when two or more state variables change and the final state depends on relative delays. A race is critical if different delay orders lead to different stable states. Race-free encodings, state insertion, or asynchronous synthesis tools are used to prevent critical races.

A static-1 hazard momentarily drives a function low when it should remain high. For example, F=AB+\overline{A}C can glitch when A changes while B=C=1. Adding the consensus term BC gives

which removes this static-1 hazard in a two-level SOP implementation under the single-input-change assumption. A static-0 hazard is the dual phenomenon, while a dynamic hazard causes multiple transitions when only one is intended.

Best professional practices include using synchronous clock enables, registering externally visible control outputs, synchronizing asynchronous inputs, defining all unused states, constraining timing paths correctly, avoiding logic-generated clocks, and verifying both RTL behavior and implemented timing.

11. Contemporary Practice, Safety, and Governance

Modern FPGA and ASIC tools can infer FSMs, retime registers, detect clock-domain crossings, and formally prove properties. Useful assertions include “opposing greens are never simultaneous,” “every granted request is eventually serviced,” and “WALK implies both traffic directions are red.” AI-assisted design may generate RTL or test cases, but its output must be reviewed against the specification, coding standards, timing reports, and safety properties.

Sequential controllers used in vehicles, medical equipment, industrial protection, or public infrastructure have ethical and regulatory significance. Engineers must document assumptions, design for diagnosability, avoid unverified optimizations, maintain traceability from requirements to tests, and use applicable functional-safety standards. Simulation alone cannot demonstrate the absence of all timing or metastability failures.

Chapter Summary

Sequential circuits retain state through feedback and are modeled using next-state and output functions. Latches are level-sensitive, while flip-flops usually respond at clock edges. Registers store and move data; counters sequence through states and implement division and timing functions. Correct request storage requires explicit priority, such as R⁺=\overline{C}(P_sync+R) for clear priority.

Reliable synchronous design requires separate setup and hold analysis, explicit clock-skew conventions, and appropriate treatment of jitter and uncertainty. Metastability cannot be eliminated, but synchronizers and sound clock-domain-crossing protocols reduce failure probability. FSM design requires complete state definitions, transitions, encodings, equations, reset behavior, and verification. Asynchronous systems additionally require race-free assignments, derived latch excitations, hazard analysis, and explicit environmental assumptions.

Key Terms

Bistable element: Circuit with two stable states used to represent one bit.

Latch: Level-sensitive storage element.

Flip-flop: Storage element that normally samples on a clock edge.

Excitation equation: Equation specifying storage-element inputs needed for desired transitions.

Register: Group of storage elements operating on a multi-bit word.

Ripple counter: Counter whose stages are clocked by preceding stages.

Synchronous counter: Counter whose state elements share a common clock.

Setup time: Minimum interval for which data must be stable before capture.

Hold time: Minimum interval for which data must remain stable after capture.

Clock skew: Difference in clock-arrival times at two state elements.

Metastability: Temporary indeterminate state caused by timing-aperture violation.

Clock-domain crossing: Transfer of information between independently timed domains.

Moore machine: FSM whose outputs depend only on present state.

Mealy machine: FSM whose outputs depend on present state and inputs.

State encoding: Assignment of binary storage patterns to symbolic states.

Critical race: Race whose outcome may be an incorrect stable state.

Static hazard: Unwanted pulse when a Boolean output should remain constant.

Fundamental mode: Asynchronous operating assumption allowing one input change after stability.

Recovery and removal: Timing constraints associated with releasing asynchronous controls.

Formal verification: Mathematical checking of specified properties over all modeled behaviors.

Review Questions

Short Answer Questions

1. Distinguish a level-sensitive latch from an edge-triggered flip-flop.
2. Why does lowering clock frequency not normally correct a hold violation?
3. State the difference between Moore and Mealy output functions.
4. Why can a ripple-counter decoder produce glitches?
5. What assumptions define fundamental-mode asynchronous operation?

Long Answer Questions

1. Derive and compare the characteristic equations of SR, JK, D, and T storage elements.
2. Explain setup, hold, clock skew, jitter, and metastability in a register-to-register path.
3. Describe a complete engineering workflow for designing and verifying a synchronous FSM.
4. Compare synchronous and asynchronous sequential systems in terms of performance, verification, and implementation risk.
5. Explain safe methods for transferring levels, pulses, and multi-bit words across clock domains.

Analytical / Application Questions

1. A path has t_CQ,max=0.25\ ns, t_comb,max=3.60\ ns, t_setup=0.20\ ns, and 0.15\ ns adverse uncertainty. Calculate the minimum clock period and maximum frequency.
2. Extend the traffic controller with an emergency input that immediately requests an all-red state at the next clock edge. Provide the revised transition rules and explain request priority.
3. For the asynchronous handshake controller, evaluate what may occur if x and a change nearly simultaneously, and propose a protocol or circuit-level remedy.

Multiple Choice Questions with Answers

Question 1

For a sticky request bit with active-high clear C having priority over synchronized set input P_sync, which next-state equation is correct?

A. R⁺=P_sync+R\overline{C}

B. R⁺=\overline{C}(P_sync+R)

C. R⁺=C(P_sync+R)

D. R⁺=P_sync\overline{R}+C

Correct Answer: B. R⁺=\overline{C}(P_sync+R)

Question 2

Which characteristic equation describes a T flip-flop?

A. Q⁺=T\oplus Q

B. Q⁺=TQ

C. Q⁺=T+Q

D. Q⁺=\overline{T}Q

Correct Answer: A. Q⁺=T\oplus Q

Question 3

A synchronous modulus-10 counter requires at least how many flip-flops?

A. 2

B. 3

C. 4

D. 10

Correct Answer: C. 4

Question 4

Using the chapter's sign convention, positive clock skew means that the capture clock arrives later. What is its usual effect?

A. It hurts setup and helps hold

B. It helps both setup and hold

C. It helps setup and hurts hold

D. It affects neither constraint

Correct Answer: C. It helps setup and hurts hold

Question 5

A register path has t_CQ,max=0.20\ ns, t_comb,max=3.50\ ns, t_setup=0.30\ ns, and 0.20\ ns adverse uncertainty. What is the conservative minimum clock period?

A. 3.50 ns

B. 3.80 ns

C. 4.00 ns

D. 4.20 ns

Correct Answer: D. 4.20 ns

Question 6

Which remedy directly addresses a hold-time violation?

A. Lowering the clock frequency

B. Adding sufficient minimum delay to the data path

C. Increasing the combinational path's maximum logic depth

D. Removing the receiving register

Correct Answer: B. Adding sufficient minimum delay to the data path

Question 7

Which clock-domain-crossing method is most appropriate for a single slowly changing asynchronous level?

A. A two-flip-flop destination-domain synchronizer

B. A ripple counter

C. An unregistered XOR gate

D. A combinational multiplexer without synchronization

Correct Answer: A. A two-flip-flop destination-domain synchronizer

Question 8

In the traffic-controller design, in which state is the pedestrian WALK output asserted?

A. AR1, code 010

B. AR2, code 101

C. WALK, code 110

D. REC, code 111

Correct Answer: C. WALK, code 110

Question 9

Why is the Gray assignment 00 → 01 → 11 → 10 useful in the asynchronous handshake controller?

A. It makes every transition change both state bits

B. It ensures only one state bit changes on each permitted transition

C. It eliminates the need for storage elements

D. It permits arbitrary simultaneous input changes

Correct Answer: B. It ensures only one state bit changes on each permitted transition

Question 10

For F=AB+\overline{A}C, which consensus term removes the indicated static-1 hazard when B=C=1 and A changes?

A. AC

B. \overline{B}C

C. BC

D. A\overline{C}

Correct Answer: C. BC