RTL for non-power-of 2 Gray Code

Gray codes are widely used in the industry for various purposes. One such application is in asynchronous FIFO where it is used to clock cross the read and write pointers. Its usefulness is because of the one special characteristic it possesses: It is a unit-distance code, meaning only 1-bit changes when moving from one count to the next. Another important characteristic of gray code is that it is a reflective code. If you write the gray code for count 0 to 15 (which will need 4-bits), you will notice that starting from count 8, the 3 LSBs are reflection of the count from 0 to 7 and the MSBs are inverted.

When we are writing gray code for power-of-2 numbers, for example gray code for 0-7 or 0-15, we do not face any problem as both the characteristics hold true for them. Now think about the situation when you must count only from 0-10 or 0-13, or something like that.

0 in gray code is 0000

10 in gray code is 1111

13 in gray code is 1011

See the problem? When we wrap around the counter, meaning when we start counting again after reaching the last count, all 4 bits are changing when going from 10 to 0, 3 bits are changing when going from 13 to 0. We are not meeting the requirement of gray code being a unit distance code, and hence it is not a gray code anymore.

So, let us say you want the depth of a FIFO to not be a power-of-2 in an asynchronous FIFO. There are two possibilities:

1. Depth is an even number

2. Depth is an odd number
   

We will deal with the easier one first: odd depth. Simply put, it is not possible to have a FIFO with odd number of depths. You should just increase the FIFO depth by 1 and have a FIFO with even number of depths, because...

Having an even depth is possible, and the following article goes into great detail about the same.

How to generate Gray Codes for non-power-of-2 sequences

I will convert one of the implementations mentioned in this article to RTL. There are other possible implementation too, please go through the link to learn about them. It will not be very hard to convert them to RTL as well, once you understand the RTL I am going to present.

Pruning the middle:

Picture taken from the EETimes article

So basically, what we are doing here is:

1. Pick the “mirror” line, where the bottom half is reflection of the upper half except the MSB

2. Remove 1 number above and below the mirror line to get 14-count code, 2 number above and below the mirror line to get 12-count code and so on and so forth.

It is quite obvious that to get a gray code counter, we need to first implement the binary counter and then convert the binary count value to gray code. The process will be same here with just one change, we are skipping some numbers. We are skipping 2 numbers for 14-count code, 4-numbers for 12-count code etc. Here is the RTL for a 12-count gray code counter.

module non_power_of_2_gray(
  input logic clk, rst,
  output logic [15:0] np2_gray_code
);
  
  logic [15:0] bin_count, next_bin_count;
  
  always @(posedge clk or posedge rst) begin
    if (rst) bin_count <= '0;
    else     bin_count <= next_bin_count;
  end
  
  //Skip to binary count 11 when counter value reaches 7
  assign next_bin_count = (bin_count==16'h7) ? (bin_count + 16'h4) :
                          (bin_count + 16'h1);
  
  //Convert binary to gray
  assign np2_gray_code = bin_count ^ (bin_count>>1);
  
endmodule

This is how you can get a non-power-of-2 gray code counter. Try to write the RTL for other implementations mentioned in the article, shouldn’t be too hard.

See you in the next article!