Finite State Machine: Difference between revisions

Latest revision as of 17:48, 7 October 2025

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.

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 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.

TODO: Describe the advantages each machine has

@@ Line 1: / Line 1: @@
+; '''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.
-{{Todo|The whole page}}
+== 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.
-A Finite State Machine is a circuit that will produce a sequence of states and output signals depending on input conditions and a state graph.
+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.
-It's constructed using either a [[ROM]], or a [[Programmable Logic Array]], by taking some or all of the components outputs and connecting them to some or all of its inputs through a [[Register]].
+== 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}}.
-The component can then be used to create mappings of one list of states to another.
+{{Todo|Add details for how this condition check is actually implemented}}
+{{Todo|Describe how multiple condition checks in the same state are handled}}
-For example, you could map the states <code>1 to 2</code>, <code>2 to 3</code>, <code>3 to 5</code>, <code>5 to 8</code>, and <code>8 to 13</code>, and as you pulse the register, you will see the sequence <code>1, 2, 3, 5, 8, 13</code> appear.
+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.
-Where state machines become really powerful though is when you map <code>13 to 1</code> , doing so creates a loop in the graph, and allows the sequence to repeat indefinitely.
+== Output Generation ==
+A state machine can also produce output signals in each state.
-You can have extra inputs to act as flags to check, allowing you to create conditional branches.
+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.
-For example, you could map <code>3 to 5</code> if the input <code>fib</code> was on, and you could map <code>3 to 4</code> if the <code>fib</code> input was off.
+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.
-{{Todo|Add details for how this condition check is actually implemented}}{{Todo|Describe how multiple condition checks in the same state are handled}}
+Such a setup is known as a '''[[wikipedia:Mealy_machine|Mealy machine]]'''.
-In cases where an input is not checked, but is actually ignored, you'll need to implement the same state mapping twice, once for if the condition is on, and again for if the condition is off, in order for the transition from state to state to happen regardless of the conditions state.
-This is only true if you're using a [[ROM]] to represent your state graph. If you are using a [[Programmable Logic Array]], you can just not connect the input.
-A state machine can also produce extra outputs in each state.
-This can be done by connecting a [[Lookup Table]] to the output of the state register, and mapping each valid state to a combination of outputs. This setup is referred to as a [[wikipedia:Moore_machine|Moore machine]].
-Alternatively, you can give the state machine more outputs and synchronize them with another register. This allows the state machine to pick the next combination of outputs at the transition. This setup is referred to as a [[wikipedia:Mealy_machine|Mealy machine]].
 {{Todo|Describe the advantages each machine has}}