Uses of Gray code in digital design

On Tue, 11 Sep 2007 05:26:23 -0700, richard.melikson@gmail.com wrote:

>> >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.
>
>An internal address counter for access to the EEPROM ? Why did you
>choose Gray encoding in this case ?

Since you seem pretty savvy about things, think about implementing an
incrementing or decrementing counter stored in EEPROM and how to
reduce the wear on some fixed locations you may be using (one could
always use another scheme where things are in constant motion, as
well.)  As I've pointed out earlier, there are quite a number of
possible Gray code sequences available for 16 bits -- in fact, with
just 5 bits instead of 16, we have 187,499,638,240 of them.  I have no
idea what the figure is for 16 bits, but "many" will have to suffice.

In the 2-byte, 16-bit case, residing at a fixed EEPROM address, you
may want to find a particular gray code sequence where it is true
that, on average over successive partial subranges, half the bit
changes will occur in one of the bytes and half of them in the other.

In base 2 binary notation, you already know that the least significant
bit changes on every increment.  So that means the low order byte is
always written on every increment or decrement.  Which means that byte
is your weak link in the chain and will determine the lifetime of your
counter.

But with Gray coding, and the selection of a 'good' sequence (which is
not the usual one, by the way), you can pretty nicely spread out the
updates 50/50 between the two bytes -- over short ranges as well as
over the total count range -- doubling the expected endurance by a
rather modest software change.  By distributing the bits over more
bytes, you can achieve much better.

Does that help?

Jon

richard.melikson@gmail.com wrote:

>>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 ?

In the days when ripple counters were more popular, it was
more of a problem.   In a ripple counter, like the TTL 7490,
each bit changes on the falling edge of the next lower bit.

(snip)
> 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 ?

Even with a synchronous counter, the bits don't change at exactly
the same time.  Even if they did, differences in wire length or
propagation velocity would cause them to be different when
they got to the first latch.

>>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 ?

Most for FPGAs like one-hot encoding.

-- glen

Mike Treseler wrote:
> richard.melikson@gmail.com wrote:
> 
>> So why do all synthesis tools propose "gray code" as one of the
>> encodings of state machines ?
> 
> I expect that the original author got it wrong and others copied
> the idea. A state is normally decoded synchronously and the the
> coding scheme makes no functional difference.

'synchronously' requires a clock driving everything.  Not avail.

-- 
 Chuck F (cbfalconer at maineline dot net)
   Available for consulting/temporary embedded and systems.
   <http://cbfalconer.home.att.net>



-- 
Posted via a free Usenet account from http://www.teranews.com

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.

  -- Mike Treseler

richard.melikson@gmail.com wrote:
> Hi Peter, thanks for replying. My comments below...
>>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 ?

Suppose you want to create a Gray counter ? - A Gray encoded state 
machine is one such way, after all, a counter is a simple state machine.

Also, even if you start with a Sync Binary counter, routing
delay deltas can still cause decoder glitches, so if you want
reliable glitch free decodes, then use a Gray counter.

-jg

On Sep 11, 8:28 pm, Jim Granville <no.s...@designtools.maps.co.nz>
wrote:
> richard.melik...@gmail.com wrote:
> > Hi Peter, thanks for replying. My comments below...
> >>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 ?
>
> Suppose you want to create a Gray counter ? - A Gray encoded state
> machine is one such way, after all, a counter is a simple state machine.
>
> Also, even if you start with a Sync Binary counter, routing
> delay deltas can still cause decoder glitches, so if you want
> reliable glitch free decodes, then use a Gray counter.
>
> -jg

So here's one caveat on Gray coding.  Multiple times, Ive seen
designers take the output of
a binary counter, feed it into a combinatrorial Gray encoder, then
treat the output as if
only one bit will change at a time.  Yes, after a settling time, the
final output will be a Gray
code, but this arrangement still has decoding glitches.

John Providenza

Jonathan Kirwan wrote:
<snip>
> In base 2 binary notation, you already know that the least significant
> bit changes on every increment.  So that means the low order byte is
> always written on every increment or decrement.  Which means that byte
> is your weak link in the chain and will determine the lifetime of your
> counter.
> 
> But with Gray coding, and the selection of a 'good' sequence (which is
> not the usual one, by the way), you can pretty nicely spread out the
> updates 50/50 between the two bytes -- over short ranges as well as
> over the total count range -- doubling the expected endurance by a
> rather modest software change.  

That's true, if you assume they BYTE write, and not PAGE write anyway :)

I see the Atmel Serial EE's only spec
Endurance 5.0V, 25&#4294967295;C, Page Mode >1M

which suggests everything is page mode, and even if only one byte
is loaded, the device reads/erase/repgms a whole page set.

-jg

Mike Treseler 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.

You didn't leave much of a quote.  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.

-- 
 Chuck F (cbfalconer at maineline dot net)
   Available for consulting/temporary embedded and systems.
   <http://cbfalconer.home.att.net>



-- 
Posted via a free Usenet account from http://www.teranews.com

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.

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.

Paul

On Wed, 12 Sep 2007 16:21:54 +1200, Jim Granville
<no.spam@designtools.maps.co.nz> wrote:

>Jonathan Kirwan wrote:
><snip>
>> In base 2 binary notation, you already know that the least significant
>> bit changes on every increment.  So that means the low order byte is
>> always written on every increment or decrement.  Which means that byte
>> is your weak link in the chain and will determine the lifetime of your
>> counter.
>> 
>> But with Gray coding, and the selection of a 'good' sequence (which is
>> not the usual one, by the way), you can pretty nicely spread out the
>> updates 50/50 between the two bytes -- over short ranges as well as
>> over the total count range -- doubling the expected endurance by a
>> rather modest software change.  
>
>That's true, if you assume they BYTE write, and not PAGE write anyway :)
>
>I see the Atmel Serial EE's only spec
>Endurance 5.0V, 25&#4294967295;C, Page Mode >1M
>
>which suggests everything is page mode, and even if only one byte
>is loaded, the device reads/erase/repgms a whole page set.

Page mode would be a problem.  ;)

Jon