Finite state machine (thing)

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.