石家庄铁道学院四方学院 教案纸 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
石家庄铁道学胱 教案纸 u和x的二进制表示为: x=(x,_1,x x12x0)2=(2xn1+2-xn-2+…+2x1+2x0)10 l=(n-1un-1…,u,l)2=(2"ln1+2n2un-2+…+2l1+2lb)o Flu.u ∑f(x xo)w F(l24,)=∑∑∑f(x2,x,x)形(+2x+22+2 a+2) x0=0x1=0x2=0 W=W(22+21+22+2+2) (21+2a+20)4x2D(2a2+2x+2)2xD(22+2a+20)x =W4(2+)2(2吗+24+24) W16x2=1,W3x=1,W32=1 F(u2,u1,)=∑∠[∑f(x2,x,x)形J )2x1 (2-a2+2a1+2uo)x =0x1=0x2=0 f(,x,x)=∑f(x2,x1,x f(0,x,x0)+f(,x12x0 f2 )=∑f(n2x,xW f(b2O,x)+f(uo1,x0川H 2)=∑f(,1,x那 f2 )+f2(b21,1)W 42+2a1 第2页
石 家 庄 铁 道 学 院 四 方 学 院 教 案 纸 第 2 页 u 和 x 的二进制表示为： 0 10 0 1 1 2 2 1 1 1 1 1 0 2 0 10 0 1 1 2 2 1 1 1 1 1 0 2 ( , , , , ) (2 2 2 2 ) ( , , , , ) (2 2 2 2 ) u u u u u u u u u x x x x x x x x x n n n n n n n n n n n n = = + + + + = = + + + + − − − − − − − − − − − − − = + + + + + + + + − − − − − − − − − − − − = 1 0 (2 2 2 2 )(2 2 2 2 ) 1 2 1 0 1 2 1 0 0 0 1 1 2 2 1 1 0 0 1 1 2 2 1 1 ( , , , , ) ( , , , , ) N x x x x x u u u u n n n n n n n n n n n n f x x x x W F u u u u 0 0 0 1 1 2 2 2 0 1 0 1 0 0 0 1 1 2 2 0 1 0 1 1 2 2 0 2 0 1 1 2 2 0 0 1 1 2 2 0 0 1 1 2 2 4 (2 )2 (2 2 2 ) (2 2 2 )4 (2 2 2 )2 (2 2 2 ) (2 2 2 )(2 2 2 ) x u u u x u u u x u u u x u u u x u u u x u x x x x u u u W W W W W W W W + + + + + + + + + + + + + = = = 1, 1, 1 16 2 2 8 2 1 8 1 2 = = = x u x u x u W W W = = = + + + = 1 0 1 0 1 0 4 (2 )2 (2 2 2 ) 2 1 0 2 1 0 0 1 2 0 0 0 1 1 2 2 2 0 1 0 1 ( , , ) { [ ( , , ) ] } x x x x u u u x u u u x F u u u f x x x W W W = = = + + + + = 1 0 1 0 1 0 (2 2 2 )(2 2 2 ) 2 1 0 2 1 0 0 1 2 0 0 1 1 2 2 0 0 1 1 2 2 ( , , ) ( , , ) x x x x x x u u u F u u u f x x x W N=8=23 ： N=8=23 ： ： = = 1 0 4 1 0 1 0 2 1 0 2 2 0 ( , , ) ( , , ) x x u f u x x f x x x W 4 0 1 0 1 0 (0, , ) (1, , ) u = f x x + f x x W = + = 1 0 (4 2 ) 2 0 1 0 1 0 1 0 1 1 0 1 ( , , ) ( , , ) x u u x f u u x f u x x W (4 2 ) 1 0 0 1 0 0 1 0 ( ,0, ) ( ,1, ) u u f u x f u x W + = + = + + = 1 0 (4 2 ) 3 0 1 2 2 0 1 0 0 2 1 0 0 ( , , ) ( , , ) x u u u x f u u u f u u x W 4 2 2 1 0 2 0 1 2 0 1 ( , ,0) ( , ,1) u u u f u u f u u W + + = +