第五章 快速傅里叶变换
第五章 快速傅里叶变换
本章目录 直接计算DFT的问题及改进的途径 ■按时间抽取的基2-FT算法 按频率抽取的基2FFT算法 a快速傅里叶逆变换(FFT算法 Matlab实现
2 本章目录 ◼ 直接计算DFT的问题及改进的途径 ◼ 按时间抽取的基2-FFT算法 ◼ 按频率抽取的基2-FFT算法 ◼ 快速傅里叶逆变换(IFFT)算法 ◼ Matlab实现
51引言 DFT在实际应用中很重要:可以计算信号的频 谱、功率谱和线性卷积等。 ■直接按DFT变换进行计算,当序列长度N很 大时,计算量非常大,所需时间会很长。 ■FFT并不是一种与DFT不同的变换,而是 DFT的一种快速计算的算法
3 5.1 引言 ◼ DFT在实际应用中很重要: 可以计算信号的频 谱、功率谱和线性卷积等。 ◼ 直接按DFT变换进行计算，当序列长度N很 大时，计算量非常大，所需时间会很长。 ◼ FFT并不是一种与DFT不同的变换，而是 DFT的一种快速计算的算法
52直接计算DFT的问题及改进的途径 DFT的运算量 设复序列x(m)长度为N点,其DFT为 X(k)=∑x(mWkc=0,,,N1 n=0 (1)计算一个X(k)值的运算量 复数乘法次数:N 复数加法次数:N一1
4 5.2 直接计算DFT的问题及改进的途径 ◼ DFT的运算量 设复序列x(n) 长度为N点，其DFT为 1 0 ( ) ( ) N nk N n X k x n W − = = k=0，，…，N-1 （1）计算一个X(k) 值的运算量 复数乘法次数： N 复数加法次数： N－1
521DFT的运算量 (2)计算全部N个Ⅺ(k)值的运算量 复数乘法次数:N2 复数加法次数:NN1) (3)对应的实数运算量 N-1 X(k)=∑x(m形X=∑[Rex(m)+jmx(m)ReW+jmW] x(n)wN n=0 2IRex(n).ReWN-Imx(n) Im W] +j[Rex(n). ImWN +Imx(n). ReWI
5 5.2.1 DFT的运算量 （2）计算全部N个X(k) 值的运算量 复数乘法次数： N2 复数加法次数： N(N－1) （3）对应的实数运算量 1 1 0 0 ( ) ( ) [Re ( ) Im ( )][Re Im ] N N nk nk nk N N N n n X k x n W x n j x n W j W − − = = = = + + 1 0 {[Re ( ) Re Im ( ) Im ] N nk nk N N n x n W x n W − = = − [Re ( ) Im Im ( ) Re ]} nk nk N N + + j x n W x n W
一次复数乘法: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 为偶数 为奇数