Counting in Gray – Part I – The Problem

May 10, 2007

I love Gray codes, there I said it. I love to try to find different and weird applications for them.
But Gray codes are one of those things where most designers heard of and know the principle they use – but when coming to implement a circuit based on Gray codes, especially when simple arithmetic is involved, things get complicated for them.

I don’t really blame them since that stuff can get relatively tricky. Maybe it is best to show with an example…
This paper is a must read for any digital designer trying to design an asynchronous FIFO. All the major issues, corner cases and pitfalls are mentioned there, and I just can’t recommend it enough.

But… what caught my attention was the implementation of the Gray counters in the design (page 2, section 2.0). Before we get into what was written, maybe a presentation of the problem is in place. Counting (i.e. only +1 or -1 operations on a vector is considered) in binary is relatively straight forward. We all learned to do this, and use it. The problem is how do you count in “Gray code” – i.e. given the 3-bit gray code number 111, what is the next number in line? (answer: 101)

The figure below shows the Gray code counting scheme for 3-bit “mirrored” Gray code (the most commonly used)

Look at any line, can you figure out what will be the next line based only on the line you look at??? If you think you know try figuring out what comes after 11011000010 ??? 🙂

There are 2 very common approaches to solve this problem:

  1. Convert to binary –> do a “+1” –> convert back to Gray
  2. Use a Look-up-Table to decode the next state

Both have severe disadvantages.

Let’s look through them one at a time.
Option 1, can be implemented in principle in two different ways (the plot thickens…)

grayplus1_o11.png grayplus1_o21.png

The implementation on the left has the big advantage that the Gray output is registered, i.e. the values stored in the Flip-Flop are truly Gray. This is necessary when the output is used in an asynchronous interface (e.g. as a FIFO pointer).
The implementation on the right is faster though, with the disadvantage of the output being combinational.
The advantage of both implementations is that they are relatively compact to describe in HDL, even for wide counters and very flexible – e.g. one can add a “-1” functionality quite easily.

Option 2, is basically a big LUT that describes the next Gray state of the counter.
The outputs will be truly registered, the implementation relatively fast, but very tedious to describe in HDL and prone to errors. just imagine a 7-bit Gray counter implemented as a big case statement with 128 lines. Now imagine that you would want to add a backward counting (or “-1”) operation.

The natural question asked is, isn’t there a better implementation that gives us the best of both worlds? Registered outputs, fast and easily described in HDL. The answer is a big “YES”, and I will show how to do it on my next post. That implementation will be even easy enough for entering it in schematic tools and using it in a full-custom environment!

hold on…


One comment

  1. […] can use the modular up/down Gray counter I described here, here and here. for our (n-1) LSBs. We have to find a priori the “switching value”, […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: