Uses of Gray code in digital design

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

What does this mean ? How is Gray better than regular binary when you
need to decode the states ?

R

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

R

<richard.melikson@gmail.com> wrote in message 
news:1189507163.594238.209960@r29g2000hsg.googlegroups.com...
>> 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

You use the change in address bit to 'register' the data into the
memory rather than a write strobe.

You can then write once per master clock cycle instead of having to have
two cycles the first with the write strobe low, the next high (typically).

I thought about trying this on an external SRAM for a project a couple
of years ago but couldn't find any data sheets confirming this is a
valid way of writing data to an SRAM and did't have time to experiment
to test it.


Nial

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.

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

Andy

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

Jonathan Kirwan wrote:
> 2005, for an EEPROM counter.
>
Richard wrote:
> An internal address counter for access to the EEPROM ? Why did you
> choose Gray encoding in this case ?

Suppose for the sake of argument that you have an EEPROM composed of
individually writeable bits, and each bit has a limited endurance of
10,000 writes.  If you want to store a 20-bit count in the EEPROM (e.g., a
page counter for a laser printer, an odometer for a car, etc.), almost every
increment will have to write multiple bits, and the least significant bit
will be rewritten at every increment, so your EEPROM will wear out after
10,000 increments.  By using gray code instead, every increment will affect
exactly one bit, and the EEPROM will last for 200,000 increments.

That's oversimilified because EEPROM erase (and thus the write endurance)
is usually at the byte level, rather than the bit level.  You could
either store one bit per EEPROM byte, to get the behavior I described above,
or adopt a scheme in which you increment entire bytes, but choose which
byte to increment in a grey code addressing sequence.

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.

I independently devised such schemes for a product developed in 1987,
but I'm sure that many other people have done similar things before and
since.  It wouldn't surprise me if some have been patented.

Eric

Eric Smith wrote:
> Richard Melikson 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 ?
>
> Jonathan Kirwan wrote:
> > 2005, for an EEPROM counter.
> >
> Richard wrote:
> > An internal address counter for access to the EEPROM ? Why did you
> > choose Gray encoding in this case ?
>
> Suppose for the sake of argument that you have an EEPROM composed of
> individually writeable bits, and each bit has a limited endurance of
> 10,000 writes.  If you want to store a 20-bit count in the EEPROM (e.g., a
> page counter for a laser printer, an odometer for a car, etc.), almost every
> increment will have to write multiple bits, and the least significant bit
> will be rewritten at every increment, so your EEPROM will wear out after
> 10,000 increments.  By using gray code instead, every increment will affect
> exactly one bit, and the EEPROM will last for 200,000 increments.
>
> That's oversimilified because EEPROM erase (and thus the write endurance)
> is usually at the byte level, rather than the bit level.  You could
> either store one bit per EEPROM byte, to get the behavior I described above,
> or adopt a scheme in which you increment entire bytes, but choose which
> byte to increment in a grey code addressing sequence.
>
> 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.
>
> I independently devised such schemes for a product developed in 1987,
> but I'm sure that many other people have done similar things before and
> since.  It wouldn't surprise me if some have been patented.
>
> Eric

don't use binary coding but unary coding.

We use unary coding when we discuss TM.

0->no 1
1->one 1
2->two 1s
3->three 1s
...
10000->10 thousand 1s


I remember there is a Chinese joke telling the story of unary coding.

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.

         -- Mike Treseler

richard.melikson@gmail.com wrote:

> How is Gray better than regular binary when you
> need to decode the states ?

Only if the decoding has to be asynchronous.

Note that it can take extra state bits
to keep all the transitions gray so
even in the asynchronous case there
may be no area savings.

       -- Mike Treseler

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 ?

All the same beast.  When multiple bits can change at once, the
precise moment of reading is highly critical.  When only one bit
can change at a time, the maximum error resulting from the moment
of reading is 1 unit.  If that bit oscillates on/off then the
result will oscillate by 1 unit, while for a binary code it
probably oscillates by 2**n units.  This is why rotary position
decoders are always handled in Gray code, for example.  The same is
advisable for an a/d converter, avoiding generating non-existant
large spikes.

-- 
 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 Sep 11, 6:39 pm, richard.melik...@gmail.com wrote:
> > 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 ?
>

Normally, reading from and writing to memory requires a "clock
signal". The clock signal is used to control a latch. The purpose of
this latch is to allow you to sample data only when the signal is
stable. In other words the latch is there to ignore data when the
address changes.

Why you ask? Because when you change the address, not all bits of the
address arrive at the same time. There are many reasons for why bits
arrive at different times -- some signals need to travel on longer
paths, some paths have thicker wires, some gates have imperfections
causing delays etc.

Take for example reding two consecutive memory locations: 5 and 6. The
change from 5 to 6 is:

00000101
00000110

But because of unequal arrival times of the electrical signals, in
reality what actually happens may very well be:

00000101
00000111  <-- for a very, very short time
00000110

This is what's called a glitch. This would obviously generate errors
on the output. So what we usually do is we use a latch to ignore
glitches. The typical write operation is:

1. change address.
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.