Uses of Gray code in digital design

An internal address counter for access to the EEPROM ? Why did you choose Gray encoding in this case ?

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

My most recent use: a combinatorial divide-by-8 counter for a clock that might be too fast to go through Flops but able to have predictable timing through three LUTs. I used it as a prescaler for the output of a ring oscillator.

Three 4-input LUTs take in one clock and the three values to pass the clock - normal or inverted as necessary - as the active "count up" bit. It was a nifty little application.

- John_H

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

J> 2005, for an EEPROM counter.

Richard wrote:

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.

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

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

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

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

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)

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.

Most for FPGAs like one-hot encoding.

-- glen

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

--
 Chuck F (cbfalconer at maineline dot net)
   Available for consulting/temporary embedded and systems.

That depends on the application. When a clock *is* available, the state encoding style is irrelevant to timing or function.

-- Mike Treseler

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

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

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.

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

Page mode would be a problem. ;)

Jon