Unit 10: Sequential Circuit Design

Unit Overview (click to expand)

Welcome to Unit 10, where we take the flip-flops from the previous unit and put them to work in complete sequential circuits — circuits that count, shift data, and make decisions over time. We begin with registers — groups of flip-flops working together to store multi-bit data. Shift registers move data one bit at a time in several configurations: serial-in serial-out, serial-in parallel-out, parallel-in serial-out, and the universal shift register that combines all capabilities. Next, we tackle counters. Ripple counters are simple but suffer from cumulative delays. Synchronous counters solve this by clocking every flip-flop simultaneously. You will design up-counters, down-counters, modulo-N counters, BCD counters, ring counters, and Johnson counters. The highlight of this unit is the finite state machine, or FSM. There are two models: Moore machines, where outputs depend only on the current state, and Mealy machines, where outputs depend on both the current state and inputs. Mealy machines can respond faster, but Moore machines are often simpler to design. You will express FSM behavior using state diagrams and state tables, choose a state encoding, and follow a systematic design procedure. As a practical application, we design sequence detectors — circuits that monitor a stream of bits and signal when a particular pattern appears. **Key Takeaways** 1. Registers and shift registers store and move multi-bit data, providing the essential storage and data-transfer building blocks used in processors and communication interfaces. 2. Synchronous counters overcome the speed limitations of ripple counters, and specialized types such as modulo-N, BCD, ring, and Johnson counters serve a wide range of applications. 3. Finite state machines — in both Moore and Mealy forms — provide a systematic methodology for designing sequential circuits that follow a defined sequence of states.

Summary

This unit brings together the concepts from previous units to design complete sequential circuits. Students will learn to design registers for parallel data storage and shifting, construct counters for various counting sequences, and master the systematic design of finite state machines (FSMs). The FSM design methodology—from state diagrams through state tables to optimized circuit implementations—forms the capstone of introductory digital design, enabling students to create controllers and sequencers that respond to inputs and produce timed output sequences.

Concepts Covered

Register Fundamentals
Parallel Load Registers
Shift Register Operation
Serial-In-Serial-Out (SISO) Register
Serial-In-Parallel-Out (SIPO) Register
Parallel-In-Serial-Out (PISO) Register
Bidirectional Shift Registers
Universal Shift Register
Counter Fundamentals
Asynchronous (Ripple) Counters
Synchronous Counters
Binary Up Counter Design
Binary Down Counter Design
Up/Down Counter
Modulo-N Counters
BCD Counter (Decade Counter)
Ring Counter
Johnson Counter
Finite State Machine Concepts
Moore Machine Model
Mealy Machine Model
State Diagram Representation
State Table Construction
State Assignment Strategies
FSM Design Procedure
Next State Logic Design
Output Logic Design
One-Hot State Encoding
State Minimization
Sequence Detector Design

Prerequisites

Before studying this unit, students should be familiar with:

Flip-flops: D, JK, and T types (Unit 9)
Timing diagrams and timing parameters (Unit 9)
Characteristic and excitation tables (Unit 9)
K-map simplification (Unit 5)
Combinational building blocks (Unit 8)

10.1 Introduction to Sequential Circuit Design

The preceding unit established how individual flip-flops store single bits of information and respond to clock edges. This unit takes the next step: combining multiple flip-flops with combinational logic to build functional sequential systems — registers that store and manipulate multi-bit data, counters that generate ordered sequences, and finite state machines that implement complex control behavior.

Sequential circuit design is the capstone of introductory digital logic. Every processor, communication controller, and embedded system relies on the design methodologies presented here. The three major categories of sequential circuits form a natural progression of complexity:

Category	Purpose	Key Characteristic	Design Complexity
Registers	Store and transfer multi-bit data	Parallel or serial data movement	Low
Counters	Generate counting sequences	Predetermined state sequence	Medium
Finite State Machines	Implement arbitrary control logic	Input-dependent state transitions	High

All three categories share a common architecture: flip-flops hold the current state, combinational logic computes the next state and outputs, and a clock signal synchronizes state transitions. The difference lies in how the next-state logic is structured and how complex the state-transition rules are.

Design Hierarchy

Registers and counters are actually special cases of finite state machines with highly regular next-state logic. Understanding them as separate categories simplifies learning, but recognizing their common FSM foundation deepens architectural understanding.

10.2 Register Fundamentals

A register is a group of flip-flops that collectively store a multi-bit binary word. An $n$-bit register consists of $n$ flip-flops sharing a common clock signal, with each flip-flop storing one bit of the word.

Registers are the most fundamental storage elements in digital systems. They appear everywhere:

Data registers in processors hold operands and results
Address registers point to memory locations
Instruction registers hold the currently executing instruction
Status registers store condition flags
I/O registers buffer data to and from peripherals

The two fundamental operations on registers are parallel load (writing all bits simultaneously) and shift (moving bits one position per clock cycle).

10.3 Parallel Load Registers

A parallel load register accepts all $n$ data bits simultaneously on a single clock edge, making it ideal for capturing the output of a combinational circuit or receiving data from a bus.

10.3.1 Structure

A 4-bit parallel load register consists of:

Four D flip-flops with a common clock
Four data inputs: $D_3, D_2, D_1, D_0$
Four outputs: $Q_3, Q_2, Q_1, Q_0$
A Load enable signal

10.3.2 Operation

The Load signal determines whether the register accepts new data or retains its current value:

Load	Clock Edge	Operation
0	$\uparrow$	Hold — all $Q_i$ retain current values
1	$\uparrow$	Load — each $Q_i$ receives corresponding $D_i$

The Load function is implemented by placing a 2-to-1 multiplexer at each flip-flop's D input. When Load = 1, the MUX selects the external data input. When Load = 0, the MUX feeds back the flip-flop's current output, creating a hold condition.

Input Equation for Each Flip-Flop

$D_i^{FF} = Load \cdot D_i + Load' \cdot Q_i$

where:

$D_i^{FF}$ is the actual D input to the $i$-th flip-flop
$D_i$ is the external data input
$Q_i$ is the current output of the $i$-th flip-flop
$Load$ is the load enable signal

Diagram: 4-Bit Parallel Load Register

When Load = 1, each MUX selects the external data input $D_i$. When Load = 0, the MUX feeds back $Q_i$ (dashed red), holding the current value. All four flip-flops share a single clock line (blue bus at bottom) and a single Load control line (orange bus at top).

10.4 Shift Register Operation

A shift register moves data bit by bit through a chain of flip-flops. On each clock pulse, the content of each flip-flop transfers to the next flip-flop in the chain, while new data enters from one end.

10.4.1 Basic Shift Right Operation

In a 4-bit shift-right register, each flip-flop's D input is connected to the Q output of the flip-flop to its left:

$D_i = Q_{i+1}$ for $i = 0, 1, 2$

$D_3 = Serial\_In$

On each rising clock edge, all bits shift one position to the right, and a new bit enters at the leftmost position (MSB).

10.4.2 Shift Register Types

Shift registers are classified by their input and output configurations:

Serial-In-Serial-Out (SISO)

The SISO register accepts data one bit at a time through a serial input and produces output one bit at a time from the serial output (the last flip-flop's Q). Data must be shifted through all $n$ stages before it appears at the output.

Use case: Serial communication, data delay lines
Latency: $n$ clock cycles to pass a bit from input to output

Serial-In-Parallel-Out (SIPO)

The SIPO register accepts serial input but makes all flip-flop outputs available simultaneously. After $n$ clock cycles of shifting, the complete $n$-bit word is available at the parallel outputs.

Use case: Serial-to-parallel conversion (e.g., receiving serial data for parallel processing)
Latency: $n$ clock cycles to fill the register

Parallel-In-Serial-Out (PISO)

The PISO register loads all bits simultaneously via parallel inputs, then shifts them out one at a time through the serial output.

Use case: Parallel-to-serial conversion (e.g., transmitting parallel data over a serial link)
Operation: Load parallel data (1 cycle), then shift out (n cycles)

Type	Serial In	Parallel In	Serial Out	Parallel Out	Primary Application
SISO	Yes	No	Yes	No	Delay lines, data buffering
SIPO	Yes	No	No	Yes	Serial-to-parallel conversion
PISO	No	Yes	Yes	No	Parallel-to-serial conversion
PIPO	No	Yes	No	Yes	Parallel storage (same as load register)

4-Bit SISO Shift Register Trace:

Clock Cycle	Serial In	$Q_3$	$Q_2$	$Q_1$	$Q_0$ (Serial Out)
0 (initial)	—	0	0	0	0
1	1	1	0	0	0
2	0	0	1	0	0
3	1	1	0	1	0
4	1	1	1	0	1

After 4 clock cycles, the first bit entered (1) appears at the serial output.

MicroSim: Shift Register Simulator

10.5 Bidirectional and Universal Shift Registers

10.5.1 Bidirectional Shift Register

A bidirectional shift register can shift data in either direction—left or right—controlled by a direction signal:

Direction = 0: Shift right ($D_i = Q_{i+1}$, serial input at MSB)
Direction = 1: Shift left ($D_i = Q_{i-1}$, serial input at LSB)

A 2-to-1 multiplexer at each flip-flop's D input selects between the left-neighbor output (for shift right) and the right-neighbor output (for shift left).

10.5.2 Universal Shift Register

The universal shift register is the most versatile shift register design, combining all capabilities into a single module controlled by a 2-bit mode selector.

Universal Shift Register Mode Table

$S_1$	$S_0$	Operation
0	0	Hold — no change
0	1	Shift right — data moves toward LSB
1	0	Shift left — data moves toward MSB
1	1	Parallel load — all bits loaded simultaneously

The 74194 is the classic TTL implementation of a 4-bit universal shift register. Each flip-flop's D input is driven by a 4-to-1 multiplexer controlled by $S_1S_0$, selecting among:

$Q_i$ (current value, for hold)
$Q_{i+1}$ (left neighbor, for shift right)
$Q_{i-1}$ (right neighbor, for shift left)
$D_i$ (parallel input, for load)

Input Equation for Bit i

\[D_i^{FF} = \overline{S_1}\,\overline{S_0}\,Q_i + \overline{S_1}\,S_0\,Q_{i+1} + S_1\,\overline{S_0}\,Q_{i-1} + S_1\,S_0\,D_i\]

where:

$D_i^{FF}$ is the actual input to flip-flop $i$
$S_1, S_0$ are the mode select signals
$Q_{i+1}$ is the left-neighbor output (shift right source)
$Q_{i-1}$ is the right-neighbor output (shift left source)
$D_i$ is the parallel data input

Diagram: Single Bit-Slice of Universal Shift Register

The following diagram shows the internal structure of one bit position ($i$). Each of the four flip-flops in the 74194 has an identical 4:1 MUX driving its D input. The four MUX inputs correspond directly to the four terms of the input equation above.

Design Pattern

The universal shift register illustrates a key design pattern: multiplexers at flip-flop inputs create multi-function registers. By increasing the MUX size, additional operations can be supported without changing the flip-flop structure.

10.6 Counter Fundamentals

A counter is a sequential circuit that cycles through a predetermined sequence of states, typically representing a binary counting pattern. Counters are among the most widely used sequential circuits, appearing in:

Timers and clocks: Counting clock cycles to measure elapsed time
Address generators: Sequentially addressing memory locations
Event counters: Counting occurrences of external events
Frequency dividers: Producing lower-frequency signals from a reference clock
Control sequencers: Stepping through phases of a multi-cycle operation

The two fundamental counter architectures differ in their clocking strategy:

Architecture	Clock Distribution	Speed	Complexity
Asynchronous (ripple)	Each FF clocked by previous FF output	Slow (cumulative delay)	Simple
Synchronous	All FFs share common clock	Fast (single delay)	More complex logic

10.7 Asynchronous (Ripple) Counters

In an asynchronous or ripple counter, only the first flip-flop receives the external clock signal. Each subsequent flip-flop is clocked by the output of the preceding stage, creating a cascading "ripple" of state changes.

10.7.1 4-Bit Ripple Up Counter

Structure:

4 T flip-flops, each permanently set to $T = 1$ (always toggle on every active clock edge)
$FF_0$ is clocked by the external clock — it is the only flip-flop that receives the system clock directly
$FF_1$ is clocked by the falling edge of $Q_0$
$FF_2$ is clocked by the falling edge of $Q_1$
$FF_3$ is clocked by the falling edge of $Q_2$

Because each flip-flop toggles at half the frequency of its clock source, every stage acts as a divide-by-2 circuit. This cascading division naturally produces the binary counting sequence.

Circuit Diagram

Each output toggles at half the frequency of its clock input, acting as a divide-by-2 stage. The state change "ripples" through the chain — $Q_0$ changes first, then $Q_1$ after one $t_{cq}$ delay, then $Q_2$ after two, and $Q_3$ after three. This accumulated delay is the fundamental tradeoff of the ripple counter: simple structure, but slow settling.

Frequency Division

Output	Frequency	Division	Toggles per CLK cycle
$Q_0$	$f_{CLK}/2$	÷ 2	Every clock edge
$Q_1$	$f_{CLK}/4$	÷ 4	Every 2nd clock edge
$Q_2$	$f_{CLK}/8$	÷ 8	Every 4th clock edge
$Q_3$	$f_{CLK}/16$	÷ 16	Every 8th clock edge

Counting Sequence (first 8 of 16 states)

Clock Pulse	$Q_3$	$Q_2$	$Q_1$	$Q_0$	Decimal
0	0	0	0	0	0
1	0	0	0	1	1
2	0	0	1	0	2
3	0	0	1	1	3
4	0	1	0	0	4
5	0	1	0	1	5
6	0	1	1	0	6
7	0	1	1	1	7
...	...	...	...	...	...
15	1	1	1	1	15
16	0	0	0	0	0 (wraps)

10.7.2 Ripple Effect and Timing

The fundamental limitation of ripple counters is the accumulated propagation delay. In a 4-bit ripple counter, the worst-case delay for all bits to settle is:

Ripple Counter Settling Time

$t_{settle} = n \cdot t_{cq}$

where:

$t_{settle}$ is the total time for all outputs to reach valid values
$n$ is the number of flip-flop stages
$t_{cq}$ is the clock-to-Q delay of each flip-flop

During this settling period, the counter outputs pass through intermediate invalid states. For a 4-bit counter transitioning from 0111 to 1000, the outputs might momentarily show 0110, 0100, and 0000 before settling to 1000—creating glitches on any combinational logic driven by the counter outputs.

MicroSim: Counter Simulator

10.8 Synchronous Counters

Synchronous counters eliminate the ripple problem by connecting all flip-flops to the same clock signal. Every flip-flop transitions simultaneously at each clock edge, and combinational logic determines which flip-flops should toggle.

Diagram: Synchronous Counter Design Flow

Designing a synchronous counter follows a systematic procedure. Starting from the desired counting sequence, the designer constructs a state table, determines the required flip-flop inputs using excitation tables, simplifies those inputs with K-maps, and finally implements and verifies the circuit.

flowchart TD
    A["<b>1. Define Counting Sequence</b>\nSpecify the desired states\nand their order (e.g. 0→1→…→15→0)"] --> B["<b>2. Construct State Table</b>\nList each present state and\nits corresponding next state"]
    B --> C["<b>3. Determine Flip-Flop Inputs</b>\nUse excitation tables to find\nrequired D, T, J, K inputs\nfor each state transition"]
    C --> D["<b>4. K-map Simplification</b>\nCreate a K-map for each\nflip-flop input and simplify"]
    D --> E["<b>5. Derive Logic Equations</b>\nExtract minimized Boolean\nexpressions from K-maps"]
    E --> F["<b>6. Implement Counter Circuit</b>\nConnect flip-flops with the\nderived combinational logic"]
    F --> G["<b>7. Verify with Timing Diagram</b>\nSimulate to confirm correct\ncounting sequence and timing"]

    style A fill:#E8DAEF,stroke:#7D3C98,color:#333
    style B fill:#D6EAF8,stroke:#2980B9,color:#333
    style C fill:#D5F5E3,stroke:#27AE60,color:#333
    style D fill:#FDEBD0,stroke:#E67E22,color:#333
    style E fill:#FADBD8,stroke:#E74C3C,color:#333
    style F fill:#FCF3CF,stroke:#F1C40F,color:#333
    style G fill:#D4E6F1,stroke:#2E86C1,color:#333

10.8.1 Binary Up Counter Design

The key design insight is determining when each bit should toggle. Look carefully at the first several values of the 4-bit binary counting sequence and notice how each column behaves:

Decimal	$Q_3$	$Q_2$	$Q_1$	$Q_0$	What toggles on the next clock edge
0	0	0	0	0	$Q_0$ (always toggles)
1	0	0	0	1	$Q_1$ and $Q_0$ (because $Q_0 = 1$)
2	0	0	1	0	$Q_0$
3	0	0	1	1	$Q_2$, $Q_1$, $Q_0$ (because $Q_1 Q_0 = 11$)
4	0	1	0	0	$Q_0$
...

The pattern: a bit at position $i$ toggles when all of the lower-order bits ($Q_0$ through $Q_{i-1}$) are simultaneously 1 — that is, when the lower portion of the counter is about to overflow and carry into bit $i$.

Synchronous Up Counter Toggle Equations

$T_0 = 1$

$T_1 = Q_0$

$T_2 = Q_0 \cdot Q_1$

$T_3 = Q_0 \cdot Q_1 \cdot Q_2$

In general, the toggle input for bit $i$ is the AND (logical product) of every lower-order output:

$T_i = \prod_{j=0}^{i-1} Q_j$

where:

$T_i$ is the toggle input for flip-flop $i$
$Q_j$ is the current output of flip-flop $j$
The $\prod$ symbol denotes a logical AND (product) of all terms from $j = 0$ to $j = i - 1$

Reading the equations in plain language:

$Q_0$ toggles on every clock edge ($T_0 = 1$, always true).
$Q_1$ toggles only when $Q_0 = 1$ (the ones place is about to carry).
$Q_2$ toggles only when $Q_0 = Q_1 = 1$ (the two lowest bits are both 1).
$Q_3$ toggles only when $Q_0 = Q_1 = Q_2 = 1$ (the three lowest bits are all 1).

10.8.2 Binary Down Counter Design

A down counter counts in reverse: $1111 \rightarrow 1110 \rightarrow 1101 \rightarrow \cdots \rightarrow 0000 \rightarrow 1111$.

The logic mirrors the up counter, but with complemented outputs. A bit at position $i$ toggles when all lower-order bits are simultaneously 0 — meaning the lower portion is about to underflow and borrow from bit $i$:

$T_0 = 1$

$T_1 = Q_0'$

$T_2 = Q_0' \cdot Q_1'$

$T_3 = Q_0' \cdot Q_1' \cdot Q_2'$

In plain language: $Q_1$ toggles when $Q_0 = 0$, $Q_2$ toggles when $Q_0 = Q_1 = 0$, and so on. Compare this directly with the up counter — the only change is replacing each $Q_j$ with its complement $Q_j'$.

10.8.3 Up/Down Counter

An up/down counter combines both counting directions into a single circuit using a direction control signal $Dir$:

When $Dir = 1$: Count up — use $Q_j$ in the toggle terms (carry logic)
When $Dir = 0$: Count down — use $Q_j'$ in the toggle terms (borrow logic)

The idea is to place a multiplexer-like expression at each stage that selects between $Q_j$ (for up) and $Q_j'$ (for down), controlled by $Dir$.

Up/Down Counter Toggle Equation

$T_i = \prod_{j=0}^{i-1} (Dir \cdot Q_j + Dir' \cdot Q_j')$

where:

$Dir$ is the direction control signal (1 = count up, 0 = count down)
The expression $(Dir \cdot Q_j + Dir' \cdot Q_j')$ acts like a 2-to-1 MUX: it passes $Q_j$ when $Dir = 1$ and $Q_j'$ when $Dir = 0$
The $\prod$ (logical AND) chains these MUX terms together, just as in the individual up and down counters

Dir	Counting Direction	Toggle Condition for Bit $i$	Logic Used
1	Up	All lower bits are 1 (carry)	$Q_j$ terms
0	Down	All lower bits are 0 (borrow)	$Q_j'$ terms

10.9 Modulo-N Counters

A modulo-N counter (or mod-N counter) counts through exactly $N$ states before repeating. A standard 4-bit binary counter is modulo-16. Designing counters with non-power-of-two modulus requires additional logic to truncate the counting sequence.

10.9.1 Design Methods

Method 1: Synchronous Reset

Detect the terminal count value and reset all flip-flops:

Build a standard binary counter
Add a combinational circuit that detects state $N$
Use the detection output to force all flip-flops to 0 on the next clock edge

Method 2: Synchronous Preset

Load a specific starting value to skip unwanted states:

Build a standard binary counter
Detect the terminal state
Load a preset value (e.g., for mod-N, load $16 - N$ in a 4-bit counter)

10.9.2 Example: Mod-6 Counter

A standard 3-bit binary counter has 8 states (000 through 111). A mod-6 counter uses only 6 of those 8 states (000 through 101), then resets back to 000 — skipping states 110 and 111 entirely.

Counting sequence:

\[000 \rightarrow 001 \rightarrow 010 \rightarrow 011 \rightarrow 100 \rightarrow 101 \rightarrow 000 \text{ (reset)}\]

State Diagram

Design Using the Reset Method

The idea is straightforward: build a normal 3-bit binary counter, then add a small combinational circuit that detects the first unwanted state (110 = decimal 6) and immediately resets all flip-flops to 000.

Step-by-step:

A standard 3-bit binary counter has 8 states: $000 \rightarrow 001 \rightarrow 010 \rightarrow 011 \rightarrow 100 \rightarrow 101 \rightarrow 110 \rightarrow 111$
For a mod-6 counter, we only need the first 6 states (000–101). When the counter reaches state 110 (the first unwanted state), the detection logic produces a Reset = 1 signal, preventing the counter from ever reaching 111
The Reset signal is connected directly to the asynchronous CLR inputs of all flip-flops, forcing an immediate return to 000 — no clock edge is needed
The counter then restarts the sequence from 000, giving the repeating cycle: $000 \rightarrow 001 \rightarrow 010 \rightarrow 011 \rightarrow 100 \rightarrow 101 \rightarrow (110 \rightarrow 000)$

Reset detection logic:

The counter must reset when $Q_2 Q_1 Q_0 = 110$. We detect $Q_2 = 1$, $Q_1 = 1$, and $Q_0 = 0$ simultaneously, then feed the result to the asynchronous CLR inputs of all flip-flops:

\[\text{Reset} = Q_2 \cdot Q_1 \cdot \overline{Q_0}\]

Normal 3-Bit Counter vs Mod-6 Counter

Property	Normal 3-Bit Counter	Mod-6 Counter
Flip-flops	3	3
Total states	8 (000–111)	6 (000–101)
Extra logic	None	AND gate + NOT gate
Sequence	000 → 001 → ... → 111 → 000	000 → 001 → ... → 101 → (110 → 000)
Reset method	None	Async CLR via AND + NOT
Skipped states	None	110 (momentary), 111 (never reached)

Glitch Consideration

The reset method causes a brief glitch: the counter momentarily enters state 110 before the reset logic forces it back to 000. In synchronous designs (where the Reset signal drives the synchronous clear input), this transient is resolved within the same clock cycle. In asynchronous designs (where Reset drives an asynchronous clear), the 110 state appears for approximately one gate delay — external circuits may see this transient.

10.9.3 BCD Counter (Decade Counter)

The BCD counter (also called a decade counter) is a mod-10 counter that counts from 0000 to 1001 (0 to 9 in decimal), then resets to 0000. It is the fundamental building block for decimal counting systems.

Design approach:

Standard 4-bit counter with reset detection for state 1010 (decimal 10)
Or: modify the toggle equations to skip states 1010 through 1111

The 7490 is the classic TTL decade counter IC. BCD counters can be cascaded to count in multiple decimal digits: units, tens, hundreds, etc.

Counter	Modulus	States	Flip-Flops Needed	Application
Binary (4-bit)	16	0–15	4	General counting
Mod-6	6	0–5	3	Seconds/minutes (tens digit)
Mod-10 (BCD)	10	0–9	4	Decimal counting
Mod-12	12	0–11	4	Hours (12-hour clock)
Mod-60	60	0–59	6	Minutes/seconds

10.10 Ring Counter and Johnson Counter

Two special counter types use shift register feedback to generate non-binary counting sequences with advantageous properties.

10.10.1 Ring Counter

A ring counter is a circular shift register where the output of the last flip-flop feeds back to the input of the first. Initialization is critical: the counter must start with exactly one flip-flop set to 1 and all others cleared to 0. Once initialized, that single 1 bit circulates through the stages — in an $n$-bit ring counter, exactly one flip-flop is 1 at any time, producing a one-hot encoded sequence. This means each counter state can be identified by reading a single flip-flop output, eliminating the need for decoding logic.

4-Bit Ring Counter Sequence:

Clock Cycle	$Q_3$	$Q_2$	$Q_1$	$Q_0$	Active State
0	1	0	0	0	State 0
1	0	1	0	0	State 1
2	0	0	1	0	State 2
3	0	0	0	1	State 3
4	1	0	0	0	State 0 (repeat)

Properties:

$n$ flip-flops produce $n$ states (inefficient use of flip-flops)
Each state is decoded by a single flip-flop output (no decoding logic needed)
One-hot encoding is inherently glitch-free
Must be initialized to a valid one-hot state (exactly one flip-flop set to 1, all others 0)

The single "1" circulates through the register: 1000 → 0100 → 0010 → 0001 → 1000 ... This is a classic example of one-hot encoding, where each state has exactly one bit set — making state decoding trivial.

10.10.2 Johnson Counter (Twisted Ring Counter)

A Johnson counter (also called a twisted ring counter) feeds the complement $\overline{Q_0}$ of the last flip-flop's output back to the input of the first flip-flop. Initialization: the counter must start with all flip-flops cleared to 0 (state 0000). This single "twist" in the feedback path doubles the number of unique states compared to a ring counter — an $n$-bit Johnson counter produces $2n$ states.

4-Bit Johnson Counter Sequence:

Clock Cycle	$Q_3$	$Q_2$	$Q_1$	$Q_0$	Decoded State
0	0	0	0	0	State 0
1	1	0	0	0	State 1
2	1	1	0	0	State 2
3	1	1	1	0	State 3
4	1	1	1	1	State 4
5	0	1	1	1	State 5
6	0	0	1	1	State 6
7	0	0	0	1	State 7
8	0	0	0	0	State 0 (repeat)

Properties:

$n$ flip-flops produce $2n$ states (better efficiency than ring counter)
Each state can be decoded with a single 2-input AND gate (examining adjacent flip-flop pairs)
Glitch-free outputs due to adjacent-bit-change property (similar to Gray code)
Must be initialized to all-zeros state (0000)

The complement feedback (the "twist") doubles the state count: 0000 → 1000 → 1100 → 1110 → 1111 → 0111 → 0011 → 0001 → 0000. Notice that only one bit changes between adjacent states — this Gray-code-like property makes Johnson counter outputs inherently glitch-free.

Comparison of Counter Types

Counter Type	Flip-Flops for $n$ States	Decoding Logic	Self-Correcting	Glitch-Free
Binary	$\lceil\log_2 n\rceil$	Complex ($n$-input)	Yes	No
Ring	$n$	None (1-hot)	No	Yes
Johnson	$n/2$	Simple (2-input AND)	No	Yes

10.11 Finite State Machine Concepts

A finite state machine (FSM) is the most general form of sequential circuit. Unlike registers and counters, which have fixed or simple state sequences, an FSM's next state depends on both the current state and the current inputs. FSMs can implement arbitrary sequential behavior, from simple pattern detectors to complex protocol controllers.

An FSM is formally defined by five elements:

States ($S$): A finite set of states $\{S_0, S_1, \ldots, S_{k-1}\}$
Inputs ($I$): A finite set of input symbols
Outputs ($O$): A finite set of output symbols
Next-state function ($\delta$): $S_{next} = \delta(S_{current}, I)$
Output function ($\lambda$): Depends on the machine model (Moore or Mealy)

The two FSM models differ only in how outputs are generated.

Diagram: General FSM Structure

Every FSM shares the same fundamental architecture: combinational logic computes the next state and outputs, while flip-flops store the current state. The feedback path from the flip-flop outputs back to the combinational logic input is what makes the circuit sequential.

10.12 Moore Machine Model

In a Moore machine, the outputs depend only on the current state — the current input values have no direct influence on the outputs. Once the FSM enters a given state, its outputs are fully determined and remain constant until the machine transitions to a different state on the next active clock edge. By contrast, a Mealy machine allows outputs to depend on both the current state and the current inputs, which can produce faster responses but also introduces the possibility of output glitches between clock edges.

Moore Output Function

$O = \lambda(S)$

where:

$O$ is the output vector
$S$ is the current state
$\lambda$ is the output function (maps each state to a fixed output value)

Key characteristics:

Outputs are tied to states, not to transitions — every time the machine is in a given state, the output is the same regardless of input values
Outputs change synchronously — they update only at a clock edge when the state itself changes
Output values remain stable for the entire clock period, making Moore machines inherently resistant to output glitches
Moore machines often require more states than an equivalent Mealy machine, because each unique output value must map to a distinct state
Preferred when clean, glitch-free outputs are critical (e.g., outputs driving other synchronous logic or external devices)

In a Moore state diagram, outputs are written inside the state circles (or listed below the state name), because the output belongs to the state itself:

   ┌────────────┐                ┌────────────┐
   │    S0      │   input = 1    │    S1      │
   │   Z = 0    │───────────────▶│   Z = 1    │
   └────────────┘                └────────────┘
     ▲  input = 0                  │  input = 0
     └─────────────────────────────┘

Notice that the output value ($Z$) appears inside each state box, not on the transition arrows. The arrows carry only the input condition that triggers the transition. This is the hallmark of a Moore diagram — if you need to know the output, look at the state, not the arrow.

10.13 Mealy Machine Model

In a Mealy machine, the outputs depend on both the current state and the current inputs. Unlike a Moore machine — where knowing the state alone determines the output — a Mealy machine's output can change immediately whenever an input changes, even in the middle of a clock period. This direct input-to-output path gives Mealy machines faster response but also makes their outputs more sensitive to input noise.

Mealy Output Function

$O = \lambda(S, I)$

where:

$O$ is the output vector
$S$ is the current state
$I$ is the current input vector
$\lambda$ is the output function (maps each state-and-input combination to an output value)

Key characteristics:

Outputs are tied to transitions, not to states — the same state can produce different outputs depending on the current input values
Outputs can change asynchronously whenever inputs change, even between clock edges
Mealy machines often require fewer states than an equivalent Moore machine, because a single state can produce multiple output values via different transitions
Outputs may respond one clock cycle earlier than a Moore equivalent, since they react to inputs immediately rather than waiting for a state change
More susceptible to output glitches if inputs change asynchronously or arrive with different propagation delays

In a Mealy state diagram, outputs are written on the transition arrows using the notation input/output. Each arrow is labeled with the input condition that triggers the transition and the output produced during that transition:

   ┌────────────┐              ┌────────────┐
   │            │   0 / 0      │            │
   │     S0     │─────────────▶│     S1     │
   │            │              │            │
   └────────────┘              └────────────┘
     ▲  1 / 0                    │  1 / 1
     └───────────────────────────┘

Notice that each arrow carries both the input and the output (separated by a slash), while the state boxes contain only the state name. This is the hallmark of a Mealy diagram — if you need to know the output, look at the arrow, not the state.

10.13.1 Moore vs Mealy Comparison

Feature	Moore Machine	Mealy Machine
Output depends on	State only	State + inputs
Output location in diagram	Inside state circles	On transition arrows
Output timing	Changes at clock edges only	Can change between clock edges
Output stability	Glitch-free	May glitch with input changes
Number of states	Often more	Often fewer
Response latency	One clock cycle slower	Immediate response
Preferred for	Clean, synchronous outputs	Faster response, fewer states

Both models are equally powerful—any Moore machine can be converted to an equivalent Mealy machine and vice versa. The choice depends on design requirements.

Diagram: Moore vs Mealy Sequence Detector Comparison

Both diagrams below detect the "01" pattern — the output $Z = 1$ whenever the two most recent input bits form "01". The Moore machine places the output inside each state circle, while the Mealy machine places it on each transition arrow as input/output.

Moore Machine — "01" Detector (output depends on state only)

S0 (Idle): No part of "01" seen. Input 0 → S1; input 1 → stay in S0.
S1 (Seen 0): Got a '0'. Input 1 completes "01" → S2; input 0 → stay in S1.
S2 (Detected 01): Output $Z = 1$. Input 0 → S1 (new attempt); input 1 → S0 (reset).

Mealy Machine — "01" Detector (output depends on state + input)

S0 (Idle): Input 0 → S1 (output 0); input 1 → stay in S0 (output 0).
S1 (Seen 0): Input 1 → S0 with output $Z = 1$ (pattern detected on the transition); input 0 → stay in S1 (output 0).

Comparison: Moore vs Mealy for "01" Detector

Feature	Moore	Mealy
Number of states	3 (S0, S1, S2)	2 (S0, S1)
Output labeled	Inside state circles	On transition arrows (input/output)
Detection output	Appears in S2 (one clock cycle after "01" arrives)	Appears immediately on the S1→S0 transition
Output timing	Synchronous — changes only at clock edges	Asynchronous — can change between clock edges
Output stability	Glitch-free	May glitch if input changes between clock edges
Why the difference?	Needs a dedicated state to hold Z=1	Produces Z=1 directly on the detecting transition

The Mealy machine uses fewer states because it produces the output immediately on the detecting transition, eliminating the need for a separate "detection" state. The Moore machine is safer because its outputs are purely synchronous.

Diagram: Moore vs Mealy State Diagrams

Diagram: Moore vs Mealy Interactive Comparison

10.14 State Diagram Representation

A state diagram (also called a state graph) is a directed graph that visually represents an FSM's behavior. It is the starting point for FSM design and the primary tool for communicating sequential behavior.

10.14.1 State Diagram Elements

Element	Symbol	Purpose
State	Circle	Represents a unique internal condition
Transition	Directed arrow	Shows state change for given input
Initial state	Arrow from nowhere (or double circle)	Identifies the starting state
Input label	Text on arrow	Condition that triggers the transition
Output label	Text inside circle (Moore) or on arrow (Mealy)	Output value(s)

10.14.2 State Diagram Construction Rules

When constructing a state diagram:

Completeness: Every state must have an outgoing transition for every possible input combination
Determinism: For each state and input combination, there must be exactly one next state
Reachability: Every state should be reachable from the initial state
Output specification: Outputs must be defined for every state (Moore) or every transition (Mealy)

Example: Moore vs Mealy State Diagram Notation

stateDiagram-v2
    direction LR

    state "Moore Example" as moore {
        state "S0 / Z=0" as MS0
        state "S1 / Z=1" as MS1
        [*] --> MS0
        MS0 --> MS1 : X=1
        MS1 --> MS0 : X=0
        MS0 --> MS0 : X=0
        MS1 --> MS1 : X=1
    }

    state "Mealy Example" as mealy {
        state "S0" as YS0
        state "S1" as YS1
        [*] --> YS0
        YS0 --> YS1 : X=1 / Z=0
        YS1 --> YS0 : X=0 / Z=1
        YS0 --> YS0 : X=0 / Z=0
        YS1 --> YS1 : X=1 / Z=0
    }

In Moore notation, outputs appear inside the state circle (State/Output). In Mealy notation, outputs appear on the transition arrows (Input/Output).

10.15 State Table Construction

A state table (or transition table) is the tabular equivalent of a state diagram, listing every state-input combination with its corresponding next state and output. State tables are easier to work with mathematically and are the bridge between the state diagram and the circuit implementation.

10.15.1 Moore Machine State Table Format

Current State	Input $X$	Next State	Output $Z$
$S_0$	0	$S_0$	0
$S_0$	1	$S_1$	0
$S_1$	0	$S_2$	0
$S_1$	1	$S_1$	0
...	...	...	...

Note: In a Moore table, the output column depends only on the current state (same output value for all input rows of a given state).

10.15.2 Mealy Machine State Table Format

Current State	Input $X$	Next State	Output $Z$
$S_0$	0	$S_0$	0
$S_0$	1	$S_1$	0
$S_1$	0	$S_2$	1
$S_1$	1	$S_1$	0
...	...	...	...

In a Mealy table, the output column depends on both the current state and the input (output can differ for different inputs in the same state).

10.16 State Assignment Strategies

State assignment is the process of mapping abstract state names ($S_0, S_1, \ldots$) to binary codes stored in the flip-flops. The choice of state assignment significantly affects the complexity of the next-state and output logic.

10.16.1 Common Strategies

Strategy	Assignment for 4 States	Flip-Flops	Next-State Logic
Binary (sequential)	00, 01, 10, 11	$\lceil\log_2 N\rceil$	Moderate
Gray code	00, 01, 11, 10	$\lceil\log_2 N\rceil$	Often simpler
One-hot	0001, 0010, 0100, 1000	$N$	Very simple
Output-based	Codes chosen to match output values	$\lceil\log_2 N\rceil$ +	May eliminate output logic

10.16.2 Binary Encoding

The simplest approach: assign consecutive binary numbers to states. Uses the minimum number of flip-flops ($\lceil\log_2 N\rceil$ for $N$ states) but may produce complex next-state logic.

10.16.3 One-Hot Encoding

One-hot encoding assigns one flip-flop per state. Exactly one flip-flop is 1 in each state. For $N$ states, this requires $N$ flip-flops.

Advantages:

Next-state logic is typically simple OR/AND of state bits and inputs
Easy to add or remove states
Well suited for FPGAs (where flip-flops are abundant)
Timing is often better due to fewer logic levels

Disadvantages:

Uses more flip-flops ($N$ instead of $\lceil\log_2 N\rceil$)
Illegal states possible (must handle recovery)

Binary vs One-Hot Encoding for 4 States

flowchart TB
    subgraph BINARY["Binary Encoding (2 FFs)"]
        direction TB
        BS0["S0 = 00"]
        BS1["S1 = 01"]
        BS2["S2 = 10"]
        BS3["S3 = 11"]
    end

    subgraph ONEHOT["One-Hot Encoding (4 FFs)"]
        direction TB
        OS0["S0 = 0001"]
        OS1["S1 = 0010"]
        OS2["S2 = 0100"]
        OS3["S3 = 1000"]
    end

    style BINARY fill:#D6EAF8,stroke:#2980B9,color:#333
    style ONEHOT fill:#D5F5E3,stroke:#27AE60,color:#333

Number of States	Binary Flip-Flops	One-Hot Flip-Flops	Logic Levels (typical)
4	2	4	Binary: 2–3, One-hot: 1–2
8	3	8	Binary: 3–4, One-hot: 1–2
16	4	16	Binary: 4–5, One-hot: 1–2
32	5	32	Binary: 5–6, One-hot: 1–2

10.17 FSM Design Procedure

The systematic FSM design procedure transforms a behavioral specification into an optimized circuit implementation. This seven-step methodology applies to both Moore and Mealy machines.

Step 1: Problem Specification

Define the FSM behavior precisely:

Identify all inputs and outputs
Describe the desired behavior in words or by example
Specify whether Moore or Mealy is preferred
Identify the reset/initial state

Step 2: State Diagram

Draw the state diagram:

Create states for each unique condition the machine must distinguish
Add transitions for every input combination from every state
Verify completeness and determinism
Label outputs appropriately

Step 3: State Table

Convert the state diagram to tabular form:

List all state-input combinations
Fill in next state and output columns
Verify consistency with the state diagram

Step 4: State Minimization

Reduce the number of states (if possible):

Identify equivalent states (same outputs and equivalent next states)
Merge equivalent states
Update the state table

Step 5: State Assignment

Choose binary codes for each state:

Select encoding strategy (binary, Gray, one-hot)
Assign codes considering logic optimization
Create the binary transition table

Step 6: Next-State and Output Logic Design

Derive the combinational logic equations:

Write the transition table with binary state variables
For each flip-flop input, create a K-map or use algebraic methods
If using D flip-flops: the next-state variable equals the flip-flop D input ($D_i = Q_i^+$)
If using JK flip-flops: use the excitation table to determine J and K inputs
Derive output equations from the output columns

Step 7: Circuit Implementation

After deriving the state transitions and logic equations, the final step is to implement the hardware circuit. The implementation includes five key components:

Flip-flops to store the current state — one flip-flop per state bit (e.g., two D flip-flops for a 4-state FSM with binary encoding)
Next-state combinational logic to compute the next state from the current state and inputs, using the minimized equations from Step 6
Output logic to generate the FSM outputs — derived from state variables only (Moore) or from state variables and inputs (Mealy)
Reset circuitry to initialize the machine to a known starting state on power-up or when a reset signal is asserted
Timing simulation to verify that the circuit produces the correct state sequence and outputs for all input scenarios before committing to hardware

MicroSim: FSM Designer

10.18 Next-State Logic Design

The next-state logic is the combinational circuit that computes the next state ($Q^+$) from the current state ($Q$) and inputs ($X$). The design approach depends on the flip-flop type used.

Diagram: Next-State Logic Block Diagram

The following block diagram shows the general architecture of an FSM implemented with D flip-flops. The input $X$ and the current state outputs ($Q_1, Q_0$) feed into the next-state combinational logic, which computes the D inputs ($D_1, D_0$). On each rising clock edge, the flip-flops capture these values as the new state. The output logic derives $Z$ from the state variables (Moore) or from both state and input (Mealy).

The red dashed feedback path is what makes the circuit sequential — the current state outputs feed back into the next-state logic, creating a loop that is broken only by the clock edge.

10.18.1 Using D Flip-Flops

With D flip-flops, the design is straightforward because:

$D_i = Q_i^+$

The D input of each flip-flop equals the desired next-state value for that bit. Simply derive the next-state expressions from K-maps and connect them directly to the D inputs.

10.18.2 Using JK Flip-Flops

With JK flip-flops, use the excitation table (from Unit 9) to determine $J$ and $K$ inputs:

$Q$	$Q^+$	J	K
0	0	0	X
0	1	1	X
1	0	X	1
1	1	X	0

The don't-care entries often allow simpler logic expressions than the D flip-flop approach. After determining $J$ and $K$ for each state variable and input combination, use K-maps to minimize the expressions.

10.18.3 Design Example: D Flip-Flop Approach

Consider a 3-state Moore FSM with binary assignment $S_0 = 00$, $S_1 = 01$, $S_2 = 10$, one input $X$, and one output $Z$.

Transition table:

$Q_1$	$Q_0$	$X$	$Q_1^+$	$Q_0^+$	$Z$
0	0	0	0	0	0
0	0	1	0	1	0
0	1	0	1	0	0
0	1	1	0	1	0
1	0	0	0	0	1
1	0	1	0	1	1
1	1	0	d	d	d
1	1	1	d	d	d

State $Q_1 Q_0 = 11$ is unused — all its entries are don't cares (marked "d"), meaning the designer is free to assign 0 or 1 to simplify the logic equations.

K-map simplification:

K-map for $D_1$ ($Q_1^+$)

Reading the K-map: The single 1-cell sits at row $Q_1Q_0 = 01$, column $X = 0$. It groups vertically with the don't-care cell at row $Q_1Q_0 = 11$ (same column $X = 0$). Grouping these two adjacent cells eliminates the variable $Q_1$ (which changes between the two rows), leaving the common variables $Q_0 = 1$ and $X = 0$:

Result: $D_1 = Q_0 \cdot X'$

Since this is the only group, no OR operation is needed. For the 3-state example, the remaining equations are:

$D_1 = Q_0 \cdot X'$

$D_0 = X$

$Z = Q_1$

10.19 Output Logic Design

The output logic produces the FSM's output signals from the state variables (Moore) or from the state variables and inputs (Mealy).

10.19.1 Moore Output Logic

Moore outputs are purely a function of the current state:

$Z = f(Q_1, Q_0, \ldots)$

Derive output expressions using K-maps with only state variables. In the example above, $Z = Q_1$ — the output equals the MSB of the state encoding.

10.19.2 Mealy Output Logic

Mealy outputs depend on both state and inputs:

$Z = f(Q_1, Q_0, \ldots, X_1, X_0, \ldots)$

Derive output expressions using K-maps with both state variables and input variables. Mealy output equations are typically more complex but the FSM may require fewer states.

Output-Based State Assignment

Sometimes choosing state codes so that the output value matches one or more state bits can eliminate the output logic entirely. For example, if a Moore machine has $Z = 1$ in states $S_2$ and $S_3$ and $Z = 0$ in $S_0$ and $S_1$, assigning $S_0 = 00$, $S_1 = 01$, $S_2 = 10$, $S_3 = 11$ makes $Z = Q_1$ — a free output with no additional gates.

Diagram: Complete FSM Hardware Circuit (3-State Example)

This circuit implements the 3-state Moore FSM from Section 10.18.3 using the derived equations: $D_1 = Q_0 \cdot X'$, $D_0 = X$, and $Z = Q_1$. Notice how simple the output logic is — $Z$ is just the $Q_1$ wire, requiring no additional gates.

The circuit has only three logic elements beyond the flip-flops: one NOT gate (to produce $X'$), one AND gate (to compute $D_1 = Q_0 \cdot X'$), and a direct wire for $D_0 = X$. The output $Z = Q_1$ requires no gate at all — the state encoding was chosen so that $Q_1$ directly represents the output.

10.20 Sequence Detector Design — Complete Example

The sequence detector is the classic FSM design exercise, tying together all concepts in this unit. We design a Moore machine to detect the input sequence "101" in a serial bit stream, with overlapping detection allowed.

Step 1: Specification

Input: $X$ (1-bit serial input)
Output: $Z = 1$ when the three most recent inputs form "101"
Overlap: After detecting "101", the final "1" can start a new detection
Model: Moore machine
Initial state: No bits of pattern received

Step 2: State Diagram

The machine must track how much of the target pattern "101" has been received:

$S_0$ (output $Z = 0$): No progress toward pattern. Initial state.
$S_1$ (output $Z = 0$): Received "1" — first bit of pattern matches.
$S_2$ (output $Z = 0$): Received "10" — first two bits match.
$S_3$ (output $Z = 1$): Received "101" — pattern detected!

Transitions:

From	Input	To	Reasoning
$S_0$	0	$S_0$	"0" doesn't start "1..."
$S_0$	1	$S_1$	"1" starts the pattern
$S_1$	0	$S_2$	"10" — two bits match
$S_1$	1	$S_1$	"11" — the latest "1" could still start a new "1..."
$S_2$	0	$S_0$	"100" — no suffix matches any prefix of "101"
$S_2$	1	$S_3$	"101" — pattern complete!
$S_3$	0	$S_2$	Overlap: "1" from "101" + "0" = "10"
$S_3$	1	$S_1$	Overlap: "1" from "101" starts new detection

Step 3: State Table

Current State	$X = 0$	$X = 1$	Output $Z$
$S_0$	$S_0$	$S_1$	0
$S_1$	$S_2$	$S_1$	0
$S_2$	$S_0$	$S_3$	0
$S_3$	$S_2$	$S_1$	1

Step 4: State Assignment (Binary)

$S_0 = 00$, $S_1 = 01$, $S_2 = 10$, $S_3 = 11$

Step 5: Binary Transition Table

$Q_1$	$Q_0$	$X$	$Q_1^+$	$Q_0^+$	$Z$
0	0	0	0	0	0
0	0	1	0	1	0
0	1	0	1	0	0
0	1	1	0	1	0
1	0	0	0	0	0
1	0	1	1	1	0
1	1	0	1	0	1
1	1	1	0	1	1

Step 6: K-Map Simplification

For $D_1 = Q_1^+$:

Two groups emerge from the K-map:

Green group (rows 01 and 11, column $X = 0$): The common variables are $Q_0 = 1$ and $X = 0$, giving the term $Q_0 \cdot X'$
Blue group (row 10, column $X = 1$): This isolated cell gives $Q_1 \cdot Q_0' \cdot X$

Combining both groups with OR:

$D_1 = Q_0 X' + Q_1 Q_0' X$

For $D_0 = Q_0^+$:

Constructing the K-map for $D_0$ reveals that $Q_0^+ = 1$ whenever $X = 1$, regardless of the current state. Therefore:

$D_0 = X$

For output $Z$:

Since this is a Moore machine, $Z$ depends only on the state. From the transition table, $Z = 1$ only when $Q_1 = 1$ and $Q_0 = 1$ (state $S_3$):

$Z = Q_1 Q_0$

Step 7: Verification

Let's trace the input sequence $X = 1, 0, 1, 0, 1$ starting from $S_0$:

Clock	$X$	State	$Q_1Q_0$	$Z$	Comment
0	—	$S_0$	00	0	Initial
1	1	$S_1$	01	0	Received "1"
2	0	$S_2$	10	0	Received "10"
3	1	$S_3$	11	1	Received "101" — detected!
4	0	$S_2$	10	0	Overlap: "10"
5	1	$S_3$	11	1	"101" detected again!

The output correctly goes high whenever the pattern "101" has been received, and overlapping detection works as specified.

Diagram: "101" Sequence Detector — State Diagram

The Moore state diagram for the "101" sequence detector with overlapping detection. Each state shows its output value, and transitions are labeled with the input bit.

stateDiagram-v2
    direction LR
    state "S0 — Idle\nZ = 0" as S0
    state "S1 — Got '1'\nZ = 0" as S1
    state "S2 — Got '10'\nZ = 0" as S2
    state "S3 — Got '101'\nZ = 1" as S3

    [*] --> S0
    S0 --> S0 : 0
    S0 --> S1 : 1
    S1 --> S1 : 1
    S1 --> S2 : 0
    S2 --> S0 : 0
    S2 --> S3 : 1
    S3 --> S2 : 0
    S3 --> S1 : 1

Diagram: "101" Sequence Detector — Hardware Circuit

The complete hardware implementation using D flip-flops with the derived equations: $D_1 = Q_0 X' + Q_1 Q_0' X$, $D_0 = X$, and $Z = Q_1 Q_0$.

The circuit uses two D flip-flops for the two state bits, combinational logic (AND, OR, NOT gates) to implement $D_1 = Q_0 X' + Q_1 Q_0' X$, a direct connection for $D_0 = X$, and a single AND gate for the output $Z = Q_1 Q_0$. The red dashed feedback paths carry the current state back to the next-state logic, completing the sequential loop.

MicroSim: Sequence Detector Demo

Diagram: Sequence Detector Interactive State Machine

10.21 State Minimization

State minimization reduces the number of states in an FSM while preserving identical input-output behavior. Fewer states means fewer flip-flops and potentially simpler next-state logic.

10.21.1 Equivalent States

Two states $S_i$ and $S_j$ are equivalent if and only if:

They produce the same output (for Moore machines: same output value; for Mealy machines: same output for every input)
For every possible input, their next states are also equivalent

10.21.2 Implication Table Method

The implication table is a systematic technique for identifying equivalent states:

Create a triangular table with all state pairs
Mark pairs with different outputs as non-equivalent (X)
For remaining pairs, list the implied state pairs that must also be equivalent
Iteratively mark pairs as non-equivalent if any of their implied pairs are non-equivalent
Repeat until no more changes occur
Unmarked pairs are equivalent and can be merged

flowchart TB
    subgraph STEP["Implication Table Method"]
        direction TB
        S1["① Create triangular table\nof all state pairs"]
        S2["② Mark pairs with\ndifferent outputs ✗"]
        S3["③ List implied pairs\nfor remaining entries"]
        S4["④ Iteratively mark\nnon-equivalent pairs ✗"]
        S5["⑤ Repeat until\nno changes"]
        S6["⑥ Merge unmarked\n(equivalent) pairs ✓"]
        S1 --> S2 --> S3 --> S4 --> S5 --> S6
    end

    style STEP fill:#FDEBD0,stroke:#E67E22,color:#333

10.21.3 Example

Consider an FSM with 4 states where analysis reveals that $S_1$ and $S_3$ are equivalent (same outputs and their next states are also equivalent for all inputs). Merging them reduces the FSM from 4 states to 3 states, potentially reducing from 2 flip-flops to 2 flip-flops (same for binary encoding of 3 or 4 states) but simplifying the next-state logic.

When Minimization Matters

State minimization is most impactful when the initial FSM has many states derived from an informal specification. For small FSMs designed carefully from the start, minimization often finds no equivalent states. However, it remains an important verification step to confirm that the design is already minimal.

10.22 Summary and Key Takeaways

This unit completed the study of digital logic design by covering the three major categories of sequential circuits:

Registers:

A register is a group of flip-flops storing a multi-bit word, with parallel load or shift capabilities
Shift registers move data serially in SISO, SIPO, PISO, and PIPO configurations
Bidirectional shift registers can shift left or right under direction control
The universal shift register (e.g., 74194) supports hold, shift right, shift left, and parallel load via a 2-bit mode selector

Counters:

Asynchronous (ripple) counters are simple but suffer from accumulated propagation delay
Synchronous counters use a common clock with toggle logic: bit $i$ toggles when all lower bits are 1 (up counter) or 0 (down counter)
Up/down counters select count direction with a control signal
Modulo-N counters truncate the counting sequence using reset or preset techniques; the BCD (decade) counter is the most common mod-10 variant
Ring counters circulate a single 1-bit ($n$ flip-flops, $n$ states, one-hot decoding)
Johnson counters feed back the complement ($n$ flip-flops, $2n$ states, simple 2-input decoding)

Finite State Machines:

Moore machines produce outputs based on state only; Mealy machines produce outputs based on state and inputs
State diagrams visually represent FSM behavior with states, transitions, and outputs
State tables provide the tabular basis for logic design
State assignment maps abstract states to binary codes; one-hot encoding trades flip-flops for simpler logic
The FSM design procedure systematically transforms a specification into an optimized circuit through seven steps: specification, state diagram, state table, minimization, state assignment, logic design, and implementation
Next-state logic is derived using K-maps with D flip-flop inputs ($D_i = Q_i^+$) or JK excitation tables
Output logic is a function of state only (Moore) or state and inputs (Mealy)
State minimization identifies and merges equivalent states to reduce circuit complexity
Sequence detectors are the classic FSM application, combining all design steps into a complete example

These techniques, combined with the combinational design methods from earlier units, provide the complete foundation for designing digital systems at the gate and register-transfer levels.

Self-Check: Why do synchronous counters have a higher maximum clock frequency than ripple (asynchronous) counters?

In a ripple counter, each flip-flop is clocked by the output of the previous flip-flop, so delays accumulate through the chain. For an $n$-bit ripple counter, the total propagation delay is $n \times t_{cq}$. In a synchronous counter, all flip-flops share the same clock signal, so they all toggle simultaneously. The maximum delay is just one flip-flop's $t_{cq}$ plus the combinational logic delay for the toggle conditions, regardless of the counter width.

Self-Check: What is the key difference between a Moore machine and a Mealy machine, and when might you prefer one over the other?

In a Moore machine, outputs depend only on the current state, so they change synchronously with state transitions and are always stable between clock edges. In a Mealy machine, outputs depend on both the current state and inputs, allowing faster response (outputs can change as soon as inputs change, without waiting for a clock edge). Prefer Moore when output glitch-free stability matters (e.g., driving other synchronous logic). Prefer Mealy when you need fewer states or faster reaction to input changes.

Self-Check: A Johnson counter with 4 flip-flops produces how many valid states, and why is this different from a ring counter with the same number of flip-flops?

A Johnson counter with $n$ flip-flops produces $2n = 8$ valid states, while a ring counter produces only $n = 4$ states. The Johnson counter feeds back the complement of the last flip-flop to the first, creating a sequence where 1s gradually fill the register and then 0s gradually fill it back. This doubles the count length compared to a ring counter, which simply circulates a single 1-bit through the register. The trade-off is that Johnson counter state decoding requires 2-input AND gates, while ring counter states are inherently one-hot (no decoding needed).

Interactive Walkthrough

Step through a 4-bit shift register loading serial data one bit at a time:

Take the Unit Quiz | See Annotated References

Load	Clock Edge	Operation
0	\(\uparrow\)	Hold — all \(Q_i\) retain current values
1	\(\uparrow\)	Load — each \(Q_i\) receives corresponding \(D_i\)

Decimal	\(Q_3\)	\(Q_2\)	\(Q_1\)	\(Q_0\)	What toggles on the next clock edge
0	0	0	0	0	\(Q_0\) (always toggles)
1	0	0	0	1	\(Q_1\) and \(Q_0\) (because \(Q_0 = 1\))
2	0	0	1	0	\(Q_0\)
3	0	0	1	1	\(Q_2\), \(Q_1\), \(Q_0\) (because \(Q_1 Q_0 = 11\))
4	0	1	0	0	\(Q_0\)
...

Current State	Input \(X\)	Next State	Output \(Z\)
\(S_0\)	0	\(S_0\)	0
\(S_0\)	1	\(S_1\)	0
\(S_1\)	0	\(S_2\)	0
\(S_1\)	1	\(S_1\)	0
...	...	...	...

Current State	Input \(X\)	Next State	Output \(Z\)
\(S_0\)	0	\(S_0\)	0
\(S_0\)	1	\(S_1\)	0
\(S_1\)	0	\(S_2\)	1
\(S_1\)	1	\(S_1\)	0
...	...	...	...

\(Q_1\)	\(Q_0\)	\(X\)	\(Q_1^+\)	\(Q_0^+\)	\(Z\)
0	0	0	0	0	0
0	0	1	0	1	0
0	1	0	1	0	0
0	1	1	0	1	0
1	0	0	0	0	1
1	0	1	0	1	1
1	1	0	d	d	d
1	1	1	d	d	d

Output	Frequency	Division	Toggles per CLK cycle
\(Q_0\)	\(f_{CLK}/2\)	÷ 2	Every clock edge
\(Q_1\)	\(f_{CLK}/4\)	÷ 4	Every 2nd clock edge
\(Q_2\)	\(f_{CLK}/8\)	÷ 8	Every 4th clock edge
\(Q_3\)	\(f_{CLK}/16\)	÷ 16	Every 8th clock edge

Dir	Counting Direction	Toggle Condition for Bit \(i\)	Logic Used
1	Up	All lower bits are 1 (carry)	\(Q_j\) terms
0	Down	All lower bits are 0 (borrow)	\(Q_j'\) terms

Counter Type	Flip-Flops for \(n\) States	Decoding Logic	Self-Correcting	Glitch-Free
Binary	\(\lceil\log_2 n\rceil\)	Complex (\(n\)-input)	Yes	No
Ring	\(n\)	None (1-hot)	No	Yes
Johnson	\(n/2\)	Simple (2-input AND)	No	Yes

\(Q\)	\(Q^+\)	J	K
0	0	0	X
0	1	1	X
1	0	X	1
1	1	X	0