第4章快速傅立叶变换(FFT) 4.1引言 4.2基2FFT算法 4.3进一步减少运算量的措施 4.4其他快速算法简介 Back
第4章 快速傅立叶变换（FFT） 4.1 引言 4.2 基2FFT算法 4.3 进一步减少运算量的措施 4.4 其他快速算法简介
第4章快速傅立叶变换(FFT) 4.1引言 DFT是数字信号分析与处理中的一种重要变换， 应用广泛。但由于直接计算DFT的计算量与变换区间 长度N的平方成正比，当N较大时，计算量太大，所 以在快速傅里叶变换FFT(Fast Fourier Transform) 出现以前，直接用DFT算法进行谱分析和信号的实时 处理是不切实际的。直到1965年库利与图基以及桑 德等提出DFT的一种快速算法FFT(基2的)以后， 情况才发生了根本的变化。 1984年杜哈梅尔和赫尔曼又提出分裂基的FFT Back
4.1 引 言 DFT是数字信号分析与处理中的一种重要变换， 应用广泛。但由于直接计算DFT的计算量与变换区间 长度N的平方成正比，当N较大时，计算量太大，所 以在快速傅里叶变换FFT(Fast Fourier Transform) 出现以前，直接用DFT算法进行谱分析和信号的实时 处理是不切实际的。直到1965年库利与图基以及桑 德等提出DFT的一种快速算法FFT（基2的）以后， 情况才发生了根本的变化。 1984年杜哈梅尔和赫尔曼又提出分裂基的FFT 。 第4章 快速傅立叶变换（FFT）
第4章快速傅立叶变换(FFT) 4.2基2FFT算法 4.2.1直接计算DFT的特点及减少运算量的基本途径 1.直接计算DFT的运算量 N-1 X(k)=∑(n)W, k=0,1,.,N-1 n=0 m 1 N- Cx(k)ws"k, n=0,1,.,N-1 k=0 两者的差别仅在指数的符号和因子1/N
4.2 基2FFT算法 4.2.1 直接计算DFT的特点及减少运算量的基本途径 ( ) ( ) , 0,1, , 1 1 0 = = − − = X k x n W k N N n nk N − = − = = − 1 0 ( ) , 0,1, , 1 1 ( ) N k nk X k WN n N N x n 两者的差别仅在指数的符号和因子1/N. 1. 直接计算DFT的运算量 第4章 快速傅立叶变换（FFT）
第4章快速傅立叶变换(FFT) 个X(k)的值的工作量，如X(1) X(四=x(0)WW+x()W队+x(2)WR++x(N-1)W- 计算一个X(k)的值：N次复数乘法运算 N-1次复数加法运算.， N点DFT运算量： 复数乘法：N2 复数加法：N(N-1) 若N=1024,则N2=1048576
计算一个X(k)的值： N次复数乘法运算 N-1 次复数加法运算. 一个X(k)的值的工作量,如X(1) 0 1 2 1 (1) (0) (1) (2) ( 1) − = + + + + − N N N N N WN X x W x W x W x N点DFT运算量： 复数乘法： N2 复数加法： N(N-1) 若N=1024,则N2=1048576 第4章 快速傅立叶变换（FFT）
改进的途径 1)、把N点DFT分解成几个较短DFT可减少计算量 (N/2)2+(N/2)2=N2/2小于N2,同时有以下性质也 可减少计算量。 2)、X“的对称性、周期性、可约性 对称性：(W*)”=W nk 可约性：W=Ww*=W加 /m 周期性：Ww-)=W-=W(~W4=W=e2成=) W2=-l,:W=e=-1) Ww)=-W
2 改进的途径 1)、把N点DFT分解成几个较短DFT可减少计算量 (N/2)2+ (N/2)2 = N2/2小于N2 ，同时有以下性质也 可减少计算量。 2）、 WN nk 的对称性、周期性、可约性 k N k N N j N N N W W W W e N = − = − = = − + − ( / 2) / 2 1,( 1) 2 nk N nk WN W − = * 对称性: ( ) m n k m N nmk mN n k 可约性: WN = W = W 周期性 WN nk =WN (n+N )k =WN n(k+N ) : ( 1) ( ) ( ) 2 ( ) = = = = = − − − Nn − k n N Nk N n k N N n k N n N k N W W W W W e
第4章快速傅立叶变换(FFT) 4.2.2时域抽取法基2FFT基本原理 染算法原理 (一)N/2点DFT 1.先将x(n)按n的奇偶分为两组作DFT,设N=2M,这样 有： x2r)=x6r=01,}-1 n为偶数时： x2r+10=x2r,r=0,1,-1 n为奇数时： X)=DFT=2ww时 n-0
4.2.2 时域抽取法基2FFT基本原理 − − = = 1 0 ( ) [ ( )] ( ) N n nk n WN X k DFT x n x 算法原理 (一)N/2点DFT (2 1) ( ), 0,1, , 1 (2 ) ( ), 0,1, , 1 2 2 1 2 + = = − = = − N N x r x r r x r x r r 1.先将x(n) 按n的奇偶分为两组作DFT,设N=2M , 这样 有: n为偶数时: n为奇数时: 第4章 快速傅立叶变换（FFT）
第4章快速傅立叶变换(FFT) X=空w±∑xaw N-1 N-1 n=0(n为偶数) n=0(n为奇数) 2rwg+2ar+Dwg叫 =0 -克+r空口my 因为：w=e疼”=e2》=W X(k)=∑xr)W+WΣx,(r)W=X(k)+WX(k)
− = + − = = + + 1 0 (2 1) 1 0 2 2 2 (2 ) (2 1) N N r r k N r r k x r WN x r W − = − = = + 1 0 1 0 ( ) ( ) ( ) N n N n nk N nk X k x n WN x n W (n为偶数) (n为奇数) 2 2 2 2 2 2 / ( ) N N W e N e W j j N = = = − − 因为： X(k) x (r)W W x (r)W X (k) W X (k) k N r k r k N r r k N N N N 1 2 1 0 2 1 0 1 2 2 2 2 = + = + − = − = − = − = = + 1 0 2 2 1 0 2 1 2 2 ( )( ) ( )( ) N N r r k N k N r r k x r WN W x r W 第4章 快速傅立叶变换（FFT）
第4章快速傅立叶变换(FFT) -1 -1 X,(k)=Σx(r)W=Σx(2r)W X(k)= 艺x)wg-三(2r+Dw 2.两点结论 (1)X1(k),X2(k)均为N/2点的DFT。 (2)X(k)=X1(k)+WNX2(k)只能确定出X(k)的 k=0.1.N/2-1个，即前一半的结果
(1) X1 (k),X2 (k)均为N/2点的DFT。 (2) X(k)=X1 (k)+WN k X2 (k)只能确定出X(k)的 k= 0.1.N/2-1 个，即前一半的结果。 − = − = − = − = = = + = = 1 0 1 0 2 2 1 0 1 0 1 1 2 2 2 2 2 2 2 2 2 1 2 N N N N N N N N r r k r r k r r k r r k X k x r W x r W X k x r W x r W ( ) ( ) ( ) ( ) ( ) ( ) 2.两点结论 第4章 快速傅立叶变换（FFT）
第4章快速傅立叶变换 (FFT) 3.Xk)的后一半的确定 -WWN=-WW X+义=XW+义+ (k+ X(k+ 由于X1和X2)均以NW2为周期，得 x空=X因x今+=x,) Xk+》=x-X,因 k=0,1,岁-1 可见X(k)的后一半，也完全由X(k),X2(k)的前一 半所确定。 *N点的DFT可由两个N/2点的DFT来计算
3.X(k)的后一半的确定 ) ( ) 2 ( 1 1 k X k N X + = ) ( ) 2 ( 2 k X2 k N X + = 由于X1 (k)和X2 (k)均以N/2为周期，得 ) 2 ) ( 2 ) ( 2 ( 2 ) 2 ( 1 N W X k N X k N X k N k = + + N + + ＋ k N k WN WN W N = = − 2 ) ( ) ( ) 0,1, , 1 2 (k 1 2 2 = − = − k N N X k W X k k N X ＋ 可见,X(k)的后一半，也完全由X1 (k), X2 (k)的前一 半所确定。 *N点的DFT可由两个N/2点的DFT来计算。 第4章 快速傅立叶变换（FFT）
第4章快速傅立叶变换 (FFT) 4.蝶形运算 1次复乘2次复加 X(k)=X1(k)+W2(k) 前一半k=0,1,2. X(k)=X1(k)-WX2(k)后一半k=0,1,2. 实现上式运算的流图称作堞形运算 (N/2个蝶形) X (k) X()=X(k)+WX2(k)(前一半) X2(k) W X(6+k)=X()-WX,(k)(后一半）
实现上式运算的流图称作蝶形运算（N/2个蝶形) 4.蝶形运算 1 2 ( ) ( ) ( ) k 0,1,2 1 2 ( ) ( ) ( k 0,1,2 1 2 1 2 = − = − = + = − N X k X k W X k N X k X k W X k k N k N 后一半 ）前一半 X(k) X (k) W X (k) (前一半) k 1 N 2 = + ) ( ) ( )(后一半) 2 ( 1 2 k X k W X k N X k + = − N 1 1 1 1 -1 ( ) 1 X k ( ) 2 X k k WN 1次 复乘2次复加 第4章 快速傅立叶变换（FFT）