THE MAGAZINE FOR COMPUTER APPLICATIONS
Circuit Cellar Online offers articles illustrating creative solutions
and unique applications through complete projects, practical
tutorials, and useful design techniques.

STATE MACHINES

by Ingo Cyliax

Start ı An ASM Example ı Input and Output Signals ı Implementation ı One-Hot Encoding ı Synthesize ı Initializing ı Until Next Time ı Sources and PDF

This month, Iıd like to look at state machine design in FPGAs. Up to now, Iıve been writing about design elements that can be used in what is called the data path of a design. Typically, a design is broken up into a data path (elements like register banks, adders, multipliers, etc.) and a control section. Some designs donıt have much of a control part. This might be something similar to a DSP element like a FIR filter, where a result on each clock cycle is computed and output.

However, more interesting designs usually have a more complex control part. Some examples are processors, algorithms that are implemented directly in hardware, or protocol controllers. Here the hardware may have to react to inputs and depend on internal state, rather than just compute an output value.

Some of you have probably studied state machines and their designs. You may have drawn state charts and computed next state equations. Writing down specifications, like in the form of a state chart, is good design practice, especially for state machine designs. They tend to be too complex for designers who start drawing schematics too early, usually designing themselves into a corner.

This month, Iım going to show you how to spec a state machine using algorithmic state machine (ASM) charts, and implement them efficiently using one-hot state encoding, which is the state machine implementation of choice for FPGAs.

ASMs were developed by T.E. Osborne and first described in C.R. Clareıs book, Designing Logic Systems Using State Machines. [1] ASMs are good to use because you can express both Mealy and Moore state machines, and they can be abstract. The latter is important in the beginning of the design process when youıre not yet sure what the implementation will look like. Although Iım going to describe synchronous state machines, ASMs can be used to describe asynchronous systems and software as well.

ASMs use graphical blocks to describe the design. There are three types of blocks I will use. One is the state block, which is a rectangle and denotes a particular state in the system. Each state block has a label next to it that describes the name of the state. This can be an abstract name at first, and later, encoding can be associated with this state label. The contents of the state box describe what happens when the machine enters that state. These are known as the unconditional outputs and describe the behavior of a Moore machine.

Another block is a diamond-shaped box. This box represents a conditional branch or test. It is used to indicate what input variables and conditions are consulted to compute the next state or a conditional output. A branch block can have multiple output graphs, each of which has a label or expression that has to be true for that branch to be taken.

Finally, there are conditional outputs. These are ovals that follow a branch to indicate one of several possible output conditions that can happen in the same state. This is used to describe what Mealy machines do.

So, you can see that ASMs can be used to describe Mealy and Moore state machines or a mix of both. Initially, the descriptions in the boxes can be abstract. In early phases of the design, these may be just phrases, like "turn on the motor" or "check operator input." As the design is refined into an implementation, these labels become more concrete and represent signals and variables.

NEXT