Technical Article

# Which Encoding Type Should I Use? Example FPGA Applications

January 06, 2021 by Eduardo Corpeño

## Follow three experiments that show the process of determining which kind of encoding suits a given FPGA.

Which encoding type should I use for my FPGA? As I discussed in the previous article, a compiler will generally decide this for you—and I recommend you follow what the compiler decides.

It is, however, important to understand the differences between the types of encoding and why a compiler might come to a certain conclusion. With that in mind, this article will walk you through an experiment that shows an example FPGA application and discusses, step by step, which encoding type is best.

So far in this series, we've discussed how to create a finite state machine (FSM) with Verilog, the initial state and how memory affects FPGA encoding, and a high-level overview comparing binary vs. one-hot vs. Gray encoding.

### The System Under Test

For this experiment, I wanted to instantiate a state machine a large number of times to magnify the differences in the resulting hardware when binary, Gray, and one-hot encodings are used.

The system I finally chose is Conway’s Game of Life, a cellular automaton that simulates the behavior of living cells in their environment, which is a rectangular 2D array of cells. Conway’s Game of Life is a simulation of these cells being born, reproducing, and dying, according to a simple set of rules that each cell follows to determine what happens in the next cycle. Each living cell may survive or die, and each dead cell may stay dead or become living. Here are the rules for each cycle:

1. Living cells with two or three living neighbors survive.
2. Dead cells with three live neighbors come to life.
3. All other cells die or stay dead.

These rules create a lot of interesting behaviors and patterns that have been widely studied in computer science.

This is how Conway’s Game of Life looks when running what is known as a single Gosper's glider gun.

### Verilog Code

Back to our testing system, each cell was designed as a state machine with eight states. Admittedly, the logic for a cell in Conway’s Game of Life can be resolved in one cycle, but I decided to make an 8-state machine to have a notable difference when using different encodings. The states are used for counting the living neighbors of a cell.

The following piece of Verilog code shows the cell module structure for these machines, including the original binary encoding of states.

define STATE_0  3'b000

define STATE_1  3'b001

define STATE_2  3'b010

define STATE_3  3'b011

define STATE_4  3'b100

define STATE_5  3'b101

define STATE_6  3'b110

define STATE_7  3'b111

module LifeCell(

        input clk,

        input nrst,

        input seed,

        input [7:0] neighbors,

        output reg alive);

    reg [2:0] state;

    always @ (posedge clk)

        if (nrst == 0)

            state <= STATE_0;

        else

            case(state)

                STATE_0: begin

                    // ...

                    state <= STATE_1;

                end

                STATE_1: begin

                    // ...

                    state <= STATE_2;

                end

                // ...

                STATE_7: begin

                    // ...

                    state <= STATE_1;

                end

            endcase

endmodule`

If you’d like to take a closer look at the code, feel free to check out the project on GitHub.

### FPGA Encoding Implementations

The system was synthesized and implemented as a world of 23x23 cells, in a total of 27 variants: three different FSMs were used, all with the three encodings mentioned above, all on three different target FPGAs.

#### FSM #1: Original Model

This machine has an initial state that runs once and then runs in a cycle through the remaining seven states. This is almost a complete sequence, so Gray encoding seemed promising to me at first.

#### FSM #3: An Arbitrary Tangle

This machine has the same critical path of FSM #1, but it goes through an arbitrary path when the number of living neighbors is known to exceed 3.

For this arbitrary state transition behavior, I expected one-hot encoding to be the best choice.

#### Target Architectures

The system was implemented for three target FPGAs, using their vendor’s development tool:

• Xilinx Vivado Suite, for an Artix 7 FPGA
• Intel Quartus Prime, for a Cyclone V FPGA
• Lattice Diamond, for a LatticeXP2 FPGA

### Comparing the Results

Comparing the performance of two or more systems is tough, mostly because the verdict depends on the metrics we use and which aspects we consider more important than others. For this experiment, I gathered the following data to produce a score for each implementation:

• Number of Logic Units. These are LUTs (look up tables) for Xilinx and Lattice FPGAs, or ALMs for Intel FPGAs. Score: 1 point.
• Number of Registers. Score: 1 point.
• Estimated Maximum Frequency. Score: 2 points.
• Estimated On-Chip Power. Score: 2 points.

For every implementation, these four aspects were compared among the three encodings, so among the encodings, I got a best, a worst, and a middle result: The best gets its positive score, the worst gets its negative score, and the middle one gets 0.

After adding up all the scores for each model, I got the following results:

##### Results table for all 27 implementations. In each row, the best encoding is shown in green, the worst in red, and the middle in yellow if there are no ties.

This seems to suggest staying away from one-hot encoding, with only two cases where it wins, one of which is a tie. Moreover, while I originally expected one-hot to be the best encoding for FSM model #3, it turned out to be its worst encoding, with no development tool recommending it. That said, there are cases where one-hot beats the rest, mostly in the frequency and power metrics.

Overall, Gray encoding seems to be the best choice for this particular system.

Extracting the winners from this table, we get the following:

### The Verdict

Even though this comparison seems to favor Gray encoding over binary and one-hot, the results depend highly on the metrics we use, and these metrics reflect what’s important to us. For example, in this comparison, I considered frequency and power more important than usage (the number of logic elements and registers in the design.) If I had valued usage over frequency and frequency over power, surely a different ranking would have resulted.

This comparison was not intended to be a definitive work on the performance obtained by using these encodings. Instead, it shows the ranking produced by my personal preferences in the architectures I used.

Once again, if you’d like to take a look at the code, check out the 27 implementations, or see my simulation of Conway’s Game of Life in action, check out the project on GitHub.

• Share
1 Comment
• A
andrewmm January 07, 2021

This is a good article on theory,
IMHO , using the default “automatic” mode is best .

All the tools I know off, have optimisation built in,

basic, encode the state machine using enumerate types,
DO NOT assign states.

The tools will then optimise your FPGA to meet your timing constraints.

Its a fact of the tools, that if the device is empty, then the tools will come up with one solution,
as the device fills up , they come to another solution to meet your desing,

Remember , the Tools , run till they meet your timing and fit in the device.

Most places I work as a consultant, have design guides that state that you will only use auto mode,
some have had designs of big machines fail when moved to a new device due to not using auto mode.

Like.