Introduction
Sequential logic extends combinational circuits by adding memory elements, enabling circuits to have state and exhibit complex behaviors over time. State machines provide a formal framework for designing and analyzing sequential systems. From simple counters to complex controllers, sequential logic is fundamental to digital system design.
This article explores sequential logic fundamentals, state machine design, and practical applications.
Historical Context
Sequential logic emerged alongside combinational logic in the early days of digital computing. The development of flip-flops and latches provided the memory elements needed for sequential circuits. State machine theory, formalized by Mealy and Moore, provided systematic design methodologies. These concepts remain central to digital design today.
Memory Elements
SR Latch (Set-Reset)
Function: Basic memory element using cross-coupled gates
Using NOR Gates:
S โโโ
โโ NOR โโโฌโโ Q
โ โ
โโโโโโโโโโ
R โโโ
โโ NOR โโโฌโโ Q'
โ โ
โโโโโโโโโโ
Behavior:
- S = 1, R = 0: Set Q = 1
- S = 0, R = 1: Reset Q = 0
- S = 0, R = 0: Hold state
- S = 1, R = 1: Invalid (undefined)
Characteristic Equation: Q(t+1) = S + R’Q(t)
Gated SR Latch
Add a control signal (enable) to the SR latch:
S โโโ
โโ AND โโโ
E โโโ โ
โโ SR Latch โโโ Q
R โโโ โ
โโ AND โโโ
E โโโ
Behavior: Latch responds to S and R only when E = 1
D Latch
Function: Capture and hold a single bit
Circuit:
D โโโ
โโ AND โโโ
E โโโ โ
โโ SR Latch โโโ Q
D'โโโ โ
โโ AND โโโ
E โโโ
Behavior:
- When E = 1: Q โ D (transparent)
- When E = 0: Q holds value (opaque)
Characteristic Equation: Q(t+1) = D when E = 1; Q(t) when E = 0
D Flip-Flop
Function: Capture input on clock edge
Master-Slave Configuration:
D โโโ Master Latch โโโ Slave Latch โโโ Q
(transparent (transparent
when CLK=0) when CLK=1)
Behavior:
- On rising clock edge: Q โ D
- Between edges: Q holds value
Characteristic Equation: Q(t+1) = D(t)
JK Flip-Flop
Function: More versatile than D flip-flop
Inputs: J (set), K (reset), CLK
Behavior:
- J = 0, K = 0: Hold state
- J = 1, K = 0: Set Q = 1
- J = 0, K = 1: Reset Q = 0
- J = 1, K = 1: Toggle Q
Characteristic Equation: Q(t+1) = JQ’(t) + K’Q(t)
T Flip-Flop
Function: Toggle on each clock pulse
Inputs: T (toggle), CLK
Behavior:
- T = 0: Hold state
- T = 1: Toggle Q
Characteristic Equation: Q(t+1) = TQ’(t) + T’Q(t) = T โ Q(t)
State Machines
Mealy Machine
Definition: Output depends on current state and current input
Components:
- States: S = {sโ, sโ, …, sโ}
- Inputs: I = {iโ, iโ, …, iโ}
- Outputs: O = {oโ, oโ, …, oโ}
- Transition function: ฮด(s, i) โ s'
- Output function: ฮป(s, i) โ o
State Diagram:
Transitions labeled: input/output
Example: 0/0 means "on input 0, output 0"
Example: Sequence Detector (detect “01”)
States: S0 (initial), S1 (saw 0), S2 (saw 01)
Transitions:
S0 --0/0--> S1
S0 --1/0--> S0
S1 --0/0--> S1
S1 --1/1--> S2
S2 --0/0--> S1
S2 --1/0--> S0
Moore Machine
Definition: Output depends only on current state
Components: Same as Mealy, but output function: ฮป(s) โ o
State Diagram:
States labeled with output
Transitions labeled with input only
Example: Sequence Detector (detect “01”)
States: S0 (initial, output 0), S1 (saw 0, output 0), S2 (saw 01, output 1)
Transitions:
S0 --0--> S1
S0 --1--> S0
S1 --0--> S1
S1 --1--> S2
S2 --0--> S1
S2 --1--> S0
Mealy vs Moore
| Aspect | Mealy | Moore |
|---|---|---|
| Output depends on | State + Input | State only |
| Output timing | Combinational delay | Sequential delay |
| States needed | Often fewer | Often more |
| Implementation | Simpler | Simpler |
| Response | Immediate | Delayed one cycle |
State Machine Design Process
Step 1: Problem Specification
Define:
- Input signals
- Output signals
- Desired behavior
- Initial state
Example: Design a traffic light controller
- Inputs: sensor (car detected)
- Outputs: red, yellow, green lights
- Behavior: Cycle through states, extend green if car detected
Step 2: State Diagram
Create state diagram showing:
- All states
- Transitions between states
- Conditions for transitions
- Output for each state (Moore) or transition (Mealy)
Example (Moore):
Red (output: red light)
--timer expired--> Green
Green (output: green light)
--timer expired or no car--> Yellow
Yellow (output: yellow light)
--timer expired--> Red
Step 3: State Table
Create table showing:
- Current state
- Input
- Next state
- Output
Example:
Current | Input | Next | Output
--------|-------|-------|--------
Red | - | Green | Red
Green | car | Green | Green
Green | no car| Yellow| Green
Yellow | - | Red | Yellow
Step 4: State Assignment
Assign binary codes to states:
- Red = 00
- Green = 01
- Yellow = 10
Considerations:
- Minimize transitions (adjacent states differ by one bit)
- Reduce logic complexity
- Minimize power consumption
Step 5: Flip-Flop Selection
Choose flip-flop type:
- D flip-flop: Simple, direct assignment
- JK flip-flop: Fewer gates for some transitions
- T flip-flop: Good for counters
Step 6: Excitation Table
Create table showing required flip-flop inputs for each transition:
Example (D flip-flops):
Current | Input | Next | D1 D0
--------|-------|------|------
00 | - | 01 | 0 1
01 | 0 | 01 | 0 1
01 | 1 | 10 | 1 0
10 | - | 00 | 0 0
Step 7: Logic Simplification
Derive Boolean expressions for:
- Next state (D inputs)
- Output signals
Use K-maps or Boolean algebra to simplify.
Step 8: Implementation
Implement using:
- Flip-flops for state storage
- Combinational logic for next state and output
Practical Examples
Binary Counter
Function: Count from 0 to 2โฟ-1, then wrap around
State Diagram:
0 --1--> 1 --1--> 2 --1--> ... --1--> 2โฟ-1 --1--> 0
Implementation (using T flip-flops):
T0 = 1 (always toggle LSB)
T1 = Q0 (toggle if Q0 = 1)
T2 = Q0 ยท Q1 (toggle if Q0 and Q1 = 1)
...
Shift Register
Function: Shift data through a series of flip-flops
Circuit:
Input โโโ D Q โโโ D Q โโโ D Q โโโ D Q โโโ Output
CLK CLK CLK CLK
Behavior: Each clock pulse shifts data one position
Sequence Detector
Function: Detect specific input sequence
Example: Detect “1011”
State Machine:
S0 (initial)
--1--> S1
--0--> S0
S1 (saw 1)
--0--> S2
--1--> S1
S2 (saw 10)
--1--> S3
--0--> S0
S3 (saw 101)
--1--> S4 (output 1)
--0--> S0
S4 (saw 1011)
--any--> S0
Analysis of Sequential Circuits
Timing Analysis
Setup Time: Time input must be stable before clock edge
Hold Time: Time input must remain stable after clock edge
Clock-to-Q Delay: Time from clock edge to output change
Maximum Frequency: f_max = 1 / (T_cq + T_logic + T_setup)
State Reachability
Reachable States: States that can be reached from initial state
Unreachable States: States that cannot be reached (design error or intentional)
Analysis: Trace all possible paths from initial state
Equivalence
State Equivalence: Two states are equivalent if they produce identical outputs for all input sequences
Minimization: Remove equivalent states to reduce circuit complexity
Glossary
Characteristic Equation: Equation describing flip-flop behavior
Clock: Periodic signal synchronizing state transitions
Excitation Table: Table showing required flip-flop inputs for transitions
Flip-Flop: Sequential element storing one bit
Latch: Level-triggered memory element
Mealy Machine: Output depends on state and input
Moore Machine: Output depends on state only
Sequential Logic: Circuits with memory (state-dependent)
State: Current configuration of flip-flops
State Diagram: Graphical representation of state machine
State Machine: System with discrete states and transitions
State Table: Tabular representation of state machine
Transition: Change from one state to another
Practice Problems
Problem 1: Design a state machine that outputs 1 every third clock pulse.
Solution:
States: S0 (count 0), S1 (count 1), S2 (count 2)
Transitions:
S0 --CLK--> S1 (output 0)
S1 --CLK--> S2 (output 0)
S2 --CLK--> S0 (output 1)
Implementation: Use 2 D flip-flops with appropriate logic
Problem 2: Analyze the sequence detector for “01” and verify it works correctly.
Solution:
Input sequence: 0, 1, 0, 1, 1, 0, 1
Trace:
S0 --0--> S1 (output 0)
S1 --1--> S2 (output 1) โ detected "01"
S2 --0--> S1 (output 0)
S1 --1--> S2 (output 1) โ detected "01"
S2 --1--> S0 (output 0)
S0 --0--> S1 (output 0)
S1 --1--> S2 (output 1) โ detected "01"
Problem 3: Design a 4-bit up/down counter with enable signal.
Solution:
Inputs: CLK, EN (enable), UP (1 for up, 0 for down)
Outputs: Q3, Q2, Q1, Q0 (4-bit count)
Logic:
When EN = 1 and UP = 1: Increment count
When EN = 1 and UP = 0: Decrement count
When EN = 0: Hold count
Implementation: Use 4 JK flip-flops with appropriate logic
Related Resources
- Sequential Logic: https://en.wikipedia.org/wiki/Sequential_logic
- State Machine: https://en.wikipedia.org/wiki/Finite-state_machine
- Flip-Flops: https://en.wikipedia.org/wiki/Flip-flop_(electronics)
- Latches: https://en.wikipedia.org/wiki/Latch_(electronics)
- Mealy Machine: https://en.wikipedia.org/wiki/Mealy_machine
- Moore Machine: https://en.wikipedia.org/wiki/Moore_machine
- Digital Circuit Design: https://en.wikipedia.org/wiki/Digital_circuit
- Counters: https://en.wikipedia.org/wiki/Counter_(digital)
- Shift Registers: https://en.wikipedia.org/wiki/Shift_register
- Sequence Detectors: https://en.wikipedia.org/wiki/Sequence_detector
- Verilog: https://en.wikipedia.org/wiki/Verilog
- VHDL: https://en.wikipedia.org/wiki/VHDL
- State Diagram: https://en.wikipedia.org/wiki/State_diagram
- Finite Automata: https://en.wikipedia.org/wiki/Finite_automaton
- Formal Verification: https://en.wikipedia.org/wiki/Formal_verification
Conclusion
Sequential logic and state machines provide the foundation for designing circuits with memory and complex behaviors. From simple counters to sophisticated controllers, understanding state machine design principles is essential for digital system design.
The systematic design processโfrom specification through state diagrams, state tables, and implementationโensures correct, efficient circuits. Modern design tools automate many steps, but understanding the underlying principles remains crucial for effective digital design.
Whether designing simple controllers or complex systems, mastery of sequential logic and state machine design enables the creation of reliable, efficient digital systems that form the foundation of modern computing.
Comments