Technical Article

Comparing Binary, Gray, and One-Hot Encoding

January 05, 2021 by Eduardo Corpeño

This article shows a comparison of the implementations that result from using binary, Gray, and one-hot encodings to implement state machines in an FPGA. These encodings are often evaluated and applied by the synthesis and implementation tools, so it’s important to know why the software makes these decisions.

Finite state machines (FSMs) are a very common part of nearly every digital system. That’s why synthesis tools often inspect your code to detect FSMs and perform optimizations that may modify the encoding of the states. It doesn’t matter if you carefully selected and specified the values that implement your states in your source code, the synthesis tool may replace those values with others that may even have a different bit length than your original encoding.

If you’d like to brush up on implementing state machines in Verilog, you should read my article titled Creating Finite State Machines in Verilog.


 

Encoding of States: Gray vs. Binary vs. One-Hot

The three most popular encodings for FSM states are binary, Gray, and one-hot.

 

Binary Encoding

Binary encoding is the straightforward method you may intuitively use when you assign values sequentially to your states. This way, you are using as few bits as possible to encode your states.

 

An example of one-hot encoding. Image by Steve Arar

 

Gray Encoding

Gray code consists of a sequence where only one bit changes between one value and the next. In addition to also using the minimum number of bits, this encoding minimizes dynamic power consumption if the sequence of states is followed optimally.

 

The Gray code wheel. Image from Marie Christiano

 

One-Hot Encoding

Finally, one-hot encoding consists in using one bit representing each state, so that at any point in time, a state will be encoded as a 1 in the bit that represents the current state, and 0 in all other bits. This may not seem very efficient at first because of the number of bits used, and the excessive number of invalid states. However, one-hot encoding is very good at simplifying the stimulus logic for the flip flops because there’s no need to decode the states. The bits are the states. 

 

An example of one-hot encoding. Image by Steve Arar

 

For more on state encodings, you may want to check out the article Encoding the States of a Finite State Machine in VHDL by Steve Arar.

 

Which Encoding Is the Best?

This is a tough question, mostly because each encoding has its benefits and shortcomings, so it comes down to an optimization problem that depends on a large number of factors.

  • If a very simple system yields very similar results across encodings, then the original encoding is the best choice.
  • If the FSM cycles through its states in one path (like a counter) then Gray code is a very good choice.
  • If the FSM has an arbitrary set of state transitions or is expected to run at high frequencies, maybe one-hot encoding is the way to go.

Now, all of these claims are just educated guesses, and finding the optimal state assignment is a complicated problem. Because of this, my official advice is to let the compiler decide for you. That said, I decided to run a comparison of the results for these three encodings in three different development tools and three different state machines.

In the next article, we'll discuss the results of my experiments.

1 Comment