View source for 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 <code>1 → 2</code>, <code>2 → 3</code>, <code>3 → 5</code>, <code>5 → 8</code>, and <code>8 → 13</code>, then each register pulse will produce the sequence <code>1, 2, 3, 5, 8, 13</code>.  
When you add a transition <code>13 → 1</code>, 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 <code>3 → 5</code> if input <code>fib</code> is {{on}}, and <code>3 → 4</code> if <code>fib</code> is {{off}}.

{{Todo|Add details for how this condition check is actually implemented}}  
{{Todo|Describe how multiple condition checks in the same state are handled}}

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 '''[[wikipedia:Moore_machine|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 '''[[wikipedia:Mealy_machine|Mealy machine]]'''.

{{Todo|Describe the advantages each machine has}}