Digital Circuits/Finite State Machines

Finite State Machines

Abstractly, a finite state machine is a system that can be described by the states it can assume, the state it starts in, the input it receives, and how it changes state. A state machine will change state dependent upon its current state and also current factors impacting the system, namely, inputs. One state is designated the initial (or start) state. Beginning with this state, the inputs are sampled periodically, and the machine changes state dependent on both the inputs and its present state. This state may be observed and treated as an output; the present input may also influence the output.

Concretely, we are interested in creating a system that produces certain outputs under certain conditions. What is special about finite state machines is that they have memory, in a sense. Unlike a logic gate, where the current output depends only on the current input, a finite state machine's output depends on both past input—through the state it has moved to over time from its initial state—and current input. We accomplish this through flip-flops. Note, too, that the state only changes at discrete times; thus, we are creating a sequential circuit.

Transition Tables

To understand the workings of a finite state machine, you must understand how it changes state. In a given state, a given output produces a change of state (perhaps to the same state). We can represent the finite state machine, then, as a function mapping an input and state to a state. We can describe this transition function using a transition table in a way similar to a truth table: label rows with the distinct inputs, columns with the distinct states, and in each input-state cell, put the label for the state the machine transitions to when given the row's input while in the column's state.

In a digital circuit, the inputs will be binary values, the transition function will be implemented by using the inputs and the outputs of the flip-flops at a given clock pulse to affect the state of the flip-flops, and the new state will be the new state of the flip-flops after the clock pulse.

State Diagrams

An alternative representation of a finite state machine is that of a state diagram. Here, the states are designated by labeled circles. An arrow is drawn from one state to another whenever the machine is able to transition in one step from the state at the arrow's tail to the state at its head. The arrow is labeled with the input that prompts the transition.

State diagrams are very useful for producing the state transition table and ensuring that all possible input transitions are accounted for. Because they can be simpler than the corresponding transition table (when several different input combinations produce the same transition, they are all used to label only a single arrow, rather than each given their own entry), they are also useful in grasping the functioning of a system.

Mealy Machines

A Mealy machine is a machine whose output is a function of the current state of memory and the current input.

Moore Machines

A Moore machine is a machine whose output is a function of the current state of memory.