State Machines & Sequential Logic Design

TAKEAWAYS:

• A finite state machine (FSM) is a sequential circuit that processes inputs based on its current state, updating to a new state via transitions.
• Mealy and Moore machines differ in whether outputs depend on the current state (Moore) or the transition (Mealy).
• State diagrams map transitions with labeled arrows, while state tables tabulate inputs, states, and outputs.
• Sequential circuits like counters and registers rely on memory elements (flip-flops) to retain state between clock cycles.
• Synchronous vs. asynchronous designs determine how state changes are triggered (clocked vs. edge-triggered).
• Real-world applications include traffic lights, vending machines, and eSewa transaction validation.

1. Introduction to Sequential Logic

Sequential circuits depend on memory elements (e.g., flip-flops) to store state. Unlike combinational circuits, their outputs depend on current inputs AND past inputs (history). Key components:

• Clock signal: Synchronizes state changes (synchronous) or triggers asynchronously.
• State register: Holds the current state (e.g., using D flip-flops).
• Next-state logic: Computes the new state based on inputs and current state.

Why it matters: In eSewa, transaction validation requires sequential checks (e.g., "verify PIN → check balance → confirm transfer"). A combinational circuit couldn’t handle this because it lacks memory.

2. Finite State Machines (FSMs)

An FSM is a mathematical model for sequential circuits with:

• States (Q): Discrete conditions (e.g., "idle," "processing").
• Inputs (X): External signals triggering transitions.
• Outputs (Y): Actions based on state/transitions.
• State transitions: Rules defining how inputs change the state.

Types of FSMs

Visualization: A state diagram shows states as circles and transitions as labeled arrows. Below is a Moore FSM for a simple traffic light controller:

stateDiagram-v2
    [*] --> Red
    Red --> Green: timer expires
    Green --> Yellow: timer expires
    Yellow --> Red: timer expires

Key observation:

• The output (light color) depends only on the current state (Moore).
• In a Mealy machine, the output would also depend on the input (e.g., "pedestrian button pressed").

3. State Tables

A state table organizes transitions and outputs in tabular form. Example for a binary counter (2-bit):

Worked Example: Design a 3-state FSM for a vending machine with states:

1. Idle (waiting for coin),
2. Coin Inserted (processing),
3. Dispense (releasing item).

State Diagram:

State Table:

4. Sequential Circuit Design

A. Synchronous vs. Asynchronous

Visual: A synchronous counter uses a clock to update all flip-flops simultaneously:

An asynchronous counter (ripple) updates flip-flops one by one, causing delay:

B. Design Steps

1. Define states (e.g., for a Daraz order tracker):
   • State 0: Order received.
   • State 1: Processing.
   • State 2: Shipped.
   • State 3: Delivered.
2. Draw state diagram.
3. Convert to state table.
4. Implement with flip-flops and logic gates.

Worked Example: Design a 2-bit synchronous counter using D flip-flops.

Solution:

1. State table (same as above for binary counter).
2. Excitation table for D flip-flops (since $D=Q_{next}$):

   Q1Q0	T	Q1'Q0'	D1	D0
   00	1	01	0	1
   01	1	10	1	0
   10	1	11	1	1
   11	1	00	0	0

3. Logic for D1 and D0:
   • $D0=T\cdot \overline{Q0}+\overline{T}\cdot Q0$ (toggle on T).
   • $D1=T\cdot (Q0\cdot \overline{Q1})+\overline{T}\cdot Q1$.

Circuit:

5. Practical Applications

A. Traffic Light Controller (Moore FSM)

Real-world use: Kathmandu’s traffic lights use FSMs to cycle through red/yellow/green phases.

State Diagram:

State Table:

Key insight:

• The output (light color) changes only when the state changes (Moore).
• If a pedestrian button were added, it would make this a Mealy machine (output depends on input).

B. eSewa Transaction Validator (Sequential Logic)

Real-world use: eSewa’s transaction flow is sequential:

1. User enters PIN → Validate.
2. Check balance → Deduct if valid.
3. Confirm transfer → Update ledger.

State Diagram:

stateDiagram-v2
    [*] --> EnterPIN
    EnterPIN --> ValidatePIN: PIN entered
    ValidatePIN --> CheckBalance: PIN correct
    CheckBalance --> Deduct: Balance sufficient
    Deduct --> Confirm: Transaction complete
    Confirm --> [*]

6. Comparison: FSM vs. Counters/Registers

Visual: A 4-bit counter (register) vs. a FSM for a microwave timer:

7. Exam Tips

1. State diagrams > state tables:

   • Always draw the state diagram first to visualize transitions. Examiners check for clarity.
   • Example: For a 3-state FSM, label all states and transitions clearly.

2. Moore vs. Mealy:

   • Moore: Output depends only on state (easier to implement).
   • Mealy: Output depends on state + input (more flexible but complex).
   • Tip: If the problem says "output depends on current state," assume Moore.

3. Synchronous design:

   • Use D or T flip-flops with a clock. Show the excitation table to derive logic.
   • Example: For a 2-bit counter, derive $D1$ and $D0$ from the excitation table.

4. Asynchronous pitfalls:

   • Avoid glitches in ripple counters. Use enable signals to prevent race conditions.
   • Example: A 3-bit ripple counter with T flip-flops will have delays between bits.

5. Real-world mapping:

   • Link FSMs to everyday systems:
     • Pathao driver’s route: States = "idle," "picking up," "driving," "dropping off."
     • NEPSE stock trading: States = "buy," "hold," "sell" (based on price thresholds).

6. Common mistakes:

   • Forgetting to list all states (e.g., missing "error" state in a vending machine).
   • Incorrectly labeling transitions (e.g., "timer expires" vs. "button pressed").
   • Not verifying the FSM with a trace table (walk through inputs to confirm outputs).

Worked Example Trace: For the vending machine FSM, trace the path:

1. Start at Idle, input = coin=1 → transition to CoinInserted.
2. In CoinInserted, input = coin=1 → transition to Dispense (output = 1).
3. In Dispense, automatically go to Idle (output = 0).

In the Real World

1. Pathao Ride Tracking:

   • Idea: A Moore FSM tracks the driver’s state:
     • State 0: "Available" (idle).
     • State 1: "Picking up passenger" (after ride request).
     • State 2: "Driving" (GPS active).
     • State 3: "Dropping off" (ride complete).
   • How it works: The app’s backend uses an FSM to update the driver’s status in real time, ensuring accurate ride tracking and passenger notifications.

2. Ncell Call Forwarding:

   • Idea: A Mealy FSM handles call forwarding rules:
     • Input: "Call received" + "Forwarding enabled."
     • Output: "Forward to number X" (depends on current state and input).
   • Example: If the phone is on silent mode (State 1) and the user presses forward (Input = 1), the FSM forwards the call to voicemail (State 2).

3. Daraz Order Fulfillment:

   • Idea: A sequential counter tracks order priority:
     • Register: Stores the next order ID (e.g., 0001, 0002).
     • Logic: When an order is processed, the counter increments to the next ID.
   • Real scenario: Daraz’s warehouse uses a priority queue (implemented with counters and FSMs) to assign order numbers and route packages efficiently.

Worked Example: Ncell Call Forwarding FSM Design a 2-state Mealy FSM for call forwarding:

• States:
  1. Normal (no forwarding).
  2. Forwarding (call redirected).
• Inputs:
  • Call: Call received (0 = no, 1 = yes).
  • Forward: User enables forwarding (0 = no, 1 = yes).
• Outputs:
  • ForwardCall: 1 if call is forwarded, else 0.

State Diagram:

State Table:

Key takeaway: This FSM ensures calls are only forwarded when the user explicitly enables it, matching Ncell’s call-forwarding logic.