Sequential Circuits

A sequential circuit's output depends on the history of its inputs, not only on their present values. That history is not stored in some diffuse way — it lives entirely in a fixed number of state bits, and everything the circuit can remember must be encodable in those bits.

The consequence is that a sequential circuit with $n$ flip-flops has at most $2^n$ states, and its complete behaviour is a table listing, for every state and every input, the next state and the output. Writing that table is the whole of the analysis, and almost every examinable question is a step of it.

The second organising fact is that a synchronous circuit is a race against the clock period. Combinational logic between two flip-flops must settle before the next edge arrives, and that single inequality determines the maximum clock frequency, explains setup and hold violations, and justifies pipelining.

The third is that latches and flip-flops differ in when they listen, not in what they store. A latch is transparent while its enable is asserted; a flip-flop captures only at an edge. Nearly every timing question turns on that distinction.

1. Latches

An SR latch is built from two cross-coupled NOR gates, or equivalently two cross-coupled NAND gates. Setting $S$ stores a 1 and setting $R$ stores a 0, while both low holds the previous value.

Asserting $S$ and $R$ together is forbidden in the NOR version, because it drives both outputs to 0, breaking the invariant that $Q$ and $\overline{Q}$ are complements. Worse, when both inputs are released simultaneously, the final state depends on which gate is faster — a race condition with an unpredictable outcome.

The gated SR latch adds an enable, so the inputs take effect only while the enable is asserted. The D latch fixes the forbidden state entirely by deriving $R$ from $\overline{S}$, so the two can never be asserted together.

A D latch is transparent while the enable is high: the output follows the input continuously. That transparency is precisely the problem in a clocked system, because a signal can pass through several latches in one clock phase.

2. Flip-Flops

A flip-flop samples its input at a clock edge rather than during a level, which stops the transparency problem.

Edge triggering is achieved either by a master-slave pair of latches driven by opposite clock phases, or by an edge-detecting circuit. In the master-slave arrangement, the master is transparent while the clock is high and the slave while it is low, so data advances by exactly one stage per clock cycle.

The four types differ in how their inputs map to the next state.

The JK flip-flop removes the forbidden state by redefining it as a toggle, which is why it is the most general of the four and why any other type can be built from it.

A T flip-flop is a JK with both inputs tied together, and a D flip-flop is a JK with $K$ tied to $\overline{J}$. Conversions in the other direction need a small amount of combinational logic derived from the excitation table.

3. Excitation Tables

A characteristic equation answers "given the inputs, what is the next state". An excitation table answers the reverse: "given the required transition, what inputs are needed".

The X entries are don't cares and they are the reason JK designs minimise so well. Every JK transition has one don't care, which supplies free flexibility on the K-map.

The design procedure for any synchronous sequential circuit follows a fixed sequence: draw the state diagram, build the state table, assign binary codes to states, use the excitation table to find the flip-flop inputs for each transition, minimise those input functions with K-maps, and draw the circuit.

Only the excitation-table step depends on which flip-flop type is used, which is why converting a design between types is mechanical.

4. Timing

Two constraints bound every flip-flop.

Setup time is the interval before the clock edge during which the data input must already be stable. Hold time is the interval after the edge during which it must remain stable. Violating either can drive the flip-flop into a metastable state, where the output hovers between levels for an unbounded time.

For two flip-flops separated by combinational logic, the clock period must accommodate the whole path:

$T_{clk}\ge T_{cq}+T_{comb}+T_{setup}$

where $T_{cq}$ is the clock-to-output delay of the first flip-flop and $T_{comb}$ is the worst-case combinational delay between them.

The maximum clock frequency is the reciprocal of that minimum period, and it is set by the slowest path in the design, not the average one. This is exactly why pipelining raises clock frequency: inserting registers shortens the longest combinational path.

The hold constraint is different in kind, because it does not involve the clock period at all:

$T_{cq}+T_{comb,min}\ge T_{hold}$

A hold violation cannot be fixed by slowing the clock, since the inequality has no clock term. It is fixed by adding delay to the fast path, which is why a design can fail hold timing at any frequency.

Clock skew — the difference in clock arrival time between two flip-flops — relaxes one constraint and tightens the other, which is why clock distribution is designed so carefully.

5. Registers and Shift Registers

A register is a group of flip-flops sharing a clock, storing a word. A shift register additionally connects each output to the next input, so data moves one position per clock.

Four configurations are named by how data enters and leaves.

A SIPO register is a serial-to-parallel converter and a PISO is the reverse, which is what makes them the core of any serial communication interface.

Two feedback arrangements produce counters from shift registers. A ring counter feeds the last output back to the first input and cycles through $n$ states for $n$ flip-flops, using a one-hot encoding.

A Johnson or twisted-ring counter feeds back the complement and cycles through $2n$ states, doubling the count at the cost of a decoding that is slightly less trivial. Neither uses the full $2^n$ states available, which is the trade for having no decoding logic at all in the ring case.

6. Counters

An asynchronous or ripple counter clocks each flip-flop from the output of the previous one. The delays accumulate, so the last stage settles only after $n$ flip-flop delays, and during that interval the counter shows transient values that are simply wrong.

Those transients are why ripple counters cannot drive decoders directly without glitches, and why they are unsuitable for high frequencies.

A synchronous counter clocks every flip-flop from the same edge, so all stages change together and the only delay is one flip-flop delay plus the combinational logic feeding the inputs. The cost is that combinational logic, which grows with the number of stages.

A modulo-$N$ counter needs $\lceil {\log }_{2}N\rceil$ flip-flops. A mod-10 counter therefore needs 4, and the six unused states must be handled — either by forcing a reset when the count reaches 10, or by treating them as don't cares in the design.

A counter that can enter an unused state and never return is said to lack self-correction. A self-correcting design guarantees that every unused state eventually leads back into the main cycle, which matters because power-up state is arbitrary.

7. Finite State Machines

A finite state machine is the general form of a sequential circuit, and the two styles differ only in where the output is computed.

In a Moore machine the output depends only on the current state. In a Mealy machine it depends on the current state and the current input.

The consequences are precise and are examined directly.

A Mealy machine reacts a cycle earlier because the input feeds the output directly, which is an advantage when latency matters and a liability when the output must be glitch-free.

Any Mealy machine can be converted to a Moore machine and vice versa. Converting Mealy to Moore generally increases the state count, because a state that produces different outputs for different inputs must be split into several states, each carrying one output value.

8. State Minimisation

Two states are equivalent if, for every possible input sequence, they produce the same output sequence. Merging equivalent states reduces the flip-flop count when it crosses a power-of-two boundary.

The partitioning method finds equivalences systematically. Begin by partitioning states into groups producing the same output. Then repeatedly split any group whose members transition, under some input, into different groups. When no further split occurs, each remaining group is a set of equivalent states.

The termination condition is worth stating exactly: stop when a full pass produces no new split. Stopping early leaves distinguishable states merged, and the resulting machine is simply wrong.

Reducing the state count does not always reduce hardware. Going from 5 states to 4 saves a flip-flop, since 4 states need 2 bits while 5 need 3, but going from 8 to 7 saves nothing, because both still need 3 bits and the next-state logic may even grow.

9. Worked Examples

Example 1. A JK flip-flop has $J=1$ and $K=1$ applied continuously with a 100 MHz clock. What is the frequency at the output?

With $J=K=1$, the characteristic equation $Q^{+}=J\overline{Q}+\overline{K}Q$ becomes $Q^{+}=\overline{Q}$, so the flip-flop toggles on every clock edge.

Two clock edges are therefore required for the output to complete one full cycle: one to go from 0 to 1 and one to return.

The output frequency is half the clock frequency: 50 MHz.

This is exactly why a chain of toggling flip-flops forms a ripple counter, with each stage halving the frequency again. A 4-stage chain divides by 16.

Example 2. A synchronous circuit has flip-flops with clock-to-output delay 2 ns, setup time 1 ns and hold time 0.5 ns, separated by combinational logic with worst-case delay 6 ns and best-case delay 0.4 ns. Find the maximum clock frequency and check the hold constraint.

Apply the setup inequality.

$T_{clk}\ge T_{cq}+T_{comb}+T_{setup}=2+6+1=9\text{ ns}$

The maximum frequency is $1/9$ ns, which is approximately 111 MHz.

Now check hold, using the minimum combinational delay because the danger is data arriving too early.

$T_{cq}+T_{comb,min}=2+0.4=2.4$ ns, which must be at least the hold time of 0.5 ns. Since 2.4 exceeds 0.5, the hold constraint is satisfied.

The point worth extracting is that the two constraints use opposite extremes of the combinational delay: setup uses the worst case and hold uses the best case. And had hold failed, slowing the clock would not have helped, because the clock period appears nowhere in the hold inequality.

Example 3. How many flip-flops are needed for a mod-12 counter, and how many states are unused?

The number of flip-flops is $\lceil {\log }_{2}12\rceil$.

Three flip-flops give 8 states, which is insufficient. Four give 16, which suffices.

So 4 flip-flops are needed, counting 0 through 11.

The unused states are 12, 13, 14 and 15, that is 4 unused states.

Those four must be handled deliberately. The usual approach is to detect the count reaching 12 and force an asynchronous clear, which returns the counter to 0. The alternative is to treat the four as don't cares during minimisation, which produces simpler logic but risks a design that can lock up if it powers on in an unused state.

A self-correcting design is one where every unused state leads back into the main cycle within a few clocks, and checking this requires computing the next state for each unused code rather than assuming the don't cares behaved conveniently.

Example 4. Convert a D flip-flop into a T flip-flop.

The required behaviour is $Q^{+}=T\oplus Q$, and the available flip-flop obeys $Q^{+}=D$.

Equating the two: $D=T\oplus Q$.

So the conversion needs a single XOR gate, with $T$ and the flip-flop's own $Q$ output as its inputs, feeding the $D$ input.

Verify against the excitation table. When $T=0$ the flip-flop must hold, and $D=0\oplus Q=Q$, which reloads the current value. When $T=1$ it must toggle, and $D=1\oplus Q=\overline{Q}$, which does exactly that.

The general procedure for any conversion is the same: write the characteristic equation of the target, write the characteristic equation of the available device, and solve for the available device's inputs in terms of the target's inputs and $Q$.

Example 5. A Mealy machine detects the sequence 101 on a serial input, with overlapping allowed. How many states does it need, and how many would a Moore machine need?

The Mealy machine needs three states, tracking how much of the pattern has been seen.

State $S_0$: nothing matched yet. State $S_1$: a 1 has been seen. State $S_2$: 10 has been seen.

From $S_2$, an input of 1 completes the pattern, so the output is asserted on that transition. Because overlapping is allowed, the machine then moves to $S_1$ rather than $S_0$, since the final 1 can begin the next match.

Three states suffice for the Mealy version, because the output is attached to a transition rather than to a state.

A Moore machine needs a fourth state. Since its output depends only on the state, there must be a distinct state that means "pattern just completed" and carries output 1. From that state, the machine behaves like $S_1$ on subsequent inputs.

So the Moore version needs four states, and its output appears one clock cycle later than the Mealy version's — the standard trade of a cleaner, registered output against an extra cycle of latency.

Example 6. Reduce the machine with states A, B, C, D where the outputs are A: 0, B: 0, C: 1, D: 0, and the next states on input 0 are A to B, B to A, C to D, D to B, and on input 1 are A to C, B to C, C to A, D to C.

Begin with an output partition. States with output 0 are $\{A,B,D\}$ and with output 1 is $\{C\}$.

Now split any group whose members go to different groups under some input. Call the first group $P_1$ and the second $P_2$.

Under input 0: A goes to B, which is in $P_1$. B goes to A, in $P_1$. D goes to B, in $P_1$. All three agree.

Under input 1: A goes to C, in $P_2$. B goes to C, in $P_2$. D goes to C, in $P_2$. All three agree again.

No split occurs on this pass, so the partition is final: $\{A,B,D\}$ and $\{C\}$.

All three of A, B and D are equivalent and merge into a single state, so the machine reduces from 4 states to 2.

That reduction crosses a power-of-two boundary — 2 states need 1 flip-flop where 4 needed 2 — so it saves genuine hardware. Note that the termination condition was a complete pass with no split, and stopping after examining only input 0 would have reached the same partition here but does so only by luck.

Summary

All of a sequential circuit's history lives in its state bits, so $n$ flip-flops give at most $2^n$ states and the state table is the complete description.

A latch is transparent while enabled; a flip-flop captures only at an edge, which is what stops data racing through several stages in one clock phase.

The SR latch has a forbidden input combination; the JK removes it by redefining that case as a toggle, which is why any other type can be built from a JK.

Excitation tables invert the characteristic equations and are the only design step that depends on the flip-flop type.

The clock period must exceed $T_{cq}+T_{comb}+T_{setup}$, using the worst-case combinational delay. The hold constraint uses the best-case delay and contains no clock term, so a hold violation cannot be fixed by slowing the clock.

A ring counter gives $n$ states and a Johnson counter $2n$, neither using the full $2^n$.

Ripple counters accumulate delay and show transient wrong values; synchronous counters change together at the cost of extra logic.

A mod-$N$ counter needs $\lceil {\log }_{2}N\rceil$ flip-flops, and the unused states must be handled or the design may not self-correct.

Moore outputs depend on state alone and change only at clock edges; Mealy outputs depend on state and input, respond a cycle earlier, and can glitch. Mealy machines usually need fewer states.

State minimisation partitions by output, then splits repeatedly until a full pass produces no split — and it saves hardware only when the count crosses a power-of-two boundary.