7
$\begingroup$

Given a sinusoidal signal, how can we efficiently determine its frequency?

$\endgroup$
9
  • 1
    $\begingroup$ If you're certain it's sinusoidal and there are no other components to it other than broadbanded.noise, and you know nothing else about it, in advance, then window a segment of the input, run that into an FFT, and find where the maximum magnitude is. $\endgroup$ Aug 8 at 11:47
  • 1
    $\begingroup$ What do you have? Samples? What do you know? Is this a Sine signal with noise? How long is the sampling interval? $\endgroup$
    – Thomas
    Aug 8 at 12:47
  • 1
    $\begingroup$ Are we computationally limited? $\endgroup$
    – Thomas
    Aug 8 at 12:49
  • 2
    $\begingroup$ Please state requirements. Rough SNR (-100 dB, -50 dB, -10 dB, etc.). Class of noise, e.g. white, pink, spikey, harmonic, etc. "Efficient" in terms of what? Time to estimation, CPU consumption, Memory consumption ? $\endgroup$
    – Hilmar
    Aug 8 at 14:37
  • 3
    $\begingroup$ This question is far too broad. Please edit your question to define what you mean by "efficiently", what are the characteristics of the signal (distortion, amplitude, noise, presence and amplitude of interfering signals), how long the observation interval is, and how accurately frequency needs to be determined. And, of course, anything I forgot to include. These factors all determine the most "efficient" way to determine a signal's frequency. $\endgroup$
    – TimWescott
    Aug 8 at 20:06
8
+100
$\begingroup$

I assume the model to be:

$$ x \left[ n \right] = \sin \left[ 2 \pi \frac{f}{ {f}_{s} } n + \phi \right] + w \left[ n \right] $$

Where $ w \left[ n \right] $ is white noise uncorrelated with the signal itself.

The obvious method here would be using DFT as the Maximum Likelihood Estimator of such case. It will probably be able to generate the best results in low SNR.

In High SNR I would use the method in Steven Kay - A Fast and Accurate Single Frequency Estimator (Alternative Source).

There are 2 methods given there.
The simplest one (Eq. 17 in the paper) is basically:

estFreq = 0;
for ii = 1:(numSamples - 1)
    estFreq = estFreq + angle(vX(ii)' * vX(ii + 1));
end

estFreq = estFreq / (2 * pi * (numSamples - 1));
estFreq = samplingFreq * estFreq; %<! Moving from normalized frequency to absolute frequency

The intuition is very simple, basically estimating the slope of the instant phase.

As can see from the paper, they achieve very good results in many real world case:

enter image description here

In Depth Analysis

The algorithm above, (Equation 17 in the paper) becomes, basically, zero crossing counting for real signal. It integrates many crossings (Assuming having many of those) hence better than just one. The issue is the assumption the phase is known and is 0.

This is an example of its performance compared to the CRLB of estimating the frequency of a sine signal without any knowledge on its amplitude (Won't make a difference even if it is known) or phase:

enter image description here

enter image description here

enter image description here

The Kay Estimator Type 1 is the estimator from Eq. 17. The Kay Estimator Type 2 is Eq. 16 (With better weighing).
As expected, when the phase isn't known the performance aren't matching the CRLB. But real world performance are pretty good (Standard deviation of ~0.03 [Hz] at 5 [dB] SNR, Since it is normalized frequency one can thing of ~3%).

The above is done for 3 different relative frequencies yes for a random phase per realization.
We need specific frequency so in 2000 realization the curve will be smooth enough (For random frequency we'll probably need something in the range for 2 orders of magnitude more realizations).

Can we do better?
Yes!

If we have a real signal (Sine / Cosine) all needed is to apply Hilbert Transform (Actually build the analytic signal as in MATLAB's hilbert()).

Then, we get:

enter image description here

enter image description here

enter image description here

Well, this is it. We have something which match the CRLB for SNR of 9 [dB] and above and works pretty well even below it.

In summary:

  • If you want good results (but not the best) with very simple algorithm, take the algorithm above and apply it directly on the real data. It is simple and work good enough. It assumes you have few cycles of the data.
  • If you want a CRLB like results (As good as it gets) for SNR of ~9 [dB] apply Hilbert transform before calling the algorithm. It will add complexity but results will be as good as it gets without DFT analysis.

Remark: Pay attention that neither of the algorithms will work for other models. Namely with more than a single tone or something like that.

$\endgroup$
5
  • $\begingroup$ The Stephen Kay link is paywalled. If there a free version of the paper available? $\endgroup$
    – Neil_UK
    Aug 9 at 11:04
  • 1
    $\begingroup$ This is great. Specifically the intuition behind it. $\endgroup$
    – Thomas
    Aug 9 at 11:17
  • 1
    $\begingroup$ This is cool. The tradeoff is being able to operate at lower SNR with MLE but computation time takes longer, or have a quicker computation time but require a higher SNR $\endgroup$
    – Engineer
    Aug 9 at 13:11
  • 1
    $\begingroup$ @Neil_UK, This will work: citeseerx.ist.psu.edu/viewdoc/…. $\endgroup$
    – Royi
    Aug 9 at 14:05
  • $\begingroup$ @Engineer, Indeed. This is a really nice trick with simple intuition. It is much more robust than the 3 points method in time domain. $\endgroup$
    – Royi
    Aug 9 at 14:06
3
$\begingroup$

A common way to do this is to take the FFT of the input signal. Since the frequency might not be right at a FFT bin, usually a second step of interpolation is done after choosing the initial peak. A couple reasons why this is commonly done is that it is the maximum likelihood solution for the AWGN case and no matter what platform you are implementing on there is likely an optimized FFT code out there for you to use. In terms of efficiency, you'd be looking at $\mathcal{O}(n\text{log}_2n)$ operations, where the heavy computational step is in taking the FFT.

$\endgroup$
2
  • $\begingroup$ In that formula for cosine omega, shouldn't the denominator be $2y[n-1]$ rather than $2y[n]$? $\endgroup$ Aug 9 at 2:44
  • $\begingroup$ @robertnetzlof commented on the wrong answer $\endgroup$
    – Engineer
    Aug 9 at 17:07
3
$\begingroup$

If you have a low-noise and well-sampled signal, a quick way to estimate it is to find $\sqrt{-f''(t)/f(t)}$. For a signal $f(t)=A sin(\omega t+\phi)$ the second derivative is $-A \omega^2 sin(\omega t+\phi)$ which is $-\omega^2$ times the original. This is useful if you want a quick response and only have part of a cycle, so no zero-crossings. But obviously it depends on being able to get an accurate second derivative numerically.

$\endgroup$
1
  • $\begingroup$ It depends in particular also on being able to compute the second derivative. Whilst it's easy to estimate that with finite differences, this is highly susceptible to noise. $\endgroup$ Aug 8 at 23:39
2
$\begingroup$

This depends on the precision needed.

If it's a pure sine wave that's noise free, you can get a very quick estimate by measuring the difference between two zero crossings.

The tricky part is that most sine wave frequencies are not integer dividers of the sample rate, so the actual zero-crossing falls between two samples and there is some inherent measurement error in this method.

The easiest way to deal with this is simply to keep measuring and averaging the results over time.

A more effective and quicker method is to estimate the exact location of the zero crossing through linear interpolation. This works quite well since a sine wave can be approximated as a line around it's zero crossing, i.e. $sin(x) \approx x, x \approx 0$. This will give you a very good estimate in a single measurement, but only if there is very little or no noise.

If things get noisy, if there are harmonics, or if there is drift, a better option is to use phase or delay locked loop to track the frequency.

Another thing to note is that you are can only measure the frequency in relation to your sample clock. Most real world sample clocks are drifting as well (albeit only by very small amounts).

If you want to go super quick you can use the relationship

$$y[n] = 2cos(\omega) \cdot y[n-1] -y[n-2]$$

which you can solve for $cos(\omega)$ using only three consecutive samples of the sine wave.

$$ cos(\omega) = \frac{y[n]+y[n-2]}{2y[n]} $$

However, this method is numerically "fragile" and even a tiny amount of noise can lead to large errors

$\endgroup$
3
  • 1
    $\begingroup$ I don't understand why this answer was voted down. It's a totally valid approach IMHO... $\endgroup$
    – applesoup
    Aug 8 at 14:36
  • 1
    $\begingroup$ Will it ever work in real life? It seems it won't. Could you compare it to other methods? $\endgroup$
    – Thomas
    Aug 9 at 11:18
  • 1
    $\begingroup$ I think your equation about $ \cos \left( \omega \right) $ is wrong. The denominator should be $ 2 y \left[ n - 1 \right] $. $\endgroup$
    – Royi
    Aug 11 at 7:45
2
$\begingroup$

As others have already mentioned in the comments, the question shows on research effort, is far too broad and needs clarification.

Depending on the requirements, the MUSIC (or ESPRIT) algorithm may be a suitable approach to efficiently find a high resolution frequency esimate. The algorithm is specifically intended for finding the frequency of sinusoids in additive noise by using a covariance approach.

Quoting the relevant passage of the linked Wikipedia article regarding efficiency:

In a detailed evaluation based on thousands of simulations, the Massachusetts Institute of Technology's Lincoln Laboratory concluded in 1998 that, among currently accepted high-resolution algorithms, MUSIC was the most promising and a leading candidate for further study and actual hardware implementation.source

Regarding its accuracy:

MUSIC outperforms simple methods such as picking peaks of DFT spectra in the presence of noise, when the number of components is known in advance, because it exploits knowledge of this number to ignore the noise in its final report.
Unlike DFT, it is able to estimate frequencies with accuracy higher than one sample, because its estimation function can be evaluated for any frequency, not just those of DFT bins.

$\endgroup$
1
  • $\begingroup$ Those are very effective methods. Yet not easy to compute (Not computationally efficient). But it is nice to see more awareness to those here. +1. $\endgroup$
    – Royi
    Aug 11 at 7:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.