快速fft算法的研究---毕业论文

《快速fft算法的研究---毕业论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、【标题】快速FFT算法的研究【作者】王明静【关键词】快速傅里叶变换 MATLAB SIMULINK DIT-FFT  快速度【指导老师】孙艳菱【专业】物理学【正文】1绪论1.1快速FFT算法的研究意义1.1.1理论意义傅利叶变换是一种将信号从时域变换到频域的变换形式，然而，当N很大的时候，求一个N点的DFT要完成N×N次复数乘法和N(N-1)次复数加法，其计算量相当大。在20世纪60年代由Cooley和Tukey提出了快速傅利叶变换(FFT)算法，它是快速计算DFT的一种高效方法，可以明显地降低运算量，大大地提高DFT的运算速度，运算时间缩短一至两个数量级，从而使DFT变换的应用迅速

2、普及，不仅在频谱分析，而且在线性卷积、线性相关等方面得到广泛应用。1.1.2现实意义随着计算机技术的发展，离散傅里叶变换(DFT)算法的出现，使得傅里叶变换在工程上进入实际运用阶段。在信号处理中，DFT的计算具有举足轻重的地位，信号的相关、滤波、谱估计等都要通过DFT来实现。但必须减少它的运算量，DFT才能在工程计算中具有实用价值，所以FFT的出现提高了它的实用价值，而FFT成为数字信号处理的关键技术，在信号处理领域扮演的角色越来越重要。高效率的快速傅立叶变换(FFT)算法是雷达信号处理、卫星通讯、生物医学和多媒体信号处理等基础和核心算法。提高FFT处理速度，满足对雷达信号处理实时性

3、的要求，在EW接收机高速数据处理方面将有广泛的应用前景。随着科学技术的不断进步，相控阵体制已广泛应用于各种星载、机载、舰载和地面雷达，对于电尺寸较大(几十甚至几百个波长)的相控阵天线(如高分辨率星载SAR天线、大型稀布阵天线等)，用公式按级数求和计算阵列天线方向图的方法效率甚低，FFT的引入将从根本上解决这一难题。平面近场测量方法是天线测量的常规手段，而FFT技术为加快了天线参数评估的速度。1.2FFT算法的研究现状信号处理有着悠久的历史。在数字信号处理中，信号是用有限精度的数的序列来表示的，用数字运算来实现处理。而离散时间信号处理既包括了作为一种特殊情况的数字信号处理，也包括了用其

4、他一些离散时间计算处理样本序列的可能。Cooley和Tukey所研究出的计算离散傅氏变换的快速傅里叶变换，将计算量从( )下降到( )，从而使得FFT在数字信号处理、石油勘探、地震预报、医学断层诊断、编码理论、量子物理及概率论等领域都得到了广泛的应用。快速傅立叶变换（FFT）属于数字信号处理中最基础的运算，已广泛应用于通讯、医学电子学、雷达或无线电天文学等领域。高性能计算机以其巨大的存储容量和极快的计算速度得到了信号处理界的重视，成了国际上的研究热点。1.2.1国外现状国外围绕快速傅立叶变换的并行计算进行了多项研究和开发。美国NewMexico（新墨西哥）大学VasiliosGeor

5、gitsis等人设计了2-DFFT程序，可处理512*512个点的图像，其底层通信基于PVM，将2-DFFT转化成1-DFFT并行计算，完成了二维图像的变换。目前最新的研究成果是由麻省理工学院计算机科学实验室超级计算技术组开发的FFTW，FFTW是计算离散Fourier变换（DFT）的快速C程序的一个完整集合，它可计算一维或多维、实数据和复数据以及任意规模的DFT[1]。在FFTW中，DFT的计算由执行器完成，执行器是由许多高度优化的、可组装的子代码模块组成的。FFTW有一个规划器，规划器用以根据具体机器的体系结构特点和具体的DFT宽度N，在运行时寻找一种有效的子代码块组装方式，因此

6、使得FFTW具有很好的自适应性和很快的运行速度。FFTW还包含对共享和分布式存储系统的并行变换。1.2.2国内现状在我国，80年代初就开展了并行算法研究。快速傅立叶变换的并行算法主要包括：基于SIMD-MC2、SIMD-BF、SIMD-CC、MIMD-DM四种体系结构上的FFT算法，它们都是基-2FFT算法，算法各有利弊，受体系结构影响较大[2]。SIMD-MC2上的FFT算法，是按频率抽取的快速傅立叶变换在网孔结构上的具体实现。假设将n个处理器P0，P1，…，PN-1排成 × 的方阵。初始序列开始时已处于阵列的各处理器中，即ak处于Pk中。算法结束时，Pk保存bk。SIMD-BF上

7、FFT算法是在一个n=2k的蝶形网络（简记为BF），将(k+1)、2k个节点，布局成(k+1)行，每行有n个节点[3]。令(r，i)表示第r行和第i列的坐标，0in-1， ；exp(r，i)表示在BF中坐标点(r，i)处的w的指数，它等于字长为k的整数j，即exp(r，i)=j，使得如果i的二进制表示为a1a2…ar-1ar…ak，则j的二进制为ar、ar-1…a1、00…0。也就是说，将i的前r位取位反（即倒序），后面其余位补零就可以得到j。因为蝶形网络