唐斌-数字信号处理课件-chap9 第1讲.pptVIP

Main contents 9.0 Introduction Comparison of the computation of DFT and DIT-FFT Ch9. Computation of the Discrete Fourier Transform Decimation-In-Time FFT algorithm (DIT-FFT) Decimation-In-Frequency FFT algorithm (DIF-FFT) IFFT The Fast Fourier Transform (FFT) is not a new algorithm which is different from the DFT, but an efficient algorithm for fast computation of the DFT. 9.1 Efficient Computation of the DFT The direct computation of DFT N N-point DFT one X[k] Real Add Real Mul Complex Add Complex Mul N-1 N(N-1) 4N 2N+2(N-1) = 4N-2 e.g. N : Complex Mul : 8 1024 64 1048576 The amount of computation (the computation time) required to compute the DFT by the direct method becomes very large for large N. For this reason, we are interested in computational procedures that reduce the number of multiplications and additions. (i) complex conjugate symmetry: (ii) periodicity in n and k : (iii) 可约性: Approaches to reduce the computation of DFT by using the Properties of (iv) FFT算法的基本思路 Decimation-In-Time FFT (DIT-FFT) Decimation-In-Frequency FFT (DIF-FFT) 利用 的周期性、对称性、可约性，使DFT运算中某些项合并 将长序列的DFT分解为若干短序列的DFT 9.3. Decimation-In-Time FFT algorithms The decomposition is based on decomposing the sequence x[n] into successively smaller subsequences. Principle of the DIT-FFT Algorithm Let —— radix-2 FFT Decompose x[n] into two sequences according n is even or odd Then, Another half of X[k]: So, Butterfly Computation: A N-point DFT is decomposed into two N/2-point DFTs one complex multiplication + two complex addition e. g. complex mul: complex add: Computation = two N/2-point DFTs + N/2 butterflies 计算量减少大约一半 (ii) The 2nd decomposition: Similarly, Then, a N-point DFT is decomposed into four N/4-point DFTs. 计算量进一步减少大约一半 e. g. Computation = Four N/4-point DFTs + 2 stages butterflies (iii) Further decomposition until 2-point DFTs are left butterfly e. g. So, the 8-point DIT-FFT: Computation of DIT-FFT 当 时，共有