Efficient frequency offset estimation of known signals

Let's say that my receiver will be receiving known data signals that range from the very simple (tone) to the complex (known data sequence that is modulated (PSK/QAM/OFDM/etc.)). What are the most computationally efficient ways to get a reasonably accurate estimate of the frequency offset?

• Have you tried plotting the I and Q results sample by sample against each other and looking at the rotation over time? That is, for every I(n) and Q(n) (n being the sample time number), plot those two values one on x axis the other on the y axis. Over time, you will notice they are rotating along the unit circle. The rate of rotation is your frequency offset. Apr 6 '12 at 19:01
• @Mohammad I know that I can do it that way, I'm just not sure that it's a computationally efficient way of doing it. At the risk of beating a dead horse, the key, for me, is computational efficiency. Apr 6 '12 at 19:10
• Not to say that there arent other methods, but I do not think that this way would necessarily be computationally intensive. Afterall, all you are doing it comparing I and Q values (that have to be computed anyway since you are demodulating I imagine), and just comparing the current I/Q values to a previous I/Q value some time back. Perhaps there is something I am not aware of per your project that is making this intensive computationally... how limited is your computing power for this task? Apr 6 '12 at 19:21
• @Mohammad I suppose you're right- it's not that intensive. My particular situation is that I am looking at implementing packetization and sometimes demodulation of GSM (tone) and WiFi (PSK, OFDM) signals in an FPGA. I guess I was hoping that there was a clever way of doing the frequency offset estimation at the same time as doing the signal detection, which I will probably do using FFT-based correlations. Apr 6 '12 at 19:32
• Hmm, well I searched around and I have heard of some methods that use auto-correlation to do pitch detection, (see here: dsp.stackexchange.com/questions/1317/…), ... and since you are doing cross-cors it might be worth looking at. (Cntrl-F for 'autocorrelation' and look at @Phonon's answer). Apr 6 '12 at 20:17

Time aligned

If the signals are time aligned, you can conjugate-multiply the received signal with the reference signal and look for the dominant frequency.

Max-Likelihood estimation of the frequency shift and complex gain of a known signal in Gaussian Noise

Let $$\vec r$$ be the noisy observation of a frequency translated version of a sent $$\vec x$$ with unknown gain. Here, let us consider the channel $$\mathbf A \in \Gamma$$ $$\vec r = \mathbf A \vec x + \vec w \in \mathbf C^N \\ [\mathbf A]_{nn} = \rho \exp(\omega n) , \rho \in \mathbf C^N , \omega \in \mathbf R \\ [\mathbf A]_{mn} = 0, \forall m \ne n \\ p(\vec w|\tau) \propto \exp\left( \frac {-\| \vec w \|^2} {\tau} \right) \\ \mathbf A^* \triangleq \operatorname*{argmax}_{\mathbf A} \max_{\tau} \underbrace{p(\vec r| \mathbf A,\vec x ,\tau)}_{ \propto \exp \left( \frac {-\| \mathbf A \vec x - \vec r \|^2} {\tau} \right) } \\ \mathbf A^* = \operatorname*{argmax}_{\mathbf A} \underbrace{ -\| \mathbf A \vec x - \vec r \|^2 }_{ \triangleq f(\mathbf A) } \\ f(\mathbf A) = - (\mathbf A \vec x - \vec r )^H (\mathbf A \vec x - \vec r ) \\ = - \vec x^H \underbrace {\mathbf A^H\mathbf A }_{|\rho|^2 \mathbf I } \vec x + 2\mathop{re} (\mathbf A \vec x)^H \vec r - \underbrace {\vec r^H \vec r}_{ \|\vec r\|^2}$$ Notice the first and third terms have no dependence on frequency $$\omega$$ nor the phase of $$\rho$$. So we simply need to find the frequency that best aligns $$\vec x,\vec r$$. That will imply the phase.

$$\omega^* = \operatorname*{argmax} \sum_n |\exp(-j\omega n) \bar {x_n} r_n|^2$$

One can use an FFT or some such frequency estimator to recover the dominant frequency

Not Time-Aligned

If the signals are not time-aligned, then you've got a time and frequency search problem on your hand. With low SNR, this is essentially the problem solved by the cross-ambiguity function (CAF). If you've got several dB of margin you can take a shortcut.

If you have a reference signal with some AM variation; you can time-align first by AM detecting both signals and then correlating your input by the reference AM. If your reference signal doesn't have much amplitude variation, but its spectrum is "spikey" you might be able to correlate the magnitude spectra of the received and reference. This is the same trick applied in the frequency domain, rather than time domain.

With the exception of the CAF, these are all fairly cheap operations.

• I'm not quite following the "conjugate-multiply" method. I assume you are talking about multiplying the two sequences sample-by-sample, with one of them conjugated. Each product, then, would have a phase of n*fo + phi, where n is the sample number, fo is the offset frequency, and phi is the starting phase offset. Should I diff the phases to get the offset frequency phase increment? Apr 7 '12 at 18:47
• Yes. If there is a constant phase offset, then the result from the conjugate-multiply operation will have linear phase. The slope of that line is the frequency offset, so differentiating will give you that. Apr 8 '12 at 2:26
• It occurred to me that we multiply in the frequency domain to correlate/convolve in the time domain. By conjugate-multiplying in the time domain we are cross-correlating in the frequency domain. If we FFT the conjugate-multiply results we should have the frequency domain cross-correlation, right? The peak of that cross-correlation should indicate what the frequency offset is. Apr 8 '12 at 21:46
• Yes. If the result from the conjugate-multiply has linear phase, then it is tone-like in nature. That will correspond to a thin peak in the frequency domain, as you noted. Apr 9 '12 at 2:35
• Is the edited answer a bit clearer? Apr 9 '12 at 3:23