10
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ sounds like you want the Zoom FFT arc.id.au/ZoomFFT.html $\endgroup$ – endolith May 23 '13 at 23:57
  • $\begingroup$ If you just do a standard DFT with sampling rate 2 Hz and duration 100 s, you'll get a frequency band from 0 to 1 Hz with 0.01 Hz resolution. Only 10% of your samples will be outside the band your interested in. Is it really worth the effort of working out the details of a "not-so-standard" algorithm to improve the efficiency of this relatively small calculation? $\endgroup$ – The Photon May 25 '13 at 3:29
  • $\begingroup$ The constraint is that, the duration need to be as short as possible. 100s is too long. We need about 10+ s $\endgroup$ – NcJie May 27 '13 at 1:05
5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ The sliding DFT is actually useful in the context of real-time spectrum analysis, where the input sequence is very long and the spectrum needs to be re-computed at regular intervals. The Goertzel algorithm is very efficient if only a few DFT values need to be computed. It wouldn't be useful for solving the given problem because the desired number of frequency points is too large. $\endgroup$ – Matt L. May 23 '13 at 12:32
  • $\begingroup$ Thanks @MattL. for pointing out the Goertzel Algorithm weakness. $\endgroup$ – NcJie May 27 '13 at 1:07
1
$\begingroup$

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.

$\endgroup$

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.