How much memory for averages?

realolman1

Suppose I was to average the input of an ADC in the following way:

I would add the input to a total and then at the end of a period of time, divide that total by the number of additions... If I ended up doing this thousands of times , would I need any special amount of memory allotted? So far as I can see, there would only be a few variables involved... the input value, the running total, the number of values added together, and the end result... the averaged values.

So it shouldn't take any special amount of memory should it?

thank you

kwinn

realolman1 wrote: »

Suppose I was to average the input of an ADC in the following way:

I would add the input to a total and then at the end of a period of time, divide that total by the number of additions... If I ended up doing this thousands of times , would I need any special amount of memory allotted? So far as I can see, there would only be a few variables involved... the input value, the running total, the number of values added together, and the end result... the averaged values.

So it shouldn't take any special amount of memory should it?

thank you

That's right. Worst case is four variables. Could get away with three variables if you stored the average value in the sum of values, so: total = total/count would divide the sum of all the readings by the number of values and store it back in total.

Edit: Could reduce it further since the number of readings to average is usually a constant. Typically the individual readings would be added to the sum in a loop and the divide by the number of values done immediately after exiting the loop.

kwinn

On the whole though trying to save variables like this does not make much of a difference to program size. The ADC reading, sum of the readings, and number of readings have to be stored somewhere, either as variables or constants.

The Basic Stamps have a small number of variables so storing the number of readings to average as a constant in the program rather than a variable makes sense. The same is true for any micro that uses a relatively large eeprom for programs and a small ram for variable data.

Heater.

You can do it very easily with one only variable.

Let's say we take an ADC reading, call it "sample". And we have an average value we are maintaining, call it "average".Then:

Set the new value of average to (0.1 * sample) + (0.9 * average)

In this way, given a constant stream of samples of equal value the average will exponentially approach the true average value. Give a time varying stream of samples the average will hover around the true average.

Change the 0.1 and 0.9 to 0.2 and 0.8 and the average will respond more quickly. Or change to 0.01 and 0.99 and it will respond more slowly.

More generally we could write:

new average = (a * sample) + (1 - a) * old average

Where "a" is a factor between 0 and 1 that determines the time constant. The speed at which it responds. Effectively "a" is determining how many historic samples are contributing the the average value.

Depends what you want to do of course but if you collect and sum a large number of samples, say 1000, then divide that sum by 1000 you are having to wait for 1000 sample times before you get an new average value. The average values you get will make step changes every 1000 samples. A bit clunky.

With the exponential averaging you get a continuously varying average value.

Of course there are many other ways to get an average: https://en.wikipedia.org/wiki/Moving_average

PaulRowntree

And to take Heater's example one step further, you can assign the first reading to old_average directly, then apply his formula for all subsequent readings. it converges towards the steady-state average much more quickly.

JonnyMac

I've done several projects with joysticks where I use the following code.

var

  long  adccog
  long  adcstack[32]
  
  long  pot[8]                                                  ' averaged pots

  long  accidx
  long  acc[32]                                                 ' 4 readings for 8 pots
  

pri start_adc

  if (adccog)                                                   ' stop if already running
    cogstop(adccog-1)

  adccog := cognew(scan_pots, @adcstack) + 1 
  

pri scan_pots | t, ofs, ch, sum

'' Scans and averages adc inputs
'' -- averages adc inputs over four readings

  adc.start(ADC_CS, ADC_CLK, ADC_DIO)                           ' mcp3208 (Spin)

  t := cnt
  repeat
    ofs := accidx << 3                                          ' offset into accumulator array
    repeat ch from 0 to 7                                       
      acc[ch + ofs] := adc.read(ch, adc#SE)                     ' read channels
      
      sum := acc[ch]                                            ' rolling average
      sum += acc[ch + 08]
      sum += acc[ch + 16]
      sum += acc[ch + 24]  
      pot[ch] := sum >> 2
      
    accidx := (accidx + 1) & %11                                ' keep 0..3

    waitcnt(t += constant(8_333 * US_001))                      ' update @ 120Hz

By using an array size that is a power of 2 (4 in this case), dividing the accumulated values in the array is simplified (and sped up) with a right shift; likewise, updating the accumulator index can be done with a bit mask. The bulk of my loop code takes about 6.5ms (I tested using a free pin and another cog), so I set the loop timing to 8.333ms; this works out to a new averaging the last four readings of each channel 120x per second.

Heater.

I'm sure you could simplify all that by just adding each channels reading to it's sum. Then every fourth reading do the shift by 2 on each sum to get the average.
Oh and use the modulus operator to roll over that counter rather than testing against 4.

Thus saving a bunch of longs by not needing a big array of readings and a bunch of byte codes as well.

evanh

realolman1,
You've just had your first lesson in the subject of digital filters!

I'll point out that there is two major categories, Finite Impulse Response (FIR) and Infinite Impulse Response (IIR). An average method falls into the FIR category, JonnyMac's is a FIR, while Heater's one falls into the IIR category (It has an internal feedback that maintains a decay rate).

IIRs are less memory hungry and generally less processing demanding than FIR, while FIRs offer a sharper cut-off frequency.

Phil Pilgrim (PhiPi)

If you want the true average of thousands of readings, rather than one of the moving averages outlined above, your biggest problem is the size of the sum, as it may overflow even a 32-bit long. To remedy this, you can use a 64-bit sum, along with my umath object, as demo'd here:

CON

_clkmode       = xtal1 + pll16x
_xinfreq       = 5_000_000

VAR

  long sum_hi, sum_lo, count, rand, average

OBJ

  u     : "umath"
  sio   : "Parallax Serial Terminal"

PUB start | reading

  sio.start(9600)
  repeat 100_000
    reading := (?rand & $7fff_ffff) // 6_000_000
    count++
    if (u.gt(sum_lo, sum_lo += reading))
      sio.char("*")
      sum_hi++
  average := u.div(sum_hi, sum_lo, count)
  sio.char(13)
  sio.dec(average)

Two methods in this object are employed: gt which compares two unsigned longs, and div, which divides a 64-bit double long, represented as two 32-bit longs. When computing the sum, the current value of the lower 32 bits is compared to the new value after adding the reading. If it's lower, there's been a carry, so 1 is added to the upper 32 bits.

In the demo program, an asterisk (*) is printed every time a carry occurs. At the end of 100,000 iterations, the 64-bit sum is divided by the count (100,000) and the average printed. Because the "readings" are just random numbers ranging from 0 to 5,999,999, you would expect the average to be around 3,000,000. Here's the output from the program:

*********************************************************************
2997051

I've attached this program as an archive that includes the umath object.

-Phil

Heater.

Phil,

If you want the true average of thousands of readings,...

What is this thing called a "true average" ?

If you only have a thousand things to measure then I guess the common average of "sum N things and divide by N" may mean something.

But when dealing with signals conceptually they run forever. We cannot sum an infinite number of samples and divide by infinity. Even if we could it's a bit too long to wait for a result than I would like

If we batch that infinite stream of samples into batches of a thousand, or whatever, then we get an average result every thousand sample periods.

I would not call any of those a "true average". That average depends on which thousand samples you take. It also makes non-contiguous jumps from one batch to the next.

All in all, I think the exponential average is as "true" as any.

All depends what you want to do with this mythical average number I guess.

Phil Pilgrim (PhiPi)

Oh my! A true average of thousands of readings is just that: the sum of those readings divided by their number. A running average is just a lossy approximation of the true average (i.e. a smoothing function), since not all the data in a given epoch is retained as a list or as a sum. The exception to this rule might be the boxcar average, which is a running average that maintains a FIFO list of the last n readings, whose true average is computed after each reading.

All of these so-called "averages" have their place. My post was just to demonstrate how one of them could be computed with the Propeller when the sum of a bunch of readings might overflow a 32-bit long.

-Phil

Heater.

I think you are agreeing with me.

As I said, if you only have N values then the school book average is perhaps something "true". In some sense.

When we have a continuous stream of values then there are many ways to get an average. Which one of them is "true"? Or more importantly which one has the best meaning for your application? As you say 'All of these so-called "averages" have their place'.

Even the "box car" is suspect. It's results depends on how many boxes you decide to maintain.

Then we have things like the average of a symmetric AC signal. Which is always zero no matter what you do. Hence RMS.

evanh

Heater, IIR filters are not an average. Averaging is a FIR filter. The moment you introduce an internal decay you've lost any average.

Also, I'll point out, Phil, a "boxcar" is the running average filter.

Duane Degn

A few years back Phil mentioned (to another forum member) that learning to use a ring buffer was a really good idea.

I took Phil's advice and learned to use ring buffers and (as usual) Phil was right; ring buffers are really useful.

In Phil's recent post he mentioned using a boxcar average. A boxcar average uses a ring buffer. When a new value is to be added to the boxcar, the oldest value is subtracted from the total and the new value is added to the total. The ring buffer is used so the oldest value can be retreived.

In case you're interesting in using a boxcar average, here's the averaging code I use in one of my current projects.

PRI BoxcarFilter(newRaw) | localIndex
 
  if filterBufferMaxIndex240 ' Normal Boxcar Filter
    result := filterHead244 + 1 ' don't let filterHead244 ever be larger than filterBufferMaxIndex240   
    filterHead244 := result & filterBufferMaxIndex240
    result := boxcarBuffer[filterHead244]
    ~~result                                   ' sign extend word to long
    filterTotal242 -= result                   ' out with the old 
    boxcarBuffer[filterHead244] := newRaw 
    filterTotal242 += newRaw                   ' in with the new
    result := filterTotal242 ~> filterBits236
  else ' If filterBufferMaxIndex240 equals zero don't filter the data.
    filterHead244 := 0
    boxcarBuffer[filterHead244] := newRaw
    filterTotal242 := newRaw
    result := newRaw

The code could be simplified a bit if I used a buffer of longs instead of a buffer of word sized values. Since I'm using words, the values have to be sign extended before being subtracted from the total.

As has been previously mentioned, using power of two sized buffers can make the math a bit easier. Using a power of two buffer size allows one to shift bits rather than divide when computing the average from the total.

One advantage of averaging words is the total is less likely to have a 32-bit rollover problem.

Here's the code I use to initialize the averaging buffer.

PRI InitBoxcarFilter(startingAverageRaw) '| previousBufferSize

 
  filterBufferSize238 := 1 << filterBits236
  filterBufferMaxIndex240 := filterBufferSize238 - 1

  filterTotal242 := startingAverageRaw << filterBits236      
  wordfill(@boxcarBuffer, startingAverageRaw, filterBufferSize238)

  filterHead244 <#= filterBufferMaxIndex240
  

FYI the variables with numeric prefixes can be accessed as registers. I include the register number in the name to make code maintenance easier.

Here's the buffer defined in a DAT section.

DAT '' After Registers

boxcarBuffer            word 0[MAX_FILTER_BUFFER_SIZE] ' always even

Here are some constants I use with this boxcar filter.

CON ' boxcar filter constants

  MIN_FILTER_BITS = 0
  MAX_FILTER_BITS = 7
  MAX_FILTER_BUFFER_SIZE = 1 << MAX_FILTER_BITS

One thing I like about this implementation of the boxcar filter is the size of the filter can be changed on the fly.

To change the size of the boxcar buffer the value "filterBits236" (aka register #236) is changed to a value from 0 to 7. When this variable/register is changed, the program triggers the execution of the "InitBoxcarFilter" method. In order to reduce the complexity of the code a bit, I don't maintain the contents of the FIFO buffer across the size transition. I just fill the buffer with the current average value. This is a bit of a trade off in accuracy which is acceptable in my current project.

Heater.

I'm afraid you have lost me with difference between IIR and FIR. Must do some research...

Boxcar may well be the running average filter. But even then it's output depends on how many boxes you have. The boxcar average of the last 10 samples may be very different than the boxcar average of the last 100 or 1000.

Which one is the "true"average? It's for you to define.

Question is what is it one is trying to do? A 1 volt sinusoid superimposed on a 10 volt level has an average of 10 volts over a long enough time span. Any technique that only takes into account a finite amount of history will give you a different result if the sinusoid period is long compared to that history.

Peter Jakacki

"FIR" what it's worth I sometimes use the boxcar/ring-buffer averaging method for accuracy as I treat it as a window or a snapshot of the signal as it is (as I would see it on the scope perhaps) but I also use this value to filter out transients (very large differences) too which would otherwise upset the accuracy. The buffer method works best when the size of that buffer is a binary multiple so all we need to do is perform a shift right to get the average but if the sum of the buffer values exceeds 32-bits then all this would have to be done using simple 64-bit additions/subtractions/shifts but sometimes though it all fits into 32-bits anyway. The buffer and accumulator needs to be cleared beforehand.

Variables
buffer - a binary multiple sized array (example 256)
index - current read/write position in the buffer
accumulator - total sum of all values in the buffer (subtract end element when adding new element)
average = accumulator>>8

btw, the "end" element can be treated as the value that you are replacing with the new element.

Phil Pilgrim (PhiPi)

A FIR filter is a boxcar averager if all the coefficients are equal and add up to one. An IIR filter is more like Heater's

new average = (a * sample) + (1 - a) * old average

It has an infinite impulse response, since the influence of samples taken eons ago never truly goes to zero -- excepting, of course, the effects of integer arithmetic or floating-point precision factors.

-Phil

evanh

Phil Pilgrim (PhiPi) wrote: »

... if all the coefficients are equal ...

Maybe I've misinterpreted but to me that's what makes it a box, AKA a rectangular window function. It's no longer a box if those conditions are not true.

Phil Pilgrim (PhiPi)

evanh wrote:

Maybe I've misinterpreted but to me that's what makes it a box, AKA a rectangular window function.

Yeah, that's exactly what I said in the previous post.

-Phil

evanh

Cool.

evanh

Heater. wrote: »

Question is what is it one is trying to do? A 1 volt sinusoid superimposed on a 10 volt level has an average of 10 volts over a long enough time span. Any technique that only takes into account a finite amount of history will give you a different result if the sinusoid period is long compared to that history.

The strength of a low-pass filter is usually expressed in terms of the cut-off frequency and, relatedly, the stronger the filter the more lag it'll introduce. This pretty much defines your filter history in both FIR and IIR. However, FIR is a crisp delay while IIR is usually defined as the -3db threshold.

Digitally, sample rate and bit depth are factors that play into the signal-to-noise ratio rather than filter strength.

evanh

All that said, I've not formally studied any of this so may not have it all perfect.

Heater.

Should we talk about "signal-to-noise" ratio? The very act of taking an average or filtering implies that there is some information in there we want to ignore. No matter if it is signal or noise.

evanh

True, everything is kind of interrelated in that the construction of higher bit depth from multiple samples is also the basis of a filter. And therefore implies classifying out-of-band readings as noise.

It's amazing how effective this trick is though. All new digital communications designs are built from the ground up on this basic idea. Modems can now dynamically track around interference. It has allowed more and more robust and higher performing radio links.

ErNa

We have to find a method to teach this kind of things a different way, more linked to the subject we filter and to our everyday experience. The academic description, ending up in IIR and FIR hardly can be followed by our fellows. ;-)

evanh

I don't think it's a bad idea to use the recognised labelling. The distinction between FIR and IIR aren't that difficult and once dealt with is helpful from then on. The difference in the name is also the difference in the function.

F for Finite, is exactly as it seems - The filter output only responds to any input for a finite time period. This is achieved by having a limited working set of historical samples.

I for Infinite, is also as expected - The filter output keeps responding to any input indefinitely. This is achieved by using the previous output value as part of the new output value, ie: There is internal feedback.

Heater.

ErNA,

We have to find a method to teach this kind of things a different way, more linked to the subject we filter and to our everyday experience.

A good point. I lot of folks have never been exposed to such ideas. They know how to program. They know how to read sensors. Then they might have a notion of wanting some kind of average. Not being aware of the options they can probably dream up something and cobble it together that sort of works.

I was such a folk some years back. I found a nice circuit for a three-way cross-over built with opamps. Thinking it was an interesting approach I proceeded to implement it in software. I figured out how to create the integrators, summing elements and whatever it had in there by modeling the capacitors, resistors and gain elements. I checked out it's response curves and phase shifts, amazingly it matched the spec's of the original analog circuit! A friend of mine created a plug-in for what ever sound mangling program he had on his PC and announced it worked very well with his speaker setup.

All of that might have been a bit easier if I had ever heard of FIR and IIR !

You see, the last time I had any formal exposure to such things there was no FIR and IIR. We just had filters. Filters were made with capacitors, resistors and inductors.
(Yeah, I know an analog filter is a IIR)

The problem for any beginner is that if they find a typical intro to digital filters they immediately get hit with gobbledygook like "linear time-invariant systems" and a pile of scary looking maths. But they just wanted an average...

realolman1

Good Lord ,folks. "Try to catch a deluge in a paper cup"

I thank you all for your replies, much of which is over my head, but I did catch several things that are new to me that I found to be very interesting and useful, and I will be using them to the extent I am able in the future.

My interest in starting this thread was trying to graph the input from the Sigma Delta ADC, and having my graph jump around instead of being somewhat smooth because it seems to me that the resolution is too large. ... I started another thread for that... That, and (although I have read some threads) re: the amount of stack space needed for cogs, I don't really understand it.

Thank you for the education

Peter Jakacki

I guess you just needed an average solution for an average problem for an average guy. Wrong forum

realolman1

Oh ... I didn't mean to be insulting by what I said... I appreciate it. If anyone took that as being insulting, I apologize ... that is not at all what I meant

It was just a bit overwhelming for what I had in mind when I started the thread, not knowing anything about all these potential solutions, ... an average solution for an average guy , indeed

Heater.

realolman1,

Ha, yes. Give these dogs a bone and watch them tug on it in all directions

Hopefully it's a bit more fun and informative than the simple answer to your question which would have been just:

"No".