FFT Algorithms In general,when we use FFT algorithms to compute an N-point DFT,the number of complex MAD's is proportional to N(p1 +p2 +...+pu),where N=P1P2....Pv. Example: N=2"→p1=p2=.=pm=2 Number of MAD's proportional to N.2v Nlog2 N. If N=210 =1024,without using FFT algorithms,number of MAD's to compute the N-point DFT is proportional to N2106,while the FFT needs MAD's proportional to N1log2N≈104. In this lecture,instead of discussing many variations of FFT algorithms in detail,we will focus on the two basic schemes and only consider the case that N is an integer power of 2,i.e.N=2. For the details of the derivation and various alternative forms,see OSB Sections 9.3 and 9.4. Decimation-in-Frequency Consider computing separately the even and odd numbered frequency samples. For the even numbered samples: N- X[2r]= ∑mwg2 n= (N/2)-1 网++当》na r=0,1,,2 (2) n=0 This is equivalent to adding the first half and the last half of the input sequence,and taking the (N/2)-point DFT.Adding the two halves of the sequence corresponds to time aliasing,which is reasonable because we are undersampling in the frequency domain when computing only the even-numbered frequency samples. Similarly,for the odd-numbered samples: N- X[2r+1]= ∑xmw2r+I) n=0 (N/2)-1 {m-n+ w吸wwe (3) n=0 This is equivalent to the (N/2)-point DFT of (x[n]-x[n+)W. 2FFT Algorithms In general, when we use FFT algorithms to compute an N-point DFT, the number of complex MAD’s is proportional to N(p1 + p2 + . . . + pv), where N = p1 · p2 · · · · · pv. Example: N = 2v ⇒ p1 = p2 = . . . = pv = 2 Number of MAD’s : proportional to N · 2v ∝ N log2 N. If N = 210 = 1024, without using FFT algorithms, number of MAD’s to compute the N-point DFT is proportional to N2 ≈ 106, while the FFT needs MAD’s proportional to N log2 N ≈ 104. In this lecture, instead of discussing many variations of FFT algorithms in detail, we will focus on the two basic schemes and only consider the case that N is an integer power of 2, i.e. N = 2v. For the details of the derivation and various alternative forms, see OSB Sections 9.3 and 9.4. Decimation-in-Frequency Consider computing separately the even and odd numbered frequency samples. For the even numbered samples: N−1 n(2r) X[2r] = � x[n]WN n=0 (N/2)−1 N N = � {x[n] + x[n + ]}Wnr 2 N/2, r = 0, 1, . . . , 2 − 1. (2) n=0 This is equivalent to adding the first half and the last half of the input sequence, and taking the (N/2)-point DFT. Adding the two halves of the sequence corresponds to time aliasing, which is reasonable because we are undersampling in the frequency domain when computing only the even-numbered frequency samples. Similarly, for the odd-numbered samples: N−1 n(2r+1) X[2r + 1] = � x[n]WN n=0 (N/2)−1 N NWnr = � {x[n] − x[n + 2 ]}Wn N/2. (3) n=0 This is equivalent to the (N/2)-point DFT of (x[n] − x[n + N N . 2 ])Wn 2