Uses of Gray code in digital design

richard.melikson@gmail.com wrote:
>>> 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.
> 

It's even better - with the Gray code, you don't need the FF 
synchronisation at all, as long as you are stepping up or down through 
the codes (it's a different matter for step machines that jump steps). 
The point is that whenever you look at the code as it passes from one 
value to the next, it is either in the old state or in the new state - 
there is nothing in between.  With a binary counter, you could see 
intermediary stages as different bits toggle with different delays. 
Synchronisation FF's have nothing to do with it.

Andy wrote:
> On Sep 11, 4:42 am, David Brown <da...@westcontrol.removethisbit.com>
> wrote:
>> Jonathan Kirwan wrote:
>>
>> <snip huge and informative post>
>>
>> I hope you copied-and-pasted a lot of that post rather than writing it
>> all yourself!
>>
>> I hadn't thought about using Gray code for communication, but it's a
>> really smart idea.  Supposing you want to send 10-bit data within a
>> 16-bit message.  All you need to do to send data "x" is to calculate:
>>
>> y = toGray16(x << 6)
>>
>> At the other side, you receive "z".  To get your best estimate for the
>> original "x", you calculate:
>>
>> x' = (fromGray16(z) + 0x1f) >> 6
>> xe = z - (x1' << 6)
>>
>> xe is the Hamming distance between the sent data (assuming the
>> corruption is not too bad, obviously) and the received data, while x' is
>> the nearest correct code.
>>
>> mvh.,
>>
>> David
> 
> Does that work?  While adjacent binary codes are always represented by
> single bit differences in gray, the converse is not true; single bit
> changes in gray are not necessarily adjacent codes in binary.
> 

No, it does not work :-(
Perhaps something can be made out of the idea, but it's back to the 
drawing board.

> Also, n-count changes in binary code are not necessarily represented
> by n-bit changes in gray.
> 
> Andy
> 

Paul Keinanen wrote:
> On Tue, 11 Sep 2007 20:03:33 -0700, Mike Treseler
> <mike_treseler@comcast.net> wrote:
> 
> 
>>CBFalconer wrote:
>>
>>
>>>'synchronously' requires a clock driving everything.  Not avail.
>>
>>That depends on the application.
>>When a clock *is* available, the
>>state encoding style is irrelevant
>>to timing or function.
> 
> 
> If you have a counter, you usually feed it with a clock :-)
> 
> A ripple counter (7490 style) is more or less useless for decoding
> states at high speeds, since the decoding can be done only after the
> sum of the flip-flop propagation delays. 
> 
> In synchronous counter (such as 74196), each flip-flop "knows" in
> advance, if it should change state at the next count pulse, thus the
> delay is only as large as the propagation delay of a single FF. Some
> gating is required to decide, if the FF should change state at the
> next count pulse or not.

It gets murkier when you have to allow for finite routing delays,
and in the newest FPGAs routing delays can be significant.


> Since gating is required anyway for the counting, I don't see the
> point of using a Gray sequence instead of a simple 1-2-4-8 weighting.
> 
> For short sequences, the Johnston counter would be ideal, if you need
> to decode all states.

Yes, Johnson counters can be useful, and can decode glitch-free as well 
as Gray counters.
The simpler D-FF structure of Johnson counters means they
can often count faster than other counters. - but they need more
registers for a given modulus, so it's a trade-off.

-jg

CBFalconer wrote:

> You didn't leave much of a quote.

Sorry. The OP said:

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

> Assuming this has to do with
> Gray codes, there is no reason to assume the source can be clocked,
> in fact this is relatively rare.  In general source values change
> when they are in the appropriate mood.  Now deal with the result.

My points for the OP were that
1.Most state machines used
in practical controllers are synchronous
and

2. Their state graphs are not a simple
loop like a counter. This makes it difficult
to maintain a Gray encoding for all transitions in any case.

      -- Mike

David Brown wrote:

> It's even better - with the Gray code, you don't need the FF
> synchronisation at all, as long as you are stepping up or down through
> the codes (it's a different matter for step machines that jump steps).

IMHO I'd be very wary of this statement (and would be interested to hear
how others see it). I remember looking at metastability tests on
flip-flops many years ago and there are two issues here:
1) Catching / not catching a state change
2) Lengthening of the FF switching time when set-up/hold times are not met

Particularily with 2), the tests I observed back then showed a factor of
three to five times against the specified switching time when
set-up/hold times are met. The higher the capacitive load on the FF the
worse it got.

So, if you have your two gray counters (one being asynchronous) and feed
them to a comparator which then goes to a Full/Empty flag FF, the timing
of the path asynch_gray_counter -> comparator -> full_or_empty_ff will
not be what your timing analysis said if you actually hit the
meta-stability window. If you are running at max speed, this may well
mean that the set-up/hold times on the full/empty FF input are not met,
effectively meaning that the output of this FF now becomes meta-stable.

IMHO, the advantage of the Gray-coding is that you are guaranteed not to
observe any intermediate switching states (i.e. point 1 above is
addressed) but I would still synchronise the output to be sure that
metastability is not just propogated down the line and eventually
causing problems at some unexpected circuit node.

Regards,
Charles

Charles, you are right.
The identity comparison of two Gray counters avoids accidental
glitches, but does not avoid the inherent asynchronous nature of the
event. The design still has to resolve (better: live with) the
matastability issue.
Luckily, modern flip-flops resolve metastability pretty fast, at least
statistically.
XAPP094 is a Xilinx app note that quantifies the results for
Virtex2Pro FPGAs.
Peter Alfke

On Sep 12, 9:13 am, "Charles, NG" <site_blackh...@trellisys.ie> wrote:
> David Brown wrote:
> > It's even better - with the Gray code, you don't need the FF
> > synchronisation at all, as long as you are stepping up or down through
> > the codes (it's a different matter for step machines that jump steps).
>
> IMHO I'd be very wary of this statement (and would be interested to hear
> how others see it). I remember looking at metastability tests on
> flip-flops many years ago and there are two issues here:
> 1) Catching / not catching a state change
> 2) Lengthening of the FF switching time when set-up/hold times are not met
>
> Particularily with 2), the tests I observed back then showed a factor of
> three to five times against the specified switching time when
> set-up/hold times are met. The higher the capacitive load on the FF the
> worse it got.
>
> So, if you have your two gray counters (one being asynchronous) and feed
> them to a comparator which then goes to a Full/Empty flag FF, the timing
> of the path asynch_gray_counter -> comparator -> full_or_empty_ff will
> not be what your timing analysis said if you actually hit the
> meta-stability window. If you are running at max speed, this may well
> mean that the set-up/hold times on the full/empty FF input are not met,
> effectively meaning that the output of this FF now becomes meta-stable.
>
> IMHO, the advantage of the Gray-coding is that you are guaranteed not to
> observe any intermediate switching states (i.e. point 1 above is
> addressed) but I would still synchronise the output to be sure that
> metastability is not just propogated down the line and eventually
> causing problems at some unexpected circuit node.
>
> Regards,
> Charles

I wrote:
> If the EEPROM bytes start as 0x00, and individual bits can be changed from
> zero to ones without having to erase the byte first, instead of incrementing
> the EEPROM byte you would use a progression like 00->01->03->07->0f etc.,
> so you get eight "increments" of a byte value with no erase, and in doing so
> only use up one unit of write endurance for that byte.

dick <dick_12345678@hotmail.com> writes:
> don't use binary coding but unary coding.

That's what I wrote, though for a large counter, you don't want to exclusively
use unary, because it will require too much space.  A combination of unary
code at the byte level with a gray code addressing scheme works quite nicely.

>glitches. The typical write operation is:
>
>1. change address.

I think you also need something like:
  1.5: Wait for new address to settle

>2. toggle write signal to write data.


>Gray code avoids glitches in a different way. It avoids glitches by
>ensuring that only a single bit changes when the address change. This
>allows us to do everything in a single clock cycle:
>
>(write signal is always set)
>1. change address and  write data.

Gray code makes sure you only write something to either the
old address or the new address.  You also have to make sure
that the new data doesn't get written to the old address.
(or probably worse, part of the new data gets written
on top of the old data)

How about
  1: change address
  2: wait for address to settle and data hold time
  3: write new data

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

Charles, NG wrote:
> David Brown wrote:
> 
>> It's even better - with the Gray code, you don't need the FF
>> synchronisation at all, as long as you are stepping up or down through
>> the codes (it's a different matter for step machines that jump steps).
> 
> IMHO I'd be very wary of this statement (and would be interested to hear
> how others see it). I remember looking at metastability tests on
> flip-flops many years ago and there are two issues here:
> 1) Catching / not catching a state change
> 2) Lengthening of the FF switching time when set-up/hold times are not met
> 
> Particularily with 2), the tests I observed back then showed a factor of
> three to five times against the specified switching time when
> set-up/hold times are met. The higher the capacitive load on the FF the
> worse it got.
> 
> So, if you have your two gray counters (one being asynchronous) and feed
> them to a comparator which then goes to a Full/Empty flag FF, the timing
> of the path asynch_gray_counter -> comparator -> full_or_empty_ff will
> not be what your timing analysis said if you actually hit the
> meta-stability window. If you are running at max speed, this may well
> mean that the set-up/hold times on the full/empty FF input are not met,
> effectively meaning that the output of this FF now becomes meta-stable.
> 
> IMHO, the advantage of the Gray-coding is that you are guaranteed not to
> observe any intermediate switching states (i.e. point 1 above is
> addressed) but I would still synchronise the output to be sure that
> metastability is not just propogated down the line and eventually
> causing problems at some unexpected circuit node.
> 
> Regards,
> Charles

Agreed - if you are looking at the gray-coded values from a different 
clock domain, then the signals are asynchronous and must be treated as 
such (with meta-stability handling as required).  Someone also pointed 
out that your binary-to-gray coder may also be subject to glitches which 
could pass through to the output - it must be designed carefully.  All 
in all, I'd prefer to let the development tools produce things like 
FIFOs - they are going to be smaller, faster and safer than if I tried 
to hand code them myself.  But it's nice to know how they work.

mvh.,

David

I ran a few posts on Gray codes in my blog - http://asicdigitaldesign.wordpress.com
.

you can find some efficient ways to build a direct Gray code counter
here (in 3 parts):
http://asicdigitaldesign.wordpress.com/2007/05/10/counting-in-gray/
http://asicdigitaldesign.wordpress.com/2007/05/13/counting-in-gray-part-ii-observations/
http://asicdigitaldesign.wordpress.com/2007/05/14/counting-in-gray-part-iii-putting-everything-together/

As for your original FSM related question - you might find this post
interesting:
http://asicdigitaldesign.wordpress.com/2007/09/04/fsm-state-encoding-more-switching-reduction-tips/

ND