Newbie question about EEPROM usage for 12,000 data points on a "rolling average"

ElectricAye

I'm only vaguely familiar with how EEPROMs are used so forgive me if this sounds like an idiotic question:

I have 3 instruments taking measurements every 1 second, each measurement storing a LONG's worth of data. I would like to establish what I call a "rolling average" of the data coming from each sensor. By "rolling average" I mean I would like the Prop to look through the past 60 minutes worth of data and give me a separate one-hour average for each of the 3 instruments. This rolling average could be displayed every 5-10 minutes or so but it's important that, as new data enters the one hour "averaging window", the data older than 60 minutes is dumped overboard so it no longer is part of the average. This approach would require me to keep every data point of the past hour stored somewhere, so it seems logical to me to use an EEPROM. I estimated the following:

(3 instruments)*(1 data point every second)*(3600 seconds/hour) = 10800 data points/hour.

I suppose that would use up about 45 kbytes of EEPROM space??? But I thought I would allocate various regions of the EEPROM's address to store data only for instrument 1, instrument 2, etc. so I could easily keep track of what is stored where. And that would use more EEPROM space.

My first question: is this a sane way to use an EEPROM?
Second question: any idea how long it would take for the Prop to read and scan through about 11,000 data points to generate such averages? I need the Prop to generate this only about 10 times per hour while doing other tasks, so if it takes 10 seconds or so, it's no big deal. But if it's the sort of operation that would likely take minutes, then I will be despondent.

thanks for your insights,
Mark

mctrivia

you will need a 512k eeprom it will wear out in 100 years at that rate. see my id object for code example

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Need to make your prop design easier or secure? Get a PropMod has crystal, eeprom, and programing header in a 40 pin dip 0.7" pitch module with uSD reader, and RTC options.

Carl Hayes

Ordinarily, logging data to an EEPROM is something that must be looked at very carefully, because each locatiion in the EEPROM has limited life, typically about a million writes.· Since you would be writing each location about once per hour, the EEPROM ought to last about a million hours, I guess.· That's 114 years, so your particular application ought to be OK in that respect.

You'll be remembering one measurement per second, retaining an hour's worth, or 3600 data.· Each datum occupies a long, or four bytes, so you'll need 14,400 bytes for each instrument, for a total of 43,200 bytes.· That's reasonable for an EEPROM.

You'll need to maintain, for each instrument, a table in EEPROM and a pointer to the current location in the table.· Each time you have a datum to record, you write it in the EEPROM at the location specified by the pointer, and then you update the pointer (add 4)·to point to the next EEPROM location.· When you reach the end of the table, you set the pointer back to the beginning.· In this way the table will always contain the last hour's data.

You speak of reading the whole table each time you want to calculate a one-hour average.· That is unnecessary.· You can calculate a rolling average more easily if you maintain the current sum of the 3600 readings for the last hour.· The rolling average will be this sum divided by 3600.

The key thing to notice is that you don't need to add up 3600 values each time you need that sum.· Instead, each time you're going to write a new value into the table, you first read the value currently in that location (which is one hour old), and subtract it from what I guess we can call the rolling sum.· Then you write the new measurement into the EEPROM (replacing the one-hour-old value), and add it to the rolling sum.

That way, each time you have a new measurement, you do one read, one subtractiion, one write, and one addition, to maintain the rolling sum.· That's way faster than reading and adding 3600 values to get the rolling sum, even if you divide by 3600 every time.

You ought to be able to do that process (including the division by 3600, which is the hardest part but not so hard at that) once per second for each of three instruments, and have lots of spare processing power.


▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
· -- Carl, nn5i@arrl.net

Post Edited (Carl Hayes) : 4/13/2009 4:28:46 PM GMT

Phil Pilgrim (PhiPi)

The EEPROM should work. With each cell being written once per hour, you can expect it to last about 11 years (assuming a typical spec of 100K maximum writes). The way to keep your processing overhead low is to organize the data in a FIFO buffer and keep a running sum of each datum. This will have to be done using two longs for each datum for accuracy. When a new data point comes in, you will increment the buffer pointer (wrapping around to the beginning after every 3600 samples), then read the contents of EEPROM at that location. This number will get subtracted from the sum and the new number added. Then the new number will replace the old one in EEPROM. That way you will have a rolling sum of the last hour's worth of readings, which you can divide by 3600 to get the average.

-Phil

Carl Hayes

Great minds think alike.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
· -- Carl, nn5i@arrl.net

ElectricAye

Hey, you guys are great! I never thought about that subtraction concept. That certainly saves a lot of trouble!

AWESOME!

Thanks!

Mark

mctrivia

I have never seen a 100k write eeprom all have been 1M write

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Need to make your prop design easier or secure? Get a PropMod has crystal, eeprom, and programing header in a 40 pin dip 0.7" pitch module with uSD reader, and RTC options.

Carl Hayes

mctrivia said...
I have never seen a 100k write eeprom all have been 1M write

100,000 and 1,000,000 are the commonest specifications, but there are a lot of different EEPROMS out there, and I'm sure some of them have still other specifications.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
· -- Carl, nn5i@arrl.net

mctrivia

I have never seen a 100k write eeprom all have been 1M write

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Need to make your prop design easier or secure? Get a PropMod has crystal, eeprom, and programing header in a 40 pin dip 0.7" pitch module with uSD reader, and RTC options.

Carl Hayes

Incidentally, why are you looking for a rolling one-hour average?· Is it for smoothing?· There's an alternative way to do smoothing, which is much easier, doesn't require storing past measurements at all, and assigns greater weight to more recent values.

What you do is maintain a single smoothed value.· Each time you get a new datum, you:

· (1)· Multiply the current smoothed value by some number n, say 1000

· (2)· Add the new value

· (3)· Divide the sum by n+1, say 1001, to get the new smoothed value.

This assigns constantly diminishing weight to old values.· The smaller n is, the faster the smoothed value changes (that is, the less it is damped).

And you don't store old values at all, and don't need the EEPROM.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
· -- Carl, nn5i@arrl.net

Bean

Carl,
That is an interesting method. Does it have a name ?

Bean.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
There is a fine line between arrogance and confidence. Make sure you don't cross it...

·

Carl Hayes

Bean (Hitt Consulting) said...
Carl,
That is an interesting method. Does it have a name ?

Bean.

No name·that I know of.·

A disadvantage of the one-hour average, shared also by my simple smoothing method as described above, is that it takes some time for either method to settle on a reasonably accurate value.

This disadvantage can be eliminated by a refinement of my smoothing method.· Instead of setting n as a hard parameter, instead set a maximum value n_max.· Start out with n = 0, and increase it by 1 (up to n_max) after processing each incoming datum.·

After the first measurement m₁, the smoothed value is simply m₁ because you multiplied by 0, added m₁, and divided by 1.· Then you increment n which now becomes 1.

After the second measurement m₂ the smoothed value will be (m₁+m₂)/2.

After the third measurement m₃, the smoother value will be (2((m₁+m₂)/2)+m₃)/3.

And so forth.· The oldest values drop out gradually (instead of suddenly after an hour).

I haven't seen this described anywhere, but I'm sure others must have thought of it before I did.· I invented it when I was doing computerized temperature control (with an IBM 1800) in glass bottle plants in the early 1970s.

By setting n_max in response, say, to button-pushes, you can change the damping on the fly.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
· -- Carl, nn5i@arrl.net

Phil Pilgrim (PhiPi)

Both methods have family names. The "rolling average" proposed by Mark is an example of a "finite impulse response" (FIR) filter, since the effects of any one datum disappear in a finite amount of time. Carl's "moving average" is an example of an "infinite impulse response" (IIR) filter, since the effects of each datum can theoretically linger forever, albeit in asymptotically diminishing fashion. (In reality, the effects are finite due to the truncation that occurs with integer arithmetic.)

-Phil

jazzed

Bean (Hitt Consulting) said...
Carl,
That is an interesting method. Does it have a name ?

Bean.

In stock market technical analysis jargon it's called an EMA "Expotential Moving Average."

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
--Steve


Propalyzer: Propeller PC Logic Analyzer
http://forums.parallax.com/showthread.php?p=788230

tonyp12

maybe single exponential smoothing is the correct way?
http://www.itl.nist.gov/div898/handbook/pmc/section4/pmc43.htm

But how to turn that jargon in to real code, that I can not do.

Carl Hayes

tonyp12 said...
maybe single exponential smoothing is the correct way?
http://www.itl.nist.gov/div898/handbook/pmc/section4/pmc43.htm

But how to turn that jargon in to real code, that I can not do.

Ummm -- I thought I explained it step by step --

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
· -- Carl, nn5i@arrl.net

kwinn

I think Tony is correct on the name. I did write a program for 8080 years ago to do something similar. Due to time and memory constraints we could not use floating point math or even multiply and divide so we found a way to accomplish the same thing using shifts and adds. With a 32 bit propeller I am sure the same could be done easily, and eeprom storage of thousands of data points would not be necessary.

tonyp12

Say you use shift-left 6 steps = *64

But apparently you are suppose to divide by one digit higher, who would you divide by 65 by not using mulp/div?

This would NOT be correct: s =(s <<6 + x )>>6

As it would divide by 64 and not 65

Post Edited (tonyp12) : 4/13/2009 7:32:41 PM GMT

Phil Pilgrim (PhiPi)

s := ((s << 6) - s + x) >> 6 is the same as s := (s * 63 + x) / 64.

-Phil

tonyp12

So someting like this (not real code)
if you want to use 100 as n_max

i=0
s=0

loop
x= current input value
s=(s*i+x)/(i+1)
if i<100 then i=i+1
print 'current temp:' x
print 'average:' s
wait 1 second
next

Post Edited (tonyp12) : 4/13/2009 8:01:38 PM GMT

Baggers

ElectricAye, don't forget if you're using the subtract method, you'll initially have to wipe all the instruments eeproms clear with zeo's, otherwise you're first hour's averages will be wrong, which will carry, and give you crazy readings. [noparse]:)[/noparse]

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
http://www.propgfx.co.uk/forum/·home of the PropGFX Lite

·

kwinn

Thanks Phil.

Carl Hayes

Here's a (skeletonized) example in XPL:


declare nmax float bit(16) initial(1000);·················· ·/* maximum value of smoothing constant n */
declare n float bit(16) initial(0);························· ··· /*·smoothing constant starts as 0··*/
declare average float bit(32) initial(0);···················· /* the floating average··*/
declare datum float bit (32);································· /* the measured instantaneous value goes here */

· ...


process_datum:··procedure;·································· /* we do it in a subroutine */
··· average ::= average * n;································ · /* multiply floating average by n· */
··· average ::= average + datum;························· · /* add the new datum (new measurement) */
··· average ::= average / (n+1);························ ··· /*· divide by n+1 to get new average */
··· n ::= n+1.0;···················································/* add 1 to n */
··· if ((n = nmax) or (n < nmax)) then return;··········· /* return if n not over limit nmax */
····n ::= nmax;········ ········································· /* else set n back to its limit */
··· return;························································· /* and that's it */
end process_datum;

I chose XPL because surely everyone can read and understand it.·

Note that, although n and nmax are going to be integer values, I declare them as floating point because they will be used in floating point calculations, and it's expensive to convert them every time they're used.· If all arithmetic is done in fixed point, then n and nmax should be fixed too.

Also, I initialize average to zero, even though the initial value doesn't affect the result.· Initializing it eliminates the risk of an early overflow or of an accidentally negative result.· In a Prop this is unnecessary because variables are initialized to zero at startup anyway.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
· -- Carl, nn5i@arrl.net

Post Edited (Carl Hayes) : 4/13/2009 8:31:26 PM GMT

Carl Hayes

Baggers said...
ElectricAye, don't forget if you're using the subtract method, you'll initially have to wipe all the instruments' eeproms clear with zeros, otherwise your first hour's averages will be wrong, which will carry, and give you crazy readings. [noparse]:)[/noparse]

[noparse][[/noparse]spelling corrected]

They'll be wrong anyway, unless you initialize with the first measured value rather than with zero.


▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
· -- Carl, nn5i@arrl.net

kwinn

ElectricAye, do you actually need to store some of the data, or do you just need the rolling average over the past hour? If you need to store it, how much do you need to store?

ElectricAye

kwinn said...
ElectricAye, do you actually need to store some of the data, or do you just need the rolling average over the past hour? If you need to store it, how much do you need to store?

I'm storing all the data on an SD card, which will eventually add up to weeks if not months worth of data (SD cards will periodically get swapped out). But to give me a sanity check on the instruments and an "at a glance" feature on my VGA display, I wanted some sort of method for comparing present outputs with outputs seen over the past hour or so. The selection of an hour is totally arbitrary. It might even be nice to have daily and weekly rolling averages, too, so this fancy filtering system that y'all have been discussing might work for that too (?). That would be great, if it does.

Wow, I never thought asking such a simple question would cause me to learn so much!

Thanks to everyone for your erudite answers and sagacious suggestions!

Mark

Beau Schwabe

Here is another thread that discusses averaging moving data....

http://forums.parallax.com/showthread.php?p=759589



Carl Hayes,

I tried your method against method 1 and 2 in the linked thread, and they are very close.



▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Beau Schwabe

IC Layout Engineer
Parallax, Inc.

kwinn

ElectricAye, I don't see a problem with a rolling hourly, daily, weekly, or monthly average if desired. One or two longs per average period should be all you require. The only gotcha would be loosing power and having the data disappear. Then you would need to read it back from the eeprom and recalculate the averages.

ElectricAye

Phil Pilgrim (PhiPi) said...
...The way to keep your processing overhead low is to organize the data in a FIFO buffer and keep a running sum of each datum. This will have to be done using two longs for each datum for accuracy....

Phil,
I know I originally stated that I would need to store a LONG on each datum, but on second thought it looks like the max number of pulses would be 500,000 so the "running sum" would not exceed:

(500,000 pulses per second) * (3600 seconds per hour) = 1800000000 which could be represented by a 32 bit LONG, I think.

So would I still need two LONGs to get accuracy??? or is there some other issue here that I'm totally missing?


thanks so much for helping me out!

Mark

Phil Pilgrim (PhiPi)

So long a the sum remains between -2³¹ and +2³¹ - 1, inclusive, a single long will accommodate it.

-Phil

ElectricAye

Thanks, Phil, that's a relief since I don't know how to deal with multiple LONGs!

And thanks to everyone who's contributed to this thread. Reading through this today and pondering all that you've said has not only solved my problems but it's also given me a nerdy high.

I love it!

Mark