Search Knowledge

© 2026 LIBREUNI PROJECT

Computer Architecture/Representation and digital state
Page 3 of 20

Sequential State

Clocks, latches, flip-flops, registers, and finite-state machines.

Lesson briefRepresentation and digital state · 9 h · 3 outcomes

Required knowledge

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

Learning outcomes

  • Model registers and finite-state controllers as transition systems with explicit reset, timing, and illegal-state behavior.
  • Derive next-state logic for counters, handshakes, timers, and clock-domain crossings.
  • Test boundary-cycle behavior and defend a state invariant against missed events or off-by-one errors.

Assessment target

Given a state machine and timing convention, produce its transition trace, prove the safety invariant, and repair one reset or timeout counterexample.

Scope boundary

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

Combinational logic answers a question about the present inputs. A processor, however, must remember a program counter, register contents, outstanding requests, protocol phase, and architectural mode. That memory is state. Sequential logic is the disciplined combination of storage elements and combinational next-state logic. Its correctness depends on both a functional relation—what state should follow what inputs—and a temporal relation—when a new state is allowed to become visible.

This chapter develops the synchronous design model used by most digital systems. It distinguishes latches from edge-triggered registers, derives setup and hold constraints, models finite-state machines formally, and treats asynchronous inputs and reset as sources of metastability and illegal behavior. The purpose is not to draw a traffic light but to make timing and state invariants explicit enough that a pipeline controller, bus arbiter, or cache controller can be reasoned about and tested.

State as a mathematical transition system

A synchronous machine can be modeled as a tuple (S,I,O,δ,λ)(S,I,O,\delta,\lambda) a set of states SS input alphabet II output alphabet OO transition function δ:S×I→S\delta:S\times I\to S and output function λ\lambda At discrete clock boundaries, if the current state is sts_t and the sampled input is iti_t then

st+1=δ(st,it),ot=λ(st,it) or ot=λ(st),s_{t+1}=\delta(s_t,i_t),\qquad o_t=\lambda(s_t,i_t) \text{ or } o_t=\lambda(s_t),

depending on whether the machine is Mealy or Moore. A Mealy output may respond combinationally to an input during a state; a Moore output depends only on registered state. Moore outputs often simplify timing and avoid input glitches at an interface, while Mealy machines may use fewer states and respond within a cycle. Neither is universally superior; the interface contract decides whether an output may change between clock edges.

The state set is an abstraction. A two-bit register physically has four encodings, but a protocol may use only 00, 01, and 10; 11 is illegal. The transition function must define what happens from an illegal encoding, usually by moving to a safe recovery state. Leaving an encoding unconstrained is not the same as proving it unreachable. Faults, reset races, soft errors, X-propagation in simulation, and design bugs can all make an “impossible” state observable.

Worked example: a request controller. Let states be IDLE, BUSY, and ERROR. In IDLE, a request starts work and transitions to BUSY; no request keeps the machine in IDLE. In BUSY, completion transitions to IDLE, while a detected fault transitions to ERROR. In ERROR, reset returns to IDLE and all normal inputs are ignored. The safety invariant is that a request is accepted only in IDLE; the liveness assumption is that a BUSY operation eventually either completes or reports a fault. The hardware design is incomplete until the priority between simultaneous completion and fault is specified.

The diagram completes that contract: reset has highest priority in every state, fault wins over completion in BUSY, and a request during BUSY is not queued. All ordinary transitions sample inputs on the active edge; the global reset rule is omitted from the arrows for legibility.

Code
[*] --> IDLE : reset
IDLE --> BUSY : request / accept pulse
IDLE --> IDLE : no request
BUSY --> ERROR : fault
BUSY --> IDLE : completion AND NOT fault
BUSY --> BUSY : neither completion nor fault
ERROR --> ERROR : no reset
ERROR --> IDLE : reset
note right of BUSY
No new acceptance while busy.
Reset overrides all inputs.
end note
IDLEBUSYERRORNo new acceptance while busy.Reset overrides all inputs.resetrequest / accept pulsecompletion AND NOTfaultno requestfaultneither completion norfaultno resetreset

Trace challenge. Starting in IDLE, sample (request, completion, fault) as (1,0,0), (1,1,1), then (1,1,0), with reset absent. Predict the post-edge states and count accepted requests.

Check the state traceExpand

The states are BUSY, ERROR, ERROR. Exactly one request is accepted, at the first edge. Fault outranks completion at the second edge; the third request cannot escape ERROR without reset. Accepting another request while busy would violate the specified no-queue contract.

State the transition

0 / 4 answered

What is required to specify a synchronous state machine?

Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.

1
A state space, next-state rule, output rule, and clock/reset assumptions
2
A random seed used to choose one transition at each edge
3
Only a list of outputs observed after selected input sequences
4
A cache-line size that fixes how many states can be stored

Latches, flip-flops, and registers

A level-sensitive latch is transparent during an enable phase and holds its previous value otherwise. If enable is high, QQ follows DD after propagation delay; if enable is low, QQ is stable. A pair of latches driven by complementary phases can form an edge-triggered element. A flip-flop is commonly abstracted as sampling DD at a clock edge and retaining that sample until the next active edge:

Q(t+)=D(tsample),Q(t^+)=D(t_{sample}),

where t+t^+ denotes the state just after the edge. A register is a bank of such storage elements, often with a shared clock-enable and reset. The abstract edge-triggered model prevents a combinational path from “seeing through” a storage element during the active edge, which makes cycle-by-cycle reasoning compositional.

The abstraction has limits. A physical flip-flop needs its input stable for a setup interval before the edge and a hold interval after it. If the input changes too close to the edge, the internal feedback may take an unusually long time to resolve to 0 or 1: metastability. The output is not a third logical value in the final system, but it can violate downstream timing while resolving. No finite synchronizer can make metastability impossible; it reduces the probability that unresolved behavior reaches logic by giving the first stage time to settle.

Two flip-flops in series are a common clock-domain crossing synchronizer for a single slowly changing control bit. The first may become metastable; the second samples it one cycle later. This is not safe for a multi-bit bus whose bits can settle on different cycles, nor does it preserve every pulse if the source toggles faster than the destination can observe. Multi-bit data requires a protocol such as a handshake, asynchronous FIFO, gray-coded pointer scheme, or a formally justified sampling method.

A correct truth table can still miss timing

A register's input changes 50 ps before the clock edge, but its setup requirement is 90 ps. Simulation using only Boolean values reports the expected next state.

Which conclusion is justified?

Timing constraints

In a single-clock path, a launching register changes after the clock-to-Q delay tcqt_{cq} combinational logic requires tcombt_{comb} and the receiving register requires data to arrive at least tsetupt_{setup} before the next edge. With clock period TT and skew tskewt_{skew} a simplified setup constraint is

tcq,max+tcomb,max+tsetup≤T+tskew.t_{cq,max}+t_{comb,max}+t_{setup}\le T+t_{skew}.

The corresponding hold constraint is a lower-bound condition: the launching register’s earliest change plus the shortest combinational delay must not reach the receiving register too soon after the same edge. A simplified form is

tcq,min+tcomb,min≥thold+tskew,hold.t_{cq,min}+t_{comb,min}\ge t_{hold}+t_{skew,hold}.

Increasing the clock period can repair setup failure but cannot generally repair hold failure. This distinction matters in pipeline design: a path may be slow enough to miss the next edge, or so short that new data corrupts the old sample immediately after the edge. Adding a register changes latency and may repair setup while creating a new architectural timing contract.

Worked timing calculation. Suppose tcq,max=80t_{cq,max}=80 ps, the worst combinational path is 620 ps, setup time is 90 ps, and the worst skew provides 20 ps of relief. Then T≥80+620+90−20=770T\ge80+620+90-20=770 ps, so the frequency bound from this path is approximately 1.30 GHz. If the shortest path has tcq,min=40t_{cq,min}=40 ps and tcomb,min=15t_{comb,min}=15 ps, with hold requirement 45 ps and no helpful hold skew, the hold inequality is satisfied at 55 ps. Notice that the setup and hold calculations use different extrema; averaging delays would be unsound.

Clock gating and enables add another layer of correctness. A register with enable ee has next-state equation D=e⋅f(s,i)+eˉ⋅sD=e\cdot f(s,i)+\bar e\cdot s meaning it retains state when disabled. A gated clock physically suppresses clock transitions and can save power, but the gate itself must be designed so enable changes cannot create a spurious pulse. A synchronous enable is usually easier to verify than ad hoc combinational clock gating.

Finite-state-machine design flow

A robust design flow begins with an interface contract rather than an encoding. First define events, inputs, outputs, safety properties, liveness assumptions, reset behavior, and simultaneous-event priority. Next identify the smallest state that distinguishes futures: two histories may share a state only if every possible future input produces equivalent outputs and transitions. Then write a state-transition table or graph, choose an encoding, derive next-state logic, and verify the implementation against the transition relation.

State minimization is a behavioral question. If two states produce different outputs for the same input, they cannot be merged. If their outputs match, they can be merged only when their successor states are themselves equivalent under every input. This is the same idea as distinguishing prefixes in automata theory, now applied to a clocked controller. One-hot encoding uses a separate bit for each state, binary encoding uses roughly ⌈log⁡2∣S∣⌉\lceil\log_2|S|\rceil bits, and gray-like encodings can reduce simultaneous bit changes. Encoding affects physical timing and fault detection but not the abstract machine.

Worked example: a ready/valid interface. Suppose a producer presents valid and data, and a consumer presents ready. A transfer occurs on a clock edge exactly when valid && ready. If the producer is allowed to keep data stable while waiting, the controller needs EMPTY and FULL states: EMPTY may accept a new item, FULL holds an item until transfer. If simultaneous dequeue and enqueue are permitted, FULL with both signals high may remain FULL while replacing the data; if not, the enqueue must be rejected. The choice changes throughput and must be stated. A common bug is to clear valid as soon as it is asserted rather than when the handshake condition is true, losing data when the consumer is not ready.

Counters, timers, and derived state

A counter is a register plus an increment, decrement, hold, or load function. For a ww-bit modulo counter, qt+1=(qt+1) mod 2wq_{t+1}=(q_t+1)\bmod2^w A timer that must represent a duration of NN cycles needs a clear convention: does zero mean “expired now,” does it count the current edge, and can reload occur on the expiration edge? Off-by-one errors are semantic errors in δ\delta not merely coding mistakes.

Worked example: a three-cycle timeout. If a request is accepted at edge t0t_0 and the specification says failure should be raised if completion has not arrived by the third subsequent edge, then the relevant checks occur at t1,t2,t3t_1,t_2,t_3 Load 3 at t0t_0 and, at each later edge without completion, decrement then test the new value: it becomes 2, 1, 0 and expires at t3t_3 An equivalent convention loads 2 and tests the old value for zero before decrementing: old values at t1,t2,t3t_1,t_2,t_3 are 2, 1, 0. Loading 2 and testing after decrement instead expires at t2t_2 one edge too early. State whether completion wins over timeout at t3t_3 and test durations 0, 1, 2, 3, and 4 explicitly; duration zero needs its own acceptance-edge rule.

Derived state should be minimized when it can be recomputed without ambiguity. Storing both a count and an empty flag creates a consistency invariant; if one updates and the other does not, the controller can accept or discard data incorrectly. Redundant state is justified when it improves timing or power, but then the equality and update invariants must be asserted.

Reset and initialization

Reset establishes an initial state but does not automatically initialize every physical bit in every technology. A synchronous reset is sampled by the clock; an asynchronous reset can affect state between edges but introduces deassertion timing concerns. A common safe pattern asserts reset asynchronously for rapid containment and deasserts it synchronously per clock domain.

Reset strategies and timing boundaries:

Reset architectureAssertion timingDeassertion timingHardware failure mode / race condition
Pure synchronousOn active clock edgeOn active clock edgeCannot reset if clock is stopped or gated; requires larger gates in logic path
Raw asynchronousImmediate (level-triggered)Asynchronous to clockDeassertion near clock edge violates recovery/removal timing, causing metastability
Synchronized deassertionImmediate (asynchronous)Synchronized via 2-FF chainClean deassertion aligned to clock; eliminates cross-register reset skew
// Reset synchronizer: asynchronous assertion, synchronous deassertion
always @(posedge clk or posedge async_rst) begin
    if (async_rst) begin
        rst_meta <= 1'b1;
        rst_sync <= 1'b1;
    end else begin
        rst_meta <= 1'b0;
        rst_sync <= rst_meta;
    end
end

Reset values should be chosen for safety, not convenience. A bus arbiter should not grant multiple owners after reset; a valid/data queue should begin empty; a privilege controller should begin in the least-authority state. If the state encoding has illegal patterns, reset should enter a legal recovery state and the transition logic should route illegal encodings there as well.

Reset is also a protocol event. Downstream logic must know when outputs are meaningful, and cross-domain consumers must not observe one domain leaving reset while another remains held. A design that “works after reset” in simulation may fail in hardware if deassertion violates recovery/removal timing or if memories and registers initialize differently.

Verification and invariants

The strongest FSM tests are derived from properties. Safety properties say something bad never occurs: never grant two mutually exclusive resources, never dequeue an empty queue, never assert done without a prior accepted request. Liveness properties say something good eventually occurs under assumptions: every accepted request eventually completes or faults, a waiting arbiter eventually grants a continuously requesting client, and a nonempty queue eventually dequeues when the consumer remains ready.

An invariant proof has the form: establish the property in every initial state, assume it before an edge, and show every allowed transition preserves it. For a one-entry queue, the invariant is valid=0 iff no item is stored, and valid=1 implies stored data is stable until a handshake. The proof must consider no operation, enqueue only, dequeue only, and simultaneous enqueue/dequeue. Omitting the simultaneous case is a classic completeness failure.

Simulation explores traces; formal verification can quantify over all input combinations within a bounded or inductive model. Neither replaces a correct environment assumption. An assertion that assumes ready is always high proves little if the actual integration allows backpressure.

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.3.1: Finite State Machine Controller Design

Constructionapplication

Design a four-state elevator controller for floors 0 and 1. Specify state, request input, motor output, door output, reset behavior, illegal-state recovery, and simultaneous arrival/request priority.

HintExpand

Construct state transition diagrams and truth tables with explicit current and next state assignments.

Worked solutionExpand

A correct solution has explicit states such as IDLE_0, MOVING_TO_1, IDLE_1, and MOVING_TO_0, with outputs derived from state. A request received while moving must be queued, ignored, or merged by specification; silently choosing one is not a design. Illegal state encodings should disable the motor and return to a known idle state after reset or fault recovery.

Exercise 1.3.2: Setup and Hold Timing Constraint Equations

Verificationapplication

A path has tcq,max=120t_{cq,max}=120 ps, tcomb,max=1.4t_{comb,max}=1.4 ns, setup 80 ps, and clock skew of -30 ps. Compute the minimum clock period and explain the sign of skew in your equation.

HintExpand

Calculate maximum clock frequency from flip-flop clock-to-Q delay, combinational logic, and setup margins.

Worked solutionExpand

The bound is T≥120+1400+80−(−30)=1630T\ge120+1400+80-(-30)=1630 ps, because negative skew makes the receiving edge effectively earlier relative to the launching edge. The maximum frequency is about 613.5 MHz. The exact sign convention can vary, but the physical question is whether skew gives or removes available setup time.

Exercise 1.3.3: Metastability and Multi-Clock Synchronizers

Descriptiontransfer

Explain why synchronizing each bit of a binary counter independently can produce a value that never existed in the source domain. Give a safer transfer protocol.

HintExpand

Explain the mean time between failures (MTBF) when crossing asynchronous clock domains with dual flip-flops.

Worked solutionExpand

Bits do not cross at the same instant. A source changing from 0111 to 1000 can be sampled as 1111, a mixed value never held by the source. Use a gray-coded counter for pointer transfer when its one-bit transition property is proven, or transfer data with a request/acknowledge handshake or asynchronous FIFO.

Exercise 1.3.4: Ready/Valid Handshake Protocol State Table

Constructiontransfer

Write a complete transition table for a one-entry ready/valid buffer, including simultaneous enqueue and dequeue. State whether it supports fall-through behavior.

HintExpand

Specify valid and ready assertion rules to prevent data loss or duplicate reads across boundaries.

Worked solutionExpand

The buffer is empty when valid=0. Enqueue without dequeue stores data and sets valid; dequeue without enqueue clears valid; neither preserves state; both can replace data and preserve valid if the protocol permits throughput one per cycle. Fall-through requires an additional combinational path from input to output when empty and a different timing contract; a registered buffer does not fall through.

Exercise 1.3.5: Queue Storage Invariant Verification

Prooftransfer

Prove the queue-valid invariant for the four cases of input handshake and output handshake. Identify the case that changes the stored data without changing occupancy.

HintExpand

Prove that enqueue and dequeue operations maintain FIFO order and correct full/empty status flags.

Worked solutionExpand

In an empty state, only an accepted enqueue makes valid true. In a full state, only an accepted dequeue without enqueue makes it false. Neither handshake preserves it. Simultaneous handshake replaces the stored item and preserves occupancy. The proof must include the fact that the producer holds input data stable while valid && !ready.

Exercise 1.3.6: One-Hot vs Binary State Encoding Trade-offs

Descriptionsynthesis

Compare one-hot and binary state encoding for 12 states. Discuss flip-flop count, decode complexity, illegal encodings, and timing rather than declaring one universally better.

HintExpand

Compare flip-flop count, combinational decode logic speed, and power dissipation between encoding strategies.

Worked solutionExpand

One-hot uses 12 state bits and often simple local decode. Of its 212=40962^{12}=4096 bit patterns, exactly 12 have one asserted bit, leaving 4084 illegal encodings, including all-zero and multi-hot values. Binary uses four bits: 12 encodings represent states and four of the 16 encodings remain unused. Binary decode may create deeper logic. Physical fanout, power, synthesis technology, and fault model determine the choice; both schemes need defined illegal-state behavior.

Exercise 1.3.7: Asynchronous Reset Assertion with Synchronous Release

Constructionsynthesis

Give a reset design for a multi-clock system with a producer, consumer, and asynchronous external interrupt. Identify which signals require synchronization and which require a handshake.

HintExpand

Explain how reset synchronizers prevent metastable transitions when releasing circuit resets.

Worked solutionExpand

Reset release should be synchronized independently in each clock domain. A single-bit interrupt request needs synchronization or an asynchronous capture circuit; a multi-bit event needs a handshake or FIFO. The producer and consumer need a defined reset interaction so neither treats stale valid/data as a new transfer.

References & Further Reading