1. Digital Logic
2. Topic: State Machine Models

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 (or state) 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 (we will use the terms somewhat interchangeably). 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 circuits in use today provide data storage for computing devices. These memory arrays often contain millions (or billions) of bits, and they use small, inexpensive DRAM memory cells that are optimized for large-scale data storage. But these types of memories come with significant overhead (for example, they need to be periodically refreshed), and they are not well suited for use in registers. On the other hand, registers, even large registers, only store relatively few bits. They are typically used to store small amounts of data, like status information or temporary operand values. Registers are prevalent in applications where simple use models and fast read/write times are more important than small cell size. Registers use flip-flops as their memory cells – in fact the term “register” means a collection of flip-flops that share the same clock and reset, but that have separate data inputs and outputs.

The state of a sequential circuit is defined by a binary number stored in its state register. The state register is composed of flip-flops, and the value stored in each flip-flop 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 unique state is defined by its unique binary number. The outputs of the state register are called the “present state” bus, and the inputs to the state register are called the “next state” bus. At every active clock edge, the next state is “clocked in” to the state register, and so becomes the present state. Flip-flops are ideally suited for use in a state register, because they can only change state during a very small window around the active edge of the clock. This window is much shorter than the time required for the present state to feed back through the next state logic circuit to become the next state, so the register can change state at each active clock edge without any difficulties.

A state machine circuit uses the general architecture shown above. 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 circuit that combines the overall circuit inputs (labeled In1, In2, etc.) with state register outputs. State register outputs also drive the output decoder circuit. This logic circuit “decodes” the state variables to create useful outputs. Note that it is the feedback of state variables allows a state machine to implement a given sequence of events.

Consider a digital combination lock with an overly simple combination of “1-6”. The lock will be opened if input button 6 is pressed immediately after button 1 is pressed. But if button 6 is pressed after any other button, the lock must not open. Thus, a sequence must be memorized in the state machine – in this case, the fact that button 1 was pressed first is “memorized” as a unique state held in the state register. That state information is fed back to the next state logic, so that if button 6 is pressed while the state register is in the “button 1 was most recently pressed” state, a new state can be entered to assert the unlock signal. Without such feedback, future state register changes could not be based on past events, and so ordered sequences like this could not be implemented.

The general model above is known as a “Moore Model” state machine, after Edward Moore who presented the general concept in a 1956 paper (that’s not very long ago!). Any sequential circuit ever built, including computers, cell phones, game consoles, etc., can be built using the Moore model.

A simple enhancement to the Moore model allows one or more inputs to bypass the state register, and combine with state variables to produce the overall circuit outputs. This addition can often reduce the number of state variables needed to solve a given problem, and thereby make the state machine more efficient. State machines that use this general architecture are known as “Mealy Model” state machines, after George Mealy who fist described this general model in 1955. Mealy model state machines are perhaps more common than Moore model state machines because they can be much more efficient, but again, any machine can be built using the Moore model.

Fed-forward inputs that bypass the state register are said to generate “conditional outputs”, because the effected outputs are not produced exclusively by decoding the state register – rather, the outputs are conditional, based on the state of the input signal.

The example timing diagram below shows the behavior of a hypothetical state machine that has two inputs, two outputs, and three state variables (what the state machine actually does is not important here - just examine the timing diagram). Note that a new present state is entered after every rising clock edge – that’s because the state register is updated at the clock edge, and in this example, the state variables and inputs combine to cause a state transition at every clock. Note the inputs can change at any time – what’s important is the value of input signals at the rising edge of each clock, because that’s when they can effect a state change. Note also the outputs can only change immediately after a clock edge – that’s because the outputs are based on the state variables, and the state variables are only updated on clock edges.

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 state codes are possible. The state machine progresses from state 0 (on reset) to states 1, 2, 3, 1, 5, 7, and 0. We will examine how (and why) the state machine changes state shortly – for now, we are only illustrating the general timing model.

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