MIT OpenCourseWare http://ocw.mit.edu 2.161 Signal Processing: Continuous and Discrete Fall 2008 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.MASSACHUSETTS INSTITUTE OF TECHNOLOGY DEPARTMENT OF MECHANICAL ENGINEERING 2.161 Signal Processing - Continuous and Discrete The Fast Fourier Transform 1 Introduction: Although the DFT was known for many decades, its utility was severely limited because of the computational burden. The calculation of the DFT of an input sequence of an N length sequence {fn} N−1 fne−j 2πmn Fm = � N , m = 0, . . . , N − 1 (1) n=0 requires N complex multiplications to compute each on the N values, Fm, for a total of N2 multi-plications. Early digital computers had neither fixed-point nor floating-point hardware multipliers, and multiplication was performed by binary shift-and-add software algorithms. Multiplication was therefore a computationally “expensive” and time consuming operation, rendering machine com-putation of the DFT impractical for common usage. In 1965 Cooley and Tukey [1] of IBM labs published a ground-breaking paper that presented a computational algorithm for the DFT that required just a small fraction of the complex multiplica-tions in Eq. (1). The Fast Fourier Transform (FFT) has revolutionized digital signal processing by allowing practical fast frequency domain implementation of processing algorithms. (It is interesting to note in retrospect that the techniques used in the FFT can be found all the way back to Gauss, although the significance was not recognized until Co oley and Tukey). There are many variations on the FFT algorithm. This handout examines just one of them: the Radix-2 FFT with decimation in time, which is probably the most commonly used FFT. The term Radix-2 refers to the limitation that the sample length N must be an integer power of 2, while decimation in time means that the sequence {fn} must be re-ordered before applying the algorithm. The Radix-2 FFT with Decimation in Time: We start by writing the DFT of Eq. (1) as N−1 fne−j 2πmn N−1 N W mnFm = � = � fn , m = 0, . . . , N − 1 (2)N n=0 n=0 where WN = e−j2π/N . We also note the following periodic and symmetry properties of WN WNk(N −n) = WN−kn = WNkn (complex conjugate symmetry), • W kn = W k(n+N ) = W n(k+N ) (periodicity in n and k),• NN N • WNn = −WNn−N/2 for n ≥ N/2. The FFT recognizes that these properties render many of the N2 complex multiplications in Eq. (1) redundant. We start by assuming that the input sequence length N is even. We then ask whether any computational efficiency might be gained from splitting the calculation of {Fm} into two sub-computations, each of length N/2, involving the even samples, {f2n}, and odd samples {f2n+1} for 1D. Rowell October 4, 2007 1nab a + W bNnn = 0 . . . N/2 − 1: P −1 P −1 m(2n+1)Fm = � f2nWN 2mn + � f2n+1WN n=0 n=0 P −1 W 2mn mP −12mn= � f2nN + WN � f2n+1WN n=0 n=0 P −1 P −1 W mn m mn= � f2nP + WN � f2n+1WP n=0 n=0 = Am + WNmBm, m = 0, . . . , N − 1. (3) where P = N/2, {Am} is a DFT of length N/2, based on the even sample points, and similarly {Bm} is a DFT of length N/2 based on the odd sample points of {fn}. We also note from the properties of the DFT that both {Am} and {Bm} are periodic with perio d N/2, that is Am+N/2 = Am, and Bm+N/2 = Bm so that Fm = Am + WNmBm for m = 0 . . . (N/2 − 1), and (4) Fm = Am−N/2 − WNm−N/2Bm−N/2 for m = N/2 . . . (N − 1) (5) Equations (4) and (5) show that a DFT of length N may be synthesized by combining two shorter DFTs from an even/odd decomposition of the original data set. For example, if N = 8, F3 and F7 are simply related: F3 = A3 + W83B3 F7 = A7 + W87B7 = A3 − W83B3 so that N/2 multiplications are required to combine the two sets. Each of the two shorter DFTs requires (N/2)2 complex multiplications, therfore the total required is N2/2+N/2 < N2, for N > 2, indicating a computational saving. A modified discrete form of Mason’s signal-flow graph is commonly used to display the algo-rithmic structure of Eq. (3). Figure 1 shows the signal-flow graph - consisting of a network of nodes connected by line segments. The algorithm works from left to right, and each right-hand node is assigned a value that is the weighted sum of the connected left-hand nodes, where the indicated weight n is the exponent of WN . If no weight is indicated, it is assumed to be unity (or equivalent to WN 0 ). Thus the output of the step shown in Fig. 1 is c = a + WNn b. Figure 1: Signal-flow graph notation. With this notation the combining of the two length N/2 DFTs is illustrated in Fig. 2 for N=8. Each right-hand node is one of the Fm, formed by the appropriate combination of Am and Bm as develop ed in Eqs. (3), (4) and (5). If N is divisible by 4, the process may be repeated, and each length N/2 DFT may be formed by decimating the two N/2 sequences into even and odd components, forming the length N/4 DFTs, 201234567AAAABBBB00112233F = A + W B04 - p o i n t D F Tf r o m e v e n s a m p l e s4 - p o i n t D F Tf r o m o d d s a m p l e s{ f , f , f , f }0246{ f , f , f , f }13570008F = A + W B11118F = A + W B22228F = A + W B33338F = A + W B = A - W B444480080F = A + W B = A - W B555581181F = A + W B = A - W B666682282F = A + W B = A - W B777783383Figure 2: Signal-flow graph representation of combining two length-4 DFT sequences, derived from even and odd sample sets, into a length-8 sequence as defined in Eq. (3). and combining these back into a length N/2 DFT, as is shown for N = 8 in Fig. 3. Notice that all weights in the figure are expressed by convention as exponents of W8. In general, if the length of the data sequence is an integer power of 2, that is N = 2q for integer q, the DFT sequence {Fm}may be formed by adding additional columns to the left and halving the length of the DFT at each step, until the length is two. For example if N = 256 = 28 a total of seven column operations would be required. The final step is to evaluate the N/2 length-2 DFTs. Each one may be written F0