FFT for a specific frequency range.

Question

I would like to convert a signal to frequency domain. The desired frequency range is 0.1 Hz to 1 Hz and the frequency resolution is 0.01 Hz.

With the sampling rate of 30 Hz, FFT gives the frequency components up to 15 Hz. Raising the sampling rate gives better frequency resolution. However, FFT gives wider frequency range. In my case, I just want 0.1 Hz to 1 Hz, FFT gives up to 15 Hz ( Extra computation ).

My question is, is there anyway standard way I can compute a frequency domain of a signal with specific frequency range and high resolution?

Answer 1

I think the best solution to your problem is to use the chirp-DFT. It's like a magnifying glass for a certain frequency range. It is more efficient than the direct implementation of the DFT (without FFT), because an FFT algorithm can be used with some appropriate pre- and post-processing. You basically need to modulate your signal with a chirp signal, then filter using an FFT, and then again chirp-modulate your signal to get the desired frequency response. See here and here for details on how to implement the chirp-DFT.

Answer 2

There is also the possibility of using frequency warping (also work as a magnifying glass in that you get improved resolution in your freqency range of interest for the same size FFT at the expense of lower resolution at higher frequencies). However, you don't save any MIPS as the FFT size is not reduced and the frequency warping is far from cheap.

If you only want to compute certain bins in the FFT (and thus save MIPS) there are a couple of methods to do that. For instance the sliding DFT. The references in this paper gives a very nice explanation http://www.comm.utoronto.ca/~dimitris/ece431/slidingdft.pdf. I also think the goertzel algo does something similar but I don't know it.

Then there is the option of downsampling before FFT'ing. That will probably also save some MIPS.

Edit: Just to clarify the comment regarding Goertzel algorithm not being useful. By directly plugging values into the expression found at the bottom of this wiki page http://en.wikipedia.org/wiki/Goertzel_algorithm then the Goertzel approach will be more complex than an FFT when the size of the FFT required is larger than 128 (assuming FFT size is a factor of 2 and a radix-2 implementation).

However, there are other factors that should be taken into account which goes in favor of the Goertzel. Just to cite the wiki page: "FFT implementations and processing platforms have a significant impact on the relative performance. Some FFT implementations[9] perform internal complex-number calculations to generate coefficients on-the-fly, significantly increasing their "cost K per unit of work." FFT and DFT algorithms can use tables of pre-computed coefficient values for better numerical efficiency, but this requires more accesses to coefficient values buffered in external memory, which can lead to increased cache contention that counters some of the numerical advantage."

"Both algorithms gain approximately a factor of 2 efficiency when using real-valued rather than complex-valued input data. However, these gains are natural for the Goertzel algorithm but will not be achieved for the FFT without using certain algorithm variants specialised for transforming real-valued data."

Answer 3

The frequency resolution is $$ \Delta f = \frac{f_\mathrm{s}}{N} $$ where $f_\mathrm{s}$ is the sampling frequency and $N$ is the FFT size. So increasing the sampling frequency in fact increases the frequency resolution (I assume by "better" you mean lower). You should therefore increase the FFT size $N$, i. e. the number of samples that are processed by the FFT in one block of data, in order to decrease frequency resolution. In your example you would need at least 300 samples to achieve the desired frequency resolution.

If $N$ cannot be increased due to computational complexity, the bandlimited signal could be frequency shifted before FFT. Let $s(t)$ be the continuous signal, $f_\mathrm{c}$ its center frequency and $f_\mathrm{b}$ its bandwidth. $x(n)$ is the sampled version of $s(t)$, namely $x(n) = s(n/f_\mathrm{s})$. Then a frequency shift can be achieved by $$ \tilde{x}(n) = x(n)e^{-j2\pi k_\mathrm{0}/N} $$ where $k_\mathrm{0}=f_\mathrm{c}/f_\mathrm{s}$. The sampling frequency can now be reduced as the signal now has a cut-off frequency of $f_\mathrm{b}$ in contrast to the cut-off frequency $f_\mathrm{b}+f_\mathrm{c}$ it had before the frequency shift. According to the sampling theorem the new sampling frequency $\tilde f_\mathrm{s}$ must be greater than or equal to $f_\mathrm{b}$ and thus $\tilde x(n)$ can be downsampled by a factor of $M = f_\mathrm{s}/f_\mathrm{b}$ thus increasing the frequency resolution while keeping $N$ constant.

This method only works if $s(t)$ is strictly bandlimited. If it is not, bandpass filtering to filter out the desired frequency band has to be applied in advance. Also note that downsampling by a fractional number $M$ will also introduce additional computational complexity.