四早一 快速傅氏变换
§4-1引言 点击进入 §4-2按时间抽取(DIT的FFT算法 §43DIF的FFT算法 §44IFFT算法 求 §45线性卷积的FFT算法
§4-5线性卷积的FFT算法 §4-3 DIF的FFT算法 §4-4 IFFT算法 §4-2按时间抽取(DIT)的FFT算法 §4-1 引言
§4-1引言 DFT的计算工作量 X(k)=)x(n)W,k=0,1…N-1 n-=0 X(kWN nk rn n=0.1∴….N-1 N 两者的差别仅在指数的符号和因子1/N
§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(0WX+x(1)W+x(2)×+…+x(N-1JXN 通常x(n)和W都是复数,所以计算一个 Ⅹ(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
二改进的途径 W的对称性和周期性 对称性:( nk、* N W k N 周期性:W=W(m+N)k=Wm小 得:W)=W=W(:WN=WA=2(=1 N/2 l(:W=ex=-1 W k+N/2) W
二.改进的途径 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=20时, 需要(1024/2)1og210=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倍
942换时间抽取T〕的FFT算法 一库利一图基算法 算法原理(基2FFT) (一)N/2点DFT 1.先将xn)按n的奇偶分为两组作DFT,设N=2 不足时,可补些零。这样有: n为偶数时:x(2r)=x()r=0,1…,2 n为奇数时:x2x+1)=x2(),r=0.1…,y-1 因此,X(k)=DFT[x(m)]=∑x()WW n-0
§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)
XY(k)=∑x(n)W+∑x(n)W n=0(n为偶数)n2=0(n为奇数) X无法显示该图片 =∑x(2n)W+∑x(2r+1)W+k r=0 =∑x()W)+W∑x2()2) r=0 0 由子:WN=e j2/() W 所以,上式可表示为 )∑xW+F∑xW=x1()+Wx2(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 + = + − = − =
X1(k)=>x1(r)W rk (2r)WA rk 其中, 0 X2(k)=x2(W k x(2r+1)W2 k r=0 2.两点结论 (1)X1(k),X2(k)均为N/2点的DF (2)X(k)=X1(k)+X2(k)只能确定出 X()的k=0,…,2-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)的后一半的确定 由子WN r(k+2) W (周期性),所以: N X1(+k)=〉x()W 42=x()W=X(k) N 同理,X2(+/)=X2(k) 这就是说,H1(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 + =