第四早 快速傅氏交换
§4-1引言 ←点击达入 §42按时间抽取①DIT)的FFT算法 §4-3DIF的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(k)=>x(n)WW,k=01…N-1 n=0 x(n)=>X(k)WN k n=0,…,N-1 N k=0 两者的差别仅在指数的符号和因子1/N
§4-1引言 一.DFT的计算工作量 两者的差别仅在指数的符号和因子1/N. ( ) ( ) , 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
个X(k)的值的工作量,如X(1) X(1)=xO0W+x(1W+x(2W2+…+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 W 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
改进的途径 1.W的对称性和周期性 对称性:(W)=W, 周期性:WM=W(+k=W+ 得:W (N-nk k M Wn=e 1) N/2 1(W, e k+N/2
二.改进的途径 1.W N nk的对称性和周期性 ; ( ) , ( ) ( ) * n k N N n N k N nk N nk N nk 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 nk 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)log2210=512*10=5120次。 5120/1048576=4.88%,速度提高20倍
利用上述特性,可以将有些项合并,并 将DFT分解为短序列,从而降低运算次数,提 高运算速度.1965年,库利(cooley)和图基 (Tukey)首先提出FFT算法.对于N点DFT,仅需 (N/2)log2N 次复数乘法运算.例如N=1024=2 10 时， 需要(1024/2)log2 2 10 =512*10=5120次。 5120/1048576=4.88% ,速度提高20倍
7§4-2按时间抽取(IT)的FFT算法 库利-图基算法 算法原理(基2FFT) (一)N/2点DFT 1.先将x(n)按n的奇偶分为两组作DFT,设N=2L, 不足时,可补些零。这样有: n为偶数时:x(2r)=x()2r=01…y n为奇数时:x(2-+1)=x2(r),r=0,1…,y-1 因此,X()=DFx(m)=∑x(n)
§4-2 按时间抽取(DIT)的FFT算法 —库利-图基算法 一.算法原理(基2FFT) (一)N/2点DFT 1.先将 按n的奇偶分为两组作DFT,设N=2 L , 不足时,可补些零。这样有: 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 nk n WN 因此，X k DFT x n x x(n)
X(k)=∑x(n)W+∑x(n)W n=0(为偶数)n=0(n为奇数) ∑x(2)W2+∑x(2r+1)W21 r=0 ∑x1()(W3)+W∑x2()WR2) 0 r=0 由子 e 所以,上式可表示为 X()=∑()W+∑2()=x1(k)+Nx2(k)
由于: 所以,上式可表示为: 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 rk N k N r rk N r r k N r rk N N n N n nk N nk 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 rk N r rk N N N N
X1(k)=∑x()W=∑x(2)W 其中 X2()∑x2()W=∑x2r+m 0 r=0 2.两点结论 (1)X1(k),X2(k)均为N/2点的DFT。 (2)X(k)=X1(k)+WX2(k)只能确定出 X()的k=0,…,y-1个; 即前一半的结果
其中, 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 rk r rk r rk r rk X k x r W x r W X k x r W x r W 0,1, , 1 2 N
3.x()的后一半的确定 由于W, r(k+) =W(周期性),所以: X1(+k) ∑ x()W1(+) ∑x(W=X() r=0 同理,X N+k)=x2(k) 这就是说,H(k),2(从)的后一半,分别 等于其前一半的值
同理, 这就是说,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 rk r 由于 （周期性）,所以: ) ( ) 2 ( 2 2 k X k N X