DSPRelated.com
Forums

Frequency Interpolation Algorithms

Started by Wicky21 7 years ago11 replieslatest reply 6 years ago567 views

I'm currently doing a project to analyze the spectral components of an environmental signal. In that case I'm using STFT.  But now im stuck due to i have bunch of bins, but when spectral peaks lies between the FFT bins i have no idea how to interpolate the exact frequency. More recently i have tried Jain's algorithm. But in my project i need to extract fundamental frequency as well as other prominent harmonics of the noisy environmental signal. Jain's algorithm have some limitations. Somebody please suggest me a best and efficient algorithm for Frequency interpolation of DFT signal.

[ - ]
Reply by CedronNovember 6, 2017

With other tones and noise you won't be able to get an exact answer.  There are a bunch of frequency estimators which can be divided into two classes:  exact and approximations.  Which to use depends on your situation, mostly the level of noise.  The more noise there is the less advantageous an exact solution is.

For the best exact solutions, I suggest you read my blog articles which you can find here:

https://www.dsprelated.com/blogs-1/nf/Cedron_Dawg....

I present exact two and three bin solutions for both real and complex tones.  There is also one blog article on exponential smoothing which is one technique for mitigating the effects of noise.

For an approximation formula that works fairly well, I recommend Jacobsen's Estimator.  It is basically a parabolic interpolation of the bin values looking for the peak.  It's advantage is that it takes fewer calculations to compute and is simple to understand.

I will be doing a future blog article on how to deal with multiple tones.  If you want a sneak preview, you can contact me using the little envelope icon below my bio info on any blog article.

Is this a school project or a work project?

Regards,

Ced

[ - ]
Reply by Wicky21November 6, 2017

Thanks for the suggestions. This is a work project. Ill contact you

[ - ]
Reply by SlartibartfastNovember 6, 2017

If there is only one tone present, there are quite a few different algorithms that can interpolate the peak value, both direct and iterative.   Here is a survey doesn't include some of the newer algorithms but gives a good background:

[6] Jacobsen, E., Kootsookos, P., "Fast, Accurate Frequency Estimators," IEEE Signal Processing Magazine, Vol. 24, Issue 3, pp. 123-125, May, 2007

For more modern estimators search on the author Cajatay Candan and for a good iterative method search on Aboutanios and Mulgrew.

When the input is not an isolated tone, though, the best options are generally around adjusting the FT parameters to get more resolution; e.g., increase N, decrease the sample rate, etc.   There are other techniques that use more sparse data, but with a performance penalty generally.


[ - ]
Reply by Wicky21November 6, 2017

Thanks for the suggestions. Anyway i have to mention that fundamental peak is much lower than harmonics in my DFT data. I don't know whether is that possible to detect fundamental rather than using Autocorrelation. Check out the attached image which shows the Audacity Spectrum 


loud_female55_76925.png

[ - ]
Reply by Fred MarshallNovember 6, 2017

Well, physics may be working against you.  You say STFT but without any parameters.  What is the temporal length of the record or window?

[ - ]
Reply by Wicky21November 6, 2017
These are parameters which i have used in my MATLAB implemetation code

% periodogram estimation
N = 1024;                                              % segment length
win = hanning(N, 'periodic');                          % window function
overlap = 512;                                         % number of the overlapped samples
nfft = 8162;                                           % number of the fft points
[S, f, ~] = spectrogram(x, win, overlap, nfft, fs);    % spectral analysis of the segments
X = mean(abs(S), 2);                                   % spectral averaging of the segments

But keep remember i implemented this on ARM Cortex M4 chip. In the ARM processor i use 1024 FFT analyze with sliding window with a help of Hanning window.
 
 
[ - ]
Reply by Wicky21November 6, 2017

Also in my case ARM processor has

  1.  Sampling frequency = 44.1KHz
  2. 1024 FFT analyze
  3. Bin frequency = 43Hz

How to interpolate the maximum peak frequencies ??? (fundamentals and overtones) Any better algorithm ?


[ - ]
Reply by Fred MarshallNovember 6, 2017

From the spectral character it looks like you could reduce the sample rate to get better frequency resolution (i.e. a longer time window).  Right now you're somewhat stuck with the 43Hz resolution.

[ - ]
Reply by jimelectrNovember 6, 2017

Ah, the dreaded "Hanning" window raises its ugly head again!  Once again, there is the Hann or von Hann window, named after Julius von Hann, and the Hamming window, named after Richard Hamming.  No such thing as a Hanning window!  Stamp out Hanning!

[ - ]
Reply by khuaswNovember 6, 2017

Looks like you're doing some sinusoidal analysis. Julius Smith's good old Quadratic Interpolated FFT (QIFFT) is a good place to start from. 

https://ccrma.stanford.edu/~abemoto/abe-aes04.pdf

This is essentially an enhanced spectrum peak picker. Since it still operates on short-time Fourier spectrum, you won't get the best time-frequency resolution (it's much better than a discrete frequency bin nevertheless).

If you want even better result, look into Flanagan's Equations in Kawahara's recent paper https://arxiv.org/pdf/1605.07809.pdf. His method can be thought of as taking two single-bin DFTs from which the phase derivative is computed.

[ - ]
Reply by chalilNovember 6, 2017

you can use Parabolic or Gaussian interpolation to get the bin in the neighborhood of 3 spectral bins. there are several articles about it.  just google http://cds.cern.ch/record/720344/files/ab-note-200...

i used this Gaussian and frequency estimation accuracy got improved. use the right window with Gaussian will give you better results.