Re: selected frequencies FFT?

On May 21, 12:30 pm, "Johnathan " <durchfalldurchf...@xxxxxxxxx>
wrote:
Is it possible to compute theFFTfor only selected frequencies, frequency ranges, or frequency spacings, or must you compute the entire thing with the minimum resolution from 0 to samplingfrequency/2 and then throw out what you don't need?

Computing a subset of the outputs of an FFT is called a "pruned" FFT.
In principle, if you only want K outputs out of N, the complexity is
reduced to O(N log K) from O(N log N). In practice, because the
savings are in the log, it is hard to get a signiicant performance
boost this way.

You can also get equally spaced points in a selected frequency range
via the chirp z-transform "FFT" algorithm (although in this case you
are not using it to compute a DFT). There is a significant constant-
factor penalty in this algorithm, although it is O(N log N), compared
to an ordinary FFT for a highly composite N, so it is unlikely to be
worthwhile unless you are seeking to finely interpolate some portion
of the spectrum.

Google will tell you more about both of these techniques.

Regards,
Steven G. Johnson
.

Relevant Pages

  • Re: FFT algorithm for fixed number of samples
    ... I am looking for a FFT algorithm for fixed number of sampling input. ... also in IEEE ... DSP Committee, ed., Digital Signal Processing II, selected ...
    (comp.dsp)
  • Re: FFT Radix
    ... method of breaking-up an N-length FFT into two shorter length ones, ... lengths M & L. You calculate the length-N FFT using the following three ... Tukey algorithm. ... single step of decomposing of a size N = LM DFT into DFTs of size L ...
    (comp.dsp)
  • Re: FFT Radix
    ... method of breaking-up an N-length FFT into two shorter length ones, ... Tukey algorithm. ... single step of decomposing of a size N = LM DFT into DFTs of size L ... it's obvious that one has no problem combining radix-2 and radix-4 ...
    (comp.dsp)
  • Re: How to fft huge data arrays?
    ... > Out-of-core FFT? ... it's referred to as the matrix Fourier algorithm. ... The data are originally badly placed in memory to execute ... is effectively transposed so as to make this set of transforms ...
    (comp.dsp)
  • Re: We have developed this revolutionary tech - now starts the hard work!
    ... It will be important to also state how the FFT is implemented. ... clear that your algorithm doesn't just look good because you use a bad ... Then FFT output is full of downward peaks, ... That's where a patent attorney comes in. ...
    (comp.dsp)