5

Earlier I asked a question here about performing FFT at lower frequencies but still at high sample frequencies. I was under the impression that the FFT was inherently calculated at every frequency 0->(Sampling Frequency)/2 distributed in bins of width Fs/(2*N). But, looking at some of the answers I received, it appears that it is possible that Fs is only useful in determining the maximum frequency, which is Fs/2, but that it is entirely possible to, say, sample at 640 Hz but to only sample frequencies 0-64 Hz.

Yet, from what I've read so far on FFT implementations, it appears that the FFT in the examples I'm seeing, is being performed on the entire range 0->Fs/2, so I'm not entirely sure how to go about performing the FFT on only a portion of the maximum frequency.

Now, just to pre-empt this, I realize that somewhere along the line there is a high chance of some sort of misunderstanding on my part. I'm not entirely sure what I'm missing, but that's why I laid out my current understanding here and maybe somebody can properly explain why I'm perceiving that the FFT is only being performed on a part of the range, which I have the suspicion, due to the contradiction outlined above, is just an incorrect interpretation by me. Or maybe oversampling requires some sort of different logic that I was unaware of. In either case, I'm left a little confused so any help is appreciated.

Community
  • 1
Scorch
  • 323
  • 1
  • 3
  • 10

3 Answers3

6

I was under the impression that the FFT was inherently calculated at every frequency 0->(Sampling Frequency)/2 distributed in bins of width Fs/(2*N).

This is roughly correct. A discrete fourier transform (DFT) produces output for frequencies between \$-F_s/2\$ and \$F_s/2\$. If the input data is real-valued (rather than complex) the negative-frequency spectrum will just be the complex conjugate of the positive-frequency spectrum, so some time can be saved by not calculating the negative frequency bin values.

The spacing of the bins is \$F_s/N\$, not \$F_s/(2N)\$.

I'm not entirely sure how to go about performing the FFT on only a portion of the maximum frequency.

To calculate a small number of bins, there is a method called the Goertzel algorithm for calculating one bin at a time.

As a rule of thumb, it's typically more efficient to calculate \$M\$ bins of a DFT by the Goertzel algorithm when

$$M \le \frac{5 N_2}{6 N} \log_2(N_2)$$

where \$N_2\$ is the next power of two greater than \$N\$.

The Photon
  • 126,425
  • 3
  • 159
  • 304
4

You are right that the FFT computes equidistant frequency samples over the whole frequency range. Apart from the Goertzel algorithm mentioned in The Photon's answer, you could also use the Chirp Z-transform, which allows you to zoom in on a certain frequency range. This document explains the algorithm and it also contains a Matlab implementation (which is also included in Matlab's signal processing toolbox as czt.m).

Also have a look at this answer.

Community
  • 1
Matt L.
  • 3,641
  • 13
  • 14
  • 1
    The CZT actually seems like a very interesting option. Though, I'm curious as to how much more inefficient it is than Goertzel Algorithm. According to the answer by The Photon, the Goertzel is efficient only across very narrow bandwidths (on the order of M=10-ish by my count, obviously depending on what the parameters of N & N2 are), so if I were to use the Goertzel it would be an inefficient form that would rely on my computer processor to pick up the slack and just let it go. But maybe somebody knows, or at least can conjecture, at what point the CZT becomes more efficient than the Goertzel? – Scorch Jun 12 '16 at 23:11
2

The DFT (discrete Fourier transform) is a process that takes N samples of data in the time domain and produces N samples of data in the frequency domain. It requires on the order of N2 operations (this is written as "O(N2)") to complete the full calculation. Each of the N output values is computed independently, and each one takes O(N) operations to compute.

The FFT (fast Fourier transform) is an implementation of the DFT that eliminates the vast amount of redundancy in the normal burte-force DFT calculation, reducing the number of operations required to O(N log2N). However, the N output results are computed "in parallel", and there's no easy way to compute only some of them without doing all of the operations.

Therefore, if you ony need a subset of the N results, it may be more efficient to use the original DFT calculation. Especially if you only need log2 N of them (or fewer). But if you need more of them, then you still come out ahead by doing the full FFT and throwing away the results you don't need.

The Goertzel algorithm is a different way of calculating a single result of a DFT. It converts the nonrecursive formula into a recursive one, which greatly reduces the amount of intermediate storage required. This is why it is popular in applications such as DTMF decoding, in which you only need to measure the relative levels of 8 different specific frequencies.

Dave Tweed
  • 168,369
  • 17
  • 228
  • 393