Previous

Encoding Techniques

The states in a state machine are represented by setting certain values in the set of state registers. This process is called state assignment or state encoding.

There are many ways to arrange, or encode, state machines. For example, for a state machine of five states, you can use three flip-flops set to values for states 000, 001, 010, 011, 100, which results in a highly encoded state machine implementation. You can also use five flip-flops set to values 00001, 00010, 00100, 01000, 10000, that is, one flip-flop per state, which results in a one-hot-encoded state machine implementation. State encoding has a substantial influence on the size and performance of the final state machine implementation.

Symbolic and Encoded State Machines

A symbolic state machine makes no reference to the actual values stored in the state register for the different states in the state table. Therefore, the software determines what these values should be; it can implement the most efficient scheme for the architecture being targeted or for the size of the machine being produced.

All that is defined in a symbolic state machine is the relationship among the states in terms of how input signals affect transitions between them, the values of the outputs during each state, and in some cases, the initial state.

An encoded state machine requires the same definition information as a symbolic machine, but in addition, it requires you to define the value of the state register for each state.

Symbolic state machines are supported for CPLDs, but they are less efficient than encoded state machines.

Compromises in State Machine Encoding

A good state machine design must optimize the amount of combinatorial logic, the fanin to each register, the number of registers, and the propagation delay between registers. However, these factors are interrelated, and compromises between them may be necessary. For example, to increase speed, levels of logic must be reduced. However, fewer levels of logic result in wider combinatorial logic, creating a higher fanin than can be efficiently implemented given the limited number of fanins imposed by the FPGA architecture.

As another example, you must factor out the logic to decrease the gate count; that is, you must extract and implement shared terms using separate logic. Factoring reduces the amount of logic but increases the levels of logic between registers, which slows down the circuit. In general, the performance of a highly encoded state machine implemented in an FPGA device drops as the number of states grows because of the wider and deeper decoding that is required for each additional state. CPLDs are less sensitive to this problem because they allow a higher fanin.

Binary Encoding

Using the minimum number of registers to encode the machine is called binary, or maximal, encoding, because the registers are used to their maximum capacity. Each register represents one bit of a binary number. The example discussed earlier in this chapter has five states, which can be represented by three bits in a binary-encoded state machine.

Although binary encoding keeps the number of registers to a minimum, it generally increases the amount of combinatorial logic because more combinatorial logic is required to decode each state. Given this compromise, binary encoding works well when implemented in Xilinx CPLD devices, where gates are wide and registers are few.

One-Hot Encoding

In one-hot encoding, an individual state register is dedicated to one state. Only one flip-flop is active, or hot, at any one time. There are two ways that one-hot encoding can significantly reduce the amount of combinatorial logic used to implement a state machine.
As noted in the “Compromises in State Machine Encoding” section, highly encoded designs tend to require many high fanin logic functions to interpret the inputs. One-hot encoding simplifies this interpretation process because each state has its own register, or flip-flop. As a result, the state machine is already “decoded,” so the state of the machine is determined simply by finding out which flip-flop is active. One-hot encoding reduces the width of the combinatorial logic and, as a result, the state machine requires fewer levels of logic between registers, reducing its complexity and increasing its speed.

Although one-hot encoding can be used for CPLDs and FPGAs, it is better suited to FPGAs.

One-Hot Encoding in Xilinx FPGA Architecture

One-hot encoding is well-suited to Xilinx FPGAs because the Xilinx architecture is rich in registers, while each configurable logic block (CLB) has a limited number of inputs. As a result, state machine designs that require few registers, many combinatorial elements, and large fanin do not take full advantage of these resources. In general, a one-hot state machine implemented in a Xilinx FPGA minimizes both the number of CLBs and the levels of logic used.

Limitations

In some cases, the one-hot method may not be the best encoding technique for a state machine implemented in a Xilinx device. For example, if the number of states is small, the speed advantages of using the minimum amount of combinatorial logic may be offset by delays resulting from inefficient CLB use.

Encoding for CPLDs

CPLD devices generally implement binary-encoded state machines more efficiently. Binary encoding uses the minimum number of registers. Each state is represented by a binary number stored in the registers. Using as few registers as possible usually increases the amount of combinatorial logic needed to interpret each state.

CPLD devices have wide gates and a large amount of combinatorial logic per register, so it is best to start with binary encoding. If the complexity of the state machine logic is such that binary encoding exhausts all product term resources of a CPLD, try a slightly less fully encoded state machine.

The syntax used to specify one-hot encoded state machines for FPGAs is also supported for CPLD designs.

Next