DT

Sequential Logic & State Machine Design

Overview: Combinational vs. Sequential Logic

  • Combinational Logic
    • Output Z depends only on present inputs: Z = f(X0, X1, …)
    • Deterministic: same input set ⇒ same output, independent of time/history.
    • Standard 4-step design flow:
    1. Derive truth-table from verbal specification.
    2. Write standard SOP / POS expression.
    3. Minimise (Boolean algebra or Karnaugh map).
    4. Draw final circuit from minimised equation.
  • Sequential Logic (= State Machine)
    • Output depends on present inputs and the machine’s current state (memory):
      Z = f(X,\;\text{STATE})
    • Requires storage elements (flip-flops); behaviour evolves on clock edges.
    • Everyday metaphors:
      • TV remote numeric keys = combinational (9→ch-9 always).
      • TV remote ↑ / ↓ arrows = sequential (result depends on current channel).
      • Traffic lights cycling R→G→Y use purely sequential timing.

Flip-Flop Fundamentals (focus on D flip-flop)

  • Pins: D (data), CLK (clock), Q, \overline Q.
  • Characteristic equation (edge triggered):
    Q^{} = D where Q^{} = value stored after the active clock edge (rising edge in examples).
  • Operating rules
    • Place desired bit on D, then apply a rising clock edge → bit latched to Q.
    • Between active edges, Q holds previous value regardless of D changes.
  • Truth-table sketch (showing only edge-triggered rows):
    D (before edge)rising CLKQ (after edge)\overline Q
    0↑01
    1↑10
  • Notation used in design
    • Current state variables written Q1, Q0 (etc.).
    • Next / future value indicated by star: Q1^{}, Q0^{}.

Generic State-Machine Design Procedure

  1. Understand and time-diagram the specification.
  2. Draw the state diagram
    • Nodes = states; directed, clock-synchronised arcs labelled input / output.
    • Most intellectually demanding step.
  3. Derive state table (list: current state, input(s), next state, output).
  4. Assign binary codes to states (state assignment) and produce the transition table.
    • Determine #flip-flops via 2^n \ge \text{#states}.
  5. Obtain transition equations (express Q^{*} in terms of current Q and inputs) using Karnaugh maps or algebra.
  6. Derive output equations (Moore: depends only on state; Mealy: state & inputs).
  7. Write excitation equations for each flip-flop (match Q^{*} to corresponding flip-flop *D*, *T*, *JK* etc.).
  8. Draw final circuit / implement in HDL/CPLD/FPGA.

Example 1 – Dentist’s Laser (3-cycle pulse)

Goal: When a push-button B is tapped, laser output X must stay HIGH for exactly three clock cycles, then turn OFF, regardless of button release; if button is held, laser must not restart a new 3-cycle pulse.

Initial naïve 4-state diagram (flawed)

  • WAIT (laser OFF) ––B–> ON-1 –> ON-2 –> ON-3 –> WAIT.
  • Issue: if B is still HIGH after ON-3, machine re-enters ON-cycle → unwanted continuous lasing.

Corrected 5-state diagram

  • States: INIT, ON-1, ON-2, ON-3, WAIT-BUTTON-HELD.
  • Transitions
    • INIT –B=1→ ON-1 (laser=1); B̅ holds INIT.
    • ON-1 –> ON-2 –> ON-3 unconditionally (clock only).
    • ON-3 checks button:
      • B=1 → WAIT-HELD (laser=0)
      • B=0 → INIT (laser=0).
    • WAIT-HELD self-loops while B=1; B=0 returns to INIT.
  • Implementation sketch produced earlier used three DFFs + 1 OR gate.

Functional simulation walk-through

  • Start all Q=0, laser OFF.
  • Button tap synchronised to a clock edge transfers ‘1’ into first FF; cascades through pipeline for 3 edges; laser OR-gated from FF outputs → stays HIGH exactly 3 clocks then LOW.
  • Holding button causes transition to WAIT-HELD, blocking re-trigger.

Example 2 – “Two-consecutive-1” Detector (single input, single output)

Specification: output Z=1 iff input X has been HIGH on two consecutive clock edges.

1 Timing analysis

  • Draw clock & X wave-form ➜ mark positions where two back-to-back 1’s occur ➜ required Z waveform built.

2 Identify states (look at last two samples)

  • Four possible ordered pairs of recent inputs → four states:
    S0 ≡ “got 00”, S1 ≡ “got 01”, S2 ≡ “got 11”, S3 ≡ “got 10”.
  • Outputs: Z=1 only in S2.

3 State diagram (Moore-type)

         (X=0)           (X=1)
 S0 (00) ───────► S1 (01) ───────► S2 (11) ──┐
  ▲  │           ▲   │             │        │
  │  │(X=0)      │   │(X=1)        │(X=1)   │
  │  └───────────┘   └─────────────┘        │
  │                                         │
  └────────────── S3 (10) ◄─────────────────┘
         ▲               ▲
         └──────(X=0)────┘

4 State table

CurrentXNextZ
000000
001010
010100
011110
110101
111111
100000
101110

5 Binary encoding & flip-flop count

  • 4 states ⇒ 2^n \ge 4 \Rightarrow n=2 D-FFs needed (Q1 Q0).
  • Assign: 00→S0, 01→S1, 11→S2, 10→S3.

6 Transition (excitation) Karnaugh-map derivation

  • Maps for Q1^{} and Q0^{} using variables (Q1,Q0,X).
  • Grouping gives minimal equations:
    Q0^{} = X Q1^{} = Q_0

7 Output equation (Moore)

Z = Q1 \;\land\; Q0

8 Circuit realisation

  • Two D-FFs clocked together.
  • Wiring
    • D_0 = X
    • D1 = Q0
    • Z = Q1 \cdot Q0 (AND gate)
  • Inputs: X, CLK. Output: Z.

Practical & Pedagogical Notes

  • Synchronous machines: all FFs share the same clock → predictable timing.
  • Star notation (Q^{*}) vital: distinguishes present vs. next value.
  • Common pitfalls
    • Forgetting to block re-trigger (e.g.
      laser example fixed by extra WAIT-HELD state).
    • Writing Q=D instead of Q^{*}=D (ignores clocked nature).
  • Design complexity grows with state count (↑FFs, ↑logic).
  • In lab sessions you will:
    • Enter equations into Quartus/CPLD, synthesize.
    • Wire D-FF ICs + gates on breadboard, clock from function generator.
    • Verify timing against simulation.
  • Equipment reminder: bring jumper wires & IC kits; USB-Blaster provided in lab.

Key Equations & Definitions Recap

  • D-FF characteristic: Q^{*}=D (on rising edge).
  • Flip-flop count: 2^{n} \ge \text{#states} ⇒ minimum n.
  • Moore output: depends only on state.
  • Mealy output: depends on state and immediate input.

Workflow Checklist for Any FSM Design

  1. Read & draw timing diagram; clarify ambiguities.
  2. Draft state diagram; verify edge cases (stuck buttons, invalid inputs).
  3. Build state table.
  4. Choose state codes; compute #FFs.
  5. Obtain next-state / output equations (K-maps or software optimiser).
  6. Map to flip-flop type (D, T, JK) → excitation equations.
  7. Draw schematic or write HDL; simulate.
  8. Hardware test, observe with LEDs/scope, iterate.