石家庄铁道学院四方学院 教案纸 33一维快速傅里叶变换 基本思想 (1) F(N-1) 其中w为变换矩阵元素 ①不必乘 W ②周期性 W(ut/N)=wu ③对称性 由变换矩阵元素可见,利用矩阵元素的周期性与对称性之后,变换矩阵中许 多元素相同。换言之,变换矩阵与输入信号相乘过程中存在着不必要的重复计算。 改进DFT的关键 利用变换矩阵元素的周期性与对称性,合理安排(即避免)重复出现的相乘 运算,就能显著减少计算工作量 二、一维FFT FFT重要环节 重新安排计算次序 矩阵分解 1、重新安排计算次序 设N=2n,经过n步计算后,其结果为m(k)=F(D其中k的二进制表示为 k=(kkn=2…kk)2=(2kn+22kn2+…+2k+2k0)0 k={0,li=0,1…,n-1 =(k,k1…,kn2kn)2=(2k+22k1+…+2kn2+2kn)0 2、矩阵分解 当N=2m,将变换矩阵分解成n个矩阵,使每个矩阵中每一行仅含有两个非零元素。有 两种分解方法: 种是按时间分解 一种是按频率分解 下面仅介绍按时间分解的FFT算法 F()=DF(x)=∑f(x)F =0,1,…,N-1 第1页石 家 庄 铁 道 学 院 四 方 学 院 教 案 纸 第 1 页 3.3 一维快速傅里叶变换 一、基本思想 其中 Wux为变换矩阵元素； 由变换矩阵元素可见，利用矩阵元素的周期性与对称性之后，变换矩阵中许 多元素相同。换言之，变换矩阵与输入信号相乘过程中存在着不必要的重复计算。 改进 DFT 的关键： 利用变换矩阵元素的周期性与对称性，合理安排（即避免）重复出现的相乘 运算，就能显著减少计算工作量。 二、一维 FFT FFT 重要环节 ◼ 重新安排计算次序 ◼ 矩阵分解 1、重新安排计算次序 设 N=2n，经过 n 步计算后，其结果为 fn(k)= F(l)其中 k 的二进制表示为 2、矩阵分解 当 N=2n，将变换矩阵分解成 n 个矩阵，使每个矩阵中每一行仅含有两个非零元素。有 两种分解方法： ⚫ 一种是按时间分解 ⚫ 一种是按频率分解 下面仅介绍按时间分解的 FFT 算法               − =               − ( 1) (1) (0) ( 1) (1) (0) f N f f F N F F ux   W 1 0 = = lN 1 W W 2 = − N W u lN u W =W (  ) xu N xu W = −W  ) 2 ( ② 周期性 ① 不必乘 ③对称性 0 1 0 0 1 1 2 2 1 1 1 2 1 0 2 k (k k k k ) (2 k 2 k 2 k 2 k ) n n n n = n n = + − + + + − − − − −   ki ={0,1} i = 0,1,  ,n −1 1 10 0 2 1 1 2 0 1 0 1 2 1 2 ( , , , ) (2 2 2 2 ) − − − − = − − = + + + n + n n n n n l k k  k k k k  k k  − = = = 1 0 ( ) [ ( )] ( ) N x ux F u DFT f x f x W u = 0,1,  ,N −1