Goertzel and FSK

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