数字信号处理第四章

《数字信号处理第四章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2021/9/1信息与通信工程学院1第四章快速傅立叶变换FFT－FastFourierTransform§4.1引言§4.2按时间抽取的基－2FFT算法§4.3按频率抽取的基－2FFT算法§4.4离散傅立叶反变换的快速计算方法－IFFT本章主要内容：2021/9/12§4.1引言FFT不是新的变换形式，只是DFT的一种快速算法，且根据对序列分解与选取方法的不同而产生了FFT的多种算法，应用很广。一DFT直接计算存在的问题设x(n)为N点有限长序列，正反变换计算量相同例N＝4：信息与通信工程学院2021/9/13例N＝4：

2、N点DFT的直接计算量1.乘法次数：对每一个k：N次复数乘法【4N次实乘和2N次实加】N个k：次复数乘法信息与通信工程学院2021/9/14加法次数：对每一个k：N－1次复加【2（N－1）次实加】N个k：N（N－1）次复加即和成正比。例N＝1024，则有1048576次复乘（约400万次实乘），假定运算器的指令速度为100MIPS，则计算时间大约为4秒。信息与通信工程学院2021/9/15旋转因子的对称性和周期性例N＝4，旋转因子W的矩阵形式为：二、改进途径信息与通信工程学院2021/9/16旋转因子W的性质：对称性:周

3、期性:得:可约性:信息与通信工程学院2021/9/17如前所述，N点DFT的复乘次数与N的平方成比例，显然N较小时乘法次数大大减少。利用上述旋转因子的特性，可以将有些项合并，并将DFT分解为短序列，从而降低运算次数，提高运算速度。1965年，库利(cooley)和图基(Tukey)首先提出FFT算法。对于N点DFT，仅需(N/2)log2N次复数乘法运算。例如N=1024=210时，需要(1024/2)log2210=512*10=5120次复乘运算，5120/1048576=4.88%，速度提高20倍。分解有时域抽取（

4、DIT）和频域抽取（DIF）两大类。改进方法概述信息与通信工程学院2021/9/18§4.2按时间抽取的基－2FFT算法（DecimationInTimeFFT）仍以N＝4为例ABABCDCD运算流图A-1C-1BD-1-1信息与通信工程学院2021/9/19一算法原理先将x(n)按n的奇偶分为两组作DFT,设N=2L（L大于等于2），不足时，可补些零，这样一个N点的DFT分解为两个N/2点的DFT。(一)N/2点DFT信息与通信工程学院2021/9/110DIT-FFT分解说明：上式中E(k)和F(k)均为N/2点的D

5、FT；因W是以N为周期，故X(k)是以N为周期；X(k)=E(k)+WF(k)只能确定出X(k)的k=个值，即前一半的结果。kNkN信息与通信工程学院2021/9/111X(k)后一半的确定由旋转因子的周期性：这就是说，E(k)和F(k)的后一半分别等于其前一半的值。同理：可见,X(k)的后一半，也完全由E(k)和F(k)的前一半确定。即N点的DFT可由两个N/2点的DFT来计算。信息与通信工程学院2021/9/112蝶形运算－－流图表示蝶形运算流图（N/2个蝶形):-1由E(k)、F(k)表示X(k)的运算是一种特殊的

6、运算-碟形运算-1信息与通信工程学院2021/9/113(二)N/4点DFT由于N=2L,所以N/2仍为偶数,可以进一步把每个N/2点的序列再按其奇偶部分分解为两个N/4的子序列。其中：蝶形图同上类似。信息与通信工程学院2021/9/114(三)2点DFT按上述办法不断划分下去，直到最后剩下2点DFT，2点DFT实际上只有加减运算。DIT－FFT算法，是在时间上对输入序列的次序是属于偶数还是属于奇数来进行分解的，所以称作按时间抽取的算法。例：作N＝8时FFT的运算流图由上推证：令与信息与通信工程学院2021/9/115例

7、续：N＝8时FFT的运算展开得：信息与通信工程学院2021/9/116例续：N=8点FFT的运算流图：WN0A(0)-1A(1)WN0WN0W0N-1-1-1B(0)B(1)D(0)C(0)C(1)D(1)WN0E(0)E(2)-1WN2WN0WN2-1-1-1E(1)E(3)F(0)F(1)F(2)F(3)X(0)X(4)N0W-1-1-1-1X(1)X(2)X(3)X(5)X(6)X(7)N1N2N3WWW信息与通信工程学院2021/9/117二DIT－FFT运算量分析由上例分析可知，N=8=需三级蝶形运算,由此可推

8、：N=2L共需L级蝶形运算，L＝log2N；每级都由N/2个蝶形运算组成；每个蝶形运算有一次复乘，两次复加。因此，N点的FFT的运算量为：复乘:mF=（N/2）*L=（N/2）*log2N复加:aF=2*（N/2）*L=N*log2N即计算量远比DFT的计算量小。以乘法作为基准，二者的比较结果如p.101图4.2.5