Most embedded engineers writing firmware have used some sort of digital filters to clean up data coming from various inputs such as ADCs, sensors with digital outputs, other processors, etc. Many times, the filters used are moving average (boxcar), finite impulse response (FIR), or infinite impulse response (IIR) filter architectures. These filters are linear in the sense that the outputs scale linearly to the amplitude of the input. That is, if you double the amplitude of the input stream the output of the filter will double (ignoring any offset). But there are many non-linear filters (NLF) that can be very useful in embedded systems and I would bet that many of you have used a few of them before. A NLF does not necessarily respond in a mathematically linear fashion to its inputs.
Wow the engineering world with your unique design: Design Ideas Submission Guide
In some cases, FIRs and IIRs can struggle with things like impulse noise and burst noise that can cause the output to react in an unacceptable way. Non-linear filters can offer protection to the data stream. Depending on your application they may be used as a stand-alone filter or as a pre-filter before the FIR, IIR, or boxcar filter.
The examples in this article are assuming one-dimensional streaming, signed or unsigned, integers (including longs and long longs). Some examples may be applicable to floats but others are not. Streaming is mentioned as it is assumed the data will be coming continuously from the source and these filters will process the data and send it out one-for-one, in real-time. In other words, we can’t just toss bad data, we need to send some value to replace the input. Some examples, though, may allow for oversampling and in that case, it can then decimate the data. For example, a sensor may send data at a rate 10 times faster than needed then process the 10 samples before sending out 1 sample to the next stage.
Another assumption for this discussion, is that we are designing for small embedded systems that are required to process incoming samples in real-time. Small in the sense that we won’t have a large amount of memory or a high MIPS rating. For that reason, we will avoid using floats.
So, let’s take a look at some of the non-linear filters and see where they are useful.
Bounds checking filter
This is one you may have used before but may not have considered it a filter. These filters are also often referred to as bounds checking, clipping, range checking, limiting, or even sanity checking. We are not referring to pointer checks but to data checking of incoming data or data that has been modified by previous code.
Here is a simple example piece of code:
#define Upper_Limit 1000
#define Lower_Limit -1000
int limit_check(int n)
{
if (n < Lower_Limit) n = Lower_Limit;
else if (n > Upper_Limit) n = Upper_Limit;
return n;
} Listing 1
You can see that if the integer n is greater than 1000 then 1000 is returned. If it is less than -1000 then -1000 is returned. If it is between 1000 and -1000, inclusive, the original value of n is returned. This would limit large impulse noise values from passing through your system, i.e., it filters the data.
When combined with another filter like a FIR, IIR, or temporal filter (described below), the limit value could be scaled based on the running filter value. If an out of range sample is detected, based on this moving limit, the bounds checker could return the latest filter output instead of a fixed limit or the suspect sample.
Some systems may provide some variation of bounds checking as a predefined function call or a macro.
Soft clipping filter
This is related to bounds checking but instead of just limiting a value after a certain level is reached, it slowly starts to back off the output value as the input approaches the maximum or minimum value. This type of soft clipping is often used in audio signal processing applications.
Soft clipping can be accomplished by something like a sigmoid function or a hyperbolic tangent function. The issue here is that these methods require significant processing power and will need fast approximation methods.
Soft clipping typically distorts a good portion of the input to output relationship, so it isn’t appropriate for use in most sensor inputs measuring things like temperatures, circuit voltages, currents, light levels, or other metrological inputs. As such, we will not discuss it further except to say there is lots of information on the web if you search “soft clipping”.
Truncated mean filter
The truncated mean, or trimmed mean, is a method where you take in a set of, at least 3, readings, toss the maximum and minimum reading, and average the rest. This is similar to the method you see in some Olympic judging. For embedded projects it is good at removing impulse noise. One method to implement this filter is by sorting, but in most applications in a small processor, this may be computationally expensive so for anything larger than 5 samples, I would suggest scanning the list to find the min and max. While running the scan, also calculate the total of all the entries. Lastly, subtract the min and max from the total and divide that value by the number of entries minus 2. Below is an example of such a function executing on an array of input values. At the end of the code there is an optional line to do rounding if needed.
#include
int TruncatedMean(int inputArray[], unsigned int arraySize) {
int i = 0;
int min = INT_MAX;
int max = 0;
int total = 0;
int mean = 0;
for (i = 0; I < arraySize; i++) {
if (inputArray[i] < min) min = inputArray[i];
if (inputArray[i] > max) max = inputArray[i];
total = total + inputArray[i];
}
//mean = (total - min - max) / (arraySize - 2);
// The previous truncates down. To assist in rounding use the following line
mean = (total - min - max + ((arraySize - 2)/2)) / (arraySize - 2);
return mean ;
} Listing 2
If you have only 3 values, it may be advantageous, in computation time, to rewrite the c code to remove looping as seen in this code example for 3 values.
int TruncatedMean_3(int a, int b, int c) {
int mean = 0;
if ((a<=b) && (a>=c) || ((a<=c) && (a>=b)) ) mean = a;
else if ((b<=c) && (b>=a) || ((b<=a) && (b>=c)) ) mean = b;
else mean = c;
return mean;
} Listing 3
Note that the truncated mean, using at least 5 samples, can also be implemented to remove more than one maximum and one minimum if desired—which would be good for burst noise. Also note that you can implement this as a sliding function or an oversampling function. A sliding function, like a moving average, slides out the oldest input and inserts the new input and then executes the function again. So, you get one output for every input. Alternatively, an oversampling function takes in an array of values, finds the mean, and then gets a fresh array of new values to process. So, every array of input samples generates only one output and then you’ll need to get a new set of input values before calculating a new mean.
Median filtering
A median filter finds the middle value in a set of samples. This may be useful for various types of noise sources. In a large set of samples, the sample array would be sorted and then the middle indexed variable would be read. For example, say we have an array of 7 samples (samples[0 to 6])—we sort them and then the median is samples[3]. Note that sorting could be problematic in a small embedded system due to execution speed so median filtering should be used judiciously. For 3 samples, the code is the same as the code example function “TruncatedMean_3”(listing 3) above. For larger groups, listing 4 shows an example piece of c code for finding the median. At the bottom of the code, you will see the setting of median based on the number of samples being odd or even. This is needed because the median for an even number of samples is defined as the average of the middle two values. Depending on your need you may want to add rounding to this average.
#define numSamples 6
int sample[numSamples] = {5,4,3,3,1,0};
int Median( int sample[], int n) {
int i = 0;
int j = 0;
int temp = 0;
int median = 0;
// First sort the array of samples
for (i = 0; i < n; ++i){
for (j = i + 1; j < n; ++j){
if (sample[i] > sample[j]){
temp = sample[i];
sample[i] = sample[j];
sample[j] = temp;
}
}
}
// If numSamples is odd, take the middle number
// If numSamples is even, average the middle two
if ( (n & 1) == 0) {
median = (sample[(n / 2) - 1] + sample[n / 2]) / 2; // Even
}
else median = sample[n / 2]; // Odd
return(median);
} Listing 4
Just as in the truncated mean filter, you can implement this as a sliding function or an oversampling function.
Majority filtering
Majority filters, also referred to as mode filters, extract the value from a set of samples that occurred the most times—majority voting. (This should not be confused with “majority element” which is the value occurring more than the number-of-samples/2.) Listing 5 shows a majority filter for 5 samples.
#define numSamples 5
int Majority( int sample[], int n) {
unsigned int count = 0;
unsigned int oldcount = 0;
int majoritysample = sample[0];
int i = 0;
int j = 0;
for (i = 0; i < numSamples; i++) {
count = 0;
for (j = i; j < numSamples; j++) {
if (sample[i] == sample[j]) count++;
}
if (count > oldcount) {
majoritysample = sample[i];
oldcount = count;
}
}
return majoritysample;
} Listing 5
The code uses two loops, the first grabbing one element at a time, and the second loop then stepping through the list and counting how many samples match the value indexed by the first loop. This second loop holds on to the highest match count, found along the way, and its sample value until the first loop steps through the entire array. If there are more than one set of sample values with the same count (i.e., {1, 2, 2, 0, 1}, two 2s and two 1s) the one found first in will be returned as the majority.
Note that the majority filter may not be applicable to typical embedded data as the dynamic range (from sensors) of the numbers would normally be 8, 10, 12 bits or greater. If the received sample uses a large portion of the dynamic range, the chance samples from a small set may be matching is minimal unless the signal being measured is very stable. Due to this dynamic range issue, a modification of the majority filter may be useful. By doing a right shift on the binary symbols, the filter can then match symbols close to each other. For example, say we have the numbers (in binary) 00100000, 00100011, 01000011, 00100001. None of these match one another—they are all different. But, if we shift them all right by 2 bits, we get 00001000, 00100011, 00010000, 00001000. Now three of them match. We can now average the original values of the matching symbols creating a modified median value.
Again, as in the truncated mean filter, you can implement this as a sliding function or an oversampling function.
Temporal filtering
This is a group of filters that react to a signal based more on time than amplitude. This will become clearer in a minute. We will refer to these different temporal filters as mode 1 through mode 4 and we begin with mode 1:
Mode 1 works by comparing the input sample to a starting filtered value (“filterout”) then, if the sample is greater than the current filtered value, the current filtered value is increased by 1. Similarly, if the sample is less than the current filtered value, the current filtered value is decreased by 1. (The increase/decrease number can also be any reasonable fixed value (e.g., 2, 5, 10, …). The output of this filter is “filterout”. You can see that the output will slowly move towards the signal level thus changes are more related to time (number of samples) than to the sample value.
Now, if we get an unwanted impulse, it can only move the output by 1 no matter what the sample’s amplitude is. This means burst noise and impulse noise is greatly mitigated. This type of filter is very good for signals that move slowly versus the sample rate. It’s works very well filtering things like temperature readings by an ADC, especially in an electrically noisy environment. It performed very well on a project I worked on to extract a very slow moving signal sent on a power line (a very noisy environment and the signal was about -120 dB below the line voltage). Also, it’s very good for creating a dynamic digital reference level such as the dc bias level of an ac signal or a signal controlling a PLL. Listing 6 illustrates the use of the mode 1 temporal filter to smooth the value “filterout”.
#define IncDecValue 1
int sample = 0;
int filterout = 512; // Starting value
call your “getsample” function here…
if (sample > filterout) filterout = filterout + IncDecValue;
else if (sample < filterout) filterout = filterout - IncDecValue;Listing 6
If the sample you are filtering is an int, you may want to do a check to make sure the filtered value doesn’t overflow/underflow and wrap around. If your sample is from a sensor or ADC that is 10 or 12 bits, this is not an issue and no check is needed.
Mode 2 is the same as Mode 1 but instead of a single value for the increase/decrease number, two or more values are used. One example is using a different increase/decrease value depending on the difference between the sample and the current filtered value (“filterout”). If they are close we use ±1, and if they are far apart we use ±10. This has been successfully used to speed up the startup of a temporal filtered control for a VCO used to match a frequency from a GPS signal.
#define IncDecValueSmall 1
#define IncDecValueBig 10
#define BigDiff 100
int sample = 0;
int filterout = 100; // Starting value
call your “getsample” function here…
if (sample > filterout) {
if ((sample - filterout) > BigDiff) filterout = filterout + IncDecValueBig;
else filterout = filterout + IncDecValueSmall;
}
else if (sample < filterout) {
if ((filterout - sample) > BigDiff) filterout = filterout - IncDecValueBig;
else filterout = filterout - IncDecValueSmall;
} Listing 7
The increment/decrement value could also be a variable that is adjusted by the firmware depending on various internal factors or directly by the user.
Mode 3 is also very similar to Mode 1 but instead of increasing by ±1, if the sample is greater than the current filtered signal, the current filtered signal is increased by a fixed percentage of the difference between the current filtered and the sample. If the sample is less than the current filtered signal, the current filtered signal is decreased by a percentage. Let’s look at an example. Say we start with a current filtered value (“filterout”) of 1000 and are using 10% change value. Then we get a new sample of 1500. This would result in an increase of 10% of 1500-100 or 50. So the current filtered value is now 1050. If the next sample is 500, and we used -10% we would get a new current filtered of 995 (1050 minus 10% of 1050-500).
#define IncPercent 10 // 10%
#define DecPercent 10 // 10%
int sample = 0;
int filterout = 1000; // Starting value
call your “getsample” function here…
if (sample > filterout) {
filterout = filterout + (((sample - filterout) * IncPercent) / 100);
}
else if (sample < filterout) {
filterout = filterout - (((filterout - sample) * DecPercent) / 100);
} Listing 8
One thing to watch for is overflow in the multiplications. You may need to use longs when making these calculations. Also note that it may be useful to make “IncPercent” and “DecPercent” a variable that may be adjusted via an internal algorithm or by user intervention.
To speed up this code on systems lacking a 1 or 2 cycle divide: instead of scaling IncPercent and DecPercent by 100, scale it by 128 ( 10 % would be ~13) Then the “/100” In the code would be “/128” which the compiler would optimize to a shift operation.
Mode 4 is comparable to Mode 3 except, like Mode 2, there are two or more levels that can come into play depending on the difference between the sample and the current output value (“filterout”). In the code in listing 9, there are two levels.
#define IncPctBig 25 // 25%
#define DecPctBig 25 // 25%
#define IncPctSmall 10 // 10%
#define DecPctSmall 10 // 10%
int sample = 0;
int filterout = 1000; // Stating value
call your “getsample” function here…
if (sample > filterout) {
if ((sample - filterout) > BigDiff) {
filterout = filterout + (((sample - filterout) * IncPctBig) / 100);
}
else filterout = filterout + (((sample - filterout) * IncPctSmall) / 100);
}
else if (sample < filterout) {
if ((filterout - sample) > BigDiff){
filterout = filterout - (((filterout - sample) * DecPctBig) / 100);
}
else filterout = filterout - (((filterout - sample) * DecPctSmall) / 100);
} Listing 9
One interesting thought is that temporal filters could also be used to generate statistics on things like impulse and burst noise. They could count the number of occurrences over a period of time and calculate stats such as impulses/sec. This could be done by adding another compare for samples being very much larger, or smaller, than the “filterout” value.
Pushbutton filtering
You may not think of this as a filter, but it is a filter for 1-bit symbols. Pushbuttons, switches, and relays have contacts that bounce open and closed for several milliseconds when pressed. If these are not filtered by external hardware (normally an RC filter) you will have to debounce (filter) it in code. There are a multitude of ways to do this. There are many discussions and much code on the web, but I think Jack Ganssle’s may have the best document at: (http://www.ganssle.com/debouncing-pt2.htm)
Using NLFs in your own projects
Although this is not a comprehensive list of NLFs, I hope this gives you a flavor of the concept. I’m sure many of you have created unique NLF’s for your own projects. Perhaps you would like to share them with others in the comments below.
Damian Bonicatto is a consulting engineer with decades of experience in embedded hardware, firmware, and system design. He holds over 30 patents.
Phoenix Bonicatto is a freelance writer.
Related Content
- Exploring software-defined radio (without the annoying RF) – Part 1
- Exploring software-defined radio (without the annoying RF)—Part 2
- Simple GPS Disciplined 10MHz Reference uses Dual PWMs
- Designing Digital Filters
- Practical applications of digital filters
googletag.cmd.push(function() { googletag.display(‘div-gpt-ad-native’); });
–>
The post Non-linear digital filters: Use cases and sample code appeared first on EDN.
