1
$\begingroup$

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

Improve this question
$\endgroup$
  • $\begingroup$ What defines the fact that you use eg. 4096 samples for the FFT? a Frequency resolution requirement? Estimator Variance requirements? $\endgroup$ – Marcus Müller Jan 12 '17 at 12:57
  • 1
    $\begingroup$ 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! $\endgroup$ – Marcus Müller Jan 12 '17 at 13:01
  • $\begingroup$ 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. $\endgroup$ – patstew Jan 12 '17 at 13:11
  • $\begingroup$ edit your question to add that info. It's crucial to your question, and should not be hidden in the comments. $\endgroup$ – Marcus Müller Jan 12 '17 at 13:12
  • $\begingroup$ 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? $\endgroup$ – A_A Jan 12 '17 at 13:18
1
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ My signal is very noisy, so I think zero crossing based approaches are hopeless $\endgroup$ – patstew Jan 12 '17 at 13:13
  • 1
    $\begingroup$ 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 (?). $\endgroup$ – A_A Jan 12 '17 at 13:15
1
$\begingroup$

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.

Improve this answer
$\endgroup$
-1
$\begingroup$ 
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
Improve this answer
$\endgroup$
  • $\begingroup$ This is the exact algorithm I mentioned in the question, I was wondering if there's a better one. $\endgroup$ – patstew Jul 13 '18 at 10:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.