基于FPGA的FFT的设计与实现

信息与通信工程学院综合实验（1）设计报告基于FPGA的FFT设计与实现学号：S309080034专业：光学工程学生姓名：彭欢任课教师：钟志副教授2010年7月基于FPGA的FFT的设计与实现彭欢信息与通信工程学院摘要：本文主要研究如何利用FPGA实现FFT处理器，包括算法选取、算法验证、系统结构设计、各个模块设计、FPGA实现和测试整个流程。设计采用基-2按时间抽取算法，以XILINX公司提供的ISE6.1为软件平台，利用VerilogHDL描述的方式实现了512点16bist复数块浮点结构的FFT系统，并以FPGA芯片场VirtexIIXC2V1000为硬件平台，进行了仿真、综合等工作。仿真结果表明其计算结果达到了一定的精度，运算速度可以满足一般实时信号处理的要求。关键词：快速傅立叶变换，现场可编程门阵列，块浮点，VerilogHDL1引言目前，FFT己广泛应用在频谱分析、匹配滤波、数字通信、图像处理、语音识别、雷达处理、遥感遥测、地质勘探和无线保密通讯等众多领域。在不同应用场合，需要不同性能要求的FFT处理器。在很多应用领域都要求FFT处理器具有高速度、高精度、大容量和实时处理的性能。因此，如何更快速、更灵活地实现FFT变得越来越重要。在过去很长一段时间，DSP处理器是DSP应用系统核心器件的唯一选择。尽管DSP处理器具有通过软件设计能适用于实现不同功能的灵活性，但面对当今速度变化的DSP应用市场，特别是面对现代通信技术的发展，DSP处理器在处理速度上早已力不从心。与DSP相比，FPGA实现FFT的主要优越性有：(1)、FPGA实现数字信号处理最显著的特点就是高速性能好。FPGA有内置的高速乘法器和加法器，尤其适合于乘法和累加等重复性的DSP任务。(2)、FPGA的存储量大。DSP内部一般没有大容量的存储器，但是FTF实时处理运算需要存储大量的数据，只能外接存储器，这样往往会使运算速度下降，同时电路也会更复杂和不稳定。目前，高档的FPGA中有巨量的高速存储器，不用外接存储器便可实现FFT实时处理运算，其速度更快，电路更简单，集成度和可靠性也大幅度提高。(3)、FPGA是硬件可编程的，比DSP更加灵活。DSP往往需要外部的接口和控制芯片配合工作，FPGA则不需要，这样使得硬件更简单和小型化。(4)、在比较FPGA和DSP时，一个极为重要的系统参数是输入/输出(1/0)带宽。除了一些专用引脚外，FPGA上几乎所有的引脚均可供用户使用，这使得FPGA信号处理方案具有非常高性能的FO带宽。大量的FO引脚和多块存储器可让系统在设计中获得优越的并行处理性能。2现场可编程门阵列(FPGA)技术2.1FPGA器件简介FPGA即现场可编程门阵列，它是作为ASIC领域中的一种半定制电路而出现的，既解决了定制电路的不足，又克服了原有可编程器件门电路数有限的缺点。FPGA结合了微电子技术、电路技术、EDA技术，使设计者可以集中精力进行所需逻辑功能的设计，缩短设计周期，提高设计质量。FPGA己经在计算机硬件、工业控制、遥感遥测、雷达声纳、数据处理、智能仪器仪表、广播电视、医疗电子和现代通信等多种领域中得到广泛应用，FPAG开发技术，己经成为数字系统的教学实践、科研试验、样机调试和中小批量生产的首选方案。2.1.1FPGA的基本结构FPGA采用了逻辑单元阵列LCA这样一个新概念，内部一般是由可配置逻辑模CLB、可编程输入/输出模块IOB和互连资源ICR及一个用于存放编程数据的静态存储器SRAM组成，以XILNIX公司的XC4000，基本结构如图2.1所示。图2.1XC4000系列FPGA基本结构2.1.2FPGA器件的性能特点FPGA器件的性能特点主要有：(1)、采用FPGA设计ASIC电路，用户不需要投片生产，就能得到合用的芯片。(2)、FPGA提供丰富的I/O引脚和触发器，集成度远远高于可编程阵列逻辑(PAL)器件。(3)、FPGA器件结构灵活，内部的CLB、IOB和ICR均可以编程，可以实现多个变量的任意逻辑。(4)、某些器件提供片内高速RAM，可用于FIFO等设计。(5)、基于SRAM编程技术，具有高密度、高速度、高可靠性和低功耗的特性。(6)、FPGA是ASIC电路中设计周期最短、开发费用最低、风险最小的器件之一。2.2基于FPGA的系统开发以XILNIX为例，FPGA设计的一般流程包括设计输入、功能仿真、设计实现、时序仿真、器件编程与测试几个步骤。设计流程图如图2.2所示。规划和预算编写代码绘制原理图HDLRTL仿真综合建立网络表功能仿真转换实现映射布局布线实现时序逼近时序仿真建立位流文件图2.2FPGA设计流程(l)、设计输入:主要输入方法有硬件描述语言和原理图，结构向导(ArchitrctureWizard)和核生成器(CoreGeneartor)可以辅助设计输入。(2)、功能仿真:功能仿真没有器件内部逻辑单元和连线的实际延时信息，只是初步验证系统的逻辑功能。(3)、设计实现:实现包括转换、映射、布局布线、时间参数提取，同时产生各种报告和文件。(4)、时序仿真:时序仿真中使用了电路延时的最坏情况，分析时序关系，检查和消除竞争冒险、并对器件的实际工作性能进行估计。(5)、器件编程与测试:设计实现以后，建立FPGA可识别文件，将编程数据下载到相应的FPGA器件中去。在FPGA设计的各个环节都有不同公司提供的不同的EDA工具。一般由FPGA厂商提供集成开发环境，如ALTERA公司的QuartusII和XILINX公司的ISE。为提高设计效率，优化设计结果，很多厂家提供了各种专业软件，用以配合FPGA/CPLD芯片厂家提供的工具进行更高效的设计。比较常见的使用方式是：集成开发环境，专业逻辑仿真软件和专业逻辑综合软件一起使用，进行多种EDA工具的协同设计。本设计采用ISE6.1+Modelsim5.7g+SynpliyfPor。2.3硬件描述语言VerilogHDLHDL是硬件描述语言(HardwareDescriptionLanguage)的缩写，是一种用形式方法来描述数字电路和系统的语言。利用这种语言，数字电路系统的设计可以从抽到具体逐层描述自己的设计思想，用一系列分层次的模块来表示极其复杂的数字统。随着EDA技术的发展，使用HDL设计FPGA已成为一种趋势。目前最主要HDL是VHDL和VerilogHDL，本设计采用VerilogHDL。作为硬件描述语言，VerilogHDL具有如下特点：(1)、能够在不同的抽象层次上，如系统级、行为级、寄存器传输级RTL、门级和开关级，对设计系统进行精确而简练的描述；(2)、能够在每个抽象层次的描述上对设计进行仿真验证，及时发现可能存在的设计错误，缩短设计周期，并保证整个设计过程的正确性；(3)、由于代码描述与具体工艺实现无关，因此易于设计标准化，提高了设计的重用性。如果有C语言的编程经验，只需很短的时间就能掌握VerilogHDL。使用HDL进行设计时，需要设计者完成的任务有编写电路描述和编写包含激励波形描述的测试平台文件，其激励用于进行电路功能测试，代测电路的行为特性由仿真器显示波形。3FFT算法原理及其硬件结构设计3.1FFT算法基本原理有限长序列()xn及其频域表示()Xk可由以下离散傅立叶变换得出：10()DFT()(),(01)NnkNnXkxnxnWkN（3.1）101()IDFT()(),(01)NnkNkxnXkXkWnNN（3.2）其中，2ejnknkNNW。式(3.1)称为离散傅立叶(正)变换，式(3.2)称为离散傅立叶反变换，x(n)与X(k)构成了离散傅立叶变换对。根据上述公式，计算一个X(k)，需要N次复数乘法和N-1次复数加法，而计算全部X(k)(0≤k≤N-1)，共需要N2次复数乘法和N(N-1)次复数加法。实现一次复数乘法需要四次实数乘法和两次实数加法，一次复数加法需要两次实数加法，因此直接计算全部X(k)共需要4N2次实数乘法和2N(2N-1)次实数加法。当N较大时，对实时信号处理来说，对处理器计算速度有十分苛刻的要求，于是如何减少计算离散傅里叶变换运算量的问题变得至关重要。为减少运算量，提高运算速度，就必须改进算法。计算DFT过程中需要完成的运算的系数里，存在相当多的对称性。通过研究这种对称性，可以简化计算过程中的运算，从而减少计算DFT所需的时间。nkNW具有周期性、对称性和可约性。利用其特性，将x(n)或X(k)序列按一定规律分解成短序列进行运算，这样可以避免大量的重复运算，提高计算DFT的运算速度。算法形式有很多种，但基本上可以分为两大类，即按时间抽取FFT算法和按频率抽取FFT算法。3.1.1基-2时间抽取FFT算法如果序列x(n)的长度N=2M，其中M是整数(如果不满足此条件，可以人为地增补零值点来达到)，在时域上按奇偶抽取分解成短序列的DFT，使最小DFT运算单元为2点。通常将FFT运算中最小DFT运算单元称为基(radix)，因而把这种算法称为基-2时间抽取FFT(DIT-FFT)算法。若Xm(p)和Xm(q)为输入数据，Xm+1(p)和Xm+1(q)为输出数据，rNW为旋转因子，则对于基-2DIF-FFT算法，蝶形运算的基本公式为：11()()()()()()kmmmNkmmmNXpXpXqWXqXpXqW（3.3）其图形表示如图3.1所示，称Xm(p)为上结点，Xm(q)为下结点。Xm(p)Xm(q)WNk+-Xm+1(p)Xm+1(q)图3.1时间抽取蝶形运算单元3.1.2基-2频率抽取FFT算法上述的基-2DIT-FFT算法是按奇偶原则对输入序列x(n)进行抽取分解，结果在频域使X(k)前后分组。如果在时域把x(n)分解成前后两组，那么在频域就会使X(k)形成奇偶抽取分组，称为频率抽取FFT(DIF-FFT)算法。若Xm(p)和Xm(q)为输入数据，Xm+1(p)和Xm+1(q)为输出数据，rNW为旋转因子，则对于基-2DIF-FFT算法，蝶形运算的基本公式为：11()()()()[()()]mmmkmmmNXpXpXqXqXpXqW（3.4）其图形表示如图3.2所示，称Xm(p)为上结点，Xm(q)为下结点。Xm(p)Xm(q)WNk+-Xm+1(p)Xm+1(q)图3.2频率抽取蝶形运算单元DIT-FFT算法与DIF-FFT算法均为原位运算，而且运算量相同，不同之处在于：①数据存放的方式不同，DIT为倒序输入、正序输出，而DIF为正序输入、倒序输出，运算完毕需进行整序操作；②蝶形运算不同，DIT的复数乘法出现在(加)减法之前，而DIF的复数乘法出现在(加)减法之后。所以DIT-FFT算法和DIF-FFT算法是两种等价的FFT运算。参照DIT-FFT的数据地址产生规律，可总结出DIF-FFT的数据地址产生规律。3.2FFT的硬件实现结构选择合适的系统结构，是提高FFT处理器性能的关键。以基-2DIT-FFT算法为例，本章将首先讨论几种常用FFT处理器的实现形式。(1)顺序处理顺序处理是FFT专用处理器的基本形式，蝶形运算单元在控制器的控制下，根据标准的FFT信号流图，按时间顺序依次进行运算。即从第1级开始，从上至下依次进行，第1级算完后，然后进行第2级，第3级，······，直至算完为止。顺序处理具有以下特点：①只用一个蝶形运算单元；②输入数据、中间数据和输出结果均使用同一组存储器；③顺序执行2log2NN次蝶形运算；④如果一次蝶形运算时间为T，则总的运算时间为2log2NTN(2)流水线处理流水线处理是把一个重复的过程分解为若干个子过程，每个子过程可以与其他子过程并行进行。对一个N点的FFT变换，每一级的N/2次蝶形运算安排一个独立的蝶形处理器按顺序完成，总共采用2logN个蝶形运算单元同时进行工作，这种形式称为流水线处理或者级联处理。流水线处理具有以下特点：①使用2logMN个蝶形运算单元；②M个蝶形运算单元在各级间并行运