Designing a sequential machine involves translating a verbal specification into a hardware circuit comprising flip-flops and combinational logic gates. Sequential machines are classified into two models:
Mealy Machine: Output depends on both the current state and the current input. Z = λ(S, X)
Moore Machine: Output depends only on the current state. Z = λ(S)
Standard 7-Step Machine Design Algorithm:
Specification & Formulation: Derive the state representation from verbal descriptions or timing requirements.
Primitive State Diagram / Table Construction: Map every possible transition sequence into initial states.
State Reduction: Eliminate redundant (equivalent) states to minimize required memory elements (flip-flops).
State Assignment: Assign unique binary codes to the reduced states (Pure Binary, Gray, or One-Hot coding).
Transition & Excitation Table Derivation: Substitute assigned state codes and derive required input conditions for chosen flip-flops (SR, JK, D, T).
Combinational Optimization: Derive simplified Boolean expressions for flip-flop inputs and outputs using Karnaugh Maps (K-Maps).
Hardware Realization: Draw the logic circuit diagram using gates and flip-flops.
7.2 Primitive State Diagrams
A Primitive State Diagram / Table is a special representation used primarily in asynchronous and complex synchronous machine designs. It is defined as a state table where exactly one stable total state exists in each row.
Key Characteristics:
Every distinct input sequence produces a new state row initially.
In Fundamental Mode operation, input variables change one at a time (Δx = 1) only after the circuit reaches a stable internal state.
Outputs are specified only for stable states; unstable state outputs are treated as Don't Cares (Χ).
Example Primitive State Table Structure:
Present State
Next State / Output (X1X0)
00
01
11
10
A
A / 0
B / Χ
—
C / Χ
B
A / Χ
B / 1
D / Χ
—
C
A / Χ
—
D / Χ
C / 0
7.3 Transition/Flow Tables
A Flow Table represents state transitions using letter symbols for states, while a Transition Table replaces state symbols with explicit binary bit vectors (Y1Y0).
Flow Table vs. Transition Table
Flow Table (Symbolic)
Transition Table (Binary Assignment)
Uses state labels: A, B, C, D
Uses state variable values: 00, 01, 11, 10
Shows stable states as circled symbols: (A)
Shows stable states matching present state variable code
High-level abstraction for state reduction
Directly maps to logic gates and flip-flop inputs
7.4 Redundant States Reduction Methods
Two states Si and Sj are defined as Equivalent (Si ≡ Sj) if and only if for every possible input sequence, the machine generates identical output sequences and transitions to equivalent next states.
State Reduction Techniques:
Equivalence Partitioning Method: Group states into output-equivalent blocks, then repeatedly refine partitions based on next-state equivalence until stability is reached.
Implication Table Method: Systematic triangular grid method used to analyze pairwise compatibility.
Implication Table Procedure:
Construct a grid comparing every pair of states (Si, Sj).
Cross out (×) pairs that produce different outputs for identical inputs.
In remaining squares, write the implied next-state pairs required for equivalence.
Pass through the table recursively: cross out square (A, B) if any of its implied pairs are already crossed out.
Uncrossed squares represent equivalent state pairs that can be merged.
7.5 Pure Binary Assignment Tables
State assignment assigns binary vectors of length m to represent N states, where 2m-1 < N ≤ 2m.
Races and Hazards in Asynchronous Machines:
Race Condition: Occurs when two or more state variables change simultaneously (e.g., 00 → 11).
Non-Critical Race: Final stable state reached is identical regardless of state change ordering.
Critical Race: Circuit reaches different stable states depending on gate delays. Must be eliminated!
Rules for Race-Free State Assignment (Adjacent Assignment Rules):
Rule 1: States that have the same next state for a given input should be assigned adjacent binary codes (differing by 1 bit).
Rule 2: States that are next states of a single state for adjacent inputs should be assigned adjacent binary codes.
Rule 3: States that share identical output vectors should be assigned adjacent codes to simplify output combinational logic.
Pure Binary Assignment Example (4 States):
State Symbol
Pure Binary (y1y0)
Gray Code (y1y0)
One-Hot Encoding (y3y2y1y0)
S0
00
00
0001
S1
01
01
0010
S2
10
11
0100
S3
11
10
1000
7.6 Excitation Maps
An Excitation Map maps present states and external inputs to required flip-flop control inputs derived from flip-flop excitation tables.
Standard Flip-Flop Excitation Characteristics
Present State (Qt)
Next State (Qt+1)
S-R FF (S, R)
J-K FF (J, K)
D FF (D)
T FF (T)
0
0
0, Χ
0, Χ
0
0
0
1
1, 0
1, Χ
1
1
1
0
0, 1
Χ, 1
0
1
1
1
Χ, 0
Χ, 0
1
0
7.7 Realization of the Models
Realization refers to deriving minimized Boolean expressions from excitation K-maps and translating them into physical logic circuits.
Steps for Circuit Realization:
Construct K-maps for each flip-flop input variable (JA, KA, DB, etc.) and system output (Z).
Group adjacent ones and don't-cares (Χ) to find minimal Sum-of-Products (SOP) forms.
Verify logic against setup and hold time constraints.
Draw gate schematics using Universal Gates (NAND/NOR) or standard AND-OR-INVERT logic.
7.8 Circuit Diagram of Synchronous Machine
A general synchronous sequential machine layout consists of a state memory block synchronized by a common system clock signal alongside combinational next-state and output logic.
7.9 One-bit and Two-bit Input Sequence Detectors
A Sequence Detector is a sequential state machine designed to produce an output signal (Z = 1) upon detecting a specific sequence of binary inputs.
Sequence Classification:
Overlapping: The final bit(s) of a detected sequence can act as the prefix for the subsequent sequence attempt (e.g., detecting 101 in 10101 produces output at index 3 and index 5).
Non-Overlapping: After a sequence detection, the machine resets completely to its initial state.
Case Study A: 1-Bit Input Sequence Detector (Pattern: 1011, Overlapping, Mealy Model)
State Specifications:
S0 (Reset): No correct bits detected yet.
S1: Detected 1.
S2: Detected 10.
S3: Detected 101.
State Table for 1011 Detector:
Present State
Next State / Output (Z)
X = 0
X = 1
S0 (00)
S0 / 0
S1 / 0
S1 (01)
S2 / 0
S1 / 0
S2 (10)
S0 / 0
S3 / 0
S3 (11)
S2 / 0
S1 / 1
Case Study B: 2-Bit Input Sequence Detector
A 2-bit input sequence detector monitors two parallel input channels (X1X0) and detects a multi-symbol temporal sequence (e.g., detecting the symbol pair sequence: 01 → 11 → 10).
Design Steps for 2-Bit Input Machines:
Input variables: X1, X0 (4 total input conditions per state: 00, 01, 11, 10).
Each state expands into 4 transition branches in state tables and K-maps.
Minimal excitation equations involve 3-variable or 4-variable K-map optimizations.
State Transition Matrix for Symbol Sequence (01 → 11 → 10):