There is a much better way! It is called a median filter. Basically,
     this is just like a moving average (or more generically, an FIR)
     filter, except that you take the median of the data instead of the
     average. You do this by sorting the data in the window by value,
     and then outputing the value which ends up in the middle.

     Why is this better? Basically, you are trying to remove impulsive
     noise. Any linear filter will have an impulse response. (And averaging
     is just a very simple linear filter.) So from a deep theoretical
     standpoint, it is not possible to create a linear filter where
     the output does not respond in some way, however small. Consider the
     data set 3, 5, 2, 47 and 3. The average is 12. The median is 3.
     (pick the middle 2 3 ->3<- 5 47) We could replace the 47 with
     5,345,356 and the median would still have been 3. The average
     would be over a million. Yuck.

     It sounds like you have a classic median filter problem - a clean
     set of data with occassional noise. If you were trying to get
     rid of Gaussian noise, some sort of averaging would be the best
     choice. But for these long-tailed distributions, some form of
     nonlinear filter is more robust. And the best part is, it requires
     no math other than comparison. Thus, your problem is solved.

     Sort of. If you want to be really efficient, when median filtering
     a data stream people generally maintain a linked list of the
     data, removing expired data, and inserting the new data on the
     fly. That way you don't have to sort the whole list each time.
     Virtually any book on numerical algorithms should discuss this.

     Good luck!

     --- phd

     P.S. Disclaimer - my dissertation was on implementing median filters
     with analog components, so I tend to be a proponent...


______________________________ Reply Separator _________________________________
Subject: Averaging Algorithm
Author:  PICLIST@MITVMA.MIT.EDU at WDI-INTERNET
Date:    9/23/97 10:34 AM


Anybody got a good averaging algorithm?

I've got a stream of numbers from 0 to 15 coming out of a PIC '620
comparator representing temperature of an appliance.  When I turn on
the flourescent lamp on my bench, the program picks up a spike, and
the relay in this thing fires momentarily, because it reads the
noise.  "NO PROBLEM" I sez, and sat down to write an averaging
algoritm.

This ought to be so easy.  The first "Algorithm" anybody learns in
kindy-garden Math 1 is how to average numbers.  I've been checking
out verious ways of averaging a stream of data, though, and don't
have one that satisfies on a PIC with Two byte arithmetic and no
floating point math.

Try this.  Make a spreadsheet with 300 or 400 random integers between
0 and 16.  Take the arithmetic average of all of 'em, probably
around 8.   Then try to simulate a PIC program processing each number
in succession that would get near the average, without floating point
math.  I tried a half dozen ways this morning.

One trick I worked out is that the average of N numbers, given the
NTH piece of data is being processed now, is (N-1)*(old average)/N
plus (Nth piece of data)/N.  If you pick 256 data points, given the
old average AVG and the new data point DATA,

NEWAVG = {(AVG*255)+DATA}/256

That oughta work!  Not so fast.  Using only integer values,no
floating point math,  the average climbs slowly toward zero and stays
there.  PICs can probably do floating point math, but there's gotta
be an easier way!


Best Regards,

Lawrence Lile