Finite State Machine
- Finite State Machine
- In Logic World, a Finite State Machine (FSM) is a circuit that produces a sequence of states and output signals depending on input conditions and a defined state graph.
Construction
An FSM is constructed using either a ROM or a Programmable Logic Array (PLA), with some or all of the component’s outputs connected back to its inputs through a Register. The register stores the current state, while the ROM or PLA defines the transition logic that determines the next state.
This structure allows the circuit to map one list of states to another.
For example, if you define transitions 1 → 2, 2 → 3, 3 → 5, 5 → 8, and 8 → 13, then each register pulse will produce the sequence 1, 2, 3, 5, 8, 13.
When you add a transition 13 → 1, the graph becomes cyclic and the sequence repeats indefinitely.
Conditional Transitions
FSMs can use extra inputs as flags to control conditional branching.
For example, you could map 3 → 5 if input fib is ON, and 3 → 4 if fib is OFF.
If an input should be ignored in a ROM-based FSM, you must duplicate the same state mapping twice—once for the input being ON and once for OFF—so that the transition occurs regardless of input state. In contrast, if you use a PLA, you can simply leave the unused input unconnected.
Output Generation
A state machine can also produce output signals in each state.
This can be done by connecting a Lookup Table to the register’s output and assigning each valid state a corresponding output pattern. Such a configuration is known as a Moore machine, where outputs depend solely on the current state.
Alternatively, outputs can depend on both the current state and the inputs by synchronizing them with another register. This allows the FSM to select a new output combination during state transitions. Such a setup is known as a Mealy machine.