A state machine is a digital device that traverses through a predetermined sequence of states in an orderly fashion. A state is a set of values measured at different parts of the circuit. A simple state machine can consist of PAL device based combinatorial logic, output registers, and buried (state) registers. The state in such a sequencer is determined by the values stored in the buried and/or output registers.

Finite state machines are so named because the sequential logic that implements them can be in only a fixed number of possible states. The counters are rather simple finite state machines. Their outputs and states are identical, and there is no choice of the sequence in which states are visited. More generally, the outputs and next state of a finite state machine are combinational logic functions of their inputs and present state. The choice of next state can depend on the value of an input, leading to more complex behavior than that of counters. Finite state machines are critical for realizing the control and decision-making logic in digital systems.

Machine is a quintuple of sets M = (S, I, O, d, b/l )
S
: Finite set of states, which define behavior and may produce actions
I: Finite set of inputs, which are either externally or internally generated
O: Finite set of outputs
d: State transition function, which are movement from one state to another
b/l: Mealy/Moore output function

Basic FSM Design Procedure:

(1) Understand the problem
(2) Obtain a formal description
(3) Minimize number of states
(4) Encode the states
(5) Choose FFs to implement state register
(6) Implement the FSM

FSM State Diagram

A finite state machine must have an initial state, which provides a starting point, and a current state, which remembers the product of the last state transition. Received input events act as triggers, which cause an evaluation of some kind of the rules that govern the transitions from the current state to other states. The best way to visualize a FSM is to think of it as a flow chart or a directed graph of states, though as will be shown; there are more accurate abstract modeling techniques that can be used.

Synchronous FSMs may change state only when a unique input, the clock occurs. Asynchronous FSMs may change state when input changes. Next state depends on present input and present state for both Moore and Mealy FSMs.