快速傅氏变换
§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 = − = − = = − = = = = = + − − − − − 得: 对称性: 周期性: