State Encoding & Optimization (SA0, SA1): Techniques, Trade-offs & FSM Design

Core Concepts: What is State Encoding?

State encoding is the process of assigning binary codes to the states of a finite state machine (FSM) to implement them in hardware. The choice of encoding directly impacts:

• Hardware complexity (number of gates, flip-flops, and logic levels).
• Speed (propagation delay through combinational logic).
• Power consumption (active gates in one-hot vs. binary encoding).

Why Optimize State Encoding?

In real FSMs (e.g., a vending machine controller or traffic light sequencer), poor encoding can:

• Increase chip area (cost).
• Slow down transitions (critical in high-speed systems like Ncell’s call routing).
• Waste power (important for battery-powered devices like Pathao’s GPS trackers).

1. Binary State Assignment (SA0)

Binary encoding assigns n-bit binary codes to each state, where n = ⌈log₂(N)⌉ (N = number of states). Example for a 4-state FSM:

State | Binary Code (SA0)
------|------------------
S0    | 00
S1    | 01
S1    | 10
S3    | 11

How It Works

1. Flip-flops: Each bit of the state code is stored in a D flip-flop (e.g., 2 bits → 2 flip-flops).
2. Next-state logic: Combinational logic (AND/OR gates) computes the next state from inputs and current state.
3. Output logic: Decodes the current state to generate outputs.

Worked Example: Traffic Light Controller (SA0)

Problem: Design a 3-state traffic light FSM (Red → Green → Yellow → Red) using SA0. States: S0 (Red), S1 (Green), S2 (Yellow). Encoding:

State | SA0 Code
------|---------
S0    | 00
S1    | 01
S2    | 10

Next-state logic (simplified):

• If current = S0 and timer_expired = 1 → next = S1 (01).
• If current = S1 and timer_expired = 1 → next = S2 (10).
• If current = S2 → next = S0 (00).

Circuit:

graph LR
    A["D Flip-Flop (Q0)"] -->|"Q0"| B["AND Gate 1"]
    C["D Flip-Flop (Q1)"] -->|"Q1"| B
    B -->|"Next Q0"| D["D Flip-Flop (Q0)"]
    E["Timer Expired"] --> B
    F["AND Gate 2"] -->|"Q0, Q1, Timer"| G["Next Q1"]
    G --> C

Advantages:

• Minimal flip-flops: Uses ⌈log₂N⌉ flip-flops (e.g., 4 states → 2 flip-flops).
• Simple logic: Fewer gates for next-state transitions.

Disadvantages:

• Glitches: Binary decoding can cause temporary invalid states (e.g., 11 during transition from S1 to S2).
• Slow for large FSMs: Decoding requires combinational logic delays.

2. One-Hot State Assignment (SA1)

One-hot encoding uses one active bit per state (e.g., 4 states → 4 flip-flops, only one 1 at a time). Example for 4-state FSM:

State | SA1 Code
------|---------
S0    | 1000
S1    | 0100
S2    | 0010
S3    | 0000

How It Works

1. Flip-flops: Each state has its own flip-flop (e.g., Q0 for S0, Q1 for S1).
2. Next-state logic: Directly routes the 1 from the current state to the next state (no decoding needed).
3. Output logic: Uses AND gates to enable outputs for the active state.

Worked Example: Vending Machine (SA1)

Problem: A vending machine with 3 states (S0: Idle, S1: Coin Inserted, S2: Dispensing). Encoding:

State | SA1 Code
------|---------
S0    | 100
S1    | 010
S2    | 001

Next-state logic:

• If current = S0 and coin_detected = 1 → next = S1 (set Q1).
• If current = S1 and select_button = 1 → next = S2 (set Q2).
• If current = S2 → next = S0 (set Q0).

Circuit:

graph LR
    A["D Flip-Flop (Q0)"] -->|"Q0"| B["AND Gate: Coin Detected"]
    B -->|"1"| C["D Flip-Flop (Q1)"]
    C -->|"Q1"| D["AND Gate: Select Button"]
    D -->|"1"| E["D Flip-Flop (Q2)"]
    E -->|"Q2"| F["D Flip-Flop (Q0)"]

Advantages:

• No glitches: Only one flip-flop is 1 at a time (no invalid intermediate states).
• Faster transitions: No combinational decoding delay.
• Simpler output logic: Directly AND the active state bit with output conditions.

Disadvantages:

• More flip-flops: Uses N flip-flops for N states (wastes hardware for large FSMs).
• Higher power: More flip-flops consume more power.

Comparison: SA0 vs. SA1

In the Real World

1. eSewa’s Payment FSM:

   • Uses SA1 encoding for its transaction states (e.g., Waiting for OTP, Processing Payment, Complete).
   • Why? Speed is critical—users expect instant confirmation. One-hot encoding avoids glitches that could corrupt transactions.

2. Ncell’s Call Routing:

   • Employs SA0 for call states (e.g., Dialing, Connected, Hanging Up) in its SS7 signaling controllers.
   • Why? Binary encoding reduces hardware cost for millions of simultaneous calls.

3. Daraz’s Order Queue System:

   • Uses a hybrid approach: SA0 for order status (e.g., Pending, Shipped, Delivered) but SA1 for critical transitions (e.g., Payment Failed → Refund Initiated).
   • Why? Balances speed (SA1 for errors) and cost (SA0 for common states).

4. NTC’s Traffic Light Controller:

   • SA0 encoding for its 4-state traffic light FSM (Red, Green, Yellow, Flashing Yellow).
   • Real-world trace:
     • At time t=0, state = S0 (Red, 00).
     • Timer expires → next state = S1 (Green, 01).
     • Timer expires → next state = S2 (Yellow, 10).
     • Timer expires → next state = S0 (Red, 00).
   • Why? Low cost and simplicity suffice for predictable traffic patterns.

Optimization Techniques

1. State Merging

Combine states with identical outputs and transitions to reduce flip-flops. Example: In a washing machine FSM, Spin Cycle and Rinse Cycle may have the same next-state logic if both lead to Drain.

2. Gray Code Encoding

Use Gray code (only one bit changes between states) to minimize glitches in SA0. Example:

State | Gray Code
------|----------
S0    | 00
S1    | 01
S2    | 11
S3    | 10

Advantage: Reduces transient errors during state transitions.

3. Mixed Encoding

Combine SA0 and SA1 for different parts of the FSM:

• Use SA1 for critical states (e.g., error handling).
• Use SA0 for common states (e.g., normal operation).

Fault Detection and State Encoding

Poor encoding can lead to metastability or invalid states. For example:

• In SA0, transitioning from S1 (01) to S2 (10) might briefly pass through 11 (invalid).
• Solution: Use Gray code or one-hot decoding with priority encoders.

Exam Tip

1. Define SA0 and SA1 clearly:

   • SA0: Binary encoding (e.g., 3 states → 2 bits: 00, 01, 10).
   • SA1: One-hot encoding (e.g., 3 states → 3 bits: 100, 010, 001).

2. Compare with a table: Always include a comparison table (as above) in long-answer questions.

3. Worked examples are key:

   • For SA0: Show next-state logic (AND/OR gates).
   • For SA1: Show direct routing of the active bit.
   • Always trace a state transition (e.g., "How does the FSM go from S0 to S1?").

4. Real-world applications:

   • Link SA0 to cost-sensitive systems (e.g., traffic lights).
   • Link SA1 to speed-critical systems (e.g., eSewa payments).

5. Common pitfalls:

   • Forgetting to calculate ⌈log₂N⌉ for SA0 flip-flop count.
   • Not showing output logic in your circuit diagram.
   • Ignoring glitches in SA0 (examiners may ask how to avoid them).

Visual Summary

1. Binary (SA0) vs. One-Hot (SA1) Flip-Flop Usage

pie
    title State Encoding Flip-Flop Usage
    "SA0 (Binary)" : 25
    "SA1 (One-Hot)" : 75

2. Traffic Light FSM (SA0 Encoding)

Shows 2 D flip-flops, AND gates for next-state logic, and output decoders for lights.

3. One-Hot Decoder Logic

graph TD
    A["Q0 (S0)"] -->|"1"| B["Output: Red Light"]
    C["Q1 (S1)"] -->|"1"| D["Output: Green Light"]
    E["Q2 (S2)"] -->|"1"| F["Output: Yellow Light"]