一次复数乘法:4次实数乘法+2次实数加法 个X(k):4N次实数乘法 2N+2(N-1)=2(2N1)次实数加法 所以整个N点DFT运算共需要: 实数乘法次数:4N 实数加法次数:NX2(2N-1)=2N(2N1)
6 一次复数乘法:4次实数乘法 + 2次实数加法 一个X(k) : 4N次实数乘法 + 2N+2(N-1)= 2(2N-1)次实数加法 所以 整个N点DFT运算共需要: N×2(2N-1)= 2N(2N-1) 实数乘法次数: 4 N2 实数加法次数:
DFT运算量的结论 N点DFT的复数乘法次数举例 N N2 N N2 4 64 4049 248 6 128 16384 64 256 65536 16 256 512 262144 32 1028 1024 1048576 结论:当№很大时,其运算量很大,对实时性很强的信号 处理来说,要求计算速度快,因此需要改进DFT的计算 方法,以大大减少运算次数。 7
7 DFT运算量的结论 N点DFT的复数乘法次数举例 N N2 N N2 2 4 64 4049 4 16 128 16384 8 64 256 65 536 16 256 512 262 144 32 1028 1024 1 048 576 结论:当N很大时,其运算量很大,对实时性很强的信号 处理来说,要求计算速度快,因此需要改进DFT的计算 方法,以大大减少运算次数
5.22减少运算工作量的途径 主要原理是利用系数W的以下特性对DFT进行分解: (1)对称性 (Wn)=Wr Tk= w k(N-n) (2)周期性 (n+N)k rn(k+N) k N N (3)可约性 WMN =WN WN=WNi 另外, WN2=-1W+N2)=-WN
8 5.2.2 减少运算工作量的途径 nk WN − = 主要原理是利用系数 的以下特性对DFT进行分解: nk WN (1)对称性 ( ) nk WN = k N n ( ) WN − (2)周期性 ( ) ( ) n N k n k N nk WWW NNN + + = = (3)可约性 mnk nk W W mN N = / / nk nk m W W N N m = 另外, 1 / 2 = − N WN k N k N WN = −W ( + / 2)
53按时间抽取的基2FFT算法 算法原理 按时间抽取基-2FFT算法与直接计算 DFT运算量的比较 按时间抽取的FFT算法的特点 按时间抽取FFT算法的其它形式流程图
9 5.3 按时间抽取的基2-FFT算法 ◼ 算法原理 ◼ 按时间抽取基-2FFT算法与直接计算 DFT运算量的比较 ◼ 按时间抽取的FFT算法的特点 ◼ 按时间抽取FFT算法的其它形式流程图
53.1算法原理 设N=2,将x(m)按n的奇偶分为两组: 2r)=x1(7) r=0,1, x(2r+1)=x2(r) X(k)=DFT(x(n)1=2x(n)W ∑x(n)Ww+∑x( n= n=0 n为偶数 n为奇数 10
10 5.3.1 算法原理 1 x r x r (2 ) ( ) = 设N=2 L,将x(n)按 n 的奇偶分为两组: 2 x r x r (2 1) ( ) + = r =0,1,…, 1 2 − N 1 0 ( ) [ ( )] ( ) N nk N n X k DFT x n x n W − = = = 则 − = − = = + 1 0 1 0 ( ) ( ) N n n n k N N n n n k x n WN x n W 为偶数 为奇数