Single pole IIR filters are a quick and dirty way to filter data in time or resource limited processing systems. These are particularly useful in embedded systems that don’t have access to dedicated multipliers. These single pole IIR filters can be computed in only a handful of cycles in modern cores that have single cycle multipliers, but more limited cores without multipliers must be configured in a more cunning fashion to keep calculation time low.
The filter coefficient A is a factor of 1, assuming a stable filter. The process for calculating these filters is simple:
- w1 = xn – yn-1
- w2 = A * w1
- yn = yn-1 + w2
The multiply in this process is the tough part. The classical definition of multiplication is a series of additions. With numbers greater than 2, this process becomes inefficient very quickly. Luckily, shifts allow for quick multiplies or divides by powers of two. This can be expoited to implement multiplies or divides by other values via additions or subtractions of shifted data. This allows us to create filters with cut-off frequencies in much finer locations.
Now comes the extra credit. I was recently inspired to implement one of these filters in an extremely limited processing core, in which timing was uniquely limited by the system’s ADC sampling rate. This timing limitation motivates a limited multiplication process. As a human, finding the optimal organization of shifts, adds, and subtracts would not be hard for a given value. For example, if I required an A value of 7/16. The simple solution would be the addition of three shifted values; a shift right by 2, a shift right by 3, and a shift right by 4 could be added together to attain 7/16. After little investigation, we can see that this may be optimized into the subtraction of a shift right by 4 from a shift right by 1. In this way, we can represent a multiplication by a series of positive or negative divisions by powers of two. For example, we can represent 7/16 as [0.5, -0.0625].
This is all well and good, but now assume that we want to be able to calculate these optimal multiplies for arbitrary values of A – for arbitrary cut-off frequencies. This is of particular interest if you are creating a tool for use by others, that do not necessarily want to know the nitty-gritty of how to create the filter itself. After some thought, it can be seen that this series of scaling values can be calculated successively.
First, the necessary number of bits required for a given accuracy must be calculated. Once this has been calculated, an integer representation of the scaling value, as a fixed point number, may be calculated. After this, the scaling list discussed before can be calculated by merely successively selecting the added or subtracted dividing power of two that brings the current remainder closest to zero. For example, if we were to programmatically perform this process for a coefficient of 7/16:
7/16 – 1/16 = 6/16
7/16 – 2/16 = 5/16
7/16 – 4/16 = 3/16
7/16 – 8/16 = -1/16
7/16 – 16/16 = -9/16
It is apparent from the above calculations that subtracting 8/16, equivalent to a right shift of 1, brings the result closest to zero. This does not yet yield a sufficiently accurate result, so we will take the remainder from the last calculation and perform it again:
-1/16 + 1/16 = 0/16
-1/16 + 2/16 = 1/16
-1/16 + 4/16 = 3/16
-1/16 + 8/16 = 7/16
-1/16 + 16/16 = 15/16
With an addition of 1/16, a shift right of 4, we reach zero, giving us a result of zero. We invert the values selected to undo the negation implicit in this process to get a list of scaling values [0.5, -0.0625], just as we determined before. Lets pop the stack a few times to get back to the application layer. When applying this method with an accuracy requirement of 0.1%, and attenuation values with granularity in the thousandths, I found that the largest number of values in these scaling lists was only 5, which is great news for the application of this multiplication scheme for single pole IIR filters.