# Fastest moving averaging techniques with minimum footprint

I have tried few running averaging techs for smoothing the change in ADC data in AtMega48 for controlling lights(PWM) when rotating a pot(ADC).

The filters (pseudo codes):

Moving average:

adc_avg += new adc_raw;

fill adc_raw_array[i] = adc_raw;
adc_avg >>=3 ; // divide by 8


I observed that the filters are very nice. But slow in response which is expected.

I am looking for a techniques like Exponential moving average. Said to be more responsive. Is there another like this one? As it says:

adc_Eavg = α * adc_raw + ( 1 - α ) * adc_Eavg ;


where α is between 0 and 1.

How to code and optimize those; code wise (without using floats) ? Or How would I convert the floats to corresponding integers for making code small, fast and responsive one.

I tried as

adc_Eavg  += α * ( adc_raw - adc_Eavg );


and I kept α = 1;

Other then that it wont work as expected. Because I'd've to change all the variables to float.

Please do not concentrate on following statement for the time being but note. Keeping floats in my code base is filling the program memory from 45% to 137%, in case of

adc_avg = adc_avg * 0.8f + adc_raw * 0.2f;

-
I don't understand your moving average code. First don't divide (or even bit shift) just use the sum in your algo. Also, you can build moving average with single sum. It is super efficient. Subtract the oldest value from the newest value and add to the sum. Probably 3 cycles and you are there. Also, you have the keep a circular buffer where the pointer points to oldest number. After you do the math, place the new in place of the old and move the pointer, so you get a the new oldest data. This is without a loop and single sum and substract. If coded well less than 20 cycles. –  Ktc Oct 4 '12 at 7:42
I have a code like that running at a commercial product filtering 500Khz signal in real time, works well. –  Ktc Oct 4 '12 at 7:43

Your moving average filter is rather inefficient; there's no need to shift the data, nor to calculate the total each time again. Instead of a FIFO implement it as a round robin:

*i points to the oldest sample in the list*
total -= samples[i]
total += new_sample
samples[i] = new_sample
i = (i+1) mod 8
average = total >> 3


So you replace the oldest sample by the new one in the list, after subtracting the oldest from the total and adding the new one. Then let the index point to the next position, which now is the oldest, to be replaced by the next sample.

FIR vs IIR
The moving average filter is a FIR (Finite Impulse Response) filter with all coefficients equal. A FIR filter is inherently stable, and its main disadvantage is that it needs more storage than the typical IIR filter. In the case of the moving average it's only the samples array, but for a generic FIR filter you need a second array with the coefficients.

Your other solution is an IIR (Infinite Impulse Response) filter; it uses a combination of the previous output and the new input to create the new output value. It's not necessarily stable (though yours is), but often needs less storage: yours only needs the previous out value. A bi-quad filter only needs a 4 sample storage (Direct Form 1, shown below) or just 2 samples in Direct Form 2.

-
It seems better. –  Rick2047 Apr 24 at 10:50

You can implement

adc_Eavg = α * adc_raw + ( 1 - α ) * adc_Eavg ;


with minimal overhead by limiting α to binary fractions. I have used this with good results.

Take the existing result,
Shift it N places right to divide by 2^N
Subtract it from the existing result.

Done.

This is not as fast at changing with a step change in the input data as you may wish, but is easy to implement and "effective enough" as a filter in many cases.

You can speed up its response by making informal decisions as to its behaviour in cases which are too different. eg maintain a count of sequential inputs which are more than some limit different than the existing result. If this count exceeds some threshold then change the N divide ratio by some factor.

eg N is usually 4-> results are shifted right 4 times = 16 divide. If input is more than xxx away from the answer do only two shifts right and multiply new sample by 4 before adding.

-

You can optimise an exponential filter if α = 1/(2^n). E.G. if α = 1/4, then:

adc_Eavg = (adc_raw>>2) + adc_Eavg - (adc_Eavg>>2);


Or, for more accuracy, but at risk of overflow:

adc_Eavg = (adc_raw + (adc_Eavg<<2) - adc_Eavg) >> 2;


Or, if your MCU has a faster multiply than shift:

adc_Eavg = (adc_raw + adc_Eavg*3) >> 2;

-