基于乘法器复用技术的FFT处理器的设计实现分析

-.z基于乘法器复用技术的FFT处理器的设计与实现龙**，耿双利，*晓昆，李彩霞摘要：提出了一种基于乘法器复用技术的FFT优化算法，该算法主要利用了旋转因子关于y轴和y=*的对称性，使用两个实数乘法器即可分时共享完成4个复数旋转因子的计算，从而减少硬件资源消耗；采用该算法采用流水线构造，设计了基2的16点IFFT处理器，使用7个实数乘法器即可完成，进一步优化可仅使用5个。通过ALTERACycloneⅡ系列的EP2C70F896C6器件进展下载验证。FPGA输出结果与MATLAB计算结果比拟，单点最大相对误差约***。关键字：FFT,乘法器复用，FPGAAbstract:ThispaperproposesanoptimizedFFTalgorithmbasedonmultipliermultiple*ingtechnology,itreducesthehardwareresourceconsumptionbytakingtheadvantageoftherotationfactorsymmetryonthe

y-a*is

andy=*;Onlyuse7realmultipliertodesignapipelinedradi*-2,16-pointIFFTprocessor,furtheroptimization

can

only

use

5.TheverificationiscarriedoutthroughthedownloadedALTERACycloneⅡseriesEP2C70F896C6device．whoseresultislessthan***differenceparedwiththeresultfromtheMATLABcalculationKeyWords：FFT；multipliermultiple*ing；FPGA1引言FFT(快速傅里叶变换)是数字信号处理中的重要模块，作为时域和频域转换的根本运算．是数字谱分析的必要前提，在信号处理、图像处理、生物信息学、计算物理、应用数学等方面都有着广泛的应用。在高速数字信号处理中，FFT的处理速度往往是整个系统设计性能的关键所在[1]。对于FFT的硬件实现，大致可以分为3种方案：通过数字信号处理器(DSP)实现；通过专用FFT芯片实现；通过FPGA实现[2]。用DSP完成FFT运算需要占用大量DSP的运算时间，使整个系统的吞吐量降低；专用的FFT处理芯片，虽然速度较快，但其可扩展性差，且本钱昂贵。FPGA不仅有大量的片内资源，而且易于组织流水和并行构造，可以大大提高FFT的处理速度。将FFT的实时性要求与FPGA的灵活性相结合，不仅可以提高处理速度，而且可以方便的移植到ASIC中。2FFT算法根本原理对于N点序列，其离散傅立叶变换(DFT)变换可写为：，〔2-1〕其中：。由式〔2-1〕分析可知，假设直接计算DFT，乘法和加法次数都和N2成正比，当N很大时，运算量是很可观的。FFT算法的根本思想：可以将一个长度为N的序列的离散傅里叶变换逐次分解为较短的离散傅里叶变换来计算，这些短序列的DFT可重新组合成原序列的DFT，而总的运算次数却比直接的DFT运算少得多，从而到达提高速度的目的[3]。这种分解根本上可分为两类，一类是将时间序列*(n)进展逐次分解，称为按时间抽取算法(DecimationInTime)；另一类将傅立叶变换序列*(k)进展分解，称为按频率抽取算法(DecimationInFrequency)。本文主要介绍了按时间抽取基一2FFT算法。我们已经知道FFT算法主要是利用的性质，通过把序列逐渐分解为短序列实现运算量的减少。的以下三种性质在FFT运算中得到了应用[4]：性质1：的周期性性质2：的对称性性质3：的可约性，基2算法中，序列的长度N为2的整数次幂，即，其中M为正整数。最初通过将分解为奇数项序列和偶数项序列的形式使FFT运算分为两组。设：，设，，利用的性质可得的DFT运算为：〔2-2〕式〔2-2〕的运算可用下列图的蝶形信号流图表示：图1蝶形运算流图由此可见，一个Ｎ点DFT分解为两个N/2点的DFT，从而实现了运算量的减少，再经过逐次分解最终分解为２点的DFT，实现了FFT运算。3乘法器复用的FFT实现构造文献[5]提出了一种蝶形运算的新构造：即先进展前一级4点蝶形运算，再进展本级的与旋转因子复乘运算，如图2所示。这种构造节省了一个旋转因子复乘模块。图2文献4所设计的FFT硬件实现框图文献[2、6]中改良的旋转因子复数乘法的原理均为：一个复数和旋转因子相乘，结果仍为复数，，可见完成一次复数乘法操作需要进展4次实乘和2次实加运算。为减少乘法的次数，将做以下变换：，，从而完成一次复乘只需进展3次实乘和5次实加，较变换前减少一次实数乘法运算，从而减少了使用面积。本文采用原理图输入与AHDL语言相结合的方法，来完成IFFT的设计。其中原理图输入的方法主要完成实乘和实加操作，而当参加加法运算的两个数位数长度不一致时，AHDL语言将二者补齐。本设计中，首先完成2点IFFT的设计，然后将其封装为.bsf格式的符号文件。之后多点的IFFT设计，设计流程如下列图3所示。N=4点的IFFT中，旋转因子为,乘法运算相当于实部虚部互换操作，可以合并到蝶形运算中且不增加硬件消耗。图3设计流程图N=8点的IFFT中，1与不需要乘法器来运算，只需要2次旋转因子的复乘运算，即与，其中与的位置如下列图4。图4N=8时旋转因子分布由图4可知与关于轴对称，假设令，则。又因为，则有〔3-1〕上式〔3-1〕可以看出两次复乘运算的结果均为*个复数与相乘，由此可以采用时分复用的方法，将参与复乘运算的两个数的实部和虚部按照上式相加减之后，经过串并变换，依次进入乘法器运算。这样完成一个8点的IFFT运算，仅需要1个实数乘法器即可完成，大大节省了芯片的资源与面积。而文献[5]中，假设完成N=8点的IFFT运算需要做两次复乘运算，经改良后仍需4个实数乘法器；文献[6]中，则需要6个实数乘法器才能完成设计。另外，以及本应为-1~+1之间的小数，为了防止浮点运算，这里乘以256归一化为9BIT有符号数，即令，最终输出时再右移8位即可。N=16点的IFFT中，1与不需要乘法器来运算，共需要6次旋转因子的复乘运算，这6个旋转因子分别为、、、、、，其位置关系如下列图。图5N=16时旋转因子分布利用旋转因子关于轴以及直线的对称性质，令，则，，，其中，，则有〔3-2〕由上式可以看出，等式右侧均为〔3-3〕因此与N=8点的IFFT一样，将乘法器时分复用，经过串并变换，将4路串为1路，这样在流程图的蝶形单元中采仅需要5个实数乘法器〔实现式〔3-3〕需要4个实数乘法器，与还需要额外的1个实数乘法器来实现〕，在流程图的两个N/2点〔4点〕的IFFT中还需要2个实数乘法器。这样按照时分复用的方法完成一个16点的IFFT运算总共需要7个实数乘法器即可。4.IFFT处理器的FPGA加载实验结果本文在ALTERACycloneⅡ系列的EP2C70F896C6芯片上实现了16点的IFFT处理器，在8个时钟周期内，仅使用7个实数乘法器即可。另外由式(3-3)可已看出，本设计可以进展进一步的优化，将实部和虚部中所有乘数为(或者)的数据，经过串并变换，将8路串为1路，这样又可以减少实数乘法器的使用个数，仅使用5个实数乘法器。同时为了防止浮点乘法运算将旋转因子扩大256倍后将最终结果输出右移8位，假设乘法器的输入为9bit*8bit，输出的结果为17bit，为了进一步减少资源消耗，将乘法输出只取高12位，并将最终的结果右移3位输出。N=8时，〔a〕传统算法〔b〕改良后算法图6N=8时的编译结果中资源占用情况由图6可以看出，将乘法器输出只取高12位后，LE节省了19%。图7IFFT输出结果仿真图由图7可知，N=8时，IFFT的输出结果与matlab的仿真结果完全一样。N=16时，图8N=16时IFFT输出结果仿真图由图8将输入与输出结果导出，并与matlab计算结果相比拟，可得到下表，表1FPGA输出结果与MATLAB计算结果比拟输入AFPGA输出BMatlab计算结果C-3-2i-4+5i-4.0000+5.0000i2+1i4-7i-1+0i-3+1i-2.1716+1.8995i0-3i3+4i4.1157+4.9361i1+2i-6-11i-3-1i-8+0i3+1i-8-4i-2+2i-8-2i0-2i2-1i-2+3i-20+10i-19.4562+9.4095i-1+1i-8-18i2-1i4+7i5.1981+7.5492i3+0i12-1i-1+3i3-13i-3+2i-11-4i1-1i-6-3i由可以计算出16点平均相对误差约0.68%。由本文算法可进一步推广到32,64,128,256,..…等多点IFFT的实现，根据旋转因子关于y轴和y=*的对称性，使用两个实数乘法器可分时共享即可完成4个复数旋转因子的计算，因此占用乘法器数量仅为传统算法的1/8左右，可以大大节省资源占用情况，减少整个系统的资金投入。参考文献[1]SansaloniT,Perez-pascualA,VallsJ.Area-efficientFPGA-basedFFTProcessor[J].ElectronicsLeeters,2003,39(19):1369-1370.[2]侯志坚，董军军，李杰等.OFDM中的FFT处理器设计及FPGA实现[J].中国现代教育装备。2010年第21期[3]A．V．奥本海姆，R．w．谢弗著．离散