Related Transforms Next  |  Prev  |  Up  |  Top  |  Index  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search

Related Transforms

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.10and 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].

Next  |  Prev  |  Up  |  Top  |  Index  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search

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

``Mathematics of the Discrete Fourier Transform (DFT), with Music and Audio Applications'', by Julius O. Smith III, W3K Publishing, 2003, ISBN 0-9745607-0-7.
Copyright © 2007-02-02 by Julius O. Smith III
Center for Computer Research in Music and Acoustics (CCRMA),   Stanford University
CCRMA  [Automatic-links disclaimer]