A finite state machine (FSM) is a kind of
digital circuit, (and, possibly, other types of
machines, including
virtual ones) that is used to process information in steps (
states). At every
state a different part of the information can be processed. This has many advantages in terms of reduced
hardware requirements over
combinational logic networks (CLNs). See
hardware/speed tradeoff. A computer is a (very sophisticated) FSM.
There are several important parts of an FSM:
+------+
+----------------------------->|Output|---> Outputs
| +-----+ |CLN |
Inputs -+->|Next | Control | |
|State| Signals +--+ | |
+->|CLN |------------>|DQ|-+->| |
| +-----+ | | | +------+
Clock--------------------------|> | |
| +--+ |
+---------------------------+
State Variables
Note: this is a block diagram of a Mealy Machine shown. See also Moore Machine, Class A Machine, Class B Machine, Class C Machine.
- Input: The input to the FSM can help to determine both the next state and the output. The inputs can either change with the clock, in which case the FSM can be called a synchronous sequential network, or the inputs can change independent of the clock, in which case the FSM is an asynchronous sequential network.
- Output: The output of an FSM is dependent upon the current state and, possibly, the current input. The value of the output variable(s) is determined by the Output Combinational Logic Network (CLN).
- State: The current state of the FSM must be stored somewhere, often in a set of D Flip-Flops, and is usually fed into both the next state logic, and the output logic.
- Control Signals: The control signals are the output of the next state logic, and are fed into the inputs of the D Flip-Flops. On an active clock edge, the value of the control signals becomes the value of the current state.
These devices are said to be causal, and to have memory, as the state of the FSM is dependant not only upon the current input, but also upon past inputs (and thus past states).
See also state assignment, state minimization, state transition table, state transition diagram, digital systems, general purpose computer, one-hot encoding.