Spec: State Machine Designer

Overview

Add a visual Finite State Machine (FSM) editor that allows users to design state machines graphically (states, transitions, outputs) and automatically generate equivalent sequential circuit implementations using flip-flops and combinational logic.

Motivation

State machines are fundamental to sequential logic design, but translating a state diagram into flip-flops, next-state logic, and output logic is tedious and error-prone. A visual FSM designer that auto-generates the circuit bridges the conceptual gap, making it an exceptional teaching tool and a productivity booster for practical designs.

Requirements

Functional Requirements

FSM Editor

1. State Creation: Click to add states (circles) on a dedicated FSM canvas.
2. Transition Drawing: Draw directed arcs between states with input conditions.
3. State Naming: Each state has a user-defined name and optional binary encoding.
4. Output Assignment: Assign outputs to states (Moore) or transitions (Mealy).
5. Reset State: Designate one state as the initial/reset state.
6. Self-Loops: Support transitions from a state back to itself.
7. Transition Conditions: Boolean expressions over input variables (e.g., A AND NOT B).
8. Don't Care States: Support don't-care conditions for optimization.
9. FSM Type Selection: Moore machine (outputs depend on state only) or Mealy machine (outputs depend on state + inputs).
10. State Encoding: Automatic or manual encoding (binary, one-hot, Gray code).

Circuit Generation

11. Auto-Generate Circuit: Convert FSM definition to a gate-level circuit.
12. Flip-Flop Selection: Choose D, JK, or T flip-flops for implementation.
13. Logic Minimization: Use Quine-McCluskey or Espresso to minimize next-state and output logic.
14. Generated Circuit Preview: Show the generated circuit before inserting into the main editor.
15. Insert as Macro: Option to insert generated circuit as a named macro component.
16. Regeneration: If the FSM is modified, regenerate the circuit (with confirmation).

Analysis

17. State Table Generation: Display the state transition table.
18. State Encoding Table: Show the binary encoding of all states.
19. Reachability Analysis: Detect unreachable states and warn the user.
20. Completeness Check: Warn if transitions are incomplete (missing input combinations).

Non-Functional Requirements

• FSM editor supports up to 32 states and 8 input variables.
• Circuit generation completes in under 3 seconds.
• Generated circuits are correct-by-construction (verified against state table).
• FSM definitions are saveable and loadable independently of circuits.

Design

FSM Data Model

public class StateMachine
{
    public string Name { get; set; }
    public FsmType Type { get; set; }  // Moore or Mealy
    public List<State> States { get; set; }
    public List<Transition> Transitions { get; set; }
    public List<string> InputVariables { get; set; }
    public List<string> OutputVariables { get; set; }
    public State ResetState { get; set; }
    public StateEncoding Encoding { get; set; }
}

public class State
{
    public string Name { get; set; }
    public string BinaryCode { get; set; }  // assigned encoding
    public Point Position { get; set; }  // canvas position
    public Dictionary<string, Signal> Outputs { get; set; }  // Moore outputs
}

public class Transition
{
    public State From { get; set; }
    public State To { get; set; }
    public string Condition { get; set; }  // Boolean expression
    public Dictionary<string, Signal> Outputs { get; set; }  // Mealy outputs
}

public enum StateEncoding { Binary, OneHot, GrayCode, Manual }
public enum FsmType { Moore, Mealy }

Generation Pipeline

FSM Definition
    → State Encoding Assignment
    → State Transition Table
    → Next-State Equations (per flip-flop input)
    → Logic Minimization (Quine-McCluskey)
    → Output Equations
    → Logic Minimization
    → Circuit Netlist (flip-flops + gates)
    → Component Placement (auto-layout)
    → Insert into Editor

UI Layout

┌────────────────────────────────────────────────────┐
│  State Machine Designer                        [X] │
├──────────────────────────┬─────────────────────────┤
│                          │ Properties              │
│   FSM Diagram Canvas     │ ─────────────────────── │
│   (states + transitions) │ Name: [traffic_ctrl]    │
│                          │ Type: ○ Moore ● Mealy   │
│                          │ Encoding: [Binary ▼]    │
│                          │ FF Type: [D-type ▼]     │
│                          │                         │
│                          │ Inputs: A, B, CLK       │
│                          │ Outputs: X, Y           │
├──────────────────────────┴─────────────────────────┤
│ State Table | Encoding | Generated Equations       │
│ ───────────────────────────────────────────────── │
│ Current | Input | Next | Output                    │
│ S0      | 00    | S0   | 0                         │
│ S0      | 01    | S1   | 0                         │
│ S1      | 1x    | S2   | 1                         │
└────────────────────────────────────────────────────┘

Implementation Tasks

1. Create DigitalWorks.Core/StateMachine/ namespace with FSM data model.
2. Implement FSM canvas (state/transition drawing with Win2D).
3. Implement state transition table generation from FSM definition.
4. Implement state encoding algorithms (binary, one-hot, Gray).
5. Implement next-state equation derivation for D/JK/T flip-flops.
6. Integrate with existing Quine-McCluskey minimizer (Karnaugh map engine).
7. Implement circuit netlist generation from minimized equations.
8. Implement auto-layout for generated circuits.
9. Create FSM designer window/dialog with properties panel.
10. Implement FSM save/load (standalone .fsm files or embedded in .dwm).
11. Add reachability analysis and completeness checking.
12. Implement "Insert as Macro" functionality.

Risks & Open Questions

• Should the FSM designer be a separate window or a mode within the main editor?
• How to handle regeneration when the user has manually modified the generated circuit?
• Should the tool support hierarchical FSMs (sub-state machines)?
• Integration with Test Bench: auto-generate test sequences from FSM transitions?

Priority

Medium-High — High educational value, strong differentiator among circuit simulators.