Vernier FFT

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&#4294967295;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&#4294967295;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