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
Saving data in CPU on-chip EEPROM
Started by ●June 14, 2005
Reply by ●June 17, 20052005-06-17
Reply by ●June 17, 20052005-06-17
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
Reply by ●June 17, 20052005-06-17
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
Reply by ●June 18, 20052005-06-18
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
Reply by ●June 18, 20052005-06-18
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
Reply by ●June 18, 20052005-06-18
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. > > JonWhat 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
Reply by ●June 18, 20052005-06-18
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