1 导言
跟着数字技能的快速开展，数字信号处理已深化到各个学科范畴。在数字信号处理中，许多算法如相关、滤波、谱估计、卷积等都可经过转化为离散傅立叶改换(DFT)完结，然后为离散信号剖析从理论上供给了改换东西。但DFT核算量大，完结困难。快速傅立叶(FFT)的提出，大大减少了核算量，从根本上改动了傅立叶改换的位置，成为数字信号处理中的中心技能之一，广泛应用于雷达、观测、盯梢、高速图画处理、保密无线通讯和数字通讯等范畴。
现在，硬件完结FFT算法的计划首要有：通用数字信号处理器(DSP)、FFT专用器材和现场可编程门阵列(FPGA)。DSP具有纯软件完结的灵活性，适用于流程杂乱的算法，如通讯体系中信道的编译码、QAM映射等算法。DSP完结FFT运算需占用很多DSP的运算时刻，使整个体系的数据吞吐率下降，一起也无法发挥DSP软件完结的灵活性。选用FFT专用器材，速度虽能够到达要求。但其外围电路杂乱，可扩展性差，本钱贵重。跟着FPGA开展，其资源丰富，易于安排流水和并行结构，将FFT实时性要求与FPGA器材规划的灵活性相结合，完结并行算法与硬件结构的优化装备，不只能够进步处理速度，而且具有灵活性高。开发费用低、开发周期短、晋级简略的特色。针对某OFDM体系中FFT运算的实践需求，提出了依据FPGA的规划来完结FFT算法，并以16位长数据，64点FFT为例，在QuartusⅡ软件上经过归纳和仿真。
2 FFT原理及算法结构
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算法分解成log 2N级运算，每级有N／2个基2碟形运算。图1是N=8的DIT-FFT运算流图。
3 FFT处理器的结构规划
FFT完结的规划计划有次序处理、级联处理、并行处理和阵列处理。次序处理每次运算仅用一个蝶形单元,处理方式简略，运算速度较慢。级联处理、并行处理和阵列处理的速度较快，但占用资源较多。考虑到该规划运算点数较少，因而选用改善的次序处理计划，在原有次序处理的基础上对FFT处理进程中数据传输进行操控。使得该结构在承继原有次序处理电路简略、占用资源较少长处一起又兼有级联处理运算速度较快的长处。选用自顶向下的办法对处理器模块化，其结构框图如图2所示。
4 模块规划与归纳仿真
整个FFT处理器是由存储器、蝶形运算单元、旋转因子单元、操控单元和数据操控单元组成，各个单元经过操控单元发生的操控和使能信号进行作业。
4．1 蝶形运算单元
蝶形运算单元是整个FFT处理单元的重要部分，直接影响整个FFT单元功能。基2时刻抽取的蝶形信号流程图如图3所示，p和q为数据序号，xm(p))和xm(q)是第m级蝶形运算的输入，xm+1(p)和xm+1(q)是该蝶形运算的输出，WrN为相应的旋转因子。
由上式看出，一个基2蝶形运算要进行1次复乘、2次复加。为了进步运算速度选用并行运算，选用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所示。
数据格局挑选定点16位二进制补码。规划时有必要考虑乘法器速度，将会直接影响整个FFT处理单元的运算速度,该规划的乘法器运用QuartusⅡ开发软件中所供给的宏单元生成。乘法器的两输入均为16位，输出32位。因为乘法器中带有旋转因子项．所以乘法运算后不该改动输入的幅值即乘法器的输出仍为16位，因而要对输出数据进行截取，截取其间16位作为加(减)法器的输入。
4．2 存储单元
在FFT处理单元中存储器是必不可少的单元，蝶形运算数据的输入输出和中心成果的存储都要经过存储器，因而它们的频频读写操刁难整个FFT处理速度影响较大。图2中存储器A和存储器B由RAM和状态机组成，各自别离具有数据总线、地址总线和触发时钟。存储器A接纳外部输入数据，存储器B是中心成果单元，除榜首级蝶形运算外每级数据的输入输出均经过该存储器。在两块存储器和蝶形运算模块之间参加两个数据操控器合作作业，能够在写入上一组中心成果的一起读取下一组蝶形运算数据，然后进步FFT的处理速度。
4．3 旋转因子单元
旋转因子单元是用于存储FFT运算所需的旋转因子WrN=exp(-j2πr／N)。在Matlab中旋转因子分为实部和虚部发生，因为它们是小于1的小数，故在规划中需将其定点化。其进程是将旋转因子扩展214倍。取整数部分转化为16位定点数，以．hex文件格局保存，运用QuartusⅡ软件的Megawizard东西规划。ROM，并将．hex文件同化在其间。依据旋转因子的对称性和周期性，在运用ROM存储旋转因子时，能够只存储旋转因子表的一部分，经过地址的改动查询出每级蝶形运算所需的旋转因子。
4．4 操控单元
操控单元用于和谐驱动各模块，在FFT运算中具有关键作用。存储器A、旋转因子单元及数据操控器的读信号，存储器B的读写信号都是由操控单元发生。操控单元经过一个有限状态机(FSM)完结，运用两个内部计数器操控状态机的翻转。操控单元具有独自的输入时钟，可发生相应的操控信号。
4．5 归纳仿真
选用Altera公司的QuartusⅡ软件作为开发渠道，以Stratix系列中的EP1S25型FPGA为中心器材，选用白顶向下的规划思路和VHDL言语，完结对各个模块单元的规划、归纳和仿真。为了简化规划，只在数据输入时钟下输入了一组64个复数，其他输入设为0，而且实部和虚部都限定在±l，±2，±3，±4，e5之内。为避免溢出先将输入数据乘以必定份额因子2-9，再乘以2 15转化为十六进制数。输出的成果如图5所示。需求留意的是：仿真成果乘以2 -6后才是实践成果。将仿真成果与Matlab核算的成果相比较，数据根本共同，说明晰规划正确，其差错首要来源于数据的截取和旋转因子的近似。
5 结束语
FFT算法是数字信号处理中一种重要运算，广泛应用于雷达、观测、盯梢、高速图画处理、保密无线通讯和数字通讯等范畴。这儿评论了一种依据FPGA的64点FFT处理器的规划计划，输入数据的实部和虚部均以16位二进制数表明，选用基2DIT-FFT算法，以Altera公司的QuartusⅡ软件为开发渠道对处理器各个的模块进行规划，在StraTIx系列中的EP1S25型FPGA经过了归纳和仿真，运算成果正确。选用FPGA完结FFT算法在体积、速度、灵活性等方面都具有优越性。
