Chirp Z transform
Matlab czt
--
Peter Beukelman
senior ASIC designer
http://www.eonic.com
Reply by Rick Lyons●November 26, 20032003-11-26
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-]
Reply by Steven G. Johnson●November 25, 20032003-11-25
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:
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�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�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.
Reply by on laplace.astro.cornell.edu●November 24, 20032003-11-24
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.
Reply by ●November 23, 20032003-11-23
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
Reply by Rune Allnor●November 23, 20032003-11-23
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