Introduction to State Machines
Sequential Circuit Design
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
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, 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.
The example timing diagram in Fig. 2 shows the behavior of a hypothetical state machine (what the state machine does is not important here—just examine the timing diagram). Note that every rising clock edge causes a state transition, where the “next state” is clocked into the state register flip-flops to become the “present state”. Each state is uniquely identified by the contents of the state register, called the “state code”. This example shows three state variables, so eight distinct states are possible. The state machine progresses from state 0 to states 1, 3, 2, 2, 6, and 4 based on the inputs I0 and I1 and the current state code. Note also that the outputs Y0, Y1, and Y2 change just after the clock—this is generally the case, because the state codes change just after the clock edge, and the state codes are inputs to the output logic block.
Important Ideas
- 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.
- A circuit that operates according to a specific sequence of events is called a “state machine” or “sequential circuit”.
- Memory devices used in sequential circuits do not store data, but rather the operating state of the circuit.
- In simpler state machines like counters and other basic sequence generators, the output logic block may not be present at all