Uses of Gray code in digital design

On Sep 11, 4:52 pm, Jonathan Kirwan <jkir...@easystreet.com> wrote:
> On Tue, 11 Sep 2007 05:55:24 -0000, richard.melik...@gmail.com wrote:
> >Hello,
>
> >Most books on digital design discuss Gray codes. However, most of the
> >focus is on generating these codes, rather than detailing their uses.
> <snip>
> >2) Async FIFO addressing between clock domains. Could anyone elaborate
> >on this ?
>
> I don't know, not having worried about this.  But I assume this refers
> to, in saying 'async', that the arrival times of different signals
> aren't necessarily exactly the same and if you have some device
> monitoring an encoded input and taking some action on that basis, it
> would be better that as each bit arrives that the functional change is
> to a "nearby" function (more gradual-appearing in some way.)  But this
> is just a random guess from me.
>

This technique is useful if you access RAM/ROM linearly as a FIFO. Say
for example a video frame buffer. Using gray code instead of straight
low to high addressing allows you to stream the data into or out of
memory without using a latch. This saves one clock cycle per unit data
but considering that data read/write with a latch is two clock cycles
(1.change address, 2.latch data) it achieves 100% improvement in
throughput.

Hi Peter, thanks for replying. My comments below...

> Binary-coded counter sequences often change multiple bits on one count
> transition. That can (will) lead to decoding glitches, especially when
> counter values are compared for identity.

What do you mean by "compared for identity" - do you mean equality of
two multi-bit registers ?

Also, what kind of glitches are you referring to here ? Logic
hazards ?

> Gray-coded count sequences always change one, and only one, bit on
> each transition. Comparing two such counters for identity will thus
> never generate a decoding glitch.
> That is the reason for Gray codes counters in FIFO addressing, where
> FULL and EMPTYis established by comparing two asynchronously clocked
> counters for identity. Gray code addressing is a must for asynchronous
> FIFOs..
>

Why can't the values just be synchronized (double FF) between the
domains with a handshake and solve the problem of glitches in the
first place ?

> The "one bit change per transition" advantage occurs only in counters,
> or under other very restrictive circumstances. I do not see an
> advantage in general state machines, where sequences are not as
> predictable.

So why do all synthesis tools propose "gray code" as one of the
encodings of state machines ?

R

> It depends on the state machine. One's with complex state-state jumps,
> will find it hard to follow a Gray pattern, but if the state engine
> is Spin-Phase-Sync in nature (ie simple circular states, with 'waits'
> and decodes ), then Gray can work well.
>

What do you mean "can work well". Won't normal encoding work just as
well ? I can see an advantage in one-hot encoding, but not Gray.

> <snip>
>
> > In general, what are the other uses of these codes? When was the last
> > time you needed Gray codes in your design and for what purpose ?
>
> Gray codes are also common in Absolute Rotary encoders.
> You could also argue that quadrature encoders, and Stepper Motor
> drive, are special 2 bit cases of Gray counters.
>

Could you elaborate on this ?

Thanks for the information, btw

R

richard.melikson@gmail.com wrote:
>>It depends on the state machine. One's with complex state-state jumps,
>>will find it hard to follow a Gray pattern, but if the state engine
>>is Spin-Phase-Sync in nature (ie simple circular states, with 'waits'
>>and decodes ), then Gray can work well.
>>
> 
> 
> What do you mean "can work well". Won't normal encoding work just as
> well ? I can see an advantage in one-hot encoding, but not Gray.

Gray is useful if you need to decode the states, and also if the 
state-next terms are async, as you have just ONE dependant FF active,
so you cannot get a false state, due to aperture effects.
With one-hot, you must ensure trigger signals are fully sync.



> 
>><snip>
>>
>>>In general, what are the other uses of these codes? When was the last
>>>time you needed Gray codes in your design and for what purpose ?
>>
>>Gray codes are also common in Absolute Rotary encoders.
>>You could also argue that quadrature encoders, and Stepper Motor
>>drive, are special 2 bit cases of Gray counters.
>>
> 
> 
> Could you elaborate on this ?
  On what,the Absolute encoder use, or the Quadrature == 2 bit gray ?
Just draw a 2 bit gray counter, and then make it UpDown, and you
will see the result.

-jg

Jonathan,

Wow - an amazing post, very informative. Personally I'm familiar with
most of this material, but it will definitely serve as a great
placeholder for searches on the subject. Google is great in indexing
such information reservoirs.

Anyway, although the topic of error correction codes using Hamming
distances is enlightening, I don't see how Gray codes help. Maybe it's
just morning dense-ness, but it appears that these topics are
tangential.

> >In general, what are the other uses of these codes? When was the last
> >time you needed Gray codes in your design and for what purpose ?
>
> That's a big question.  Start with the above and see if that helps.

I didn't mean it as a big question. It's quite simple, really - when
was the last time *you* Jonathan (and other readers interested in
sharing) used Gray codes in digital design, either in coding logic or
software ?

TIA
R

richard.melikson@gmail.com wrote:

> Hi Peter, thanks for replying. My comments below...
> 
> 
>>Binary-coded counter sequences often change multiple bits on one count
>>transition. That can (will) lead to decoding glitches, especially when
>>counter values are compared for identity.
> 
> 
> What do you mean by "compared for identity" - do you mean equality of
> two multi-bit registers ?

yes,

> Also, what kind of glitches are you referring to here ? Logic
> hazards ?
> 
> 
>>Gray-coded count sequences always change one, and only one, bit on
>>each transition. Comparing two such counters for identity will thus
>>never generate a decoding glitch.
>>That is the reason for Gray codes counters in FIFO addressing, where
>>FULL and EMPTYis established by comparing two asynchronously clocked
>>counters for identity. Gray code addressing is a must for asynchronous
>>FIFOs..
>>
> 
> 
> Why can't the values just be synchronized (double FF) between the
> domains with a handshake and solve the problem of glitches in the
> first place ?

They could be, but that would add latencies to the FIFO that
are best avoided. ie why compromise the operation, when a Gray
Code design will work better ?

-jg

> This technique is useful if you access RAM/ROM linearly as a FIFO. Say
> for example a video frame buffer. Using gray code instead of straight
> low to high addressing allows you to stream the data into or out of
> memory without using a latch.

Could you elaborate on this, please - how does it avoid a latch, and
where does the latch come from anyway in straight addressing ?

R

On Tue, 11 Sep 2007 10:37:30 -0000, richard.melikson@gmail.com wrote:

><snip>
>> That's a big question.  Start with the above and see if that helps.
>
>I didn't mean it as a big question. It's quite simple, really - when
>was the last time *you* Jonathan (and other readers interested in
>sharing) used Gray codes in digital design, either in coding logic or
>software ?

2005, for an EEPROM counter.

Jon

>> Why can't the values just be synchronized (double FF) between the
>> domains with a handshake and solve the problem of glitches in the
>> first place ?
>
>They could be, but that would add latencies to the FIFO that
>are best avoided. ie why compromise the operation, when a Gray
>Code design will work better ?

It's more complicated than that.  Running a multi-bit value
through a synchronizer doesn't work if more than one bit changes.
Some of the bits might get there in time when others don't.

If the data changes from 000 to 111, you might see
001, 010, 100, 011, 101, or 110 for a cycle before
it settles.  (That's assuming it was stable at 000
for several cycles and then stays at 111 for several
cycles.)

-- 
These are my opinions, not necessarily my employer's.  I hate spam.

> >They could be, but that would add latencies to the FIFO that
> >are best avoided. ie why compromise the operation, when a Gray
> >Code design will work better ?
>
> It's more complicated than that.  Running a multi-bit value
> through a synchronizer doesn't work if more than one bit changes.
> Some of the bits might get there in time when others don't.
>
> If the data changes from 000 to 111, you might see
> 001, 010, 100, 011, 101, or 110 for a cycle before
> it settles.  (That's assuming it was stable at 000
> for several cycles and then stays at 111 for several
> cycles.)

Ah - this is a most important point, I think. So, you imply that if I
want to share a counter between two clock domains, I can so a simple
double FF synchronization on it if it's encoded in Gray, whilst for a
normal counter I need a handshake protocol with a synchronized control
signal ?
I think I understand how this can make things faster.

R