Fast, accurate frequency estimators

Let's say I have an FFT of the given size N, and I want to get an 
estimate of a frequency of a noisy tone (input SNR ~ 1/N).
Increasing FFT size is not an option.

I can do the following processing:

1) Average the magnitudes for every bin through several FFTs, then do a 
curve fit through max_bin, max_bin-1, max_bin+1 to find the peak.

2) Do the FFT, then estimate the frequency by one of the estimators 
described in [1], then do a weighted average of the result of the 
estimator through several FFTs.

3) Do several FFTs progressively shifting the input by the frequency 
from 0 to 1/2 of bin spacing, do some post-processing.

4) Anything else?

What do you think?



[1] "Fast, Accurate Frequency Estimators"
E. Jacobsen, P. Kootsookos
p.107 "Streamlining digital Signal Processing"
edited by R. Lyons
(c)IEEE 2007

//------------------------------

Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

On 5/3/2010 8:13 AM, Vladimir Vassilevsky wrote:
>
> Let's say I have an FFT of the given size N, and I want to get an
> estimate of a frequency of a noisy tone (input SNR ~ 1/N).
> Increasing FFT size is not an option.
>
> I can do the following processing:
>
> 1) Average the magnitudes for every bin through several FFTs, then do a
> curve fit through max_bin, max_bin-1, max_bin+1 to find the peak.
>
> 2) Do the FFT, then estimate the frequency by one of the estimators
> described in [1], then do a weighted average of the result of the
> estimator through several FFTs.
>
> 3) Do several FFTs progressively shifting the input by the frequency
> from 0 to 1/2 of bin spacing, do some post-processing.
>
> 4) Anything else?
>
> What do you think?
>
>
>
> [1] "Fast, Accurate Frequency Estimators"
> E. Jacobsen, P. Kootsookos
> p.107 "Streamlining digital Signal Processing"
> edited by R. Lyons
> (c)IEEE 2007
>
> //------------------------------
>
> Vladimir Vassilevsky
> DSP and Mixed Signal Design Consultant
> http://www.abvolt.com


How fine does the estimate need to be?  Would decreasing the bin spacing 
by a factor of four or so be adequate?

If so, then the method in this paper (described in more detail in 
Appendix B) can work by computing the interpolated samples between bins 
and picking the magnitude maximizer.  The idea is that once the main 
peak is found interpolation is done only in that region and only to the 
resolution needed.  One can even do tricky things like a binary search 
to minimize the number of interpolations performed.

http://www.ericjacobsen.org/FTinterp.pdf

Also, I don't recall whether you're an Octave user or not, but the 
Matlab code for the sims in [1] is available here toward the bottom of 
the page:

http://www.ericjacobsen.org/fe2/fe2.htm

The routines are pretty straightforward and the simulation is easy to 
tweak to facilitate experimentation to see what works for your application.

FWIW, the problem that led to my looking at these things in the first 
place was ultimately solved by using the dot product interpolator 
described in Appendix B of the mentioned paper.

I have code for the dot product interpolator method as well if it's 
useful to you.


-- 
Eric Jacobsen
Minister of Algorithms
Abineau Communications
http://www.abineau.com

Eric Jacobsen wrote:

> On 5/3/2010 8:13 AM, Vladimir Vassilevsky wrote:
> 
>> Let's say I have an FFT of the given size N, and I want to get an
>> estimate of a frequency of a noisy tone (input SNR ~ 1/N).
>> Increasing FFT size is not an option.

[...]

> How fine does the estimate need to be?  Would decreasing the bin spacing 
> by a factor of four or so be adequate?

Factor of 4 would be adequate; problem is the accuracy limited by SNR 
rather then method of interpolation. I am looking for the options of 
combining the results of several subsequent FFTs into one better 
estimate. The trivial way would be average the magnitudes and then 
interpolate; there are other ideas also. I wonder what would be a good 
way to accomplish that.


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

On 3 Mai, 17:13, Vladimir Vassilevsky <nos...@nowhere.com> wrote:
> Let's say I have an FFT of the given size N, and I want to get an
> estimate of a frequency of a noisy tone (input SNR ~ 1/N).
> Increasing FFT size is not an option.
>
> I can do the following processing:
>
> 1) Average the magnitudes for every bin through several FFTs, then do a
> curve fit through max_bin, max_bin-1, max_bin+1 to find the peak.
>
> 2) Do the FFT, then estimate the frequency by one of the estimators
> described in [1], then do a weighted average of the result of the
> estimator through several FFTs.
>
> 3) Do several FFTs progressively shifting the input by the frequency
> from 0 to 1/2 of bin spacing, do some post-processing.
>
> 4) Anything else?
>
> What do you think?

I haven't read Eric and Peter's piece, so I don't know what they
say about the subject. With that proviso:

'Fast' and 'accurate' are contradictions in terms. Any estimator
might be *either* fast *or* accurate, but no one estimator will
be both.

I'd start with a periodogram with weight function. With N samples,
compute a 2N pt DFT and compute the weighted sum of of adjacent
bins (use the cosine weights from the window of your choise, the
Hann or Hamming window). Or use a nonlinear median filter to
suppress noise in the spectrum.

Detect the frequency estimate as the maximum in this filtered
spectrum.

This would probably be the simplest compromise between fast
(simple computations) and accurate (long DFTs). Of course,
the downside of some of the tweaked variants is that they
can not be characterized very well in terms of performance
or statistics. Which might mean that clients or customers
might not accept them used as part of solutions.

Rune

Vladimir Vassilevsky wrote:
>
> Let's say I have an FFT of the given size N, and I want to get an
> estimate of a frequency of a noisy tone (input SNR ~ 1/N).
> Increasing FFT size is not an option.
>
> I can do the following processing:
>
> 1) Average the magnitudes for every bin through several FFTs, then do a
> curve fit through max_bin, max_bin-1, max_bin+1 to find the peak.
>
> 2) Do the FFT, then estimate the frequency by one of the estimators
> described in [1], then do a weighted average of the result of the
> estimator through several FFTs.
>
> 3) Do several FFTs progressively shifting the input by the frequency
> from 0 to 1/2 of bin spacing, do some post-processing.
>
> 4) Anything else?
>
> What do you think?
>
>

I have only tried this a couple of times:

Sort the bins by whatever magnitude function you choose,
and look at the relative radix-es of the indices of the top n bins
(you have to save the indices, ala a 'C' struct like)

typedef struct {
     int index;
     double magnitude;
} blah;


or alternately, by "inverting" a Tcl array -
foreach.... { y[$x[$k]] = $k }

I've only used this in kind of a "spreadsheet" or "interpretive"
context - not in a fully formed system.

I have also noticed that when you arbitrarily pick a threshold,
and zero out the buckets below it, all heck breaks out and you
get weird-sounding audio from it.

>
> [1] "Fast, Accurate Frequency Estimators"
> E. Jacobsen, P. Kootsookos
> p.107 "Streamlining digital Signal Processing"
> edited by R. Lyons
> (c)IEEE 2007
>
> //------------------------------
>
> Vladimir Vassilevsky
> DSP and Mixed Signal Design Consultant
> http://www.abvolt.com

On May 3, 11:13&#4294967295;am, Vladimir Vassilevsky <nos...@nowhere.com> wrote:
> Let's say I have an FFT of the given size N, and I want to get an
> estimate of a frequency of a noisy tone (input SNR ~ 1/N).
> Increasing FFT size is not an option.
>
> I can do the following processing:
>
> 1) Average the magnitudes for every bin through several FFTs, then do a
> curve fit through max_bin, max_bin-1, max_bin+1 to find the peak.
>
> 2) Do the FFT, then estimate the frequency by one of the estimators
> described in [1], then do a weighted average of the result of the
> estimator through several FFTs.
>
> 3) Do several FFTs progressively shifting the input by the frequency
> from 0 to 1/2 of bin spacing, do some post-processing.
>
> 4) Anything else?
>
> What do you think?
>
> [1] "Fast, Accurate Frequency Estimators"
> E. Jacobsen, P. Kootsookos
> p.107 "Streamlining digital Signal Processing"
> edited by R. Lyons
> (c)IEEE 2007
>
> //------------------------------
>
> Vladimir Vassilevsky
> DSP and Mixed Signal Design Consultanthttp://www.abvolt.com

A ML solution is to do FFT #1, wait a fixed time interval, and do FFT
#2 of new data. The phase change of the bin of interest from FFT #1 to
FFT #2, combined with the know delay, gives the fine frequency. Watch
out for wraps though.

John

On May 3, 8:13&#4294967295;am, Vladimir Vassilevsky <nos...@nowhere.com> wrote:
> Let's say I have an FFT of the given size N, and I want to get an
> estimate of a frequency of a noisy tone (input SNR ~ 1/N).
> Increasing FFT size is not an option.
>
> I can do the following processing:
>
> 1) Average the magnitudes for every bin through several FFTs, then do a
> curve fit through max_bin, max_bin-1, max_bin+1 to find the peak.

If you have several offset windows of data with which to do more
than one FFT, then phase vocoder techniques can be used to
improve the frequency estimates.  Depending on the type of noise,
the phase error between offset windows may be less than the
magnitude error between bins, and/or the difference between a
perfect sinc curve fit and your polynomial estimator of choice.

Using a phase vocoder is one of the techniques mentioned on
my quick and dirty frequency estimation page:
  http://www.nicholson.com/rhn/dsp.html#1

IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M

On 3 May, 12:43, Rune Allnor <all...@tele.ntnu.no> wrote:

> I haven't read Eric and Peter's piece, so I don't know what they
> say about the subject. With that proviso:
>
> 'Fast' and 'accurate' are contradictions in terms. Any estimator
> might be *either* fast *or* accurate, but no one estimator will
> be both.

Yes and no.

Unbiased estimators can generally only be as accurate as the Cramer-
Rao Lower bound (CRLB) on the variance of such estimators.

There exist many frequency estimators that meet this bound.

The ones that Eric and I wrote about meet the CRLB and are faster to
calculate than a periodogram.

There is certainly a price: these estimators exhibit threshold
behavior at lower noise levels than the periodogram.

So, you are correct, but it's not quite as straightforward as your
text suggests.

Ciao,

Peter K.

On 5 Mai, 05:35, "Peter K." <koots...@gmail.com> wrote:
> On 3 May, 12:43, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> > I haven't read Eric and Peter's piece, so I don't know what they
> > say about the subject. With that proviso:
>
> > 'Fast' and 'accurate' are contradictions in terms. Any estimator
> > might be *either* fast *or* accurate, but no one estimator will
> > be both.
>
> Yes and no.
>
> Unbiased estimators can generally only be as accurate as the Cramer-
> Rao Lower bound (CRLB) on the variance of such estimators.
>
> There exist many frequency estimators that meet this bound.
>
> The ones that Eric and I wrote about meet the CRLB and are faster to
> calculate than a periodogram.

One has one of two options to achiev that kind of thing:

1) Compute only parts of the peridogram
2) Use a model-based frequency estimator

Both apporaches rely on prior knowledge / assumptions /
prejudice / hearsay about what the spectrum actually looks
like, and what one will find.

The problem with such approaches is that they are not
awfully robust with respect to flawed prior assumptions:
If the spectrum line is not in the band where one computes
the partial periodogram, one will not find it. If the data
do not comply to whatever parametric model the estimator
is based on, the computed numbers are little more than
mumbo-jumbo.

Pulling this to the ridiculously extreme, the fastest
frequency estimator is to state the number directly.
No computations required. Of course, this relies on that
the number is (assumed) known up front. If one states the
wrong number, one is screwed.

Rune

On 5 May, 05:41, Rune Allnor <all...@tele.ntnu.no> wrote:

> One has one of two options to achiev that kind of thing:
>
> 1) Compute only parts of the peridogram
> 2) Use a model-based frequency estimator
>
> Both apporaches rely on prior knowledge / assumptions /
> prejudice / hearsay about what the spectrum actually looks
> like, and what one will find.

Exactly.

> The problem with such approaches is that they are not
> awfully robust with respect to flawed prior assumptions:
> If the spectrum line is not in the band where one computes
> the partial periodogram, one will not find it. If the data
> do not comply to whatever parametric model the estimator
> is based on, the computed numbers are little more than
> mumbo-jumbo.

Agreed.  If the signal ain't a sine wave in noise, you'll get
garbage.  But then anything will give you garbage in that case if you
estimate the "frequency".

> Pulling this to the ridiculously extreme, the fastest
> frequency estimator is to state the number directly.
> No computations required. Of course, this relies on that
> the number is (assumed) known up front. If one states the
> wrong number, one is screwed.

Ah, but that's a biased estimator! ;-)

Such an estimator can, indeed, give a better estimation error than the
periodogram.... for precisely the right constant value. ;-)

But then you knew that.

Ciao,

Peter K.