Efficient frequency determination

Question

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...

Answer 1

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.

Answer 2

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.

Answer 3

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