This post is a tutorial on fixed point DSP, where I provide a detailed worked example of porting a Goertzal algorithm based tone decoder from float to fixed point.
My post on Fixed Point Scaling is consistently popular. I think that’s because there just isn’t much information out there on fixed point DSP. In particular, step by step instructions on how to convert a floating point DSP algorithm into fixed point. How to engineer it. Systematically.
The Goertzal algorithm computes a 1 point Discrete Fourier Transform (DFT). It takes a time domain signal (e.g. a sine wave in noise), and works out how much power is present at a certain frequency. For Matt’s application, he will tune it to the CTSS frequency, and it will return a big number if energy is present at that frequency. Apply a threshold and you have a tone decoder.
Matt would like to run it on a little AVR micro-controller, so it must be in fixed point. Which is where the fun begins.
Here is the step by step fixed point port of the Goertzal from float to fixed point, in working C source code form. Each step runs, and the results can be compared. Lots of notes in the source, including the simple algebra I use to engineer the conversion.
I dumped the variable s into a text file and plotted it using Octave in order to determine the maximum value and work out suitable scaling for the fixed point version of s.
octave:6> load s.txt
ans = 8.6974e+05
ans = 19.730
Hmm, it looks like an unstable oscillator (i.e. keeps growing), and would need more magnitude bits bits if N or AMP was larger. Lets call it 20 bits of magnitude, add 1 for a little headroom, and one for the sign bit so that makes a suitable fixed point format Q22.10. If you are not familiar with the Q format, please see this post on Fixed Point Scaling.
Look at the scaling for the input signal x[n]. We immediately right shift discarding 6 magnitude bits. The maximum value of x[n] is 512 (9 magnitude bits) so the algorithm works just fine with the input sine wave quantised to just 3 magnitude bits! My reasoning for this is that we are trying to detect a frequency, and frequency information can be conveyed by just the sign bit (0 magnitude bits). For example a frequency counter works with just a zero crossing detector. Or Frequency Modulation (FM) – which uses non-linear amplifiers in both the transmitter and receiver that discard the magnitude information.
Beer and Original Thinking
I came up with this algebraic approach to fixed point during a 3-pint lunch when I was working at DSpace about 10 years ago. I was stuck on fixed point DSP issues that morning and the beer helped shift me off the “rail road tracks” and generate some original ideas. Well original to me at least, I’m sure other people are using similar techniques. Unfortunately when I staggered back from lunch I couldn’t think straight enough to code that day!
To explore the frequency response we wrote an Octave script pgoertzal.m. You can see a sweep from 0 to 250 Hz (typical CTSS tone range), and a close up of the area around the 91.5Hz tone we designed the detector for. You can see that the float and fixed point versions are very close. The red line is the mask for valid tone detection.
The C simulation has a bunch of automated tests. Test1 compares the various steps in the fixed point port. Test2 performs the frequency sweeps that we plot with pgoertzal.m, and Test3 evaluates various points around the red tone detector mask above, to make sure tone is (or is not detected):
david@bear:~/Desktop/goertzal$ gcc goertzal.c -o goertzal -Wall -lm && ./goertzal
float.: 3.865059e+10 PASS
step 1: 3.865059e+10 PASS
step 2: 3.795299e+10 PASS
step 3: 3.794384e+10 PASS
p: 3.719829e+10 e: 3.859250e+10 expect: 1 we got: 1 PASS
p: 9.067479e+09 e: 9.671114e+09 expect: 1 we got: 1 PASS
p: 5.038281e+09 e: 3.859631e+10 expect: 1 we got: 1 PASS
p: 4.822790e+09 e: 3.854798e+10 expect: 1 we got: 1 PASS
p: 3.700040e+08 e: 3.860324e+10 expect: 0 we got: 0 PASS
p: 3.825746e+08 e: 3.852967e+10 expect: 0 we got: 0 PASS
Fixing my HP8656 Signal Generator
While I was working on the fixed point code Matt was kindly working on my HP8656 signal generator. This had developed a fault that was popping my house circuit breakers every time I plugged it in! Matt traced the fault to a short in the input mains filter that was an integral part of the IEC power connector. He bypassed the faulty filter and the sig gen burst back into life! Thanks Matt! Now I will be able to work on the simple (uC-based) SDR radio ideas I have.
The inside of the HP8656 is really a lovely example of engineering. It sports a bunch of DIL (non surface mount) chips, including both 8085 and 6502 CPUs, lots of semi-rigid coax, copper fingers everywhere, programmable attenuators, and a linear power supply. It must have been a joy to be an engineer at HP back in the day.