 Introduction to State Machines

Sequential Circuit and State Machine

Although combinational logic circuits form the backbone of digital circuits, sequential circuits are used in the vast majority of useful devices; there are more than 100 billion in existence.

Many problems require the detection or generation of a sequence of events. As examples, an electronic combination-lock door controller must detect when a particular sequence of numbered buttons has been pressed, and an elevator controller must create a sequence of signals to shut the doors, move the cabin, and then reopen doors. In such situations, a circuit can only advance to the next action (or next state) if the current action is known. For example, an elevator should not move until the doors are shut, and pressing a '2' at some point on a combination lock may or may not contribute to the unlock sequence. A circuit that operates according to a specific sequence of events is called a “state machine” or “sequential circuit”. A state machine requires memory to store information about past actions, and it uses that memory to help determine what action to take next. Outputs from sequential circuits are functions of the current inputs and memorized past inputs. This is in contrast to a combinational circuit, where the outputs are strictly a function of the current inputs.

Most memory-containing circuits provide data storage for computing devices. Examples include RAM arrays for computers, registers and register files for microprocessors, cache memories, accumulators, status indicators, etc. These memory circuits may use flip-flops, latches, or RAM cells (depending on the particular application), and they are only used to store data elements in a processor environment. Memory devices used in sequential circuits do not store data, but rather the operating state of the circuit. The state of a sequential circuit is defined by the collective contents of all of its memory devices. The value stored in each memory device in a state machine is referred to as a state variable. Since a state variable can only take one of two values ('0' or '1'), a circuit with N state variables must be in one of $2^N$ states, and each state is defined by a unique N-bit binary number. The memory devices in a given state machine are collectively referred to as the state register.

The previous lab presented basic memory devices, including the basic cell, the D-latch, and the DFF. While any of these (or other) memory devices could be used to implement a state register, the sequential machine design process is greatly simplified if memory devices with certain characteristics are used. Those characteristics are: the ability to be driven to a stable operating state ('0' or '1'), a timing signal that generates the smallest possible sampling window to dictate exactly when new data can be written, a single data input that directly programs the memory device, and a single reset signal that can drive the output to '0' regardless of the data or clock input signals. All of these characteristics are contained in a DFF, and DFFs are used in practically all sequential circuits. In fact, DFFs can be used to construct any sequential circuit, and their use will always yield the smallest, simplest sequential circuits.

A sequential circuit follows the general model shown in Fig. 1 below. The state register is controlled directly by an external clock and reset signal. Data inputs to the state register arise from a “next state” logic block that combines circuit inputs with state register outputs—this feedback of the state variables is the reason a sequential circuit can implement a given sequence of events. Without this feedback, future state register changes could not be based on past events, and so ordered sequences could not be implemented. The output from the state register is called the “present state”, and the input to the state register is called the “next state”. At each edge of the clock, the next state is written into the state register and so becomes the current state.

Like the next-state logic circuit, the output logic circuit contains only combinational devices. In Fig. 2 below, the most general state machine model is shown with circuit inputs fed forward to the output logic block where they can be combined with state variables to determine overall circuit outputs. This most general model is called the “Mealy” model; in the simpler “Moore” model, only the state variables drive the output logic block, so the feed-forward signal would not be shown (i.e., the red line would be absent). In simpler state machines like counters and other basic sequence generators, the output logic block may not be present at all. In such cases, the state register outputs are used as the overall circuit outputs.