There are alternatives to the Cooley-Tukey FFT which can serve the
same or related purposes and which can have advantages in certain situations
[8]. Examples include the fast discrete cosine
transform (DCT) [4], discrete Hartley transform
[19], number theoretic transform
[2], prime factor algorithm (PFA)
[34,42,8,81],^{A.10}and the
Winograd Fourier transform [42]. A tutorial
review of fast Fourier transform algorithms (1990) is given in
[20].^{A.11}

The DCT, used extensively in image coding, is described in §A.6.1 below. The Hartley transform, optimized for processing real signals, does not appear to have any advantages over a ``pruned real-only FFT'' [72]. The number theoretic transform has special applicability for large-scale, high-precision calculations (see §A.6.2 below). The PFA and Winograd transform are closely related, with the PFA being somewhat faster [7].

[How to cite this work] [Order a printed hardcopy]

Copyright ©

Center for Computer Research in Music and Acoustics (CCRMA), Stanford University

[Automatic-links disclaimer]