Seeking explanation of FSK demodulator algorithm

Started by Robert Krten September 2, 2005
Hi folks,

I'm wondering if someone has a clear, simple explanation of the "classical"
FSK demodulation algorithm below?  I'm writing an article for the C Users
Journal that makes use of the algorithm, and I'd really like to be able
to include a description of the algorithm (more than just, "it does a
bunch of DSP stuff that seems to work" :-))

Basically, what I'm doing is a Bell-202 Caller ID modem in software on a
PC.  I sample at 8 kHz, and decode 1200 Hz and 2200 Hz tones.  Then, a
software UART assembles the bits, passes them on to the caller ID decoder,
and displays them on my TV.

To decode the bits, I set up four arrays; a sin table of one waveform of
1200 Hz, a cos table of the same, and a sin table of the same number of
samples worth but of a 2200 Hz waveform and another of the cos.  I
call the length of this table "ncorr".

Then, as samples arrive, I buffer them in a ring buffer, because I
need "ncorr" worth of samples in order to do the math, let's call this
a block.
For each block, I do a multiply-accumulate of each sample against
its corresponding sin/cos table entry.
These accumulates are then squared, and the 1200 Hz sum-of-squares is
compared against the 2200 Hz sum-of-squares.
Whichever sum is bigger indicates which frequency has been detected.
(There's other logic later that deals with detecting bit cell boundaries.)

When the next sample arrives, I shift all the samples by one (via ring
buffer) and perform the same math again.

Please forgive the ASCII art, but here's the math; I've used "E" for the
summation symbol (a fixed point font will help here :-))
("fm" and "fs" are the constants used to generate the MARK and SPACE
frequencies)...

          ncorr
factor0 = E     sin (fm * i) * sample (i)
          i = 0

          ncorr
factor1 = E     cos (fm * i) * sample (i)
          i = 0
          ncorr

factor2 = E     sin (fs * i) * sample (i)
          i = 0

          ncorr
factor3 = E     cos (fs * i) * sample (i)
          i = 0

current_bit = (factor0^2 + factor1^2) - (factor2^2 + factor3^2)

If current_bit > 0, it means MARK, < 0 means SPACE.

Any help anyone can shed on this is much appreciated.

Thanks in advance,
-RK


-- 
Robert Krten, Antique computer collector looking for PDP-series
minicomputers; check out their "good home" at www.parse.com/~museum
Email address is valid; click on URL mailed back to whitelist yourself.
Robert Krten wrote:
> ncorr > factor0 = E sin (fm * i) * sample (i) > i = 0 > > ncorr > factor1 = E cos (fm * i) * sample (i) > i = 0 > ncorr > > factor2 = E sin (fs * i) * sample (i) > i = 0 > > ncorr > factor3 = E cos (fs * i) * sample (i) > i = 0 > > current_bit = (factor0^2 + factor1^2) - (factor2^2 + factor3^2) > > If current_bit > 0, it means MARK, < 0 means SPACE. >
This is doing a two-bin Discrete Fourier Transform (DFT) at the mark and space frequencies, computing the magnitude of those two frequency components, and then comparing them. I'm not an expert, but I don't think this is really the "classic approach" to FSK demod. -- Jim Thomas Principal Applications Engineer Bittware, Inc jthomas@bittware.com http://www.bittware.com (603) 226-0404 x536 Never ascribe to malice that which is adequately explained by incompetence. - Napoleon Bonaparte
Jim Thomas wrote:

> Robert Krten wrote: > >> ncorr >> factor0 = E sin (fm * i) * sample (i) >> i = 0 >> >> ncorr >> factor1 = E cos (fm * i) * sample (i) >> i = 0 >> ncorr >> >> factor2 = E sin (fs * i) * sample (i) >> i = 0 >> >> ncorr >> factor3 = E cos (fs * i) * sample (i) >> i = 0 >> >> current_bit = (factor0^2 + factor1^2) - (factor2^2 + factor3^2) >> >> If current_bit > 0, it means MARK, < 0 means SPACE. >> > > This is doing a two-bin Discrete Fourier Transform (DFT) at the mark and > space frequencies, computing the magnitude of those two frequency > components, and then comparing them. I'm not an expert, but I don't > think this is really the "classic approach" to FSK demod. >
I'd say that it's implementing a pair of matched filters at mark and space; not only is the terminology is different but it indicates some improvement (not much) that could be taken if the originating signal takes FSK and filters it before applying it to the phone line. The "classic" approach to FSK demod implements these two filters using big capacitors and audio-frequency coils, followed by vacuum tube amplifiers and relays. Block diagrams of the two approaches wouldn't be that different. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com
Jim Thomas <jthomas@bittware.com> wrote:
> Robert Krten wrote: > > ncorr > > factor0 = E sin (fm * i) * sample (i) > > i = 0 > > > > ncorr > > factor1 = E cos (fm * i) * sample (i) > > i = 0 > > ncorr > > > > factor2 = E sin (fs * i) * sample (i) > > i = 0 > > > > ncorr > > factor3 = E cos (fs * i) * sample (i) > > i = 0 > > > > current_bit = (factor0^2 + factor1^2) - (factor2^2 + factor3^2) > > > > If current_bit > 0, it means MARK, < 0 means SPACE. > >
> This is doing a two-bin Discrete Fourier Transform (DFT) at the mark and > space frequencies, computing the magnitude of those two frequency > components, and then comparing them. I'm not an expert, but I don't > think this is really the "classic approach" to FSK demod.
Ok, thanks for that -- one follow-on "dumb" question -- do I need to calculate the factors for the higher frequency for "ncorr" samples, or should I only really be calculating them for less samples, corresponding to one complete waveform? Thanks! -RK -- Robert Krten, Antique computer collector looking for PDP-series minicomputers; check out their "good home" at www.parse.com/~museum Email address is valid; click on URL mailed back to whitelist yourself.
Tim Wescott <tim@seemywebsite.com> wrote:
> Jim Thomas wrote:
> > Robert Krten wrote: > > > >> ncorr > >> factor0 = E sin (fm * i) * sample (i) > >> i = 0 > >> > >> ncorr > >> factor1 = E cos (fm * i) * sample (i) > >> i = 0 > >> ncorr > >> > >> factor2 = E sin (fs * i) * sample (i) > >> i = 0 > >> > >> ncorr > >> factor3 = E cos (fs * i) * sample (i) > >> i = 0 > >> > >> current_bit = (factor0^2 + factor1^2) - (factor2^2 + factor3^2) > >> > >> If current_bit > 0, it means MARK, < 0 means SPACE. > >> > > > > This is doing a two-bin Discrete Fourier Transform (DFT) at the mark and > > space frequencies, computing the magnitude of those two frequency > > components, and then comparing them. I'm not an expert, but I don't > > think this is really the "classic approach" to FSK demod. > > > I'd say that it's implementing a pair of matched filters at mark and > space; not only is the terminology is different but it indicates some > improvement (not much) that could be taken if the originating signal > takes FSK and filters it before applying it to the phone line.
I'm not 100% sure I follow you; but as I understand it, the phone company generates FSK on the phone line *with nothing else* -- so I'm not fishing for this signal in a sea of noise, it's the only thing on the line at that point.
> The "classic" approach to FSK demod implements these two filters using > big capacitors and audio-frequency coils, followed by vacuum tube > amplifiers and relays. Block diagrams of the two approaches wouldn't be > that different.
:-) Cheers, -RK -- Robert Krten, Antique computer collector looking for PDP-series minicomputers; check out their "good home" at www.parse.com/~museum Email address is valid; click on URL mailed back to whitelist yourself.
Robert Krten wrote:

> Tim Wescott <tim@seemywebsite.com> wrote: > >>Jim Thomas wrote: > > >>>Robert Krten wrote: >>> >>> >>>> ncorr >>>>factor0 = E sin (fm * i) * sample (i) >>>> i = 0 >>>> >>>> ncorr >>>>factor1 = E cos (fm * i) * sample (i) >>>> i = 0 >>>> ncorr >>>> >>>>factor2 = E sin (fs * i) * sample (i) >>>> i = 0 >>>> >>>> ncorr >>>>factor3 = E cos (fs * i) * sample (i) >>>> i = 0 >>>> >>>>current_bit = (factor0^2 + factor1^2) - (factor2^2 + factor3^2) >>>> >>>>If current_bit > 0, it means MARK, < 0 means SPACE. >>>> >>> >>>This is doing a two-bin Discrete Fourier Transform (DFT) at the mark and >>>space frequencies, computing the magnitude of those two frequency >>>components, and then comparing them. I'm not an expert, but I don't >>>think this is really the "classic approach" to FSK demod. >>> >> >>I'd say that it's implementing a pair of matched filters at mark and >>space; not only is the terminology is different but it indicates some >>improvement (not much) that could be taken if the originating signal >>takes FSK and filters it before applying it to the phone line. > > > I'm not 100% sure I follow you; but as I understand it, the phone company > generates FSK on the phone line *with nothing else* -- so I'm not fishing > for this signal in a sea of noise, it's the only thing on the line at that > point. >
The phone lines are bandlimited, so you only get something like 300Hz to 3kHz -- I was talking about that filtering, which tends to smear signals out (not significantly for the 1200 baud I think you're talking about). Now that you mention it, however, the phone company _always_ throws in some noise for free, although it's much less now that they've gone all digital.
> >>The "classic" approach to FSK demod implements these two filters using >>big capacitors and audio-frequency coils, followed by vacuum tube >>amplifiers and relays. Block diagrams of the two approaches wouldn't be >>that different. > > > :-) > > Cheers, > -RK
-- Tim Wescott Wescott Design Services http://www.wescottdesign.com
Robert Krten wrote:

> Jim Thomas <jthomas@bittware.com> wrote: > >>Robert Krten wrote: >> >>> ncorr >>>factor0 = E sin (fm * i) * sample (i) >>> i = 0 >>> >>> ncorr >>>factor1 = E cos (fm * i) * sample (i) >>> i = 0 >>> ncorr >>> >>>factor2 = E sin (fs * i) * sample (i) >>> i = 0 >>> >>> ncorr >>>factor3 = E cos (fs * i) * sample (i) >>> i = 0 >>> >>>current_bit = (factor0^2 + factor1^2) - (factor2^2 + factor3^2) >>> >>>If current_bit > 0, it means MARK, < 0 means SPACE. >>> > > >>This is doing a two-bin Discrete Fourier Transform (DFT) at the mark and >>space frequencies, computing the magnitude of those two frequency >>components, and then comparing them. I'm not an expert, but I don't >>think this is really the "classic approach" to FSK demod. > > > Ok, thanks for that -- one follow-on "dumb" question -- do I need to calculate > the factors for the higher frequency for "ncorr" samples, or should I only > really be calculating them for less samples, corresponding to one complete > waveform? > > Thanks! > -RK
To make it a matched filter you should select ncorr to match the baud rate -- so for 1200 baud ncorr should correspond to 833us. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com
Robert Krten wrote:

> Jim Thomas <jthomas@bittware.com> wrote: > >>Robert Krten wrote: >> >>> ncorr >>>factor0 = E sin (fm * i) * sample (i) >>> i = 0 >>> >>> ncorr >>>factor1 = E cos (fm * i) * sample (i) >>> i = 0 >>> ncorr >>> >>>factor2 = E sin (fs * i) * sample (i) >>> i = 0 >>> >>> ncorr >>>factor3 = E cos (fs * i) * sample (i) >>> i = 0 >>> >>>current_bit = (factor0^2 + factor1^2) - (factor2^2 + factor3^2) >>> >>>If current_bit > 0, it means MARK, < 0 means SPACE. >>> > > >>This is doing a two-bin Discrete Fourier Transform (DFT) at the mark and >>space frequencies, computing the magnitude of those two frequency >>components, and then comparing them. I'm not an expert, but I don't >>think this is really the "classic approach" to FSK demod. > > > Ok, thanks for that -- one follow-on "dumb" question -- do I need to calculate > the factors for the higher frequency for "ncorr" samples, or should I only > really be calculating them for less samples, corresponding to one complete > waveform? > > Thanks! > -RK
To make it a matched filter you should select ncorr to match the baud rate -- so for 1200 baud ncorr should correspond to 833us. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com
Robert Krten wrote:

> Tim Wescott <tim@seemywebsite.com> wrote: > >>Jim Thomas wrote: > > >>>Robert Krten wrote: >>> >>> >>>> ncorr >>>>factor0 = E sin (fm * i) * sample (i) >>>> i = 0 >>>> >>>> ncorr >>>>factor1 = E cos (fm * i) * sample (i) >>>> i = 0 >>>> ncorr >>>> >>>>factor2 = E sin (fs * i) * sample (i) >>>> i = 0 >>>> >>>> ncorr >>>>factor3 = E cos (fs * i) * sample (i) >>>> i = 0 >>>> >>>>current_bit = (factor0^2 + factor1^2) - (factor2^2 + factor3^2) >>>> >>>>If current_bit > 0, it means MARK, < 0 means SPACE. >>>> >>> >>>This is doing a two-bin Discrete Fourier Transform (DFT) at the mark and >>>space frequencies, computing the magnitude of those two frequency >>>components, and then comparing them. I'm not an expert, but I don't >>>think this is really the "classic approach" to FSK demod. >>> >> >>I'd say that it's implementing a pair of matched filters at mark and >>space; not only is the terminology is different but it indicates some >>improvement (not much) that could be taken if the originating signal >>takes FSK and filters it before applying it to the phone line. > > > I'm not 100% sure I follow you; but as I understand it, the phone company > generates FSK on the phone line *with nothing else* -- so I'm not fishing > for this signal in a sea of noise, it's the only thing on the line at that > point. >
The phone lines are bandlimited, so you only get something like 300Hz to 3kHz -- I was talking about that filtering, which tends to smear signals out (not significantly for the 1200 baud I think you're talking about). Now that you mention it, however, the phone company _always_ throws in some noise for free, although it's much less now that they've gone all digital.
> >>The "classic" approach to FSK demod implements these two filters using >>big capacitors and audio-frequency coils, followed by vacuum tube >>amplifiers and relays. Block diagrams of the two approaches wouldn't be >>that different. > > > :-) > > Cheers, > -RK
-- Tim Wescott Wescott Design Services http://www.wescottdesign.com
Tim Wescott <tim@seemywebsite.com> wrote:
> Jim Thomas wrote:
> > Robert Krten wrote: > > > >> ncorr > >> factor0 = E sin (fm * i) * sample (i) > >> i = 0 > >> > >> ncorr > >> factor1 = E cos (fm * i) * sample (i) > >> i = 0 > >> ncorr > >> > >> factor2 = E sin (fs * i) * sample (i) > >> i = 0 > >> > >> ncorr > >> factor3 = E cos (fs * i) * sample (i) > >> i = 0 > >> > >> current_bit = (factor0^2 + factor1^2) - (factor2^2 + factor3^2) > >> > >> If current_bit > 0, it means MARK, < 0 means SPACE. > >> > > > > This is doing a two-bin Discrete Fourier Transform (DFT) at the mark and > > space frequencies, computing the magnitude of those two frequency > > components, and then comparing them. I'm not an expert, but I don't > > think this is really the "classic approach" to FSK demod. > > > I'd say that it's implementing a pair of matched filters at mark and > space; not only is the terminology is different but it indicates some > improvement (not much) that could be taken if the originating signal > takes FSK and filters it before applying it to the phone line.
I'm not 100% sure I follow you; but as I understand it, the phone company generates FSK on the phone line *with nothing else* -- so I'm not fishing for this signal in a sea of noise, it's the only thing on the line at that point.
> The "classic" approach to FSK demod implements these two filters using > big capacitors and audio-frequency coils, followed by vacuum tube > amplifiers and relays. Block diagrams of the two approaches wouldn't be > that different.
:-) Cheers, -RK -- Robert Krten, Antique computer collector looking for PDP-series minicomputers; check out their "good home" at www.parse.com/~museum Email address is valid; click on URL mailed back to whitelist yourself.
Jim Thomas <jthomas@bittware.com> wrote:
> Robert Krten wrote: > > ncorr > > factor0 = E sin (fm * i) * sample (i) > > i = 0 > > > > ncorr > > factor1 = E cos (fm * i) * sample (i) > > i = 0 > > ncorr > > > > factor2 = E sin (fs * i) * sample (i) > > i = 0 > > > > ncorr > > factor3 = E cos (fs * i) * sample (i) > > i = 0 > > > > current_bit = (factor0^2 + factor1^2) - (factor2^2 + factor3^2) > > > > If current_bit > 0, it means MARK, < 0 means SPACE. > >
> This is doing a two-bin Discrete Fourier Transform (DFT) at the mark and > space frequencies, computing the magnitude of those two frequency > components, and then comparing them. I'm not an expert, but I don't > think this is really the "classic approach" to FSK demod.
Ok, thanks for that -- one follow-on "dumb" question -- do I need to calculate the factors for the higher frequency for "ncorr" samples, or should I only really be calculating them for less samples, corresponding to one complete waveform? Thanks! -RK -- Robert Krten, Antique computer collector looking for PDP-series minicomputers; check out their "good home" at www.parse.com/~museum Email address is valid; click on URL mailed back to whitelist yourself.
Jim Thomas wrote:

> Robert Krten wrote: > >> ncorr >> factor0 = E sin (fm * i) * sample (i) >> i = 0 >> >> ncorr >> factor1 = E cos (fm * i) * sample (i) >> i = 0 >> ncorr >> >> factor2 = E sin (fs * i) * sample (i) >> i = 0 >> >> ncorr >> factor3 = E cos (fs * i) * sample (i) >> i = 0 >> >> current_bit = (factor0^2 + factor1^2) - (factor2^2 + factor3^2) >> >> If current_bit > 0, it means MARK, < 0 means SPACE. >> > > This is doing a two-bin Discrete Fourier Transform (DFT) at the mark and > space frequencies, computing the magnitude of those two frequency > components, and then comparing them. I'm not an expert, but I don't > think this is really the "classic approach" to FSK demod. >
I'd say that it's implementing a pair of matched filters at mark and space; not only is the terminology is different but it indicates some improvement (not much) that could be taken if the originating signal takes FSK and filters it before applying it to the phone line. The "classic" approach to FSK demod implements these two filters using big capacitors and audio-frequency coils, followed by vacuum tube amplifiers and relays. Block diagrams of the two approaches wouldn't be that different. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com
Robert Krten wrote:
> ncorr > factor0 = E sin (fm * i) * sample (i) > i = 0 > > ncorr > factor1 = E cos (fm * i) * sample (i) > i = 0 > ncorr > > factor2 = E sin (fs * i) * sample (i) > i = 0 > > ncorr > factor3 = E cos (fs * i) * sample (i) > i = 0 > > current_bit = (factor0^2 + factor1^2) - (factor2^2 + factor3^2) > > If current_bit > 0, it means MARK, < 0 means SPACE. >
This is doing a two-bin Discrete Fourier Transform (DFT) at the mark and space frequencies, computing the magnitude of those two frequency components, and then comparing them. I'm not an expert, but I don't think this is really the "classic approach" to FSK demod. -- Jim Thomas Principal Applications Engineer Bittware, Inc jthomas@bittware.com http://www.bittware.com (603) 226-0404 x536 Never ascribe to malice that which is adequately explained by incompetence. - Napoleon Bonaparte
Hi folks,

I'm wondering if someone has a clear, simple explanation of the "classical"
FSK demodulation algorithm below?  I'm writing an article for the C Users
Journal that makes use of the algorithm, and I'd really like to be able
to include a description of the algorithm (more than just, "it does a
bunch of DSP stuff that seems to work" :-))

Basically, what I'm doing is a Bell-202 Caller ID modem in software on a
PC.  I sample at 8 kHz, and decode 1200 Hz and 2200 Hz tones.  Then, a
software UART assembles the bits, passes them on to the caller ID decoder,
and displays them on my TV.

To decode the bits, I set up four arrays; a sin table of one waveform of
1200 Hz, a cos table of the same, and a sin table of the same number of
samples worth but of a 2200 Hz waveform and another of the cos.  I
call the length of this table "ncorr".

Then, as samples arrive, I buffer them in a ring buffer, because I
need "ncorr" worth of samples in order to do the math, let's call this
a block.
For each block, I do a multiply-accumulate of each sample against
its corresponding sin/cos table entry.
These accumulates are then squared, and the 1200 Hz sum-of-squares is
compared against the 2200 Hz sum-of-squares.
Whichever sum is bigger indicates which frequency has been detected.
(There's other logic later that deals with detecting bit cell boundaries.)

When the next sample arrives, I shift all the samples by one (via ring
buffer) and perform the same math again.

Please forgive the ASCII art, but here's the math; I've used "E" for the
summation symbol (a fixed point font will help here :-))
("fm" and "fs" are the constants used to generate the MARK and SPACE
frequencies)...

          ncorr
factor0 = E     sin (fm * i) * sample (i)
          i = 0

          ncorr
factor1 = E     cos (fm * i) * sample (i)
          i = 0
          ncorr

factor2 = E     sin (fs * i) * sample (i)
          i = 0

          ncorr
factor3 = E     cos (fs * i) * sample (i)
          i = 0

current_bit = (factor0^2 + factor1^2) - (factor2^2 + factor3^2)

If current_bit > 0, it means MARK, < 0 means SPACE.

Any help anyone can shed on this is much appreciated.

Thanks in advance,
-RK


-- 
Robert Krten, Antique computer collector looking for PDP-series
minicomputers; check out their "good home" at www.parse.com/~museum
Email address is valid; click on URL mailed back to whitelist yourself.