文献综述-基于FPGA的FFT算法实现

1、毕业设计（论文）文献综述课题名称：基于FPGA的FFT算法实现学 院：机电工程学院专 业：电子信息工程年 级：指导教师：学生姓名：学 号：起迄日期：一、前言DFT 和卷积是信号处理中两个最基本也是最常用的运算，他们涉及到信号 与系统的分析与综合这一广泛的信号处理领域。卷积可以化为 DFT 来计算，实 际上其他许多算法，如相关、滤波、谱估计等也都可以化为 DFT 来计算。当然， DFT 也可化为卷积来实现。 由后面的讨论可知， 它们之间有着互通的关系。 对 N 点序列x(n),要求出DFT变换对，就需要先求出N点X(k)需要N2次复数乘法， N(N-1)次复数加法。众所周知，实现一次复数乘需要四

2、次实数乘两次加法，实现 一次复数加则需要两次实数加。当 N 很大时，其计算量是相当可观的。例如， 若N=1024,则需要1048576次复数乘法，即4194304次实数乘。所需要时间过 长，难于“实时”实现。对于 2-D 图像处理，所需要计算量更是大得惊人 1。又例如，在FIR滤波器设计中会遇到从h(n)求H(k)或由H(k)求h(n),这就 需要计算DFT。再有，信号的频谱分析对通信、图像传输、雷达、声纳等都是 很重要的。此外，在系统的分析、设计和实现中都会用到DFT的计算。但是，在相当长的时间里，由于DFT的计算量太大，即使采用计算机也很难对问题进 行实时处理，所以并没有得到真正的应用。直

3、到1965年库利在计算数学杂志上发表了著名的“及其计算傅里叶级数的一种算法”的文章，提出了 DFT 的 一种快速算法FFT，后来又有桑德和图基的快速算法 FFT相继出现，情况才发 生了变化 2 。二、主题序列和线性时不变系统的频域特征是用 Z 变换和傅里叶变换来表示的。对 于有限长序列，可以导出另一种傅里叶变换表示式，即离散傅里叶变换(简称 DFTDiscrete Fourier Transform)，它是解决频谱离散化的有效方法，并因存在着计算 DFT 的高效算法快速傅里叶变换 FFT(Fast Fourier Transform)， 因而离散傅里叶变换不仅在理论上有重要意义， 而且在各种数

4、字信号处理的运算 方法中起着重要的作用 3-4 。FFT 算法可分为时间抽取法和频率抽取法。时间抽取法，就是在时域内逐 次将序列分解成奇数子序列和偶数子序列，通过求子序列的 DFT 而实现整个序 列的DFT，将计算DFT的运算量从N2减少到(N/2) logzN次复乘。频率抽选法 就是在品域内将 X(k) 逐次分解成偶数点子序列和奇数点子序列，然后对这些分 解得越来越短的子序列进行 DFT运算，就可得整个频域内序列的 FFT流图3。FFT算法在数字信号处理中应用十分广泛，它可以用软件来实现，也可以用 硬件实现。由前面分析可知，FFT算法的实质是完成算法所需的全部蝶形运算， 核心运算是蝶形运算。

5、 所谓软件实现就是在通用计算机上用高级语言或汇编语言 编制软件程序顺次实现全部蝶形运算。 而所谓硬件实现就是用专用硬件来实现蝶 形运算。一个蝶形运算可以看成一个运算器， 运算器是用专用硬件电路或芯片来 实现。它可以用位片式微处理器(例Am2900系列芯片)、快速阵列乘法器或是单 片信号处理器组成。 当然专用硬件仍然需要微程序来控制 亦就是说仍是离不开 软件的，同样在通用机上软件实现亦离不开 CPU 芯片等硬件。因此严格地说应 是软硬兼备的。所谓软硬之分仅是习惯上的分类罢了 4。FFT 算法巧妙地利用了 DFT 的一些特性，大大地减少了运算量。因而亦大 大地提高了运算速度。 但在许多实时信号处理

6、中， 要求在输入信号的同时， 及时 地一段段地完成对信号的FFT运算。这将对计算机的运算速度提出更高的要求， 采用软件实现实时信号处理便有一定的因难， 通常需采用硬件方式实现。 硬件实 现的方法很多， 既与选用的运算器件有关 亦与所用运算器的数量及编排方法有 关，还与算法的流图形式有关， 可以是单运算器的顺序处理或多远算器的级联处 理、并行迭代处理，阵列处理及流水线式处理。FFT算法的一个明显特点是具有 分级运算的结构。 因此，为了提高运算速度， 可以在每级运算中采用单独的运算 器，第一级运算器算完后送给第二级， 自己再算新来的数据， 第二级算完后送第 三级， , ，形成流，亿线的工作方式 4

7、。对于逻辑集成器件、无论是基本 SSI 或 MSI 技术的标准通用逻辑集成电路， 如 74系列， 4000系列器件、 还是基本 LSIVLSI 技术的数字系统单片化的专用 集成电路(ASIC)，其从生产厂家出来后、电路的逻辑功能是固定的、用户只能去 根据自己用户系统的需求， 选择它， 应用它， 而无法去重新修改或重新定义其逻 辑功能。凡是搞过硬件电路的设汁工程师都知道， 用通用的标准逻辑集成器件组 合设计一块特定逻辑功能的电路板是很麻烦的。 光要进行逻辑电路设计， 然后再 进行印刷电路板设计， 最后焊接为成品； 不但设计周期长、 工艺可靠性及可维修 性差、又其物理空间的体积亦无法缩小。 互用一

8、块块简单逻辑集成器件构成的逻 辑功能板的集成容量是比较低的。在现代电子系统产品设计中、随着 VLSI 技术 发展，系统单片化设计的 ASIC 成为主流。但是，这类针对用户系统要求而订制 的 ASIC 器件，其往往需要很长的设计周期。且前期一次性投资大，设计风险亦 大，除非大批量的产品需要。否则器件成本很高 5。用户现场可编程门阵列器件 （FPGA） 是一种新出现的可由用户自行定义配置 的高容量密度的专用集用电路（IC），其将定制的VLSI电路的单片逻辑集成的优 点和用户可编程逻辑器件的设计灵活， 工艺实现方便， 产品上市快捷的长处结合 起来，目前已成为一类标准的产品，以 FPGA为代表，FPG

9、A器件在集成电路工 厂按高的容量密度来大量生产， 然后由用户在现场， 利用专用的开发系统， 根据 专门的应用设计要求，进行设计、编程、实现，从而可将以前由几个乃至几百个 TTL ， PLD， EPLD 逻辑器件执行的逻辑功能可以在现场直接集成到一单片的 FPGA器件之中，从而可以有效地避免定制 ASIC设计的高成本，高风险和较长 的设计周期的不足，为数字系统应用设计者，特别是对少批量产品，试制产品， 提供了新的实现路径 5。FPG的整体设计可以分为输入/输出2个部分：输入部分主要由数据接收处理 模块组成，输出部分主要由FFT运算处理部分组成。2个模块之间的数据传递通过 地址生成及数据查找模块完

10、成 6 。硬件实现快速傅里叶变换（FFT）算法的方案包括：数字信号处理器（DPS）、 专用集成电路（ASIC）和现场可编程门阵列（FPGA）。其中DSP适合用于流 程复杂的算法，例如在通信系统中信道的编码和解码，利用DSP进行FFT运算将占用大量DSP的运算时间，降低整个系统的数据吞吐率，也无法发挥 DSP的 灵活性；采用ASIC运行FFT运算完全能达到速度要求，但可扩展性差； FPGA 具有可重构的特点， 是适合于算法结构固定、 运算量大的前端数字信号处理。 现 在FPGA产品都采用多层布线结构，核心电压低、IO管脚丰富、容量可达到100K 个逻辑单元，并且内置嵌入式 RAM 资源、集成多个

11、数字锁相环和多个嵌入的硬 件乘法器 7 。因此，FPGA在数字信号处理领域显示出自己特有的优势，并且也已经广泛应用。近年来，国内也设计完成很多利用硬件方法处理FFT算法的实例，并且基于 FPGA 设备的方法也已经提出并正在实现。 但电子设备对速度的要求也越来 越快，面对这种情况，针对目前所拥有的方法，设计出一种利用FPGA实现FFT运算的加速方案，并以1024点FFT为例，从而在ISE软件上通过了综合和仿真 6。三、总结对于本毕设的基于FPGA的FFT算法实现的设计，首先要学习多种 FFT变 换的算法、VHDL语言以及FPGA芯片，其次在确定FFT的实现方案以后，要运用 VHDL语言进行编程，并在软件上实现其仿真。查找参考文献是写好论文的关键， 只有通过不断的学习FFT算法的相关的知识，才能让自己有一个更加快速的提 高。最终，通过这次的设计提高了自己的动手能力， 从而使自己将理论知识与实 践相结合，为自己以后踏入社会打下基础。参考文献：1 胡广书数字信号处理-理论、算法与实现M.北京：清华大学出版社，19972 程佩青. 数字信号处理教程（第二版） M. 北京：清华大学出版社 .2001.83 门爱东，杨波，全子一 .数字信号处理 M. 北京：人民邮电出版社，