-
离散傅里叶变换是数字信号处理研究中最为重要的部分，同时也是我们进行信号分析处理工作过程中最为常用的工具之一。早在200多年前，法国数学家、物理学家傅里叶就提出了这种变换，并以他名字命名傅里叶级数，此后，DFT这个分析信号的重要工具就已经慢慢渗透到人们的生活中了。但是这种算法提出的初期，在很长时间内，由于这种方法运算量非常之大，用DFT进行应用是不切实际的，所以并没有被重视。直到1965年，库利（J.W.Cooley）和图基（J.W.Tukey）在期刊《计算机科学》上发表著名的《机器计算傅立叶级数的一种算法》这一论文后，FFT才开始崭露头角，并获得大规模应用。此后，众多算法相继出现，其中最具代表性的便是1984年，由法国学者杜哈梅（P.Dohamel）和霍尔曼（H.Hollamann）提出了分裂基块快速算法，使FFT的运算效率进一步提高，高效的FFT运算方法逐渐成型，即现在我们在应用的快速傅立叶变换。这种算法使DFT的运算效率提高1．2个数量级，为数字信号处理技术应用于各种信号的实时处理创造了良好的条件，大大推动了数字信号处理技术的发展[6][7]。26413
- 上一篇：自由视点立体电视技术国内外研究现状
- 下一篇：国内真伪币识别技术研究现状
FFT算法可以在多个平台上的实现。例如，现如今FFT算法已经可以应用特定的集成电路（ASIC）作为FFT处理器得以实现。FFT处理器的硬件设计通常能够符合高速或低功耗规格，但缺点是缺乏灵活性。算法已经可以由通用处理器上的软件作为模拟或数据处理系统的构建块实现了，但是基于通用处理器的软件模拟仿真虽然灵活，但通常比硬件在线调试的实现速度慢得多。数字信号处理器（DSPs）是一种为优化数字信号处理应用的特殊类型的处理器，如FIR滤波器，IIR滤波器和FFT，并且利用DSP软件实现FFT算法变得比基于ASIC和通用处理器实现算法更受欢迎，因为能够在成本，性能，灵活性和实现复杂度之间进行了良好的折衷。论文网
国外现状
快速傅里叶变换吸引了众多国外学者的目光，尤其是其并行计算更是有大批学者进行了多项研究和开发。快速傅里叶变换的并行算法主要包括基于SIMD-BF、MIMD-DM、SIMD-CC、SIMD-MC2四种体系结构，它们都是基-2 FFT算法，性能虽然不同但是各有千秋，其应用与效率与体系结构有关。
目前比较先进的研究成果是由麻省理工学院计算机科学实验室超级计算技术组开发的FFTW，FFTW是计算离散傅里叶变换的快速C程序的一个完整集合，它可计算一文或多文、实数据和复数据以及任意规模的DFT[3]。FFTW还包括了对共享及分布式存储系统的并行变换，可以自行适应机器、缓存、存储器大小以及寄存器个数。
国内现状
我国在80年代就对并行算法展开了研究：国防科技大学以向量机上的FFT为着手点对并行算法作了许多系统的研究，更根据离散变换、卷积、滤波的并行算法，开发出用多项式计算离散卷积以及利用短卷积嵌套计算长卷积的并行算法，进而研究出了离散卷积的并行计算下界，还对一文和二文的滤波给出了用变化法及递推公式计算的并行算法；西安电子科技大学信息科学研究所提出了一种基于共享存储的多机系统并行计算FFT算法；中国科学院计算技术研究所侯紫峰研究员利用星型互联网的递归可分解性的多样性，提出了一种基于星型互联网络的并行FFT算法。