speakerguy79

Averaging Filters in Embedded Systems

Averaging filters are frequently used in embedded systems for a variety of reasons. A very common task in which they are used is to eliminate noise from an analog signal that has been sampled. Here we investigate how to make these computations faster and occupy less memory space.

The Wrong Way to Average

A very poor method of averaging, while mathematically correct, is to store the last (n-1) measured samples in an array to be averaged (where n is the order of the filter). The newest measured value would added to the previous (n-1) values, and then divided by a factor of n. Having accomplished this, the oldest stored value in the array would be discarded and the newest measured value shifted into the array for future calculations. The C code for a 4th order (n = 4) moving average filter implanted like this might look like the following:

int average(new_val) {

sum = new_val + previous_val[0] + previous_val[1] + previous_val[2];
avg = sum / 4;

previous_val[2] = previous_val[1];
previous_val[1] = previous_val[0];
previous_val[0] = new_val;

return avg;
}

This method is extremely poor in terms of both execution time and memory usage. In addition for the need to store (n-1) array elements, this function requires (n-1) values to be shifted through the array, (n-1) additions to be made, and a divide instruction which alone can take up to 38 instruction cycles on a PIC18F series device. All of the above must happen every time this function is called.

A Simpler Solution

A better method of removing noise from a signal uses an approximation of the moving average. This method is faster, uses less memory, and is significantly better for higher-order filters. This quasi-average is calculated by taking the most recent measured value, adding it to the previous average multiplied by (n-1), and divides that sum by n. In this method n does not represent the number of samples you are averaging over, but simply the order of the averaging filter. The C code for this algorithm with n = 10 would look like the following:

int average(new_val) {
avg = (new_val + 9 * avg) / 10;
return avg;
}

That’s a whole lot simpler, eh? It only requires one integer to be stored, one addition, one multiplication, and one division. It does not give a true moving average, but is still a very effective function for smoothing data and eliminating noise.

Getting Really Smart

The improved method above is much better, and is one you should remember when coding for any computer system where an averaging or smoothing filter is required. But for PIC microcontrollers, the divide and multiply instructions still cause a lengthy execution time. By being a little bit smarter, we can eliminate this source of inefficiency. This is accomplished by picking a power of two for the value of n, and using unsigned 8-bit numbers for all the operands.

Picking a power of two for the value of n allows for division to be accomplished with a series of bit shifts instead of a true divide. Each rightward bit shift uses only one execution cycle and effectively divides the number by two. By using one, two, three, or four bit shifts we can accomplish division by a factor of two, four, eight, or sixteen, respectively.

By using unsigned 8-bit integers for our operands, we can take advantage of the 8x8 hardware multiplier inherent in all PIC18F processors. If you have a particularly noisy signal the extra two or four bits provided by a 10 or 12 bit analog to digital converter may be buried in the noise, or you may simply not need that precision. In either case you can take advantage of the single-cycle 8x8 hardware multiply supported by the 18F series of PICs.

Below is what the C code might look like for a sixteenth order averaging filter:

unsigned short average(new_val){
avg = (new_val + 15 * avg) >> 4;
return avg;
}

One addition, a single-cycle multiplication, and four single cycle bit shifts. If you can live with a quasi-average and eight bit precision, the above method will yield much faster execution times and require much less system memory.

Remember this the next time you have to de-noise a signal, and you won’t be left wondering why your program takes so long to execute.

Mark Hayenga
© 2008

3v0

Looks good to me.

I would prefer to see
avg = (new_val + (15 * avg)) >> 4;

__________________
search engine for electronic parts
Junebug USB PIC programmer kit., USB Bit Wacker, Homepage
The 15 Minute Printed Circuit Board! (+drill time)

Torben

I just see a couple of typos:

Overall, I found that very informative. Good job!


Torben

Torben

Oops--one more nitpick. The C example functions never declare their internal variables.

Told you it was a nitpick.


Torben

speakerguy79

They're all global.

Pththththththth

Actually I had all the decs and initializations in there, but I removed them for simplicity. I even thought about writing it in pseudo-code.

Thanks for all the suggestions and corrections guys!

Torben

I *knew* you were going to say that. hehe

Are you putting together a site for this stuff? I'd be interested in reading more app notes like that.


Torben

speakerguy79

Yes, I'll be putting up a site. I'm just now getting started with it.

speakerguy79

Alright, suggestions and corrections incorporated, though variable decs left out for clarity.

Attached Files

Averaging Filters in Embedded Systems.pdf (12.0 KB, 11 views)

philba

in the brute force average case, you don't need to move the data in the array. just overwrite the oldest one in a circular fashion. increment the index mod N.

kchriste

Or forget about arrays and just add the 8bit samples to a 16bit variable and then divide (use shift for speed) the 16bit variable by the number of samples taken. The average result is in the lower 8bits of the 16bit variable.

__________________
--- The days of the digital watch are numbered. ---

eng1

Some compilers define the 'short' type as an 8-bit variable and the result would be wrong because of possible overflows. C18 defines the 'short' type as a 16-bit variable (it is the same as an 'int' variable). I would define 'avg' as an 'unsigned int' and 'new_val' as an 'unsigned char' in order to avoid the confusion caused by different conventions.

BTW, it's always a good idea to check the assembly code generated by the compiler