资源描述：
《快速离散傅立叶变换》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第十章快速离散傅立叶变换本章的教学内容改进DFT计算的方法按时间抽取的FFT算法（DITFFT）按频率抽取的FFT算法（DIFFFT）第十章快速离散傅立叶变换（1）FFT:FastFourierTransform（2）傅立叶级数和傅立叶变换理论在19世纪就已经提出,时域离散傅立叶变换理论也在20世纪初发展完善.但由于其手工计算的复杂性,在工程实践中并没有得到广泛应用.相反,在应用中使用广泛的是其它一些手工计算相对简单的数学分析手段,如沃尔什变换.直到1965年,库利-图基提出了针对N时复合数情况的快速离散傅立叶变换算法,与传统算法
2、相比降低了1～２个数量级,由此引发了研究快速算法的热潮.这些算法统称为FFT.FFT算法的广泛应用，不仅奠定了离散傅立叶变换在数字信号处理中的经典地位,也极大推动了数字信号处理应用与发展.第一节改进DFT计算的方法衡量算法的复杂性:乘.加法运算次数,不考虑控制调度等操作;只考虑DFT的正变换,因为:K=0,1,…,N-1DFT正变换DFT反变换反变换相对正变换:输入取共扼;输出取共轭并加权.直接计算DFT的运算量n=0,1,…,N-1k=0,…,N-1复数运算对每一个k值:复乘:N复加:N-1第一节改进DFT计算的方法对所有k:复
3、乘:复加:N(N-1)即复数运算量与近似成正比(不考虑情况)实数运算k=0,…,N-1第一节改进DFT计算的方法对每一个固定k:实乘:4N实加:对所有k:实乘:4N2实加:2N(2N-1)=4N2-2N实数运算量与近似成正比结论:直接计算DFT的乘.加运算量近似与成正比.第一节改进DFT计算的方法改善运算效率的途径（1）利用的对称性和周期性等特性合并运算项复共轭对称性:对n和k的周期性:可约性特殊值第一节改进DFT计算的方法式中其它各对称项也可以找到类似归并办法.这样乘法次数大约可减少一半.(2)大点数DFT逐次分解成小点数DFT
4、)分解正是FFT算法的基本原理第一节改进DFT计算的方法例:利用对称性,可以合并对称项:FFT的基本原理：为了提高DFT的运算效率,把大点数DFT按倒位序逐次分解为更小点数DFT的合成.在分解过程中,要利用系数的对称性和周期性.如果算法是逐次分解时间序列得到的,那么这种分解算法称为按时间抽取算法.阐述按时间抽取原理最方便的方法是研究这种特殊情况.由于N为2的整数幂,可以不断将x(n)一分为二.这就是最常用的基-2FFT算法.如果序列不满足这个条件,可以人为地加上若干零点得到.第一节改进DFT计算的方法第二节按时间抽取FFT算法算法
5、原理：假设序列x(n)长为(n=0,…,N-1),由于N为偶数,可以将x(n)按n为奇数和偶数分解为两个N/2的长序列,并依此逐级分解来计算x(k).是x(n)按n为奇、偶数分为2个子序列，得:第二节按时间抽取FFT算法第一级分解定义偶序列与奇序列:上式可写为:第二节按时间抽取FFT算法其中:k=0,…N/2-1第二节按时间抽取FFT算法上式表明一个N点的DFT可以分解成两个点的DFT.这两个点的DFT又可按式合成一个N点DFT一个问题:和的长度为,它们的DFT和的点数也为,而x(k)却有N个点。利用的周期性解决这一问题，即：第二
6、节按时间抽取FFT算法表达为前后两个部分:前半部分后半部分k=0,…k=0,…和的周期为同样可得把即：第二节按时间抽取FFT算法这样只要求出0~-1区间所有和,就可以求出0~N-1区间内全部X(k)的值.这就是FFT运算的关键所在。用以下信号流图表示为：根据流图的形状，上述运算称为碟形运算。第二节按时间抽取FFT算法复乘:1复加:2一次蝶形运算:运算分析:当一次分解后DFT运算的信号流图为：第二节按时间抽取FFT算法仍为偶数,可以直接计算N点DFT所需复乘,复加N(N-1),可见当N较大时,一次分解后运算量减少近一半.由于N=(M
7、>1),经一次分解后点DFT再分别分解为两个点DFT的组合.进一步把每个复乘:一次分解:2个点DFT+个蝶形运算复加:第二节按时间抽取FFT算法第二级分解可得:第二节按时间抽取FFT算法与第一级分解一样,利用和隐含的周期性,为改写为前，后两部分:其中:第二节按时间抽取FFT算法由此一个点DFT分解成两个点的DFT.其流图为:第二节按时间抽取FFT算法也可以进行同样分解:第二节按时间抽取FFT算法奇序列中的偶序列,奇序列中的奇序列第二节按时间抽取FFT算法为改写为前,后两部分:第二节按时间抽取FFT算法其中:系数统一为(今后都使用统
8、一的系数),这样,一个N点DFT就分解成4个N/4点的DFT,其信号流图为:第二节按时间抽取FFT算法根据前面的分析,第二级分解组合比第一级分解后的运算量又降低了一半.对于N=8点的DFT,经过两次分解后,最后剩下四个N/4=2的DFT,即(k=0
