Forums

Vernier FFT

Started by Rune Allnor November 23, 2003
Hi all. 

Does anyone know how to compute the DFT coefficients efficiently 
in a narrow frequency band (few but more than one bins)? I guess 
such an algorithm would be a cousin of the Goertzel algorithm?

Rune
Zoom FFT.

In article <f56893ae.0311231005.307ae00@posting.google.com>, 
allnor@tele.ntnu.no (Rune Allnor) wrote:
>Hi all. > >Does anyone know how to compute the DFT coefficients efficiently >in a narrow frequency band (few but more than one bins)? I guess >such an algorithm would be a cousin of the Goertzel algorithm? > >Rune
FractionalFFT:

http://citeseer.nj.nec.com/bailey95fractional.html

(See Bailey's web site for errata for that article.)

-Tom

-- 

To respond by email, replace "somewhere" with "astro" in the
return address.
Rune Allnor wrote:
 > Does anyone know how to compute the DFT coefficients efficiently
 > in a narrow frequency band (few but more than one bins)? I guess
 > such an algorithm would be a cousin of the Goertzel algorithm?

Tom Loredo wrote:
> FractionalFFT: > > http://citeseer.nj.nec.com/bailey95fractional.html
This can be useful if you want a large number of points in the narrow frequency band, more finely sampled than the usual DFT outputs (although the uncertainty principle still applies: you only get a sinc interpolation, not really more resolution). If you have N sampling points in time, and you want M frequency amplitudes, it is O((M + N) log (M + N)). [*] On the other hand, if you only want a set of K << N bins that are a subset of the ordinary DFT coefficients, it is more efficient just to compute the full N-point FFT than to use the above-cited method. In this case, what you really want is something called a "pruned FFT". Unfortunately, you can show that, in general, the efficiency of a pruned FFT is O(N log K), i.e. the savings are only in the log, so it is usually not worth the trouble. In comparison, Goertzel would be O(N K), of course, which can be faster than the full FFT for small K. There are also a couple of *approximate* DFT methods for computing a subset of the DFT outputs inexactly; see: * H. Guo and C. S. Burrus, "Fast approximate Fourier transform via wavelets transform," Proc. SPIE Intl. Soc. Opt. Eng. 2825, 250&#2013266070;259 (1996). * O. V. Shentov, S. K. Mitra, U. Heute, and A. N. Hossen, "Subband DFT. I. Definition, interpretations and extensions," Signal Processing 41 (3), 261&#2013266070;277 (1995). Steven [*] Nota bene: Bailey's terminology is non-standard. This is generally called the chirp z-transform algorithm, after Rabiner, Schafer and Rader (1969). (See also http://en.wikipedia.org/wiki/Bluestein%27s_FFT_algorithm) If you do a literature search, you'll find that a "fractional Fourier transform" or "fractional DFT" more commonly refer to something completely different, essentially the Fourier linear operator to a non-integer power.
On 23 Nov 2003 10:05:01 -0800, allnor@tele.ntnu.no (Rune Allnor)
wrote:

>Hi all. > >Does anyone know how to compute the DFT coefficients efficiently >in a narrow frequency band (few but more than one bins)? I guess >such an algorithm would be a cousin of the Goertzel algorithm? > >Rune
Hi Rune, maybe the sliding DFT algorithm would work for you. [-Rick-]
Chirp Z transform
Matlab czt

--
Peter Beukelman
senior ASIC designer
http://www.eonic.com