Finite State Machine

A sequential circuit is a digital system that has memory and decisions. It makes for a given input depend on what it has memorized. These circuits have local (inside flip-flops) or global feed backs and the number of feed backs determine how much of its past history it remembers.

The number of states of a sequential circuit is determined by its memory. A circuit with n memory bits has 2n possible states. Signals or variables representing these states (n of them) are called state variables. Because sequential circuits have a finite number of states, they are also called finite state machines (FSM).

All sequential circuits from a single latch to a network of high performance computers can be regarded as an FSM. These machines can be modeled as a combinational circuit with feedback. If the feedback path includes an array of flip-flops with a clock for controlling the timing of data feeding back, the circuit becomes a synchronous sequential circuit. Figure below shows the Huffman model of synchronous sequential circuits. This model divides a circuit into a combinational part and a register part.

The clock shown is the synchronization signal. Outputs that are fed back to the inputs are state variables. The inputs of the flip-flops become the present state of the machine after the circuit clock ticks. The circuit decides on its outputs and its next state based on its inputs and its present state.



References:

• Digital Design and Implementation with Field Programmable Devices, Zainalabedin Navabi, Kluwer Academic Plubishers, 2005.