第4章 快速傅里叶变换 FFT

《第4章 快速傅里叶变换 FFT》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数字信号处理(第3版)DigitalSignalProcessing(DSP)程佩青清华大学出版社主讲:张华君福州大学物理与信息工程学院2012.9快速傅里叶变换(FastFourierTransform)直接计算DFT的问题及改进的途径按时间抽取的基2-FFT算法按频率抽取的基2-FFT算法快速傅里叶逆变换(IFFT)算法Matlab实现Ch.4FFT2012/10/3024.1引言refertop.118,equ.(3-81)DFT在实际应用中很重要:可以计算信号的频谱、功率谱和线性卷积等。直接按DFT变换进行计算，当序列长度N很大时，计算量非常

2、大，所需时间会很长。FFT并不是一种与DFT不同的变换，而是DFT的一种快速计算的算法。Ch.4FFT2012/10/3034.2直接计算DFT的问题及改进的途径DFT的运算量设复序列x(n)长度为N点，其DFT为N1nkXk()xnW()Nk=0，，…，N-1n0（1）计算一个X(k)值的运算量复数乘法次数：N复数加法次数：N－1Ch.4FFT2012/10/3044.2.1DFT的运算量（2）计算全部N个X(k)值的运算量复数乘法次数：N2复数加法次数：N(N－1)（3）对应的实数运算量NN11nknknkXk()xnW()N[Re()

3、xnjIm()][RexnWNjImWN]nn00N1nknk{[Re()RexnWNNIm()ImxnW]n0nknkj[Re()ImxnWIm()RexnW]}NNCh.4FFT2012/10/3054.2.1DFT的运算量一次复数乘法：4次实数乘法＋2次实数加法一个X(k)：4N次实数乘法＋2N+2(N-1)=2(2N-1)次实数加法所以整个N点DFT运算共需要：实数乘法次数：4N2实数加法次数：N×2(2N-1)=2N(2N-1)Ch.4FFT2012/10/306DFT运算量的结论N点DFT的复数乘法次数举例NN2NN224

4、64404941612816384864256655361625651226214432102810241048576结论：当N很大时，其运算量很大，对实时性很强的信号处理来说，要求计算速度快，因此需要改进DFT的计算方法，以大大减少运算次数。Ch.4FFT2012/10/3074.2.2减少运算工作量的途径nk主要原理是利用系数WN的以下特性对DFT进行分解：（1）对称性nknkkNn()()WWWNNN（2）周期性(nNk)nkN()nkWWWNNN（3）可约性mnknknknkm/WWWWmNNNNm/另外，N/2(kN/2)kWN

5、1WNWNCh.4FFT2012/10/3084.3按时间抽取的基2-FFT算法授课思路算法原理按时间抽取基-2FFT算法与直接计算DFT运算量的比较按时间抽取的FFT算法的特点按时间抽取FFT算法的其它形式流程图Ch.4FFT2012/10/3094.3.1算法原理设N＝2L，将x(n)按n的奇偶分为两组：xr(2)xr()1Nr=0，1，…，12xr(21)xr()2则N1nkXk()DFTxn[()]xnW()Nn0N1N1nknkx(n)WNx(n)WNn0n0n为偶数n为奇数NN112222rrkk(1

6、)x(22r)WNNx(r1)Wr0r0Ch.4FFT2012/10/3010N1N1nknkx(n)WNx(n)WNn0n0n为偶数n为奇数NN11222rkk(12r)x(2r)WNNx(2r1)Wr0r0NN1122rkkrkkxrW12()NWNxrW()NXk12()WXkN()r02r02式中，X(k)和X(k)分别是x(n)和x(n)的N/2点的DFT。1212另外，式中k的取值范围是：0，1，…，N/2－1。Ch.4FFT2012/10/3011k因此，Xk()X12()k

7、WNX()k只能计算出X(k)的前一半值。后一半X(k)值，N/2，N/2＋1，…，N？利用r()Nk2rkWWN2N2可得到N21N21NrN(2k)rkXk1()xr1()WN2x1()rWN2X1(k)2r0r0同理可得NX(k)Xk()222Ch.4FFT2012/10/3012考虑到W()Nk2WN2WkWkNNNN及前半部分X(k)kXk()Xk()WX()k12Nk=0，1，…，N/2－1因此可得后半部分X(k)NNNkN2Xk()Xk()WX(k)12N222kXk()WXk()12Nk=

8、0，1，…