Which Encoding Type Should I Use? Example FPGA Applications
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:
- Living cells with two or three living neighbors survive.
- Dead cells with three live neighbors come to life.
- 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.
A variation of Conway's Game of Life, known as Bill Gosper's Glider Gun. Gif created by Lucas Vieira [CC BY-SA 3.0]
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 #2: A Sequence
This machine behaves as a 3-bit counter, so I also expected Gray encoding to crush the competition.
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.
