www.piclist.com/techref/logic/dsps.htm?key=filter

Bob Shaver wrote:

{Quote hidden}

I haven't looked at Lawrence's code, but here's an algorithm I have used

that combines a median filter with a good ol' fashioned averaging one:

o as data samples are acquired, place them into a circular array.

o as a new sample is inserted, add it to the cumulative sum of all the

elements and at the same time subtract the value that's being over

written. This saves the time consuming task of summing the elements each

time to find the average.

o maintain a list of pointers to each element of the array and sort

the pointer list (and not the elements)

o apply the 'median operator' by subtracting from the cumulative sum

those values that are at the extremes of the sorted list.

For example, you could have a circular buffer of 8 elements. When

sorted, you may decide to discard the top two and the bottom two -

leaving you with 4. After each pass through the above algorithm, you

would shift the cumulative sum right 2 positions (i.e. divide by 4) to

get the average.

The 'pointers' only need to be nibbles for small buffers (the typical

case), so the storage over head is no too sever. Keeping the sorted list

of pointers means that you only have to make one pass through the sorter

each time a sample is acquire. (alternatively, you have to make a ~n^2

sorta computation if you sort the entire array each time a new sample is

acquired.)

BTW. I used something like this in that caller ID project. It kills two

stones with one bird - it smoothes the sampled data by averaging and at

the same time discards unwanted spikes. Also it's relatively fast...

Scott

See also: www.piclist.com/techref/logic/dsps.htm?key=filter