freq error estimation of GMSK (GSM) signals

Hi all

I'm looking at some code that is supposed to be estimating (coarsely) the
frequency error of a GSM signal (that is basically a bursted GMSK modulated
signal).
The algorithm that I gleaned out of the code is as follows (in pseudo code
with some matlab notations).

input is baseband (I,Q) data.
I_temp = I.^2 - Q.^2
Q_temp = I.*Q

fft_out = fft(I_temp + j*Q_temp);

CenterPoint = mod(floor(270833/2/fft_resolution), Nfft)    %270833 is the
GSM symbol rate

Search for peak power +/- 1000 points around CenterPoint of fft_out and
record PeakPowerPoint

CoarseFreqError = (PeakPowerPoint - CenterPoint)*fft_resolution/2;

I'm hoping someone can shed some light on this algorithm and how and why it
works.

Here is my interpretation of it,
The first step seems to be squaring of the complex baseband signal (I+jQ)^2
The constellation of a GMSK signal has 4 points with pi/4 offsets (well, a
GSM signal ends up with more points on the constellation due to ISI I
guess).
By squaring the signal, the constellation folds into 2 points (on a line).
Taking an FFT of this results in 2 peaks that correspond to the input signal
frequency and since we know where an ideal signal would be located we can
then get the delta_frequency from ideal??
I'm not sure I'm making much sense and I can't find any references that come
close.
BTW, you can consider me to be a beginner when it comes to digital
(de)modulation and digital communications in general.

I suspect this is a "Oh yeah - here is how it works..." kinda deal for
someone like Eric. I'd appreciate any pointers or explanation from anyone.

Note - the algorithm then goes on to use this coarse freq estimate, multiply
the raw baseband data with a complex exponential that uses this coarse
estimate (thereby removing the coarse error), repeats this squaring
operation to arrive at a fine freq error estimate.

Cheers
Bhaskar

BTW, does anyone have a electronic copy of Peter Kootsookos' paper on
frequency estimation? All links I could find to his web page don't work
anymore - so I'm hoping one of you downloaded a pdf at some point.

Cheers
Bhaskar

"Bhaskar Thiagarajan" <bhaskart@deja.com> wrote in message
news:3ajqofF6acgpjU1@individual.net...
> Hi all
>
> I'm looking at some code that is supposed to be estimating (coarsely) the
> frequency error of a GSM signal (that is basically a bursted GMSK
modulated
> signal).
> The algorithm that I gleaned out of the code is as follows (in pseudo code
> with some matlab notations).
>
> input is baseband (I,Q) data.
> I_temp = I.^2 - Q.^2
> Q_temp = I.*Q
>
> fft_out = fft(I_temp + j*Q_temp);
>
> CenterPoint = mod(floor(270833/2/fft_resolution), Nfft)    %270833 is the
> GSM symbol rate
>
> Search for peak power +/- 1000 points around CenterPoint of fft_out and
> record PeakPowerPoint
>
> CoarseFreqError = (PeakPowerPoint - CenterPoint)*fft_resolution/2;
>
> I'm hoping someone can shed some light on this algorithm and how and why
it
> works.
>
> Here is my interpretation of it,
> The first step seems to be squaring of the complex baseband signal
(I+jQ)^2
> The constellation of a GMSK signal has 4 points with pi/4 offsets (well, a
> GSM signal ends up with more points on the constellation due to ISI I
> guess).
> By squaring the signal, the constellation folds into 2 points (on a line).
> Taking an FFT of this results in 2 peaks that correspond to the input
signal
> frequency and since we know where an ideal signal would be located we can
> then get the delta_frequency from ideal??
> I'm not sure I'm making much sense and I can't find any references that
come
> close.
> BTW, you can consider me to be a beginner when it comes to digital
> (de)modulation and digital communications in general.
>
> I suspect this is a "Oh yeah - here is how it works..." kinda deal for
> someone like Eric. I'd appreciate any pointers or explanation from anyone.
>
> Note - the algorithm then goes on to use this coarse freq estimate,
multiply
> the raw baseband data with a complex exponential that uses this coarse
> estimate (thereby removing the coarse error), repeats this squaring
> operation to arrive at a fine freq error estimate.
>
> Cheers
> Bhaskar
>
>
>

Bhaskar Thiagarajan wrote:

> I'm looking at some code that is supposed to be estimating (coarsely)
the
> frequency error of a GSM signal (that is basically a bursted GMSK
modulated
> signal).
> The algorithm that I gleaned out of the code is as follows (in pseudo
code
> with some matlab notations).
>
> input is baseband (I,Q) data.
> I_temp = I.^2 - Q.^2
> Q_temp = I.*Q
>
> fft_out = fft(I_temp + j*Q_temp);
>
> CenterPoint = mod(floor(270833/2/fft_resolution), Nfft)    %270833 is
the
> GSM symbol rate
>
> Search for peak power +/- 1000 points around CenterPoint of fft_out
and
> record PeakPowerPoint
>
> CoarseFreqError = (PeakPowerPoint - CenterPoint)*fft_resolution/2;
>
> I'm hoping someone can shed some light on this algorithm and how and
why it
> works.

I = cos(blah)
Q = sin(blah)

I.^2 - Q.^2 = cos^2(blah) - sin^2(blah) = cos(2*blah)

I.*Q = 0.5*sin(2*blah)

Are you sure there is not a 2 in front of I.*Q?

> Here is my interpretation of it,
> The first step seems to be squaring of the complex baseband signal
(I+jQ)^2
> The constellation of a GMSK signal has 4 points with pi/4 offsets
(well, a
> GSM signal ends up with more points on the constellation due to ISI I
> guess).
> By squaring the signal, the constellation folds into 2 points (on a
line).
> Taking an FFT of this results in 2 peaks that correspond to the input
signal
> frequency and since we know where an ideal signal would be located we
can
> then get the delta_frequency from ideal??
> I'm not sure I'm making much sense and I can't find any references
that come
> close.
> BTW, you can consider me to be a beginner when it comes to digital
> (de)modulation and digital communications in general.
>
> I suspect this is a "Oh yeah - here is how it works..." kinda deal
for
> someone like Eric. I'd appreciate any pointers or explanation from
anyone.
>
> Note - the algorithm then goes on to use this coarse freq estimate,
multiply
> the raw baseband data with a complex exponential that uses this
coarse
> estimate (thereby removing the coarse error), repeats this squaring
> operation to arrive at a fine freq error estimate.

OK.  It doesn't seem very refined... but if it works, what the hey.

Ciao,

Peter K.

Bhaskar Thiagarajan wrote:

> BTW, does anyone have a electronic copy of Peter Kootsookos' paper on
> frequency estimation? All links I could find to his web page don't
> work anymore - so I'm hoping one of you downloaded a pdf at some
> point.

Still looking at the options for hosting.

The report you're after is available from UQ's eprint archive:

http://eprint.uq.edu.au/archive/00000955/

Ciao,

Peter K.

On Fri, 25 Mar 2005 17:03:37 -0800, "Bhaskar Thiagarajan"
<bhaskart@deja.com> wrote:

>Hi all
>
>I'm looking at some code that is supposed to be estimating (coarsely) the
>frequency error of a GSM signal (that is basically a bursted GMSK modulated
>signal).
>The algorithm that I gleaned out of the code is as follows (in pseudo code
>with some matlab notations).
>
>input is baseband (I,Q) data.
>I_temp = I.^2 - Q.^2
>Q_temp = I.*Q
>
>fft_out = fft(I_temp + j*Q_temp);
>
>CenterPoint = mod(floor(270833/2/fft_resolution), Nfft)    %270833 is the
>GSM symbol rate
>
>Search for peak power +/- 1000 points around CenterPoint of fft_out and
>record PeakPowerPoint
>
>CoarseFreqError = (PeakPowerPoint - CenterPoint)*fft_resolution/2;
>
>I'm hoping someone can shed some light on this algorithm and how and why it
>works.
>
>Here is my interpretation of it,
>The first step seems to be squaring of the complex baseband signal (I+jQ)^2
>The constellation of a GMSK signal has 4 points with pi/4 offsets (well, a
>GSM signal ends up with more points on the constellation due to ISI I
>guess).
>By squaring the signal, the constellation folds into 2 points (on a line).
>Taking an FFT of this results in 2 peaks that correspond to the input signal
>frequency and since we know where an ideal signal would be located we can
>then get the delta_frequency from ideal??

Yeah, that seems to be basically it, but the squaring results in a
decrease in SNR.

Are you trying to get initial offset from a burst or track frequency
through a signal?

I don't recall what the GSM bursts look like but usually the preamble
in a bursty system is designed to allow this sort of thing to be
estimated well enough.


>I'm not sure I'm making much sense and I can't find any references that come
>close.
>BTW, you can consider me to be a beginner when it comes to digital
>(de)modulation and digital communications in general.
>
>I suspect this is a "Oh yeah - here is how it works..." kinda deal for
>someone like Eric. I'd appreciate any pointers or explanation from anyone.
>
>Note - the algorithm then goes on to use this coarse freq estimate, multiply
>the raw baseband data with a complex exponential that uses this coarse
>estimate (thereby removing the coarse error), repeats this squaring
>operation to arrive at a fine freq error estimate.

Is this post processing once the burst has been received?  That sounds
workable if that's the case, but there are other methods.

Frequency tracking methods in comm signals often depend on the type of
modulation used.  I'm not a GSM expert, but IIRC it uses pi/4-QPSK or
something like that...no?  In any case, frequency can be estimated
from the average phase increment from symbol-to-symbol once the
modulation has been detected or removed.   Does that make sense?


Eric Jacobsen
Minister of Algorithms, Intel Corp.
My opinions may not be Intel's opinions.
http://www.ericjacobsen.org

"Eric Jacobsen" <eric.jacobsen@ieee.org> wrote in message
news:424c9467.249355890@news.west.cox.net...
> On Fri, 25 Mar 2005 17:03:37 -0800, "Bhaskar Thiagarajan"
> <bhaskart@deja.com> wrote:
>
> >Hi all
> >
> >I'm looking at some code that is supposed to be estimating (coarsely) the
> >frequency error of a GSM signal (that is basically a bursted GMSK
modulated
> >signal).
> >The algorithm that I gleaned out of the code is as follows (in pseudo
code
> >with some matlab notations).
> >
> >input is baseband (I,Q) data.
> >I_temp = I.^2 - Q.^2
> >Q_temp = I.*Q
> >
> >fft_out = fft(I_temp + j*Q_temp);
> >
> >CenterPoint = mod(floor(270833/2/fft_resolution), Nfft)    %270833 is the
> >GSM symbol rate
> >
> >Search for peak power +/- 1000 points around CenterPoint of fft_out and
> >record PeakPowerPoint
> >
> >CoarseFreqError = (PeakPowerPoint - CenterPoint)*fft_resolution/2;
> >
> >I'm hoping someone can shed some light on this algorithm and how and why
it
> >works.
> >
> >Here is my interpretation of it,
> >The first step seems to be squaring of the complex baseband signal
(I+jQ)^2
> >The constellation of a GMSK signal has 4 points with pi/4 offsets (well,
a
> >GSM signal ends up with more points on the constellation due to ISI I
> >guess).
> >By squaring the signal, the constellation folds into 2 points (on a
line).
> >Taking an FFT of this results in 2 peaks that correspond to the input
signal
> >frequency and since we know where an ideal signal would be located we can
> >then get the delta_frequency from ideal??
>
> Yeah, that seems to be basically it, but the squaring results in a
> decrease in SNR.

Hi Eric
Is this a 'standard' technique? I've seen ().^4 being used for QPSK signals
as well. Is there some material that explains why this works or this is
based more on intuition (I can't claim to possess much of this in this new
area)? I understand that it decreases SNR but perhaps it isnt' critical to
maintain SNR to get a coarse estimate of the frequency error.

> Are you trying to get initial offset from a burst or track frequency
> through a signal?
>
> I don't recall what the GSM bursts look like but usually the preamble
> in a bursty system is designed to allow this sort of thing to be
> estimated well enough.

Firstly, I'm looking at someone else's code and I'm trying to understand
what it does.
I think this section is used to estimate the carrier frequency error of the
received signal and use this information to 'lock' to the carrier (basically
perform carrier recovery?).

> >I'm not sure I'm making much sense and I can't find any references that
come
> >close.
> >BTW, you can consider me to be a beginner when it comes to digital
> >(de)modulation and digital communications in general.
> >
> >I suspect this is a "Oh yeah - here is how it works..." kinda deal for
> >someone like Eric. I'd appreciate any pointers or explanation from
anyone.
> >
> >Note - the algorithm then goes on to use this coarse freq estimate,
multiply
> >the raw baseband data with a complex exponential that uses this coarse
> >estimate (thereby removing the coarse error), repeats this squaring
> >operation to arrive at a fine freq error estimate.
>
> Is this post processing once the burst has been received?  That sounds
> workable if that's the case, but there are other methods.

Yes, this is post processing after a burst(s) has been received - typically
1-2 frame's worth of data is acquired. This code is used in a measurement
system that tries to generate metrics for the transmitter (it doesn't run on
a cell phone).
Can you provide a brief introduction to said other methods?
I found a reference after much searching that seemed to summarize several
techniques - I guess it would be beneficial for me to go over these
techniques (even though they seem fairly theoretical to me).
http://tinyurl.com/5sx6g

> Frequency tracking methods in comm signals often depend on the type of
> modulation used.  I'm not a GSM expert, but IIRC it uses pi/4-QPSK or
> something like that...no?  In any case, frequency can be estimated
> from the average phase increment from symbol-to-symbol once the
> modulation has been detected or removed.   Does that make sense?

yes - I can understand how the type of modulation used will affect the
frequency tracking. GSM uses GMSK (not pi/4-QPSK which is what the old
IS-136 used I think).
Your last statement of average phase increment from symbol-to-symbol being
used for frequency estimation makes partial sense - if the modulation needs
to be removed, then don't you need carrier lock first - which means wouldn't
you need to estimate this *before* demodulation?

Perhaps I need to read up a lot more on my fundamentals before posing such
questions...but I find I learn a lot more by asking stupid questions here.

I did find a few related comp.dsp threads - I hope to pore over them in the
hope of enlightenment...
http://tinyurl.com/542by
http://tinyurl.com/5kfvg
http://tinyurl.com/5auxa

Cheers
Bhaskar



> Eric Jacobsen
> Minister of Algorithms, Intel Corp.
> My opinions may not be Intel's opinions.
> http://www.ericjacobsen.org

On Fri, 1 Apr 2005 12:00:21 -0800, "Bhaskar Thiagarajan"
<bhaskart@deja.com> wrote:

>> Yeah, that seems to be basically it, but the squaring results in a
>> decrease in SNR.
>
>Hi Eric
>Is this a 'standard' technique? I've seen ().^4 being used for QPSK signals
>as well. Is there some material that explains why this works or this is
>based more on intuition (I can't claim to possess much of this in this new
>area)? I understand that it decreases SNR but perhaps it isnt' critical to
>maintain SNR to get a coarse estimate of the frequency error.

Demodulation algorithms are almost never standardized, so I guess it's
not a standard technique.   It's not unheard of, but I wouldn't call
it common, either, because of the noise and spur amplification
problems.

The problem with the spurs as the order of the nonlinearity increases
(say from two to three or four) is that the spurs become as large as
the tone that you're trying to find.   Once it's to the point where
you're losing reliability in being able to detect the signal tone and
start getting false detections on spurs it starts to lose utility.
FWIW I've always gotten by with other algorithms that work as well or
better and are simpler.

If the code you're looking at is for testing a modulator then it's not
a bad assumption that the SNR will be very high and this may be a
non-issue.   In a demodulator where noise is a significant impairment
you need to worry about the nonlinearity, but for testing a modulator
with a super-clean signal it may be a non-issue.

>> Are you trying to get initial offset from a burst or track frequency
>> through a signal?
>>
>> I don't recall what the GSM bursts look like but usually the preamble
>> in a bursty system is designed to allow this sort of thing to be
>> estimated well enough.
>
>Firstly, I'm looking at someone else's code and I'm trying to understand
>what it does.
>I think this section is used to estimate the carrier frequency error of the
>received signal and use this information to 'lock' to the carrier (basically
>perform carrier recovery?).

Oh, that may be a little bit different than just frequency estimation,
then.    Sometimes a sliding block estimate of phase is made (to
increase detector SNR) in order to estimate the phase of the signal in
the middle of the block in order to demodulate it.   Maybe that's what
they're doing rather than just frequency estimation.   i.e.,
estimating phase over a block rather than frequency.

>> Is this post processing once the burst has been received?  That sounds
>> workable if that's the case, but there are other methods.
>
>Yes, this is post processing after a burst(s) has been received - typically
>1-2 frame's worth of data is acquired. This code is used in a measurement
>system that tries to generate metrics for the transmitter (it doesn't run on
>a cell phone).
>Can you provide a brief introduction to said other methods?
>I found a reference after much searching that seemed to summarize several
>techniques - I guess it would be beneficial for me to go over these
>techniques (even though they seem fairly theoretical to me).
>http://tinyurl.com/5sx6g

Wow.   Apparently it's easier to get a PhD at V. Polytech than I ever
thought.  :(

Again, it depends on what you really want to do.   Do you really want
frequency or phase?   They're related, but which you want may affect
how you go about getting them.  You're right that you need to remove
the modulation to really get frequency using symbol-to-symbol phase
increment, and that may require an estimate of the phase if you don't
want to use the nonlinearity.   You can use a block estimator (there's
a famous short paper by Andrew Viterbi and his daughter, called
Viterbi-and-Viterbi, that describes a very simple short block
estimator), obtain initial phase estimates and use those to not only
demodulate but estimate phase increment and therefore frequency.
It's not hard to see that you can then go back and remove the
frequency estimate and do it again interatively.

Or use the nonlinearity, take an FFT, and see what you get.

Or run a carrier-phase-tracking loop and see if there's a bias in the
output....

...etc., etc.   I think you start to see the dimensionality of the
possible solutions.   People get really creative with this stuff.

>> Frequency tracking methods in comm signals often depend on the type of
>> modulation used.  I'm not a GSM expert, but IIRC it uses pi/4-QPSK or
>> something like that...no?  In any case, frequency can be estimated
>> from the average phase increment from symbol-to-symbol once the
>> modulation has been detected or removed.   Does that make sense?
>
>yes - I can understand how the type of modulation used will affect the
>frequency tracking. GSM uses GMSK (not pi/4-QPSK which is what the old
>IS-136 used I think).
>Your last statement of average phase increment from symbol-to-symbol being
>used for frequency estimation makes partial sense - if the modulation needs
>to be removed, then don't you need carrier lock first - which means wouldn't
>you need to estimate this *before* demodulation?

Yeah, sorta, just covered that above.

>Perhaps I need to read up a lot more on my fundamentals before posing such
>questions...but I find I learn a lot more by asking stupid questions here.
>
>I did find a few related comp.dsp threads - I hope to pore over them in the
>hope of enlightenment...
>http://tinyurl.com/542by
>http://tinyurl.com/5kfvg
>http://tinyurl.com/5auxa
>
>Cheers
>Bhaskar

I hope that gets you going in the right direction.   This is one of
those things where after staring at it long enough the lights just
come on and it becomes pretty easy after that.



Eric Jacobsen
Minister of Algorithms, Intel Corp.
My opinions may not be Intel's opinions.
http://www.ericjacobsen.org

"Eric Jacobsen" <eric.jacobsen@ieee.org> wrote in message
news:424f306e.420371359@news.west.cox.net...
> On Fri, 1 Apr 2005 12:00:21 -0800, "Bhaskar Thiagarajan"
> <bhaskart@deja.com> wrote:
>
> >> Yeah, that seems to be basically it, but the squaring results in a
> >> decrease in SNR.
> >
> >Hi Eric
> >Is this a 'standard' technique? I've seen ().^4 being used for QPSK
signals
> >as well. Is there some material that explains why this works or this is
> >based more on intuition (I can't claim to possess much of this in this
new
> >area)? I understand that it decreases SNR but perhaps it isnt' critical
to
> >maintain SNR to get a coarse estimate of the frequency error.
>
> Demodulation algorithms are almost never standardized, so I guess it's
> not a standard technique.   It's not unheard of, but I wouldn't call
> it common, either, because of the noise and spur amplification
> problems.


<lotsa technical details snipped>

> Eric Jacobsen
> Minister of Algorithms, Intel Corp.
> My opinions may not be Intel's opinions.
> http://www.ericjacobsen.org

Many thanks for taking the time to respond Eric. Your responses certainly
help(ed). The light hasn't turned on yet, but there might be a little
flicker once in a while. One thing that your post made clear was that I need
to familiarize myself with the digital comms language a lot better if I want
to ask better questions and understand answers better.

Cheers
Bhaskar