毕业设计（论文）文献综述
课题名称：基于FPGA的FFT算法实现
学院：机电工程学院
专业：电子信息工程
年级：
指导教师：
学生姓名：
学号：______
起迄日期：__
日
一、前言
DFT和卷积是信号处理中两个最基本也是最常用的运算，他们涉及到信号与系统的分析与综合这一广泛的信号处理领域。卷积可以化为DFT来计算，实际上其他许多算法，如相关、滤波、谱估计等也都可以化为DFT来计算。当然，DFT也可化为卷积来实现。由后面的讨论可知，它们之间有着互通的关系。对N点序列x(n),要求出DFT变换对，就需要先求出N点X(k)需要N2次复数乘法，N(N-1)次复数加法。众所周知，实现一次复数乘需要四次实数乘两次加法，实现一次复数加则需要两次实数加。当N很大时，其计算量是相当可观的。例如，若N=1024，则需要1048576次复数乘法，即4194304次实数乘。所需要时间过长，难于“实时”实现。对于2-D图像处理，所需要计算量更是大得惊人[1]。
又例如，在FIR滤波器设计中会遇到从h(n)求H(k)或由H(k)求h(n)，这就需要计算DFT。再有，信号的频谱分析对通信、图像传输、雷达、声纳等都是很重要的。此外，在系统的分析、设计和实现中都会用到DFT的计算。但是，在相当长的时间里，由于DFT的计算量太大，即使采用计算机也很难对问题进行实时处理，所以并没有得到真正的应用。直到1965年库利在《计算数学》杂志上发表了著名的“及其计算傅里叶级数的一种算法”的文章，提出了DFT的一种快速算法FFT，后来又有桑德和图基的快速算法FFT相继出现，情况才发生了变化[2]。
主题
序列和线性时不变系统的频域特征是用Z变换和傅里叶变换来表示的。对于有限长序列，可以导出另一种傅里叶变换表示式，即离散傅里叶变换（简称DFT——DiscreteFourierTransform），它是解决频谱离散化的有效方法，并因存在着计算DFT的高效算法——快速傅里叶变换FFT（FastFourierTransform），因而离散傅里叶变换不仅在理论上有重要意义，而且在各种数字信号处理的运算方法中起着重要的作用[3-4]。
FFT算法可分为时间抽取法和频率抽取法。时间抽取法，就是在时域内逐次将序列分解成奇数子序列和偶数子序列，通过求子序列的DFT而实现整个序列的DFT，将计算DFT的运算量从N2减少到（N/2）log2N次复乘。频率抽选法就是在品域内将X(k)逐次分解成偶数点子序列和奇数点子序列，然后对这些分解得越来越短的子序列进行DFT运算，就可得整个频域内序列的FFT流图[3]。
FFT算法在数字信号处理中应用十分广泛，它可以用软件来实现，也可以用硬件实现。由前面分析可知，FFT算法的实质是完成算法所需的全部蝶形运算，核心运算是蝶形运算。所谓软件实现就是在通用计算机上用高级语言或汇编语言编制软件程序顺次实现全部蝶形运算。而所谓硬件实现就是用专用硬件来实现蝶形运算。一个蝶形运算可以看成一个运算器，运算器是用专用硬件电路或芯片来实现。它可以用位片式微处理器(例Am2900系列芯片)、快速阵列乘法器或是单片信号处理器组成。当然专用硬件仍然需要微程序来控制．亦就是说仍是离不开软件的，同样在通用机上软件实现亦离不开CPU芯片等硬件。因此严格地说应是软硬兼备的。所谓软硬之分仅是习惯上的分类罢了[4]。
FFT算法巧妙地利用了DFT的一些特性，大大地减少了运算量。因而亦大大地提高了运算速度。但在许多实时信号处理中，要求在输入信号的同时，及时地一段段地完成对信号的FFT运算。这将对计算机的运算速度提出更高的要求，采用软件实现实时信号处理便有一定的因难，通常需采用硬件方式实现。硬件实现的方法很多，既与选用的运算器件有关．亦与所用运算器的数量及编排方法有关，还与算法的流图形式有关，可以是单运算器的顺序处理或多远算器的级联处理、并行迭代处理，阵列处理及流水线式处理。FFT算法的一个明显特点是具有分级运算的结构。因此，为了提高运算速度，可以在每级运算中采用单独的运算器，第一级运算器算完后送给第二级，自己再算新来的数据，第二级算完后送第三级，……，形成流，亿线的工作方式[4]。
对于逻辑集成器件、无论是基本SSI或MSI技术的标准通用逻辑集成电路，如74系列，4000系列器件、还是基本LSI／VLSI技术的数字系统单片化的专用集成电路(ASIC)，其从生产厂家出来后、电路的逻辑功能是固定的、用户只能去根据自己用户系统的需求，选择它，应用它，而无法去重新修改或重新定义其逻辑功能。凡是搞过硬件电路的设汁工程师都知道，用通用的标准逻辑集成器件组合设计一块特定逻辑功能的电路板是很麻烦的。光要进行逻辑电路设计，然后再进行印刷电路板设计，最后焊接为成品；不但设计周期长、工艺可靠性及可维修性差、又其物理空间的体积亦无法缩小。互用一块块简单逻辑集成器件构成的逻辑功能板的集成容量是比较低的。在现代电子系统产品设计中、随着VLSI技术发展，系统单片化设计的ASIC成为主流。但是，这类针对用户系统要求而订制的ASIC器件，其往往需要很长的设计周期。且前期一次性投资大，设计风险亦大，除非大批量的产品需要。否则器件成本很高[5]。
用户现场可编程门阵列器件(FPGA)是一种新出现的可由用户自行定义配置的高容量密度的专用集用电路(IC)，其将定制的VLSI电路的单片逻辑集成的优点和用户可编程逻辑器件的设计灵活，工艺实现方便，产品上市快捷的长处结合起来，目前已成为一类标准的产品，以FPGA为代表，FPGA器件在集成电路工厂按高的容量密度来大量生产，然后由用户在现场，利用专用的开发系统，根据专门的应用设计要求，进行设计、编程、实现，从而可将以前由几个乃至几百个TTL，PLD，EPLD逻辑器件执行的逻辑功能可以在现场直接集成到一单片的FPGA器件之中，从而可以有效地避免定制ASIC设计的高成本，高风险和较长的设计周期的不足，为数字系统应用设计者，特别是对少批量产品，试制产品，提供了新的实现路径[5]。
FPGA的整体设计可以分为输入/输出2个部分：输入部分主要由数据接收处理模块组成，输出部分主要由FFT运算处理部分组成。2个模块之间的数据传递通过地址生成及数据查找模块完成[6]。
硬件实现快速傅里叶变换（FFT）算法的方案包括：数字信号处理器（DPS）、专用集成电路（ASIC）和现场可编程门阵列（FPGA）。其中DSP适合用于流程复杂的算法，例如在通信系统中信道的编码和解码，利用DSP进行FFT运算将占用大量DSP的运算时间，降低整个系统的数据吞吐率，也无法发挥DSP的灵活性；采用ASIC运行FFT运算完全能达到速度要求，但可扩展性差；FPGA具有可重构的特点，是适合于算法结构固定、运算量大的前端数字信号处理。现在FPGA产品都采用多层布线结构，核心电压低、IO管脚丰富、容量可达到100K个逻辑单元，并且内置嵌入式RAM资源、集成多个数字锁相环和多个嵌入的硬件乘法器[7]。
因此，FPGA在数字信号处理领域显示出自己特有的优势，并且也已经广泛应用。近年来，国内也设计完成很多利用硬件方法处理FFT算法的实例，并且基于FPGA设备的方法也已经提出并正在实现。但电子设备对速度的要求也越来越快，面对这种情况，针对目前所拥有的方法，设计出一种利用FPGA实现FFT运算的加速方案，并以1024点FFT为例，从而在ISE软件上通过了综合和仿真[6]。
三、总结
对于本毕设的基于FPGA的FFT算法实现的设计，首先要学习多种FFT变换的算法、VHDL语言以及FPGA芯片，其次在确定FFT的实现方案以后，要运用VHDL语言进行编程，并在软件上实现其仿真。查找参考文献是写好论文的关键，只有通过不断的学习FFT算法的相关的知识，才能让自己有一个更加快速的提高。最终，通过这次的设计提高了自己的动手能力，从而使自己将理论知识与实践相结合，为自己以后踏入社会打下基础。
参考文献：
[1]胡广书.数字信号处理-理论、算法与实现[M].北京：清华大学出版社.数字信号处理（第二版）[M].北京：清华大学出版社.[M].北京：人民邮电出版社，2003.4
[4]俞卞章.数字信号处理[M].西安：西北工业大学出版社，2002.8
[5]朱明程.现场可编程逻辑门陈列器件FPGA原理及应用设计[M].1994年05月第1版
[6]苏彦鹏，张汉富，韩磊.基于FPGA的4k点基-16FFT模块的实现［J］电子与封装，2007,7（9）:8-11.
[7]褚振勇,翁木云.FPGA设计及应用[M].西安:西安电子科技大学出版社,2002:11-15
|
|
