基于FPGA的FFT设计与实现

基于FPGA的FFT设计与实现胥实08电子信息工程0845531138摘要:在数字信号处理中，许多算法如相关、滤波、谱估计、卷积等都可通过转化为DFT实现，从而为离散信号分析从理论上提供了变换工具。但DFT计算量大，实现困难。FFT的提出使DFT的运算效率提高了1～2个数量级。在基于FPGA的FFT设计中,为了提高速度,提出了用移位寄存器存储旋转因子的方法,并且在FPGA上做了验证。实验结果表明,该方法和普遍采用ROM做旋转因子存储器的方法相比,大幅提高了FFF的处理速度,能够更好地满足了FFT实时处理的要求。关键词:FFT；FPGA；蝶形运算；旋转因子1引言由于FPGA器件速度快、密度高、功耗低、可配置性强,现已在许多领域得到广泛地应用。高速FFT运算需要乘法器、大量RAM、寄存器,适合用FPGA实现。在FFT的硬件设计中,要充分利用芯片资源,减少复杂逻辑,为了提高系统时钟频率,实现高速处理,可以采用流水线方式与“双蝶形”结构并行处理。在流水线设计中,可以采用双RAM流水线结构,也可以采用局部流水和反馈思想,在简化结构的同时提高处理速度。一般用RAM存储FFT运算的中间数据,对旋转因子的存储通常采用ROM实现。随着FPGA发展，其资源丰富，易于组织流水和并行结构，将FFT实时性要求与FPGA器件设计的灵活性相结合，实现并行算法与硬件结构的优化配置，不仅可以提高处理速度，并且具有灵活性高。开发费用低、开发周期短、升级简单的特点。本文提出了基于FPGA的设计来实现FFT算法，并以16位长数据，64点FFT为例，在QuartusⅡ软件上通过综合和仿真。算法实现的可以是基2/4混合基FFT，也可以是纯基4FFT和纯基2FFT运算。2FFT原理和运算流图FFT是离散傅立叶变换(DFT)的快速算法。对于N点离散的有限长时问序列x(n)，其傅里叶变换为：完成N点的DFT需要N2次复数乘法和N(N-1)次复数加法。点数大时，计算量也大，所以难以实现信号的实时处理。FFT的基本思想是利用旋转因子WN的周期性、对称性、特殊性以及周期N的可互换性，将长度为N点的序列DFT运算逐次分为较短序列的DFT运算，合并相同项，大大减少了计算量。FFT算法分为两大类：一类是针对N=2的整数次幂的算法，如基2算法、基4算法、实因子算法和分裂算法等：另一类是N≠2的整数次幂算法，以winograd为代表的一类算法。硬件实现时，不仅要考虑算法运算量的大小，而且要考虑算法的复杂性和模块化。控制简单、实现规整的算法在硬件系统中要优于仅降低运算量的算法。现有FFT算法的FPGA设计方案基本上都是针对于第一类算法，而第二类算法尽管有其重要的理论价值，但硬件不易实现。由于该设计点数不是太多，综合考虑FFT处理器的面积和成本。所以采用按时间抽取的基2快速傅立叶算法(基2DIT-FFT)。对于长度为N=2m的序列x(n)，其中m是整数，将x(n)按奇偶分成两组，即令：n=2r和n=2r+1，而r=0，1，…，N/2-1，于是：所以A(k)和B(k)可完整表示X(k)。依次类推，可一直向前追溯到2点的FFT，这样整个N点的FFT算法分解成log2N级运算，每级有N／2个基2碟形运算。图1是N=8的DIT-FFT运算流图。图1N=8的DIT-FFT运算流图3FFT处理器结构框图FFT实现的设计方案有顺序处理、级联处理、并行处理和阵列处理。考虑到该设计运算点数少，在原有顺序处理的基础上对FFT处理过程中数据传输进行控制。采用自顶向下的方法对处理器模块化，其结构框图如图2所示。图2FFT处理器结构框图4模块设计整个FFT处理器是由存储器、蝶形运算单元、旋转因子单元、控制单元和数据控制单元组成，各个单元通过控制单元产生的控制和使能信号进行工作。蝶形运算单元是整个FFT处理单元的重要部分，直接影响整个FFT单元性能。基2时间抽取的蝶形信号流程图如图3所示，p和q为数据序号，xm(p))和xm(q)是第m级蝶形运算的输入，xm+1(p)和xm+1(q)是该蝶形运算的输出，WrN为相应的旋转因子。为了提高运算速度采用并行运算，采用4个实数乘法器、3个实数加法器和3个实数减法器组成。设输入数据：x1=x1_r+jx1＿im，x2=2＿r+jx2＿im，旋转因子为WrN=c-jd，则输出y1=y1_r+jy1_im和y2=y2_r+jy2＿im。实现蝶型运算单元如图4所示。图4蝶形运算单元数据格式选择定点16位二进制补码。设计时必须考虑乘法器速度，将会直接影响整个FFT处理单元的运算速度,该设计的乘法器利用QuartusⅡ开发软件中所提供的宏单元生成。乘法器的两输入均为16位，输出32位。因为乘法器中带有旋转因子项．所以乘法运算后不应改变输入的幅值即乘法器的输出仍为16位，因此要对输出数据进行截取，截取其中16位作为加(减)法器的输入。在FFT处理单元中存储器是必不可少的单元，蝶形运算数据的输入输出和中间结果的存储都要经过存储器，因此它们的频繁读写操作对整个FFT处理速度影响较大。图2中存储器A和存储器B由RAM和状态机组成，各自分别具有数据总线、地址总线和触发时钟。存储器A接收外部输入数据，存储器B是中间结果单元，除第一级蝶形运算外每级数据的输入输出均经过该存储器。在两块存储器和蝶形运算模块之间加入两个数据控制器配合工作，可以在写入上一组中间结果的同时读取下一组蝶形运算数据，从而提高FFT的处理速度。旋转因子单元是用于存储FFT运算所需的旋转因子WrN=exp(-j2πr／N)。在Matlab中旋转因子分为实部和虚部产生，由于它们是小于1的小数，故在设计中需将其定点化。其过程是将旋转因子扩大214倍。取整数部分转化为16位定点数，以．hex文件格式保存，利用QuartusⅡ软件的Megawizard工具设计。ROM，并将．hex文件同化在其中。根据旋转因子的对称性和周期性，在利用ROM存储旋转因子时，可以只存储旋转因子表的一部分，通过地址的改变查询出每级蝶形运算所需的旋转因子。控制单元用于协调驱动各模块，在FFT运算中具有关键作用。存储器A、旋转因子单元及数据控制器的读信号，存储器B的读写信号都是由控制单元产生。控制单元通过一个有限状态机(FSM)实现，使用两个内部计数器控制状态机的翻转。控制单元具有单独的输入时钟，可产生相应的控制信号。5仿真结果选用Altera公司的QuartusⅡ软件作为开发平台，以Stratix系列中的EP1S25型FPGA为核心器件，采用白顶向下的设计思路和VHDL语言，实现对各个模块单元的设计、综合和仿真。为了简化设计，只在数据输入时钟下输入了一组64个复数，其余输入设为0，并且实部和虚部都限定在±l，±2，±3，±4，e5之内。为防止溢出先将输入数据乘以一定比例因子2-9，再乘以215转化为十六进制数。输出的结果如图5所示。需要注意的是：仿真结果乘以2-6后才是实际结果。将仿真结果与Matlab计算的结果相比较，数据基本一致，说明了设计正确，其误差主要来源于数据的截取和旋转因子的近似。图5FFT运算仿真图6结束语FFT是数字信号处理中是一种重要的运算,在通信、语音处理、图像处理等领域有着广泛地应用。FPGA具有成千上万的查找表和触发器，因此，FPGA平台可以利用更低的成本达到此通用DSP更快的速度。本文提出了用移位寄存器存储旋转因子的方法，设计了一种基于FPGA的FFT处理器的方案，输入数据以二进制数表示，采用基2FFT算法，以QuartusⅡ软件为开发平台对处理器各个的模块进行设计和仿真，得到理想运算结果。采用FPGA实现FFT算法在体积、速度、灵活性等方面都具有优越性。采用FPGA技术，还可以获得高性能，满足成本要求，并享有快速有效地对新设计进行优化的灵活性。参考文献:[1]吴大正.信号与线性系统,高等教育出版社2009，第4版:115—187.[2]高西全，丁玉美.数字信号处理.西安电子科技大学出版社,2008，第3版:110-123.[3]韩颖,王旭,吴嗣亮.FPGA实现高速FFT处理器的设计[J].电讯技术,2003(2)：60—78.[4]罗雪荀,詹阳.用FPGA实现FFT算法[J].今日电子,2002，第2版:11-18.