Sequential Circuit - State reduction and assignment

Tags: #◇Computer Science #◇CSARCH1 #◇Problem Solving #◇M5

---

◇Overview

Reduction in the number of flip-flops in a sequential circuit is referred to as the state-reduction problem. Minimizing states simplifies the combinational logic and can lead to fewer flip-flops required, as long as external input-output requirements remain unchanged.

State Reduction

Two states are equivalent if, for each possible input, they give exactly the same output and send the circuit to the same state or to an equivalent state.
When two states are found to be equivalent, one of them can be removed without altering the system's input-output relationships. The state table is then rebuilt using the remaining states.

State Assignment

After state reduction, symbolic state names (e.g., a, b, c) must be mapped to physical binary values (e.g., 000, 001, 010).
Common state assignment encodings include:

• Straight Binary: Normal counting sequence (000, 001, 010, 011). Minimizes flip-flop count (e.g. 5 states -> 3 bits).
• Gray Code: Only one bit changes per state transition (000, 001, 011, 010). Good for minimizing power consumption and glitching.
• One-Hot: Uses one bit per state, where only one bit is '1' at a time (00001, 00010, 00100, 01000). Requires more flip-flops (5 states -> 5 bits) but often drastically simplifies combinational logic.

◇Worked Examples

Given a state table with abstract states (a, b, c, d, e, f, g), state reduction iteratively merges rows that have identical next states and outputs for all inputs. Once the minimized set of states is found (e.g., 5 states remaining), an assignment strategy is chosen to build a binary-coded state table.

◇References & Navigation

• Previous Topic: ◇Sequential Circuit - Analysis
• Next Topic: ◇Sequential Circuit - Design
• Related Notes: ◇Sequential Circuit - Analysis, ◇Sequential Circuit - Design