Prev: simple questions about the DFT and its limits of integration
Next: CYCLOSTATOIONARITY BASED FREQUENCY ESITMATION?
From: Vladimir Vassilevsky on 3 May 2010 11:13

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
From: Eric Jacobsen on 3 May 2010 11:54
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
From: Vladimir Vassilevsky on 3 May 2010 12:39


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
From: Rune Allnor on 3 May 2010 12:43
On 3 Mai, 17:13, Vladimir Vassilevsky <nos...(a)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
From: Les Cargill on 3 May 2010 18:42
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

 |  Next  |  Last
Pages: 1 2 3
Prev: simple questions about the DFT and its limits of integration
Next: CYCLOSTATOIONARITY BASED FREQUENCY ESITMATION?