Design of Sequential Circuits: State Machines, Flip-Flop Networks, and Timing

Core Concepts

Sequential circuits differ from combinational circuits because they remember past inputs via memory elements (flip-flops). Their behavior depends on:

1. Current state (stored in flip-flops).
2. Current inputs (external signals).
3. Next state (computed from current state + inputs).
4. Output (can depend on state and/or inputs).

Key subtopics:

• State machine models: Mealy vs. Moore.
• Design procedure: From problem → state diagram → excitation table → logic circuit.
• Flip-flop selection: D, JK, T flip-flops and their excitation tables.
• Timing analysis: Critical race, essential hazard, and setup/hold constraints.
• Applications: Traffic lights, vending machines, CPU control units.

1. State Machines: Mealy vs. Moore

Sequential circuits are modeled as finite state machines (FSMs). Two types:

Mealy Machine

• Output depends on both current state and inputs.
• Faster response (output changes immediately with inputs).
• Example: A vending machine that dispenses a drink only if the correct coin is inserted and the button is pressed.

Moore Machine

• Output depends only on the current state.
• Slower but simpler (output changes only when the state changes).
• Example: A traffic light that turns green only after the timer in the "green" state expires.

stateDiagram-v2
    [*] --> StateA
    StateA --> StateB : Input=1
    StateB --> StateA : Input=0
    StateA : Output = x
    StateB : Output = y
    StateA -->|Output = x'| StateB : Input=1 (Mealy)
    StateA --> StateB : Input=1 (Moore)
    StateB --> StateA : Input=0

Comparison Table

2. Design Procedure: Step-by-Step

Convert a real-world problem into a sequential circuit using this workflow:

Step 1: Define States and Transitions

• List all possible states (e.g., "Idle," "Processing," "Error").
• Draw a state diagram (use stateDiagram-v2 above as a template).
• Example: A traffic light controller has 3 states:
  • Red → Green (after timer).
  • Green → Yellow (after timer).
  • Yellow → Red (immediately).

Step 2: Assign Binary Codes to States

Use binary encoding (e.g., 2-bit for 4 states, 3-bit for 8 states). Example:

Step 3: Construct State and Excitation Tables

• State table: Lists current state, inputs, next state, and output.
• Excitation table: Derives flip-flop inputs (e.g., J/K/T/D) from next-state logic.

Example: Traffic Light State Table

Excitation Table for D Flip-Flops

Step 4: Derive Boolean Equations

From the excitation table, write equations for flip-flop inputs and outputs. Example:

• $D_A=\overline{A}B+A\overline{B}$ (from next-state logic).
• $D_B=\overline{A}\overline{B}+A\overline{B}$.
• Output $Z=\overline{A}\overline{B}C+A\overline{B}\overline{C}+\overline{A}BC$ (for lights).

Step 5: Draw the Logic Circuit

Use D flip-flops (from excitation table) + combinational logic (from Boolean equations). Example Circuit:

flowchart LR
    A["D Flip-Flop (A)"] -->|"D_A"| B["D Flip-Flop (B)"]
    B -->|"D_B"| A
    A & B -->|"Inputs"| C["Combinational Logic"]
    C -->|"Output Z"| D["Traffic Light"]

3. Flip-Flop Selection and Excitation Tables

Choose the right flip-flop type based on the excitation table:

Example: Converting JK to D Flip-Flop For a JK flip-flop:

• $D=J\overline{Q}+\overline{K}Q$. Derivation: If $J=K=1$, the flip-flop toggles. To implement this with a D flip-flop:
• $D=\overline{Q}$ (toggle on every clock).

4. Timing Analysis: Critical Race and Hazards

Sequential circuits suffer from timing issues:

1. Critical Race: Next state depends on multiple flip-flops changing simultaneously (e.g., $A^{+}=B$, $B^{+}=A$).
   • Solution: Use non-overlapping clock phases or hazard-free encoding.
2. Essential Hazard: Glitches in combinational logic due to unequal propagation delays.
   • Solution: Add delay elements or use hazard-free designs.

Example: Critical Race in a Counter

stateDiagram-v2
    [*] --> State00
    State00 --> State01 : Clock
    State01 --> State10 : Clock (Critical Race if B+ depends on A)
    State10 --> State11 : Clock
    State11 --> State00 : Clock

5. Worked Example: Vending Machine Controller

Problem: Design a vending machine with:

• States: Idle, CoinInserted, Dispensing, Error.
• Inputs: Coin (1), Select (1), Error (1).
• Output: Dispense (1).

Step 1: State Diagram

stateDiagram-v2
    [*] --> Idle
    Idle --> CoinInserted : Coin=1
    CoinInserted --> Dispensing : Select=1
    Dispensing --> Idle : Dispense=1
    CoinInserted --> Error : Error=1
    Error --> Idle : Reset=1

Step 2: State Assignment (2-bit)

Step 3: Excitation Table (D Flip-Flops)

Step 4: Boolean Equations

• $D_A=\overline{A}B+A\overline{B}\overline{\text{Error}}$.
• $D_B=\overline{A}\overline{B}\text{Coin}+A\overline{B}\text{Select}$.
• $\text{Dispense}=A\overline{B}\text{Select}$.

Step 5: Logic Circuit

flowchart LR
    A["D Flip-Flop (A)"] -->|"D_A"| B["D Flip-Flop (B)"]
    B -->|"D_B"| A
    A & B & Inputs -->|"Combinational Logic"| C["Dispense Output"]

6. Real-World Applications

In the Real World

1. eSewa Payment System

   • Idea Used: State machine for transaction validation.
   • How: When you pay via eSewa, the system transitions through states:
     • Idle → User Authenticated (after PIN) → Processing → Complete.
     • Uses Moore machine logic (output depends only on state, e.g., "Payment Successful").

2. Pathao Ride Allocation

   • Idea Used: Priority-based state machine for driver matching.
   • How: The app’s backend uses a Mealy machine to:
     • Accept ride requests (input = user location).
     • Assign nearest driver (output depends on current state + input).
     • Update state to "Driver Assigned."

3. NTC Traffic Light Controller

   • Idea Used: Synchronous sequential circuit with timers.
   • How: The traffic light at a busy intersection (e.g., Thapathali) uses a 3-state Moore machine:
     • Red (00) → Green (01) (after 30s timer).
     • Green (01) → Yellow (10) (after 5s).
     • Yellow (10) → Red (00) (immediate).
   • Flip-Flops Used: Two D flip-flops to store the 2-bit state.

7. Common Mistakes and Pitfalls

1. Forgetting to account for all states:
   • Example: Missing the "Error" state in a vending machine leads to undefined behavior.
2. Incorrect flip-flop excitation:
   • Example: Using $D=Q$ for a toggle operation (should be $D=\overline{Q}$).
3. Ignoring timing constraints:
   • Example: Not checking for critical races in a counter causes incorrect counting.
4. Confusing Mealy/Moore outputs:
   • Example: Designing a traffic light as a Mealy machine (output depends on input) instead of Moore (output depends only on state).

8. Exam Tip

What Examiners Look For

1. Complete state diagram:
   • Must include all states and transitions (no missing arrows).
   • Label inputs/outputs clearly.
2. Correct state assignment:
   • Use binary encoding (e.g., 2-bit for 4 states).
   • Avoid illegal states unless specified.
3. Accurate excitation tables:
   • Show current state, inputs, next state, and flip-flop inputs.
   • Derive Boolean equations from the table.
4. Logic circuit with flip-flops:
   • Use standard symbols (D, JK, T flip-flops).
   • Include clock and reset if needed.
5. Timing analysis:
   • Identify critical races or hazards and suggest fixes.
6. Real-world connection:
   • Relate your design to a known system (e.g., traffic light, vending machine).

High-Scoring Answers Include

• Step-by-step derivation (no skipping steps).
• Clear labeling (states, inputs, outputs).
• Visual aids (state diagrams, excitation tables, logic circuits).
• Explanation of choices (e.g., "Used D flip-flops for simplicity").

Avoid

• Vague descriptions (e.g., "The circuit works" without showing how).
• Incorrect flip-flop usage (e.g., using JK when D is sufficient).
• Ignoring inputs/outputs in state transitions.