基于FPGA的FFT实现

1、基于FPG刖FFT实现随着多年的研究，FFT算法已经趋于成熟，有组合数FFT算法和以维诺格兰为代表的一类傅立叶变换算法，实现的算法原理也是基于这些算法。现成可编程门阵列(FPGA)是八十年代中期出现的新型高密度可编程逻辑器件，它是在PAL、GAL、EPLD等可编程器件的基础上进一步发展的产物。随着超大规模集成电路工艺的不断提高，单一芯片内部可容纳上百万个晶体管，FPGA/CPLD芯片的规模也越来越大，其单片逻辑门数目已达到上百万门，它所能实现的功能也越来越强。用FPGA实现FFT处理器具有硬件系统简单、功耗低的优点，同时具有开放时间短、成本较低的优势。其中大部分的研究是针对FPGA的结构特点，

2、充分使用了其RAM和灵活的逻辑资源实现并行处理和阵列处理来提高运算速度从而减少计算时间；也有部分提高运算精度和速度，提出自定义浮点格式FFT处理器的FPGA硬件实现方案；最近也有对FFT算法中部分计算的研究改进，使之更加适合FPGA结构，提高运算速度。具体计划如下：1) 9月30日前完成课程论文计划书。2) 9月15日10月1日，在这段时间里通过借阅相关书籍以及网上的相关资料，了解FFT的FPGA实现的原理。3) 10月7日10月27日，这这期间，通过前段时间对原理的学习，在掌握基本的方法的情况下，参考书籍中提供的资料，学会用硬件描述语言VHDL进行编程设计，并基于FFT对FPGA进行实现。4

3、) 10月28日11月9日，进行MATLAB程序的编写及仿真。5) 11月10日16日，通过学习以及参考书籍中的相关资料，撰写论文。6) 11月18日前提交论文。编辑版word摘要及其逆变换IFFF（快64、256、1024点提出一种利用并行算法来实现FFT（快速傅里叶变换）速傅里叶逆变换）的设计方法。该处理器可由用户动态配置成复数FFT或其逆变换IFFTo关键词：FPGA,FFT,IFFT编辑版word1引言高速实时数字信号处理对系统性能要求很高，因此，几乎所有的通用DSP都难以实现这一要求。可编程逻辑器件允许设计人员利用并行处理技术实现高速信号处理算法，并且只需单个器件就能实现期望的性能。

4、在数据通信这样的应用中，常常需要进行高速、大规模的FFT及其逆变换IFFT运算。当通用的DSP无法达到速度要求时，唯一的选择是增加处理器的数目，或采用定制门阵列产品。现在，随着微电子技术的发展，采用现场可编程门阵列（FPGA）进行数字信号处理发展迅速。采用现场可编程器件不仅加速了产品上市时间，还可满足现在和下一代便携式设计所需要的成本、性能、尺寸等方面的要求，并提供系统级支持。本文研究了基于FPGA的FFT及其逆变换IFFT处理器的硬件电路实现方法。在系统时钟频率为100MHz时，1024点复位FFT的计算时间只需要10巧左右。2基4FFT/IFFT算法序列x（n）,n=0,.,N-1的离散傅

5、里叶变换为：Xg=':旧片“次”,-I（HE前相应的傅里叶逆交换为IA'lri）二*->这说明IFFT可以由FFT求出。因此，FFT和IFFT处理器可以用统一的硬件结构来实现。对于FFT,设序列x（n）的长度为N=4p（p为整数），则基4频率抽取蝶菜运算单元方程为：编辑版wordX(tj)=C.rOi)+.rC*i:1+J+2X(>-)十rtw4-3-r1)l!X(n十*-*:J=15Jir(rr+51Kr'(>+"rg1-3>W+2Xr'1)=j(h).rCw+-ij_|_t3)，5"4axr-*r(A+3X-J”V

6、(/f+3x4f'=Ln灯)卜+4"i)一+2X4-7)-H和+3x4，学上面的公式中八力基1HF算法流图中的蝶茸单元的级数y=*LII5短乂4/7+45取3I'IJ在取口,14s-1u-川X：W；一-三3FFT/IFFT的硬件实现我们采用Xilinx公司的Virtex-II系列FPGA来实现FFT/IFFT处理器。3.1 蝶形运算单元结构基4频率抽取FFT计算一共包括了10g4(N)级运算，其中，在每一级中包含了N/4个基4蝶形运算，蝶形运算器如图1所示。Virtex-II系列FPGA有内嵌18bitx18bit补码乘法器以及大容量用户可配置RAM,非常适合做大规模

7、算术运算。图1所示的蝶形运算器可以在一个时钟周期内完成一次基4蝶形运算。其中，操作数A、B、C、D存放在RAM中，三个18位放置因子W1、W2、W3存放在ROM中。由于运算结果可能会超过原数据，所以要进行量化移位12。3.2 并行运算结构通用DSP的蝶算单元通常是从内存中顺序读入四个操作数A、B、C、D,因而计算速度受到了很大限制。而使用FPGA可充分利用并行计算技术在一个时钟编辑版word周期内并行读取四个操作数，以便完成一次基4蝶形运算。我们采用四对RAMX2（分别存放实部和虚部）来存储蝶算中的操作数A、B、C、Do如图2所示,处理器在每个时钟周期从RAM中读出数据A、B、C、D送入蝶形运

8、算器（图1）运算结果AO、BO、CO、DO在下一个时钟周期写回原地址。rhMti色父一ToT*-0-RAMD淞IAi修以蛆理（同址运第J叫T甲址坨,-址：地'地W>1皿M仆仆n（崛K立而*I：&心鸟他留培内图2中的四对RAMX2的地址A0,A1,A2,A3分别对应公式（3）中的n,n+4p-s-1,n+2X4p-s-1,n+3X4p-s-1。A0,A1,A2,A3可以按下述方法产生:设a,b为两个递减计数器，它们组成一个大的计数器Counter=ax4p-1+b。如图3所示。编辑版wordROTATEn（x,m）表示把x（n位二进制）循环左移m位。则图2中四个操作数地址为

9、：A。ROTATE“IM.储A=ROTATE乩+.2-JrROTATE仍+2,2口（HUKC1TATK,附+2uJ式（4）中每个地址对应一个RAMX2的入口地址。设操作数地址A的四进制表达式为A=（Kp-1.KiK0）4o定义Mk为A的所有四进制位数和除以4的余数*f.mod（W匣，4.（3）j0式（5）中，mod为求余运算。可以证明地址A0,A1,A2,A3的Mk值互不相同，取值范围是0,1,2,3。因此我们采取如图2所示的并行存储结构：所有Mk=0的操作数都存放在RAMA中，Mk=1的操作数都存放在RAMB中，Mk=2的操作数都存放在RAMC中，Mk=3的操作数都存放在RAMD中。通过以上

10、地址映射，我们可以在一个时钟周期并行读取四个操作数地址，完成蝶形运算。3.3 放置因子的生成为了加快FFT/IFFT运算速度，我们采用查表的方式来得到放置因子W1,W2,W3（图1）,我们采用3对ROMX2（实部和虚部）来存放复数W1,W2,W3,三个ROM的入口地址都为c。可以证明，把图3中的计数器b的低2（p-a-1泣都置为0所得到的值即为c的值。即：编辑版word3.4 FFT/IFFT芯片整体结构FFT/IFFT芯片整体结构如图4所示。在式（2）中讨论过，我们可以用FFT来计算IFFT,只需要先求出输入序列的共腕X*（k）,然后进行正常的蝶形运算，在输出时再进行一次求共腕运算。所谓复位

11、的共腕是对它的虚部取反，实部不变。因此，我们可以把处理器动态地配置成FFT或其逆变换IFFT。为了充分利用I/O带宽、连续地进行FFT/IFFT。为了充分利用I/O带宽、连续地进行FFT/IFFT。我们采用了乒乓缓冲存储结构，如图4所示。由于FFT/IFFT计算采用的是同址计算，每次蝶形运算结果要写回原地址中,所以，RAMX和RAMY有输入和工作两种模式。这里，我们把RAMX和RAMY配置成乒乓结构，当RAMX处于工作模式时，RAMY处于输入状态。当一次64/256/1024点FFT/IFFT完成后，RAMX和RAMY将自动切换到另一个状态。这样，输入序列就可以连续地输入到FFT/IFFT处理

12、器中进行变换，以达到实时处理的要求。输出结果存放在RAMZ中，可以由用户读出。4测试结果这个电路采用VerilogHDL完成设计，采用Virtex-IIXC2V250实现。使用VilinxISE4.2i完成整套流程，图5是部分仿真波形（modelsim+sdf）。在系统时钟为100MHz时，完成一次1024点复数FFT/IFFT需要12.8的。相比之下，TI公司的TMS320C67（主频167MHz）需要120gAD公司的ADSP21160（主频100MHz）需要90的。可见，基于FPGA的FFT/IFFT处理器由于其硬件上的并行性，速度远远快于一般的通用DSP。5结束语FPGA具有成千上万的

13、查找表和触发器，因此，FPGA平台可以利用更低的成编辑版word本达到此通用DSP更快的速度。采用FPGA技术，还可以获得高性能，满足成本要求，并享有快速有效地对新设计进行优化的灵活性。针对这一特性，本文研制了一种基于并行算法的FFT/IFFT处理器，可以广泛应用在高速信号处理系统中。T%输入工作HIMIi&UEI承八工作KAMYI用-0艇归因于»M-r-A*JCFffdKFT闻I卜TTHFT芯片作沐”.叶编辑版word参考文献1 W.R.KnightandR.Kaiser.ASimpleFiexed-PointErrorBoundfortheFastFourierTransform.IEEETrans.Acoustics,SpeechandSignalProc.,Dec,1979Vol.27,No.6:6156202 L.R.RabinerandB.Gold.TheotyandApplicationofDigitalSignalProcessing.Prentice-HallInc.,En