On Sat, 18 Jun 2005 15:49:40 +0200, David Brown
<david@westcontrol.removethisbit.com> wrote:

>Jonathan Kirwan wrote:
>> On Fri, 17 Jun 2005 16:04:16 +0200, Anton Erasmus
>> <nobody@spam.prevent.net> wrote:
>> 
>> 
>>>>If you can make your hardware safe for a single byte write, you can make 
>>>>it safe for a two byte write (or whatever length of counter you want), 
>>>>elimating the complexity of gray codes.  I'd still avoid a system that 
>>>>relied on running after power has been turned off - journaling is easy 
>>>>to do if you think it through carefully, and far more flexible (for 
>>>>example, you can group a number of changes).  If you have lots of eeprom 
>>>>space and want to spread your wear-and-tear evenly, that's perfectly 
>>>>possible too (add a version number to your data).
>>>
>>>The gray code method is only suitable for incrementing/decrementing a
>>>counter in EEPROM. If one wants to save other types of data reliably
>>>to EEPROM, then other methods such as you describe are in order.
>>>For just a counter the gray code method is simple and easy to code as
>>>well as reliable.
>> 
>> 
>> Interesting in the case of EEPROM non-volatile storage, where the
>> concern may be at byte-resolution for wear-leveling, is the ability to
>> distribute the changes in such a way that incrementing the count
>> alternates evenly through the available byte changes.
>> 
>> Since any gray code sequence is equivalent to any one of the possible
>> Hamiltonian walks of an N-dim hypercube, where each vertex is visited
>> exactly once and all vertices are eventually visited, it's possible to
>> assign the codes so that this occurs exactly this way.  However, I
>> haven't worked out an algorithmic approach for it in the case of, for
>> example, a 16-dim space (two bytes.)  I wonder if someone has.
>
>What you would be looking for here is a gray code sequence in which an 
>average of half the bit changes occur in one byte, and half in the 
>other.  I can't think off hand of a pattern that does this (or even 
>whether such a pattern could exist),

Oh, I think at least one approach is possible to work out.  You can
note that in the case of only a 2-bit gray code, you have two changes
in bit 0 and two changes in bit 1, before returning to the start of
the cycle.  So, 2+2 which provides your 4 total symbols in 2 bits.  In
the case of 3-bit gray codes (there are 96 possible such gray codes
that fully return back to the starting symbol and 48 more possible
gray codes that 'saturate' and do not return to the starting symbol
but dead-end, instead), you will have something like the pattern of
2+2+4, which gives your 8 symbols.  In the case of 4-bit gray codes,
it is a pattern like 2+2+4+8.  And so on.

So one thought that arrives quickly from examining this pattern is
that if the least significant bit (which, in the commonly used gray
code form, changes fastest) placed into one byte and all the other
bits placed into the other byte (up to 9 bit gray code), then the
changes will be distributed evenly between the two bytes.

It's wasteful, I suppose, of bits in the first byte.  But it does seem
to work out exactly in every case.

>but here's a simple idea that would 
>get very close, and be simple to work with - consider a standard 16-bit 
>gray code, rotated one bit to the right (so that the LSB gets moved to 
>the MSB).  In standard gray code, every other step changes the LSB, with 
>alternate steps changing other bits with half the frequency for each bit 
>away from the LSB (i.e., in 2**16 steps, bit 0 changes 2**15 times, bit 
>1 changes 2**14 times, etc.).  In this rotated code, the frequencies are 
>the same but the bit numbers are changed, so that bit 15 changes 2**15, 
>while bits 0 to 7 change 2**14 .. 2**7 times.  Overall, the "low" byte 
>changes 0x7f80 times, and the "high" byte changes 0x8080 times, which is 
>pretty close to optimal.

Yes, I'd considered that, too.  Since I was looking at the patterns
as:

2:    2+2
3:    2+2+4
4:    2+2+4+8
5:    2+2+4+8+16
6:    2+2+4+8+16+32
7:    2+2+4+8+16+32+64
8:    2+2+4+8+16+32+64+128
...
16:   2+2+4+8+16+32+64+128+256+512+1024+2048+4096+8192+16384+32768

Rotating the case for 16 produces:

16:   32768+2+2+4+8+16+32+64+128+256+512+1024+2048+4096+8192+16384
      ---------------------- -------------------------------------

Which is exactly as you said, above.

This does have the effect of not wasting any bits and roughly
distributing the changes.  And when I wrote, yesterday, I had already
thought it out this far.

However, it wasn't "perfect" in the sense of exactly distributing the
changes and I was wondering if there was a way of choosing a
particular Hamiltonian walk on the hypercube in order to achieve
"perfect use" while at the same time using every bit, too.  I haven't
figured that out.

Thanks for the response!!

Jon

Jonathan Kirwan wrote:
> On Fri, 17 Jun 2005 16:04:16 +0200, Anton Erasmus
> <nobody@spam.prevent.net> wrote:
> 
> 
>>>If you can make your hardware safe for a single byte write, you can make 
>>>it safe for a two byte write (or whatever length of counter you want), 
>>>elimating the complexity of gray codes.  I'd still avoid a system that 
>>>relied on running after power has been turned off - journaling is easy 
>>>to do if you think it through carefully, and far more flexible (for 
>>>example, you can group a number of changes).  If you have lots of eeprom 
>>>space and want to spread your wear-and-tear evenly, that's perfectly 
>>>possible too (add a version number to your data).
>>
>>The gray code method is only suitable for incrementing/decrementing a
>>counter in EEPROM. If one wants to save other types of data reliably
>>to EEPROM, then other methods such as you describe are in order.
>>For just a counter the gray code method is simple and easy to code as
>>well as reliable.
> 
> 
> Interesting in the case of EEPROM non-volatile storage, where the
> concern may be at byte-resolution for wear-leveling, is the ability to
> distribute the changes in such a way that incrementing the count
> alternates evenly through the available byte changes.
> 
> Since any gray code sequence is equivalent to any one of the possible
> Hamiltonian walks of an N-dim hypercube, where each vertex is visited
> exactly once and all vertices are eventually visited, it's possible to
> assign the codes so that this occurs exactly this way.  However, I
> haven't worked out an algorithmic approach for it in the case of, for
> example, a 16-dim space (two bytes.)  I wonder if someone has.
> 
> Jon

What you would be looking for here is a gray code sequence in which an 
average of half the bit changes occur in one byte, and half in the 
other.  I can't think off hand of a pattern that does this (or even 
whether such a pattern could exist), but here's a simple idea that would 
get very close, and be simple to work with - consider a standard 16-bit 
gray code, rotated one bit to the right (so that the LSB gets moved to 
the MSB).  In standard gray code, every other step changes the LSB, with 
alternate steps changing other bits with half the frequency for each bit 
away from the LSB (i.e., in 2**16 steps, bit 0 changes 2**15 times, bit 
1 changes 2**14 times, etc.).  In this rotated code, the frequencies are 
the same but the bit numbers are changed, so that bit 15 changes 2**15, 
while bits 0 to 7 change 2**14 .. 2**7 times.  Overall, the "low" byte 
changes 0x7f80 times, and the "high" byte changes 0x8080 times, which is 
pretty close to optimal.

mvh.,

David

Anton Erasmus wrote:
> On 17 Jun 2005 15:45:18 -0700, Eric Smith <eric@brouhaha.com> wrote:
> 
> 
>>Anton Erasmus <nobody@spam.prevent.net> writes:
>>
>>>Yes Agreed, but the OP specifically asked about a counter in EEPROM.
>>
>>The problem is that most EEPROMs do a full erase and rewrite of a byte
>>(or sometimes a 16-bit word) whenever you write to that byte, so you're
>>burning the endurance of that entire byte with every write even if you
>>only toggle a single bit in it.  Thus using a Grey code at the byte level
>>in a typical EEPROM won't gain you anything.
>>
>>If I needed to be able to count to ten million using EEPROM rated for
>>one hundred thousand writes, I'd use pairs of bytes to count from 0 to 65535,
>>and as each pair hit the limit I'd move on to the next pair.  This would
>>take 306 bytes of EEPROM.  It's possible to do it with less bytes used,
>>but the algorithm becomes a lot more complex.
>>
> 
> 
> Yes, 
> 
> That is the same way I have implemented a large counter in EEPROM as I
> have described in a previous post.

You _can_ gain a little with modified Gray code, on the wear front.
With Binary, one byte R/W's 65536, and the other 256.

In the most common Gray Code, one of the two LSBs changes every second 
clock, and you have a skewed edge count over the two bytes.
If you shift the storage, so the two quadrature LSBs are in different 
bytes, then those edges ( which dominate ) are evened between the two 
bytes. - so you can halve the peak R/W count.
- you can still rotate onto another byte pair, as detailed above, for 
more wear leveling. The example above acually hits 65% of the 100K,
at 10 Million counts.

  You also only write ONE (alterating) byte, which has small advantages :
* Less hold-up time needed, if you are doing power fail schemes
* SW can exit faster; no need to wait for first one to complete 1/256 times.

-jg

On 17 Jun 2005 15:45:18 -0700, Eric Smith <eric@brouhaha.com> wrote:

>Anton Erasmus <nobody@spam.prevent.net> writes:
>> Yes Agreed, but the OP specifically asked about a counter in EEPROM.
>
>The problem is that most EEPROMs do a full erase and rewrite of a byte
>(or sometimes a 16-bit word) whenever you write to that byte, so you're
>burning the endurance of that entire byte with every write even if you
>only toggle a single bit in it.  Thus using a Grey code at the byte level
>in a typical EEPROM won't gain you anything.
>
>If I needed to be able to count to ten million using EEPROM rated for
>one hundred thousand writes, I'd use pairs of bytes to count from 0 to 65535,
>and as each pair hit the limit I'd move on to the next pair.  This would
>take 306 bytes of EEPROM.  It's possible to do it with less bytes used,
>but the algorithm becomes a lot more complex.
>

Yes, 

That is the same way I have implemented a large counter in EEPROM as I
have described in a previous post.

Regards
  Anton Erasmus

Anton Erasmus <nobody@spam.prevent.net> writes:
> Yes Agreed, but the OP specifically asked about a counter in EEPROM.

The problem is that most EEPROMs do a full erase and rewrite of a byte
(or sometimes a 16-bit word) whenever you write to that byte, so you're
burning the endurance of that entire byte with every write even if you
only toggle a single bit in it.  Thus using a Grey code at the byte level
in a typical EEPROM won't gain you anything.

If I needed to be able to count to ten million using EEPROM rated for
one hundred thousand writes, I'd use pairs of bytes to count from 0 to 65535,
and as each pair hit the limit I'd move on to the next pair.  This would
take 306 bytes of EEPROM.  It's possible to do it with less bytes used,
but the algorithm becomes a lot more complex.

Eric

On Fri, 17 Jun 2005 14:41:42 -0000, Grant Edwards <grante@visi.com>
wrote:

>On 2005-06-17, Anton Erasmus <nobody@spam.prevent.net> wrote:
>
>[Regarding gray code]
>
>>>But, since you can't erase/program a single bit it's mostly
>>>moot.
>>
>> If only a single bit changes, it folows that only a single byte
>> changes. Hence to increment a counter one only has to write one byte
>> no matter how many bits the total counter is. To prevent corruption of
>> the counter one have only to ensure that either the one byte write
>> completes fully or is not performed at all. It is not to difficult to
>> ensure that there is enough time from a "pending power fail" signal
>> until the MCU is reset for an EEPROM write to complete.
>
>If all you ever need to save to EEPROM is counters, then I
>guess it could be useful.  If, however, you have to save to
>EEPROM anything that's not a counter, then you've got to have a
>more general solution for atomic writes to EEPROM.

Yes Agreed, but the OP specifically asked about a counter in EEPROM.

Regards
  Anton Erasmus

On Fri, 17 Jun 2005 16:04:16 +0200, Anton Erasmus
<nobody@spam.prevent.net> wrote:

>>If you can make your hardware safe for a single byte write, you can make 
>>it safe for a two byte write (or whatever length of counter you want), 
>>elimating the complexity of gray codes.  I'd still avoid a system that 
>>relied on running after power has been turned off - journaling is easy 
>>to do if you think it through carefully, and far more flexible (for 
>>example, you can group a number of changes).  If you have lots of eeprom 
>>space and want to spread your wear-and-tear evenly, that's perfectly 
>>possible too (add a version number to your data).
>
>The gray code method is only suitable for incrementing/decrementing a
>counter in EEPROM. If one wants to save other types of data reliably
>to EEPROM, then other methods such as you describe are in order.
>For just a counter the gray code method is simple and easy to code as
>well as reliable.

Interesting in the case of EEPROM non-volatile storage, where the
concern may be at byte-resolution for wear-leveling, is the ability to
distribute the changes in such a way that incrementing the count
alternates evenly through the available byte changes.

Since any gray code sequence is equivalent to any one of the possible
Hamiltonian walks of an N-dim hypercube, where each vertex is visited
exactly once and all vertices are eventually visited, it's possible to
assign the codes so that this occurs exactly this way.  However, I
haven't worked out an algorithmic approach for it in the case of, for
example, a 16-dim space (two bytes.)  I wonder if someone has.

Jon

On 2005-06-17, Anton Erasmus <nobody@spam.prevent.net> wrote:

[Regarding gray code]

>>But, since you can't erase/program a single bit it's mostly
>>moot.
>
> If only a single bit changes, it folows that only a single byte
> changes. Hence to increment a counter one only has to write one byte
> no matter how many bits the total counter is. To prevent corruption of
> the counter one have only to ensure that either the one byte write
> completes fully or is not performed at all. It is not to difficult to
> ensure that there is enough time from a "pending power fail" signal
> until the MCU is reset for an EEPROM write to complete.

If all you ever need to save to EEPROM is counters, then I
guess it could be useful.  If, however, you have to save to
EEPROM anything that's not a counter, then you've got to have a
more general solution for atomic writes to EEPROM.

-- 
Grant Edwards                   grante             Yow!  FEELINGS are
                                  at               cascading over me!!!
                               visi.com            

On Fri, 17 Jun 2005 14:50:35 +0200, David Brown
<david@westcontrol.removethisbit.com> wrote:

>Anton Erasmus wrote:
>> On Fri, 17 Jun 2005 09:30:29 +0200, David Brown
>> <david@westcontrol.removethisbit.com> wrote:
>> 
>> 
>>>Anton Erasmus wrote:
>>>
>>>>On Fri, 17 Jun 2005 07:27:03 +1200, Jim Granville
>>>><no.spam@designtools.co.nz> wrote:
>>>>
>>>>
>>>>
>>>>>Anton Erasmus wrote:
>>>>>
>>>>>
>>>>>>>One solution may be to use checksum on all block of data, and
>>>>>>>always recalculate the new checksum after each parameter change.If
>>>>>>>the checksum is not OK I can clear all parameters.I don't like this
>>>>>>>solution because in case of one error I should clear all
>>>>>>>the list of failures.
>>>>>>>Is there any other solution or suggestion how to solve this problem?
>>>>>>
>>>>>>
>>>>>>Use Gray Code for the counters. Only one bit changes between succesive
>>>>>>counts, which of course means only one byte changes. Make sure that if
>>>>>>there is a power failure, you have enough power to at least complete
>>>>>>any write you are busy with. That way if power fails, you either have
>>>>>>incremented the counter, or you have missed only one count.
>>>>>
>>>>>Sounds fine, but what actually happens in the EEPROM update process,
>>>>>is the buried EE state engine first erases the byte (or page) and then
>>>>>replaces it with the new value(s).
>>>>>Some have Page schemes, but allow single byte replace - that just 
>>>>>means they ready the page, XOR it with the new info, and write the whole 
>>>>>page back.
>>>>>Thus, even with Gray code, there are finite times, where you have
>>>>>[OldValue][Erasing to 0FFH][0FFH][Writing NewValueZeroes][NewValue]
>>>>
>>>>
>>>>That is why I suggested that there must be enough capacitance to allow
>>>>any write that has started to complete. Many external brownout
>>>>detectors has a "power-fail" alarm pin that activates at a higher
>>>>voltage than the reset. This pin can be used to make sure that a write
>>>>is not started just before a power fail.
>>>>
>>>>[Snipped]
>>>>
>>>
>>>Gray code here provides no possible benefit, since the data is not 
>>>updated a bit at a time.  Gray code is important when sampling multi-bit 
>>>data in different clock domains (such as for absolute position encoders, 
>>>or counters in FIFOs), but gives you little (avoiding the occasional 
>>>write of the high byte of your 16-bit counter) for the extra headaches 
>>>here.  If your power-fail alarm and your capacitor charges are 
>>>sufficient to ensure that power-fail will never stop in the middle of a 
>>>write, then just store the counters directly.  Of course, it relying on 
>>>such a system would be risky if it is not clearly over-dimensioned, 
>>>especially when there are such simple ways of ensuring reliability 
>>>without it.
>> 
>> 
>> I disagree. Using gray code when incrementing/decrementing a counter
>> in EEPROM ensures that one need to worry only about one byte at a
>> time. (Only one bit changing implies that only one byte changes) One
>> then only has to ensure that the EEPROM write is not started just
>> before a power fail, and if the power fails just after a write has
>> started, that there is enough reserve power for the one byte write to
>> finish. Using the appropriate external browout detector, makes this
>> simple and reliable.
>> One can also put the Gray count value in the EEPROM such that one
>> EEPROM byte represents a single bit. Again because only one bit
>> changes, one has to worry only about updating one byte per count.
>> Even if the underlying mechanism erases a page, and reprograms it,
>> there is still a maximum time that it takes to do this, and one must
>> just ensure that if a write has started, that the MCU stays alive for
>> this time before going down.
>> 
>> Regards
>>   Anton Erasmus
>
>If you can make your hardware safe for a single byte write, you can make 
>it safe for a two byte write (or whatever length of counter you want), 
>elimating the complexity of gray codes.  I'd still avoid a system that 
>relied on running after power has been turned off - journaling is easy 
>to do if you think it through carefully, and far more flexible (for 
>example, you can group a number of changes).  If you have lots of eeprom 
>space and want to spread your wear-and-tear evenly, that's perfectly 
>possible too (add a version number to your data).

The gray code method is only suitable for incrementing/decrementing a
counter in EEPROM. If one wants to save other types of data reliably
to EEPROM, then other methods such as you describe are in order.
For just a counter the gray code method is simple and easy to code as
well as reliable.

Regards
  Anton  Erasmus

Anton Erasmus wrote:
> On Fri, 17 Jun 2005 09:30:29 +0200, David Brown
> <david@westcontrol.removethisbit.com> wrote:
> 
> 
>>Anton Erasmus wrote:
>>
>>>On Fri, 17 Jun 2005 07:27:03 +1200, Jim Granville
>>><no.spam@designtools.co.nz> wrote:
>>>
>>>
>>>
>>>>Anton Erasmus wrote:
>>>>
>>>>
>>>>>>One solution may be to use checksum on all block of data, and
>>>>>>always recalculate the new checksum after each parameter change.If
>>>>>>the checksum is not OK I can clear all parameters.I don't like this
>>>>>>solution because in case of one error I should clear all
>>>>>>the list of failures.
>>>>>>Is there any other solution or suggestion how to solve this problem?
>>>>>
>>>>>
>>>>>Use Gray Code for the counters. Only one bit changes between succesive
>>>>>counts, which of course means only one byte changes. Make sure that if
>>>>>there is a power failure, you have enough power to at least complete
>>>>>any write you are busy with. That way if power fails, you either have
>>>>>incremented the counter, or you have missed only one count.
>>>>
>>>>Sounds fine, but what actually happens in the EEPROM update process,
>>>>is the buried EE state engine first erases the byte (or page) and then
>>>>replaces it with the new value(s).
>>>>Some have Page schemes, but allow single byte replace - that just 
>>>>means they ready the page, XOR it with the new info, and write the whole 
>>>>page back.
>>>>Thus, even with Gray code, there are finite times, where you have
>>>>[OldValue][Erasing to 0FFH][0FFH][Writing NewValueZeroes][NewValue]
>>>
>>>
>>>That is why I suggested that there must be enough capacitance to allow
>>>any write that has started to complete. Many external brownout
>>>detectors has a "power-fail" alarm pin that activates at a higher
>>>voltage than the reset. This pin can be used to make sure that a write
>>>is not started just before a power fail.
>>>
>>>[Snipped]
>>>
>>
>>Gray code here provides no possible benefit, since the data is not 
>>updated a bit at a time.  Gray code is important when sampling multi-bit 
>>data in different clock domains (such as for absolute position encoders, 
>>or counters in FIFOs), but gives you little (avoiding the occasional 
>>write of the high byte of your 16-bit counter) for the extra headaches 
>>here.  If your power-fail alarm and your capacitor charges are 
>>sufficient to ensure that power-fail will never stop in the middle of a 
>>write, then just store the counters directly.  Of course, it relying on 
>>such a system would be risky if it is not clearly over-dimensioned, 
>>especially when there are such simple ways of ensuring reliability 
>>without it.
> 
> 
> I disagree. Using gray code when incrementing/decrementing a counter
> in EEPROM ensures that one need to worry only about one byte at a
> time. (Only one bit changing implies that only one byte changes) One
> then only has to ensure that the EEPROM write is not started just
> before a power fail, and if the power fails just after a write has
> started, that there is enough reserve power for the one byte write to
> finish. Using the appropriate external browout detector, makes this
> simple and reliable.
> One can also put the Gray count value in the EEPROM such that one
> EEPROM byte represents a single bit. Again because only one bit
> changes, one has to worry only about updating one byte per count.
> Even if the underlying mechanism erases a page, and reprograms it,
> there is still a maximum time that it takes to do this, and one must
> just ensure that if a write has started, that the MCU stays alive for
> this time before going down.
> 
> Regards
>   Anton Erasmus

If you can make your hardware safe for a single byte write, you can make 
it safe for a two byte write (or whatever length of counter you want), 
elimating the complexity of gray codes.  I'd still avoid a system that 
relied on running after power has been turned off - journaling is easy 
to do if you think it through carefully, and far more flexible (for 
example, you can group a number of changes).  If you have lots of eeprom 
space and want to spread your wear-and-tear evenly, that's perfectly 
possible too (add a version number to your data).

mvh.,

David