The discrete Fourier transform (DFT) is a fundamental transform in digital signal processing, with applications in frequency analysis, fast convolution, image processing, etc. Moreover, fast algorithms exist that make it possible to compute theDFTvery efficiently. The algorithms for the efficient computation of the DFT are collectively called fast Fourier transforms (FFTs). The historic paper by Cooley and Tukey [15] made well known an FFT of complexity N log2 N, where N is the length of the data vector. A sequence of early papers [3, 11, 13, 14, 15] still serves as a good reference for the DFT and FFT. In addition to texts on digital signal processing, a number of books devote special attention to the DFT and FFT [4, 7, 10, 20, 28, 33, 36, 39, 48].

The importance of Fourier analysis in general is put forth very well by Leon Cohen [12]:

. . . Bunsen and Kirchhoff, observed (around 1865) that light spectra can be used for recognition, detection, and classification of substances because they are unique to each substance.

The kth DFT coefficient of a length N sequence {x(n)} is defined as

Back to Index

The DFT of a length N sequence {x(n)} can be represented as a matrix-vector product. For example, a length 5 DFT can be represented as

X⁢0X⁢1X⁢2X⁢3X⁢4=( 11111 1WWDid not convert matrixrow/degreeWW )⁢x⁢0x⁢1x⁢2x⁢3X⁢4 X 0 X 1 X 2 X 3 X 4 1 1 1 1 1 1 W W 2 W W x 0 x 1 x 2 x 3 X 4

It is very useful to illustrate the entries of the matrix FN as in Fig. 2.1, where each complex value is shown as a vector. In Fig. 2.1, it can be seen that in the kth row of the matrix the elements consist of a vector rotating clockwise with a constant increment of 2πk/N. In the first row k = 0 and the vector rotates in increments of 0. In the second row k = 1 and the vector rotates in increments of 2π/N.

Back to Index

To formalize the type of frequency analysis accomplished by the DFT, it is useful to view each DFT value {X(k)} as the output of a length N FIR filter hk(n). The output of the filter is given by the convolution sum

Figure 1: The truncated DFT coefficients and the time signal reconstructed from the truncated DFT.

Back to Index