DjSapsan: improved formatting

2025-10-07T17:48:31Z

improved formatting

← Older revision		Revision as of 17:48, 7 October 2025
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}}		{{Todo\|Describe the advantages each machine has}}

N00basaurus: Created a rough outline of a Finite State Machine page

2025-10-06T06:24:21Z

Created a rough outline of a Finite State Machine page

New page

{{Todo|The whole page}}

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.

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

The component can then be used to create mappings of one list of states to another.

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.

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.

You can have extra inputs to act as flags to check, allowing you to create conditional branches.

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.

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

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

Finite State Machine - Revision history

DjSapsan: improved formatting

N00basaurus: Created a rough outline of a Finite State Machine page