For the Mesh Potato spectrum analyser I used a filter to smooth the signal strength estimates. There isn’t much written about fixed point DSP, so I decided to describe how I built the filter. This post is a mini tutorial on fixed point DSP.
Now don’t get scared, if you understand year 8 algebra, you can follow this post.
First of all, why fixed point? Well it runs faster on CPUs that don’t have floating point hardware. For example low cost DSP chips and the SoC router chip we use for the Mesh Potato. These CPUs do integer maths OK, but are slow at floating point maths as they need to call library functions. Kernel mode code (like the Linux kernel) also avoids floating point maths, even if the CPU has floating point support.
The low pass filter is a fixed point Infinite Impulse Response (IIR) filter. Now that sounds scary. Lets break it into small pieces. The filter I used look like this:
y(n) = 0.875*y(n-1) + 0.125*x(n).
This means “take 1/8 of the current input sample x(n) and add it to 7/8 of the previous output sample y(n-1). This gives us the new output sample y(n)”. So if we feed a x(n) =1 (a DC signal, top plot) into it, we get y(n) (bottom plot):
See how y(n) responds slowly to the new input? That’s the averaging or low pass filter effect. If we feed an impulse into it (x(0)=1, x(n)=0 after that), we get:
This is known as the impulse response. Because of the y(n) = 0.875*y(n-1) feedback loop the impulse response for this filter actually goes on forever. It gets smaller and smaller but never quite gets to zero as 0.875 of a very small number is still a number greater than 0. So in DSP-speak we call it an infinite impulse response (IIR) filter. I generated these plots with this Octave script. GNU Octave is very cool software for experimenting with DSP.
Fixed Point Numbers
Fixed point DSP is the art of representing real numbers with integers. Lets say we have 16 bit integers. We usually say this represents the numbers of 32767 to -32768. The binary codes map to numbers like this:
|0000 0000 0000 0001||1|
|0000 0000 0000 0010||2|
|0111 1111 1111 1111||32767|
|1111 1111 1111 1111||-32767|
However if we like, it could represent any range of numbers with 2^16 discrete values. For example lets assume the LSB in the integer represents 0.125, rather than 1. Then we get something like:
|0000 0000 0000 0001||0.125|
|0000 0000 0000 0010||0.250|
|0000 0000 0000 1000||1.000|
|0000 0000 0000 1001||1.125|
|0111 1111 1111 1111||4095.875|
|1111 1111 1111 1111||-4096.000|
This is a fixed point number, as the position of the decimal point is always fixed. One form of describing a fixed point number is Q format. For example the first table is “Q16.0″ (regular integers), the second table “Q13.3″. Q-notation tells you how many bits are to the right and left of the decimal point.
Fixed Point Scaling
Now lets convert the IIR filter described above to fixed point. The filter is used for averaging Wifi signal strengths that are numbers like x = -65, -60, -63 etc. The averaged output from the filter is y. I know that for this application (filtering signal strengths) the x numbers are always in the range of 0 to -128. So for this example I have decided to use Q13.3 format. This allows me to represent numbers between 0 to -128 and gives me a few fractional bits to improve the accuracy of my maths.
However I could have chosen other formats. For example Q8.8 would be a better choice, as this lets me represent numbers between 127.996 and -128.0 and gives me 8 fractional bits to make my maths nice and precise. However I only figured this out while I was writing this post. As I am too lazy to change the actual code I am sticking to Q13.3 for this example.
I’ll start with floating point C code and work my way through using simple algebra. We start with y and x as floats:
y = 0.875*y + 0.125*x
Now in Q13.3 format, a 1.0 is represented by binary 1000 or an integer “code” of 2^3 = 8. So we need to multiply everything by 8. Another way of looking at this is for Q13.3 we shift everything left 3 bits. This gives us:
8y = 0.875*(8y) + x
Note how I have kept the 8 close to the y above. This is because they are the same variable in the C code, and must have the same fixed point format. This clearer if we substitute z=8y:
z = 0.875*z + x
Now because I cheated and used 0.875 as the filter coefficient we can re-arrange:
z = (1 - 0.125)*z + x
z = z - 0.125*z + x
Multiplying by 0.125 is the same as a 3 bit right shift. Shifts are efficient ways to do divides in fixed point. Now you can see why I chose 0.875 = 1 – 0.125 as the filter coefficient, it maps to a nice power of two in the filter implementation. So anyway by converting the multiply to a shift we get:
z = z - z>>3 + x
So that’s the actual C code implementation of the fixed point IIR filter in Q3.13, it’s equivalent to the floating point C code “y = y*0.875 +0.125*x”. We can extract the filtered output y:
z = 8y
y = z/8
y = z >> 3
As z is in Q13.3 we can convert it to y in Q16.0 by a right shift.
For a long time I did fixed point scaling by guesswork, but I like the approach above as I can use algebra to get an engineered solution faster. I tend to put the algebra above in C source comments so that the fixed point code looks less like Klingon when I have to maintain it.
The general approach for fixed point porting is to first choose a Q format to suit the dynamic range of the floating point signal you are working with. For example Q13.3 (or even Q8.8) suits the signal strength values above. As you convert each variable to fixed point, test carefully (say with unit tests) as each fragment is ported.