Forums

Goertzel and FSK

Started by Fender123 February 14, 2012
Hi all.
Adapting Goertzel algorithm for FSK in a system with a preset sampling
rate, tones and baud rate does not always result in ideal parameters. 

Let me try to explain what I mean:
For example, consider a case with Fs=9600, tones 1650 and 1850 Hz, and baud
300. That's N=32 samples per symbol, giving too close bin indices k={ 5.5 
6.2 }. Twiddling some numbers, the tones would fit better into respective
bins if we considered something like N=58, which gives near-integer bin
indices {10 11.2} and hence less leakage. But then, N is too wide a window
when related to the symbol duration.

Would one gain anything by using N=58 tapered window on the input data and
sliding it? Or some other ideas to improve FSK tone discrimination or to
get things to fit better. 

Brian.
Warning: Mind the DSP L-plate stuck on my 'back' ;-)
On Tue, 14 Feb 2012 17:42:03 -0600, "Fender123"
<joeborg123@n_o_s_p_a_m.excite.com> wrote:

>Hi all. >Adapting Goertzel algorithm for FSK in a system with a preset sampling >rate, tones and baud rate does not always result in ideal parameters. > >Let me try to explain what I mean: >For example, consider a case with Fs=9600, tones 1650 and 1850 Hz, and baud >300. That's N=32 samples per symbol, giving too close bin indices k={ 5.5 >6.2 }. Twiddling some numbers, the tones would fit better into respective >bins if we considered something like N=58, which gives near-integer bin >indices {10 11.2} and hence less leakage. But then, N is too wide a window >when related to the symbol duration. > >Would one gain anything by using N=58 tapered window on the input data and >sliding it? Or some other ideas to improve FSK tone discrimination or to >get things to fit better. > >Brian. >Warning: Mind the DSP L-plate stuck on my 'back' ;-)
Hi Brian, What is an "L-plate?" [-Rick-]
>On Tue, 14 Feb 2012 17:42:03 -0600, "Fender123" ><joeborg123@n_o_s_p_a_m.excite.com> wrote: > >>Hi all. >>Adapting Goertzel algorithm for FSK in a system with a preset sampling >>rate, tones and baud rate does not always result in ideal parameters. >> >>Let me try to explain what I mean: >>For example, consider a case with Fs=9600, tones 1650 and 1850 Hz, and
baud
>>300. That's N=32 samples per symbol, giving too close bin indices k={ 5.5
>>6.2 }. Twiddling some numbers, the tones would fit better into
respective
>>bins if we considered something like N=58, which gives near-integer bin >>indices {10 11.2} and hence less leakage. But then, N is too wide a
window
>>when related to the symbol duration. >> >>Would one gain anything by using N=58 tapered window on the input data
and
>>sliding it? Or some other ideas to improve FSK tone discrimination or to >>get things to fit better. >> >>Brian. >>Warning: Mind the DSP L-plate stuck on my 'back' ;-) > >Hi Brian, > What is an "L-plate?" > >[-Rick-] >
Not sure if you're being sarcastic, Rick. An L-plate is what we use here in Europe affixed to a car with a learner driver at the wheel (and an instructor in the passenger's seat). Small world that it is, I should have stated that I am using your 'Understanding DSP' 2ed book re: Goertzel explanations. Brian.
On Tue, 14 Feb 2012 17:42:03 -0600, Fender123 wrote:

> Hi all. > Adapting Goertzel algorithm for FSK in a system with a preset sampling > rate, tones and baud rate does not always result in ideal parameters. > > Let me try to explain what I mean: > For example, consider a case with Fs=9600, tones 1650 and 1850 Hz, and > baud 300. That's N=32 samples per symbol, giving too close bin indices > k={ 5.5 6.2 }. Twiddling some numbers, the tones would fit better into > respective bins if we considered something like N=58, which gives > near-integer bin indices {10 11.2} and hence less leakage. But then, N > is too wide a window when related to the symbol duration. > > Would one gain anything by using N=58 tapered window on the input data > and sliding it? Or some other ideas to improve FSK tone discrimination > or to get things to fit better. > > Brian. > Warning: Mind the DSP L-plate stuck on my 'back' ;-)
For the same level of complexity as a Goertzel, you can have a real live IIR bandpass filter, with controlled damping and everything. So you could use two of those, instead. Or use a discriminator. Or use any of a number of other ways (what _is_ the cannonical Bell 103 modem demodulator?). -- Tim Wescott Control system and signal processing consulting www.wescottdesign.com
On Tue, 14 Feb 2012 17:42:03 -0600, "Fender123" wrote:

>Hi all. >Adapting Goertzel algorithm for FSK in a system with a preset sampling >rate, tones and baud rate does not always result in ideal parameters. ..(etc)
Brian: As Tim mentioned, you could search for the Bell 103 modem, which uses an old standard for 300 baud (and I believe it used closer tones). And many modems are backwards compatible, so you could find info for more recent modems as well. And, keep in mind that, while you do indeed need to distinguish the two tones, they are not simultaneous. With 32 points, you've got several cycles of the waveform to deal with (9600/1650 = 5.8... samples/cycle and 9600/1850 = 5.18... samples/cycle). And I'd probably prefer sliding DFT over Goertzel. There was a thread about this not many months ago. There are other ways of approaching the problem, but I'm not sure you need them. Kevin McGee
On Tue, 14 Feb 2012 20:55:51 -0600, "Fender123"
<joeborg123@n_o_s_p_a_m.excite.com> wrote:

   [Snipped by Lyons
>> >>Hi Brian, >> What is an "L-plate?" >> >>[-Rick-] >> > >Not sure if you're being sarcastic, Rick. An L-plate is what we use here in >Europe affixed to a car with a learner driver at the wheel (and an >instructor in the passenger's seat).
Hi, Nope, I wasn't being sarcastic. Your clever 'L-plate' remark flew right over my head. [-Rick-]
Thanks all for bearing with me. 

But, my original question was about improving Goertzel application for FSK,
and whether my suggestion makes sense or not, or other related suggestion.


I am aware of alternate signal chains, but that is not what I asked about.
Perhaps some of you guys should consider running for office ;-)

My example was taken from 'relaxed' V.21 which is similar to the old Bell
103 that Tim/Kevin mentioned. I am also wondering how to take it further
for higher-shift FSK like that used in CallerID. 

Still, I am interested to learn, or at least hear views on, how far
Goertzel can be pushed, and with what techniques.

Brian.
On Wed, 15 Feb 2012 01:37:37 -0800, kevin wrote:

> On Tue, 14 Feb 2012 17:42:03 -0600, "Fender123" wrote: > >>Hi all. >>Adapting Goertzel algorithm for FSK in a system with a preset sampling >>rate, tones and baud rate does not always result in ideal parameters. >>..(etc) > > Brian: > > As Tim mentioned, you could search for the Bell 103 modem, which uses an > old standard for 300 baud (and I believe it used closer tones). And many > modems are backwards compatible, so you could find info for more recent > modems as well. > > And, keep in mind that, while you do indeed need to distinguish the two > tones, they are not simultaneous. With 32 points, you've got several > cycles of the waveform to deal with (9600/1650 = 5.8... samples/cycle > and 9600/1850 = 5.18... samples/cycle). > > And I'd probably prefer sliding DFT over Goertzel. There was a thread > about this not many months ago. > > There are other ways of approaching the problem, but I'm not sure you > need them.
You made me check Wikipedia: The Bell 103 modem does, indeed, have 200Hz spacing with 300 baud. I'm not sure what the rational was behind the tone spacing, and I've always been curious to know if the modem was designed to be phase- continuous or not (if it were, then in theory it would be trellis modulation and you could make a more-optimal decode than just a cruddy pair of filters). I agree that a sliding DFT would be better than a couple of Goertzels, and I should have mentioned it. A pair of IIR bandpass filters wouldn't be _bad_, and in some situations may even be easier than sliding DFT, but I wouldn't be surprised if the sliding DFT didn't work better. -- My liberal friends think I'm a conservative kook. My conservative friends think I'm a liberal kook. Why am I not happy that they have found common ground? Tim Wescott, Communications, Control, Circuits & Software http://www.wescottdesign.com
On Wed, 15 Feb 2012 06:50:13 -0600, Fender123 wrote:

> Thanks all for bearing with me. > > But, my original question was about improving Goertzel application for > FSK, and whether my suggestion makes sense or not, or other related > suggestion. > > > I am aware of alternate signal chains, but that is not what I asked > about. Perhaps some of you guys should consider running for office ;-) > > My example was taken from 'relaxed' V.21 which is similar to the old > Bell 103 that Tim/Kevin mentioned. I am also wondering how to take it > further for higher-shift FSK like that used in CallerID. > > Still, I am interested to learn, or at least hear views on, how far > Goertzel can be pushed, and with what techniques.
Well, you mentioned that you were a newbie, and I think the consensus is that a Goertzel isn't the best way to approach this -- which is why we were trying to steer you away from it. The Goertzel algorithm was invented as a way to (essentially) implement a single-bin DFT on computers with a certain sort of sparse computing resources. It requires little storage, but does require at least two multiplies and two or three additions (if someone has the exact number -- chime in). It constrains you to starting your "DFT" at a certain point and ending it at a certain other point. Depending on whose literature you read, it also may or may not constrain you to setting the bin frequency to an integer fraction of the total time (you don't have to do this). In a demodulator application this means that your data clock synchronization will be complicated by the use of the algorithm compared to using some sort of band-pass filter technique. Contrast that to the two alternatives that have been proposed: the single- point sliding-window DFT, and an IIR bandpass filter. The DFT (sliding-window or not) does not contain any feedback, so quite unlike the Goertzel algorithm the quantization error in the multiplies and additions does not build up. So a single-point DFT can have much lower precision (in fact, my first experience with serious digital modem building involved a DFT whose 'multiplies' were to take the incoming samples and add them to an accumulator, subtract them, or ignore them, meaning my effective coefficients were restricted to the set {-1, 0, 1} -- and it worked damn fine). Making the DFT into a sliding-window DFT is as easy as pi, and takes only 64 words of storage -- and storage is way cheaper these days than it was when the Goertzel was invented. I'm pretty sure that a non-sliding-window DFT -- on the surface -- is going to use similar ALU resources to the Goertzel: unless you have phase synchronization you'll need to collect both an inphase bin and a quadrature bin, so the DFT will require two multiplies and two accumulates. To make the thing sliding-window you'll need a 32-point delay on two vectors and two subtractions, plus all the ALU operations involved in the indexing, so it'll be "bigger". But -- the DFT can do all of this with much reduced precision, so depending on your processor you may save big with a DFT (obviously, if you have a 32-bit processor you're not going to save much). The big advantages that you get from the use of the DFT is that the code is more clear and the precision needs are reduced. The fact that you're demodulating at the expected signal frequency is obvious from the template that you put into the demod vector, as opposed to the Goertzel where you're basically building an undamped IIR filter that responds to one frequency by "magic". The precision issue has been explained. The big advantage that you get by using the sliding window DFT is that the filter forgets what's happened one bit-period earlier. This means that you can just take the magnitude of the filters' responses, subtract them, and treat the result as an NRZ binary stream, to be synchronized to and decoded like any other baseband stream. So your clock recovery is completely separated from your data recovery. I mentioned that the Goertzel is an IIR filter: it is. A Goertzel is basically a 2nd-order bandpass (or lowpass filter, depending on the algorithm details) whose coefficients are chosen such that it has zero damping. As such, by itself, it is hardly less complicated than a 2nd- order bandpass filter _with_ damping (in the obvious realization the Goertzel has one "multiplication" by 1 that needs to be less than 1 in the damped case). If you use a damped IIR filter (and choose the damping ratio wisely), you gain the same advantage that you do with the sliding window: the filter forgets what has happened to it in the past, letting you just sample for magnitude of response and separate your clock and data recovery tasks. But shove that all aside: yes, you can use a Goertzel. Yes, you can increase the sampling rate and either taper the window (which will boost your complexity) or take other measures. One thing you could do is go ahead and design the Goertzel for a fractional frequency, and at the end of the Goertzel's window you can use both states to determine the magnitude. You could, for instance, sample at 61050Hz, which makes all the necessary ratios (sampling/baud, sampling/mark frequency and sampling/ space frequency) into integers. But doing so is kind of like putting a Model A Ford engine into a Ford Pinto (I've seen pictures), or building your stereo receiver out of vacuum tubes, or plowing your garden with an ox: it's feasible, it works as well as it ever did, but it doesn't work as well as the modern alternatives. So, if you really must use Goertzel, my recommendation is that you use the Goertzel with a fractional period (i.e., just go ahead and set the coefficients to 2 * cos(2 * pi * 1650/9600) and 2 * cos(2 * pi * 1850/9600)), then use both states of the thing at the end of a bit period to determine the amplitude in the Goertzel, and have fun. But when you come back asking how to do bit clock synchronization -- expect to be criticized for choosing the Goertzel. -- My liberal friends think I'm a conservative kook. My conservative friends think I'm a liberal kook. Why am I not happy that they have found common ground? Tim Wescott, Communications, Control, Circuits & Software http://www.wescottdesign.com
Tim Wescott <tim@seemywebsite.com> wrote:

(snip)
> You made me check Wikipedia: The Bell 103 modem does, > indeed, have 200Hz spacing with 300 baud.
> I'm not sure what the rational was behind the tone spacing, and I've > always been curious to know if the modem was designed to be phase- > continuous or not (if it were, then in theory it would be trellis > modulation and you could make a more-optimal decode than just a > cruddy pair of filters).
Ones I used to know used PLLs. The standard is pretty old, though, I believe before ones like the 565 and 567 were around. If they patented it, you could look up the patent. Maybe also in the Bell System Technical Journal. (I believe that is the name.) Stories I used to see said it should work to 450 baud or even 600 baud, but I never saw it done. Anyone remember the Motorola MC6860? Also, see: http://www.datasheetarchive.com/indexdl/Scans-000/Scans-0014750.pdf -- glen