# Efficient frequency determination

Is there any algorithm that tells you the most dominant frequency component, i.e. does argmax(fft(x)) or similar, that's more computationally efficient than argmax(fft(x))?

I need to continuously find which fft bin contains a tone, of (up to) 4096 bins in the full signal bandwidth. This is part of an RF detection system implemented in FPGA. As the input is taken from the air, the input signal is very noisy. Calculating argmax(fft(x)) with a length 4096 fft does what I need, but I was wondering if there's a way to do it without calculating all the 'unnecessary' fft outputs, to save fpga resources.

For example could there be some fft-type algorithm that bisects the spectrum to find the peak without calculating many of the outputs? Though I suspect this wouldn't really work without high SNR...

• What defines the fact that you use eg. 4096 samples for the FFT? a Frequency resolution requirement? Estimator Variance requirements? Jan 12, 2017 at 12:57
• In other words: you forgot to define what your estimator needs to achieve! We can't recommend anything until you do that. You should very likely edit your question and add info on what you're doing, and why, and why the FFT-based estimator's performance is problematic in the first place! Jan 12, 2017 at 13:01
• I need to continually find which fft bin contains a tone, and there are (up to) 4096 bins in the full bandwidth. This is part of an RF detection system implemented in FPGA. argmax(fft(x)) does what I need, but I was wondering if there's a way I'm unaware of to do it without calculating all the 'unnecessary' fft outputs, to save fpga resources. Jan 12, 2017 at 13:11
• edit your question to add that info. It's crucial to your question, and should not be hidden in the comments. Jan 12, 2017 at 13:12
• I am a bit confused. What does RF detection mean? Wide band detection? De-modulation of a carrier? If it is not wide-band why don't you use a PLL?
– A_A
Jan 12, 2017 at 13:18

Is there any algorithm that tells you the most dominant frequency component, i.e. does argmax(fft(x)) or similar, that's more computationally efficient than argmax(fft(x))?

Mostly no.

The "trouble" is not the argmax, but fft. One alternative to this is to use autocorrelation and then determine whether that function is periodic and where does it crosses zero. The other alternative is to not evaluate the FFT in all 2048 possible points via the use of the Goertzel algorithm.

This covers why the answer is "mostly" no.

But here is a case where the answer might be yes.

Instead of trying to estimate the frequency via the typical "sinusoidal" concept, you can pass your signal through a sign function which will make it look like a square wave and then count its zero-crossings. (For complex $x$, you would have to do it twice). This is an inexpensive way of getting some estimate of "dominant" frequency.

Hope this helps.

• My signal is very noisy, so I think zero crossing based approaches are hopeless Jan 12, 2017 at 13:13
• Thank you for your comment. Then the answer is a definite "no". In any case, if you were to provide a bit more detail about your signal and use case (by editing your question), maybe we can have another think (?).
– A_A
Jan 12, 2017 at 13:15

If you need to detect one of a known number $N$ of tones, then, well, the $N$-FFT is definitely the most efficient way.

You could apply parametric estimators like ESPRIT to fewer samples to get the same frequency resolution as an $N$-FFT. But ESPRIT needs an autocorrelation matrix estimate, and that is relatively bad to implement on an FPGA.

Since you refuse to talk about your exact application, that's as far as our help can go. I guess if you can't ask others, you'll need to become an expert on spectral estimation yourself. Which means: get a few of the classical specest books, maybe one or two signal classification tracts, too. Spent a month with those, and you'll be able to answer your own questions.

imin = max(0, int(np.floor(not_to_fftbin(NOTE_MIN-1))))
imax = min(SAMPLES_PER_FFT, int(np.ceil(note_to_fftbin(NOTE_MAX+1))))

(np.abs(fft[imin:imax]).argmax() + imin)*FREQ_STEP

• This is the exact algorithm I mentioned in the question, I was wondering if there's a better one. Jul 13, 2018 at 10:37