Electronic – Non-Volatile Serial Memory Chip

What you need is a technique called wear leveling. It doesn't write your data every time at the same location in the EEPROM, but uses some algorithm to use different locations. I've read about complex wear leveling algorithms, but I wouldn't know why the following simple method wouldn't work.

Add to your data a 24-bit counter, so that your data block is for instance 8 bytes long. Pages on a 24AA64 are 32 bytes long, so a 64kb EEPROM holds 256 pages. From the datasheet:

"When doing a write of less than 32 bytes the data in the rest of the page is refreshed along with the data bytes being written. This will force the entire page to endure a write cycle, for this reason endurance is specified per page."

so it doesn't make sense to use data blocks smaller than a 32 bytes page.

Look at the counter of the first page. If it's zero you used the maximum number of write cycles for that page, so you move on to the next page and check that counter. Repeat until you find a counter > zero. That's the page you're currently using. Microchip's EEPROMs have a 1 million cycles endurance, which you can increase to 256 million with the given example of maximum 32 bytes per block in a 64kb EEPROM. That should be enough to outlast your product: 40 years if you write once every 5 seconds(!).

You'll want to initialize your EEPROM on first use. How do you know when that is. Use the last page to write a unique signature upon initialization. Check at each power-up if the signature is there. If it isn't the device has to be initialized. You can preset the counter in each page with 0xF4240 (for 1 million) or clear everything to 0xFF and write the 0xF4240 when you first use the page.
Initializing an EEPROM is needed because sometimes a certain pattern is written to it in the production/test process.

edit
The wear leveling should solve your problems, but I still want to comment on the capacitor solution. You say the board is rather power-hungry, but maybe you can isolate the microcontroller/EEPROM's power from the rest of the board with a diode. So you'll probably need only a few mA when main power is gone. The 24AA64 writes a page in less than 5ms, then at 10mA and an allowable voltage drop of 100mV you'll need

\$ C = \dfrac{I \cdot t}{\Delta V} = \dfrac{10mA \cdot 5ms}{100mV} = 500\mu F \$

Easy with a small supercap.

further reading
datasheet 24AA64
EEPROM Endurance Tutorial

Yes, you understand the definition of volatile and non-volatile memory. From that alone you'd think non-volatile is always better. However, in the real world that is not true since the different technologies for making these memories cause other attributes to appear beyond volatileness.

Tradeoffs that various different memory technologies force on us include:

1. Read speed.

2. Write speed.

3. Cost.

4. Size.

5. Power consuption when idle, reading, and writing.

6. Operating lifetime.

7. Number of lifetime reads or writes.

and that's just what came to mind quickly. Obviously, the ideal memory is fast to read, fast to write, costs little, is small, takes little power, lasts a long time, and can be used many times. There is no one technology that does a good job in all these areas together. Volatileness is just one more entry in the list of parameters to consider.

In something like a microcontroller intended to be embedded into a circuit that needs to turn on quickly, having the main program memory be non-volatile is imortant. That today generally means it will be slow to write, have a finite number of lifetime writes, and will forget its content after a few 10s of years. Obviously we'd like to not have these drawbacks, but nobody knows how to make a memory that doesn't have them for the size and cost required in a micro.

The data memory in a micro could be arbitrarily written and read in a loop millions of times in seconds, possibly going on for years, so a technology that doesn't have a finite number of lifetime reads or writes is important. To get that, we give up the ability to retain the values when power is removed.

There are all kinds of memory technologies that optimize some of these parameter, inevitably at the expense of others. Some common technologies:

• CMOS static RAM. These are really logic circuits optimized to hold bits. They are fast, have effectively infinite lifetime reads and writes, take little power when not being accessed, and have a long operating lifetime. On the other hand, this memory is volatile, and the cells are relatively large, which makes them expensive with high densities not attainable.

• EEPROM. Actually that's not strictly speaking a technology, but today (this could easily change) these memories are commonly implemented with floating gate MOSFETs. Their main attribute is that they are non-volatile. Density is high, so cost is low, but they get physically worn out a little bit every time the charge on the gate is changed, which is what writing or erasing does.