What is the uHz-rotator algorithm?

Question

According to this page, the Baudline software tool implements

...the uHz-rotator algorithm that operates in the complex domain to calculate an extremely accurate estimate of the frequency.

Furthermore

Under good conditions (strong signal and low noise) the frequency accuracy can exceed 8 significant digits (~.000001 Hz).

I tested it with a signal generator (ToneGen). For 82.41 Hz (E2) it displays 82.40999 with averaging and 82.4 without (the rest of the digits keep spinning). The FFT size is only 2048 and the sample rate is the standard 44100Hz.

To compare, an implementation I'm working on, which employs quadratic interpolation, has a poor estimate of anywhere between 84 and 86Hz. The phase difference estimator isn't doing much better. In both cases I only get the precision to the first decimal when I increase the FFT size to 8192.

What is this uHz algorithm and how do you get such precision?

Answer 1

From the (limited) description the uHz rotator algorithm sounds like one of the phase-weighted averages from this site, but it's not an algorithm I am familiar with.

The Cramér–Rao lower bound$^1$ for estimating the frequency of sinusoid with amplitude $A$ in white noise with variance $\sigma^2$ is given by:

$$ \mathrm{var}(\hat{f}) \ge \frac{12}{(2\pi)^2\eta N(N^2-1)} $$

where $N$ is the number of samples and $\eta = A^2/(2\sigma^2)$ (taken from Kay's Fundamentals of Statistical Signal Processing, Estimation Theory equation 3.41).

So, assuming $A =1$, $\sigma^2 = 0.1$, and assuming that frequency accuracy can exceed 8 significant digits means that $\mathrm{var}(\hat{f}) < (10^{-8})^2$ we get: $$ \begin{array} \ (10^{-8})^2 &\ge& \frac{12}{(2\pi)^2 5 N(N^2-1)}\\ \frac{20}{12} \pi^2 \times 10^{-16} &\ge& \frac{1}{N(N^2-1)}\\ N(N^2-1) &\ge& 6.079271 \times 10^{14}\\ N &\ge& 84713 \end{array} $$

This means that your data length would need to be 84713 samples to achieve this accuracy.

For different values of $\sigma^2$ see the following table.

$$ \begin{array} \ \sigma^2 & \eta & 10\log_{10}(\eta) & N\\ \\ 0.1& 5.\ \ & 6.9897\ \ & 84714.\\ \\ 0.01& 50.\ \ & 16.9897\ \ & 39321.\\ \\ 0.001& 500.\ \ & 26.9897\ \ & 18252.\\ \\ 0.0001& 5000.\ \ & 36.9897\ \ & 8472.\\ \end{array} $$

PS: I have emailed the author of that web-site and asked for their comment. Let's see if they respond.

---

$^1$ The Cramér–Rao lower bound is the lowest achievable variance of an unbiased estimator.

Answer 2

I'll take an orthogonal tack to answering this question from what Peter K has (validly) already proposed. I assert that the 8-significant-figure claim is little more than marketing-speak; while the software may be able to provide you an estimate with that many digits on it, that doesn't mean that they carry any real information!

It appears that the software in question is intended for use with input signals taken from a sound card. Since any frequency measurements that are taken in the digital domain are relative to the sample rate of the input, the rate at which samples are taken is critical if accurate digital frequency measurements are required. The sample rate of the card is going to be driven by a reference oscillator of some kind.

A typical sound card is likely to have a crystal-controlled oscillator that controls its sample frequency. Crystals are very short-term stable, but over the long term (months and years), aging causes their frequency to drift. Further, they can be relatively sensitive to temperature variations, with small amounts of frequency deviation as you sweep the temperature across its specified operating range (which often is something like -10 to +30 degrees Celsius or so). The temperature problem can be addressed using a temperature-controlled crystal oscillator (TCXO, cheap and small) or oven-controlled crystal oscillator (OCXO, expensive, power-hungry and large).

A quality sound card might have a TCXO to provide maximum initial accuracy from the factory at a specified operating temperature. However, typical values for a highly precise crystal cut from the factory are in the 0.1-0.2 parts per million (ppm) range. Therefore, if the intended crystal frequency is 1 MHz, then the crystal's true oscillating frequency can vary by ~0.2 Hz or so. For most purposes, this is actually quite sufficient. However, if one wants to measure a particular frequency with 8 significant figures, this falls short: the reference oscillator used by your sampler has much more error than the software purports to provide, an example of false precision.

If you truly wanted to build a system that was capable of measuring frequency that accurately, you would need a very accurate frequency reference to compare it against. A couple ways you could do that would be:

• Use more expensive hardware. Rubidium frequency standards could be used for this sort of application. They typically provide frequency accuracies in the $10^{-4}$-ppm range or so over long periods of time, so a Rubidium standard could be used as the reference oscillator for a sampler.

• Borrow expensive hardware to calibrate your cheap hardware. The frequency error in your sound card is likely to be pretty stable for a short period of time, so you could use a calibration procedure to estimate what the sample rate error in your card is. However, there's no free lunch: you need to get a very accurate signal source to perform the calibration, which could be just as difficult as the first option. Also, the calibration would only be valid in similar environmental conditions for a limited period of time.

While I've provided a simplified treatment of the problem above, the analysis of oscillator accuracy is actually pretty complicated. There are more complicated metrics that are used to characterize oscillator performance in various contexts that might be more appropriate.