第四早 快速傅氏交换
§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 得: 对称性: 周期性: