DSP-Ch3快速傅立叶变换.pdf

3.1 问题的提出 3 快速傅立叶变换（FFT） 1 wei@ustc.edu.cn 2 wei@ustc.edu.cn 3.1 问题的提出 3.1 问题的提出 已知N点有限长序列x(n) 的DFT为 若不计加法，需要N 2 次复数乘法。 Ν −1 X ( k ) ∑x ( n ) W nk k = 0,1,…N-1 N n 0 复数乘法： 直接计算N点谱线， (a +jb )(a +jb ) a a −b b +j (a b +a b )  X (0)  W0 W0 L W0  x (0)  1 1 2 2 1 2 1 2 1 2 2 1    N N N   X (1) W0 W 1 L W (N −1) x (1)    N N N   N点DFT ：4 N 2 次实数乘法。  M   M M M  M     0 (N −1) (N −1)( N −1)   X (N −1) W W L W x (N −1) N N N 3 wei@ustc.edu.cn 4 wei@ustc.edu.cn 3.1 问题的提出 3.1 问题的提出 减少运算量的两个途径 W0 1 W1 −j W2 =−1 W4 1 4 4 4 4 W3 W2 ⋅W1 j W6 W2 =⋅W4 =−1 1)利用指数因子的特性（周期性，对称性） 4 4 4 4 4 4