石家庄铁道学院：《数字图象处理》第三章（3-3） 一维快速傅里叶变换

石家庄铁道学院四方学院 教案纸 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=(xn12xn1…,x1,x)2=(2xn1+2xn2+…+2x1+2x010 l=(n-1un-1…,u,l)2=(2"ln1+2n2un-2+…+2l1+2lb)o FO ∑f(x xo)w F(l24,)=∑∑∑f(x2,x,x)形(x+2x+22+2+2 x0=0x1=0x2=0 W=W(2+2x+210X2n2+2+2) W(2+2+22)4xW(2吗2+24+2)2xW(22+24+2) =W4(2+)2(2吗+24+24) 1,W 1W82=1 F(l2,,)=∑{[∑f(x2,x1,x32形(2+2 =0x1=0x2=0 N=8=23: f(uo, x, xo )=>f(x2, x, xo )w 43x3o f(0,x,x0)+f(,x12x0 f2 )=∑f(n2x,xW =f(a,0,x)+f(l,1,x)W(4-+2m) f3(b,1,2)=∑f(124,x)形F(4+2+010 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 + + = +

石家庄铁道学胱 教案纸 F(l2,1210)=f3(l,1,2) 矩阵表示 f1(0.0.0)(1 f(0.0,1) f(00,1) f(0,0) f(0,10 f(0,1,1) f(0,1) f(,0.0) f(1,0.0) f(,0.1) f(1,0,1) f(1,10) f(1,1) f2(0.0,0) 0 f(0,0,0) f(0.0.1)010 f(0,0,1) f2(0,0)10W40 f(0,0) f(01)1010W4 f(0,1) f2(1,0,0) 10W20f(10.0) 0102f(10.1 f2(1,0) 0f(1,0) f2(1 010W6人f(1) f3(0.0.0) f2(0.0.0) f3(00.1)1 f2(0,0,1) f(0,10) f2(0,1,0) f3(0,1,1) f2(0,,1) f(10) f2(100) f(.0.1) f2(10,1) f(10) 1W3‖f2(,10) f(1 1W人(1) 第3页

石 家 庄 铁 道 学 院 四 方 学 院 教 案 纸 第 3 页 矩阵表示 ( , , ) ( , , ) 2 1 0 3 u0 u1 u2 F u u u = f                                                     =                           (1,1,1) (1,1,0) (1,0,1) (1,0,0) (0,1,1) (0,1,0) (0,0,1) (0,0,0) 1 1 1 1 1 1 1 1 (1,1,1) (1,1,0) (1,0,1) (1,0,0) (0,1,1) (0,1,0) (0,0,1) (0,0,0) 4 4 4 4 0 0 0 0 1 1 1 1 1 1 1 1 f f f f f f f f W W W W W W W W f f f f f f f f                                                     =                           (1,1,1) (1,1,0) (1,0,1) (1,0,0) (0,1,1) (0,1,0) (0,0,1) (0,0,0) 0 1 0 1 0 0 0 1 0 1 0 2 0 0 1 0 1 0 0 0 1 0 1 0 0 (1,1,1) (1,1,0) (1,0,1) (1,0,0) (0,1,1) (0,1,0) (0,0,1) (0,0,0) 1 1 1 1 1 1 1 1 6 6 2 4 4 0 0 2 2 2 2 2 2 2 2 f f f f f f f f W W W W W W W W f f f f f f f f                                                     =                           (1,1,1) (1,1,0) (1,0,1) (1,0,0) (0,1,1) (0,1,0) (0,0,1) (0,0,0) 1 1 1 1 1 1 1 1 (1,1,1) (1,1,0) (1,0,1) (1,0,0) (0,1,1) (0,1,0) (0,0,1) (0,0,0) 2 2 2 2 2 2 2 2 7 3 5 1 6 2 4 0 3 3 3 3 3 3 3 3 f f f f f f f f W W W W W W W W f f f f f f f f

石家庄铁道学院 教案纸 FFT流程图 N=8时FFT流程图 #1 10.0.0) fi(0,0,0) f2(0.0,0) 示0.00=FO.0,0) 10.0,1) 60 f(0.0,1) f60.0.1)=F1.0,0) 01)×01)×010 fi(0.,1,0) 2(O1.0)=E(0,1.0) f(0.,1,1)一 (0.1,1)=F(1,1,0) 1.00 6.0.0) f2(1.0,0) 6(1,0.0)=(OO,1) 1.0,1) =6(1.0,1) f2(1.0,1) m(1.,1)=F(1.0,1) 1,1,0) f(1,1,0) f(1,1.0) 26(11.0)=F(O,1,1) 1,1,1) fi(1,1,1) f2(1,1,1) (1,1,1)=F(1,1,1) (1)整个流程需要的计算步数为m=log2N(N=2n) (2)在第r步计算中,要乘的因子为 0,1…,2-1-1;r (3)第r步计算中有2r-1个组,每组有(N2r-1)个元素,每组的W因子各不相 同,且每组只有一种类型的W因子,此因子在组中上一半为正,下一半为负 每组的第一个待求量:f(k)=f,(k21kn2…kk) 将k=(kn1kn2…kk)2右移nr位,左边空出的位置补0,得k=(kn1,kn2,…,k1,k)2 再将k逆位即得W因子的指数k0=(,k,…k2,kn1)2 (4)对比DFT与IDFT的定义式,只要将上述FFT算法中W因子用其共轭代替, 并将最后结果乘以1N,就是计算IDFT即离散傅里叶反变换的快速算法。 (5)在每步计算中,需要的乘法次数N2,加法次数为N,因此FFT的总计算量 为 乘法次数为 N 加法次数为Nbg2N 而直接计算DFT的计算量为:乘法次数为M2,加法次数为NN-l)。当N=2048 时,DFT需要4194304次乘法运算,而FFT只需要11264次乘法运算,二者之 比为 N2/(C~log2N)=3724 第4页

石 家 庄 铁 道 学 院 四 方 学 院 教 案 纸 第 4 页 3、FFT 流程图 N=8 时 FFT 流程图 (1) 整个流程需要的计算步数为 n=log2N (N=2n)； (2) 在第 r 步计算中，要乘的因子为 (3) 第 r 步计算中有 2r-1 个组，每组有（N/2r-1）个元素，每组的 W 因子各不相 同，且每组只有一种类型的 W 因子，此因子在组中上一半为正，下一半为负。 (4) 对比 DFT 与 IDFT 的定义式，只要将上述 FFT 算法中 W 因子用其共轭代替， 并将最后结果乘以 1/N，就是计算 IDFT 即离散傅里叶反变换的快速算法。 (5) 在每步计算中，需要的乘法次数 N/2，加法次数为 N，因此 FFT 的总计算量 为： 乘法次数为 加法次数为 而直接计算 DFT 的计算量为：乘法次数为 N2，加法次数为 N(N-1)。当 N=2048 时，DFT 需要 4194304 次乘法运算，而 FFT 只需要 11264 次乘法运算，二者之 比为 W s r n r sN r 0,1, ,2 1; 1, , 2 =  −1 − =  N N 2 log 2 N log2 N log ) 372.4 2 /( 2 2 N = N N