快速傅氏变换
§4-1引言 击进入 §42按时间抽取(DIT的FT算法 §4-3DⅠF的FFT算法 §4-4IFFT算法 录 §4-5线性卷积的FFT算法
§4-5线性卷积的FFT算法 §4-3 DIF的FFT算法 §4-4 IFFT算法 §4-2按时间抽取(DIT)的FFT算法 §4-1 引言
s4-1引言 DFT的计算工作量 X(4)=∑xO)W,k=01…N-1 n= N x(n) X(kWA k n=0,1,…,N-1 N 两者的差别仅在指数的符号和因子1/
§4-1引言 一.DFT的计算工作量 两者的差别仅在指数的符号和因子1/N. ( ) ( ) , 0,1, , 1 1 0 = = − − = X k x n W k N N n n k N − = − = = − 1 0 ( ) , 0,1, , 1 1 ( ) N k n k X k WN n N N x n
个X(k)的值的工作量,如X(1) X(1)=x(0)W0+x(1)W+x(2)W2+…+x(N-1)WN 通常x(n)和W都是复数,所以计算一个 X(k)的值需要N次复数乘法运算,和N-1次 复数加法运算.那么,所有的X(k)就要N次复 数乘法运算,N(N-1)次复数加法运算.当N很 大时,运算量将是惊人的,如N=1024,则要完 成1048576次(一百多万次)运算.这样,难以 做到实时处理
通常x(n)和 都是复数,所以计算一个 X(k)的值需要N次复数乘法运算,和 次 复数加法运算.那么,所有的X(k)就要N 2次复 数乘法运算,N(N-1)次复数加法运算.当N很 大时,运算量将是惊人的,如N=1024,则要完 成1048576 次(一百多万次)运算.这样,难以 做到实时处理. nk WN 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
二改进的途径 1.W咪的对称性和周期性 对称性:(WN k 周期性:W=W0+=Wm n(k+N) 得:W (N-n)k k WN( Wn=e 2nk(n) N N =1) WA2=-1(:W=ex=-1) W(+N2)=-Wk
二.改进的途径 1. WN nk 的对称性和周期性 ; ( ) , ( ) ( ) * n k N N n N k N n k N n k N n k N W W W W W + + − = = = . 1( 1), ( 1), ( / 2) / 2 ( ) ( ) 2 ( ) 2 k N k N N j N N N Nn k n N Nk N n k N N n k N n N k N W W W W e W W W W W e N = − = − = = − = = = = = + − − − − − 得: 对称性: 周期性:
利用上述特性,可以将有些项合并,并 将DFT分解为短序列,从而降低运算次数,提 高运算速度.1965年,库利( cooley)和图基 ( Tukey)首先提出FFT算法对于N点DFT,仅需 (N/2)1og2N次复数乘法运算.例如N=1024-210时, 需要(1024/2)10g2210=512*10=5120次。 5120/1048576=4.88%,速度提高20倍
利用上述特性,可以将有些项合并,并 将DFT分解为短序列,从而降低运算次数,提 高运算速度.1965年,库利(cooley)和图基 (Tukey)首先提出FFT算法.对于N点DFT,仅需 (N/2)log2N 次复数乘法运算.例如N=1024=210 时， 需要(1024/2)log2 2 10 =512*10=5120次。 5120/1048576=4.88% ,速度提高20倍
§4-2换时间抽取(DT)的FF算法 一库利一图基算法 算法原理(基2FFT) (-)N/2点DFT 1.先将x(n)按n的奇偶分为两组作DFT,设N=2, 不足时,可补些零。这样有: n为偶数时:x(2r)=x1(T),r=0.1…,2-1 n为奇数时:x(2-+1)=x2(),r=01,…,-1 因此,X(k)=DFT[x(m)=∑x(n)Wx
§4-2 按时间抽取(DIT)的FFT算法 —库利-图基算法 一.算法原理(基2FFT) (一)N/2点DFT 1.先将 按n的奇偶分为两组作DFT,设N=2L , 不足时,可补些零。这样有: n为偶数时: n为奇数时: (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 0 ( ) [ ( )] ( ) N n n k WN 因此， X k DFT x n x n x(n)
X(k)=∑x(n)W+∑x(n)WM n=0(n为偶数)n=0(n为奇数) ∑x(2n)W3+∑x(2r+1)W21 (r)(W) k +w k ∑x2(m)(WN)y k N 2兀 由于:Wk=e j2() W 所以,上式可表示为 (6)=∑x(W+w∑x2(W=X()+W含X2(k) =0
由于: 所以,上式可表示为: − = − = − = + − = − = − = = + = + + = + 1 0 2 2 1 0 2 1 1 0 (2 1) 1 0 2 1 0 1 0 2 2 2 2 ( )( ) ( )( ) (2 ) (2 1) ( ) ( ) ( ) N N N N r r k N k N r r k N r r k N r r k N N n N n n k N n k N x r W W x r W x r W x r W X k x n W x n W (n为偶数) (n为奇数) 2 2 2 2 2 2 / ( ) N N W e N e W j j N = = = − − ( ) ( ) ( ) ( ) ( ) 1 2 1 0 2 1 0 1 2 2 2 2 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 + = + − = − =
XI(k X,(rwA rk x(2r)WA k 其中 X2)=∑x2(W=∑x(+1) 0 2.两点结论 (1)X1(k),X2(k)均为N/2点的DFT (2)X(k)=X1(k)+kX2(k)只能确定出 Ⅹ(k)的k=0.1 A即一半的结排
其中, 2.两点结论: (1) X (k),X (k)均为N/2点的DFT。 (2) X(k)=X (k)+W X (k)只能确定出 X(k)的k= 个； 即前一半的结果。 1 2 1 2 k N − = − = − = − = = = + = = 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 0,1, , 1 2 − N
3.X(k)的后一半的确定 r(k+ 由于V =W(周期性),所以 XG+k) r(2+k) X,(r)WA k N XI(k =0 同理y +k)=X2(k) 这就是说,(k,2(k)的后一半,分别 等于其前一半的值
同理, 这就是说,X1(k),X2(k)的后一半,分别 等于其前一半的值。 3.X(k)的后一半的确定 r k rk N N WN W 2 2 2 ( ) = + ) ( ) ( ) ( ) 2 ( 1 1 0 1 ( ) 1 0 1 1 2 2 2 2 2 k x r W x r W X k N X N N N N N r r k r k r + = = = − = + − = 由于 （周期性）,所以: ) ( ) 2 ( 2 2 k X k N X + =