A Finite State Machine (FSM) is a sequential circuit that moves between specific states according to a well-defined set of rules.
A general FSM has some standard properties:
- The next state is determined from the output of combinatorial logic involving both the current state and any inputs.
- The current state is held in a register.
- The next state becomes the current state at the rising edge of every clock cycle.
- The outputs are determined by a combinatorial block the current state, and occasionally also any inputs. It is important to note the third point, and recognise that the implementation of a FSM does not remain in a single state for multiple clock cycles, but rather repeatedly move to the same state.
Finite state machines can be seen as the equivalent for sequential circuits of the boolean expression representing the behaviour of a combinatorial circuit. A FSM is a deterministic and, importantly, exhaustive description of the behaviour of a sequential circuit over time.
Describing Finite State Machines
A FSM can be represented with a graph-like diagram, known as a State Transition Diagram using vertices to represent states and edges the possible transitions between them. Alternatively, a State Transition Table maps each combination of inputs and current state to the respective next state.
Unused states
It is likely there that will be numerical values that do not have assigned states (if the number of states is not a power of 2). In this case, it is good practice to ensure that if one of these ‘unused’ states is encountered, the behaviour is defined and the machine returns to a valid state.