Speakerguy
Active Member
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
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
Last edited:
