Fastest moving averaging techniques with minimum footprint

Question

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; 
adc_avg >>= 1;

8-point Moving Average Filter:

fill adc_raw_array[i] = adc_raw; 
adc_raw_array[8] <-- delete left most, move left, push adc_raw. 
adc_avg = sum(adc_raw_array); 
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;

Answer 1

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.

Answer 2

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.
Add new data

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.

Answer 3

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;