Other FFT Algorithms

There are many variations on the FFT, most of which have advantages in certain situations [8]. Examples include the fast discrete cosine transform (DCT) [4], discrete Hartley transform [18], number theoretic transform [2], prime factor algorithm (PFA) [29,36,8], and the Winograd Fourier transform [36]. A tutorial review of fast Fourier transform algorithms (1990) is given in [19].

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