1228.dft快速算法的研究

《1228.dft快速算法的研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、目录摘要………………………………………………………………..1第一部分FFT的回顾……………………………………………2第一节DFT与FFT的过渡…………………………………….2第二节按时间抽取以2为基的算法(FFT-DIT2)（库利-图基算法）………………………………………………………………...2第三节按频率抽取以2为基的算法(FFT-DIT2)（桑德-图基算法）...………………………………………………………………6第二部分混合基与分裂基的研究………………………………..7第一节混合基的相关知识………………………………………7第二节分裂基的相关知识…………………………………

2、……9第三部分FFT算法改进…….…………..……………………….12第四部分FFT实例运行结果及比较……………………………14第五部分总结与感想………………………………………….……18参考文献…..……………………………………………………...19摘要快速傅立叶变换FFT是离散傅立叶变换DFT的一种快速算法,我们知道有限长序列的主要特点是其频域也可以离散化成有限长序列，即能进行DFT变换。DFT广泛应用于信号的频谱分析、滤波器的设计以及系统的分析、设计和实现中。而在相当长时间中由于N值大时，计算量大。无法达到实时处理的要求。1965年,库利(cooley)和图基(Tukey

3、)首先提出FFT算法.对于N点DFT,仅需(N/2)log2N次复数乘法运算。大大提高了计算效率。后来又有桑德快速算法以及一些算法改进。FFT是DFT的一种快速计算机算法，无任何近似，无精度损失。本论文主要介绍基本FFT算法与实现，以及混合基、分裂基等一些先进算法，最后附有方案改进和算法程序设计。第一部分FFT的算法回顾第一节DFT与FFT的过渡N点有限长序列x(n)的DFT为二者仅有一符号之差和一个常熟因子1/N。由DFT可知完成整个DFT运算共需N2次复数乘法和N(N-1)次复数加法。由复数知识可知，此运算4N2次实数乘法和2N(N-1)次实数加法运算。因此DFT正比于N2

4、，当N很大时，其运算量很可观。为此我们对此加以改进。在DFT中我们知道WNnk具有一些特定性质：可得出由此可对DFT中的一些项合并，将其分解为短序列DFT，FFT就是由此而得出的。第二节按时间抽取以2为基的算法(FFT-DIT2)（库利-图基算法）设序列点数N=2L，L∈Z。如条件不满足可人为加上若干个0，N=2L序列n的奇偶分两组于是得经过WNnk的性质转换使X（k）前后分离如下：对X(k)的前一半（k=0,1,…,N/2-1）,由DFT定义:对X(k)的后一半（k=N/2,N/2+1,…,N-1）由此我们只需求0——N/2－1区间的，，就可求出X（k）。其算法流图如下图一。

5、X1（0）N/2点DFTx(0)X（0）X1（1）WN0x(2)X（1）X1（2）WN1x(4)X（2）X1（3）WN2x(6)X（3）Y1（0）WN4WN3N/2点DFTx(1)X（4）Y1（1）WN5x(3)X（5）Y1（2）WN6x(5)X（6）Y1（3）WN7x(7)X（7）图一N点离散傅立叶变换的计算化为两个N/2点离散傅立叶变换的计算（N=8）由以上流图可见，其FFT的运算量大大减少。直接计算DFT与FFT算法的计算量比值见下表1。表1NN2N22414.041644.0864125.416256328.03210248012.864409619221.412816

6、38444836.625665536102464.0由流图可知，输入为顺序，而输出为倒位序，其完成是通过变址运算来实现的。下表2是N=8时的顺序二进制数以及相应的倒位序二进制数。表2自然数二进制数倒位序二进制数倒位序顺序0000000010011004201001023011110641000011510110156110011371111117通过上面的推导可以看出，N点DFT可以分解为两个N/2点的DFT，每个N/2点的DFT又可以分解为两个N/4点的DFT。依此类推，当N为2的整数次幂时（N=2M），由于每分解一次降低一阶幂次，所以通过M次的分解，最后全部成为一系列2点D

7、FT运算。以上就是按时间抽取的快速傅立叶变换（FFT）算法。序列X（k）的离散傅立叶变换的区别在于将WN改变为WN-1，并多了一个除仪N的运算。因为WN和WN-1对于推导按时间抽取的快速傅立叶变换算法并无实质性区别，因为可将FFT和快速傅立叶反变换（IFFT）算法合并在同一个程序中。如下语句（C语言）：1.子函数语句voidsrfft(x，y，n，sign)1.形参说明x――双精度实型一维数组，长度为n。开始时存放要变换数据的实部，最后存放变换结果的实部。y――双精度实型一维数组，长度为n。