Efficient Moving Average and Moving Variance Calculations

Steven Smith in "Digital Signal Processing" describes an
efficient algorithm for computing a moving average. This
algorithm is also mentioned in the Wikipedia article describing
Moving Average:

http://en.wikipedia.org/wiki/Moving_average

Rick Lyons once asked in this newsgroup about an efficient
algorithm for computing "moving variance":

http://groups.google.com/group/comp.dsp/browse_frm/thread/330ac90a92f8dfaf/02a3b89dcf21fdcc?hl=en&lnk=st&q=variance+group%3Acomp.dsp+author%3AHadstate#02a3b89dcf21fdcc

With minimal effort, one can modify the "Moving Average"
algorithm to efficiently compute a "Moving Variance" and a
"Moving Average" simultaneously at each time step.

Notice that one of the equations for computing a sample
variance over a window with N samples can be written as:


N * Sum(X**2) - (Sum(X)**2)
V = ---------------------------
N * (N - 1)


where X is the input.

To implement this efficiently, allocate two history buffers,
one for values of X and one for values of X**2, each containing
room for N points. These buffers need to be initialized,
perhaps to the first sample of X and X**2 or perhaps to zero,
your choice. Then initialize two variables, SX1 to be the
Sum(elements in X history buffer) and SX2 to be Sum(elements in
X**2 history buffer).

Then, at each time-step k, compute:

X1 = (new sample value)
X2 = X1 * X1

Y1 = (oldest X1 value from X1 history buffer)
Y2 = (oldest X2 value from X2 history buffer)

Overwrite oldest value in X1 history buffer with X1.
Overwrite oldest value in X2 history buffer with X2.

SX1(k) = SX1(k-1) + X1 - Y1
SX2(k) = SX2(k-1) + X2 - Y2

Calculate Moving Average:
M = SX1 / N

Calculate Moving Variance:
V = (N * SX2 - (SX1 * SX1)) / (N * (N - 1))



.

Relevant Pages

  • Re: Efficient Moving Average and Moving Variance Calculations
    ... efficient algorithm for computing a moving average. ... Rick Lyons once asked in this newsgroup about an efficient ...
    (comp.dsp)
  • Re: Moving average filter ...
    ... - is this a valid moving average algortithm? ... - does this algorithm have a name? ... not an FIR. ... I like to think of these things as an approximate digital RC filter - they have a similar effect on the signals, and are just as easy to implement. ...
    (comp.arch.embedded)
  • Re: Moving average filter ...
    ... Algortihm is; ... - is this a valid moving average algortithm? ... - does this algorithm have a name? ... "Applied Control Theory for Embedded Systems" gives you just what it says. ...
    (comp.arch.embedded)
  • Re: Moving average filter ...
    ... This is not the same thing as the moving average, although it is certainly useful algorithm. ... void MovingAvg ... - is this a valid moving average algortithm? ...
    (comp.arch.embedded)
  • Re: Efficient Moving Average and Moving Variance Calculations
    ... efficient algorithm for computing a moving average. ... algorithm for computing "moving variance": ... Overwrite oldest value in X1 history buffer with X1. ...
    (comp.dsp)
Loading