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.

This weekend I’ve been working with Matt (VK5ZM) who is building a CTSS tone decoder board for FM repeaters. Matt is using the efficient, but difficult to spell Goertzal algorithm.

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

octave:7> plot(s)

octave:8> max(s)

ans = 8.6974e+05

octave:10> log2(max(s))

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!

**Automated Testing**

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

Test 1:

ideal.: 3.865471e+10

float.: 3.865059e+10 PASS

step 1: 3.865059e+10 PASS

step 2: 3.795299e+10 PASS

step 3: 3.794384e+10 PASS

Test 2:

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.

Filters with integral IEC connectors and (if you want one) power switches can be found on eBay for a few bucks, just look for “Corcom”.

BTW, if your MOV fails shorted, it’s usually becuase there was a big enough transient for you to need it.

Good point, and it’s a valuable piece of kit. I’ll buy a new MOV and solder it in.

One of the beauties of using fixed point for a Goertzel transform is you can easily and efficiently make a sliding window form of it. Then you get a continuous estimate instead of a block by block one, which is often useful. Floating point just won’t let you remove from the end of the window exactly what you injected at the start.

That is something we’ll definitely be looking at.

I’ve just got a bit more hardware to solder together for a test bed, then we can see how fast the fixed point algorithm is cf the floating point implementation.

Good idea Steve. I also think it’s possible to implement a moving exponential window rather than a rectangular one which might be useful if you need some windowing (we didn’t in this case).

There is no MOV in this filter and it’s not entirely clear what’s failed (sealed metal can). The caps should have been X2 or Y2 safety rated and should have failed open circuit, not short. It’s more like the common mode choke has gotten hot, probably from mains THD or flat topping which has then overheated and the insulation resistance reduced. There was a fair amount of difficult to move gunk that had oozed out of the IEC filter.

Fitting a MOV won’t hurt but will be slightly challenging to fit. Getting that PSU assembly out of the case is tricky with the hardline and internal DB15 connector.

The power supply in this unit is a transformer / linear regulator so fairly robust without any additional protection. I’d think that the EMC filter is there to just reduce the phase noise of the oscillator output from mains noise like ripple tones etc.

Was fun to look inside and patch the unit up so David can get cracking on his new SDR ideas.

Thanks Matt for pointing that out. It is a pleasure to work with some one so skilled in hardware! I learnt a lot by watching you and also by reading your comment above.

Cheers,

David

I have used Goertzels/Geortzals a few times before. One trick to improve accuracy in fixed point is changing the value of N, to improve the accuracy of the coefficient representation. I’ve got some code that searches for the best value of N, to give the best accuracy. Also adjusting the sample rate can also help. Mike