基于FPGA的点FFT处理器设计

任炳宇;战荫伟

【摘 要】采取基-4按频率抽取FFT算法,设计一种可在FPGA上实现的点、32位长、定点复数FFT处理器.基-4堞形运算单元中采用六级流水线设计,并行处理4路输入/输出数据,能极大地提高FFT的处理速度.该设计采用VHDL描述的多个功能模块,经ModelSim对系统进行逻辑综合与时序仿真.实验证明,利用FPGA实现点FFT,运算速度快,完全可以处理高速实时信号. 【期刊名称】《现代电子技术》 【年(卷),期】2009(032)014 【总页数】4页(P1-3,6)

【关键词】FPGA;基-4FFT算法;点FFT;VHDL 【作 者】任炳宇;战荫伟

【作者单位】广东工业大学,信息工程学院,广东,广州,510006;广东工业大学,计算机学院,广东,广州,510006 【正文语种】中 文 【中图分类】TN409 0 引 言

DFT作为DSP领域中时域和频域转换的基本运算，存在运算量太大的缺点，导致其应用受到局限。DFT快速算法FFT的提出，简化了DFT的运算过程[1]，使其在

实时信号处理领域中得到广泛应用。FFT实现的方法包括软件实现和硬件实现两种。采用软件实现FFT的方法存在计算慢，实现过程复杂等缺点，所以目前比较流行的方式是采用硬件实现FFT。硬件实现的具体方法可以分为ASIC方法、FPGA方法、DSP方法和通用处理机方法等。

FPGA是20世纪80年代中期出现的一种新的电子设计自动化技术，具有集成度高，逻辑实现能力强，设计灵活等优势。在FPGA上实现数字信号处理，即用纯数字逻辑进行DSP模块设计，为高速数字信号处理算法提供了实现途径[2]。在此，采用FPGA方法设计点FFT处理器[3]。

现有的FFT模块可以对多点数据进行运算，但是存在运算周期长，结构复杂，硬件资源耗费大等缺陷。采用点FFT可以通过优化结构来快速处理多点数数据。目前设计的点FFT处理器主要采用以专用处理单元取代常规FFT处理单元的方法[4]，或者按照固定几何结构设计FFT处理器的方法[5]。这里所介绍的点FFT处理器是在固定几何结构设计方法的基础上加以改进，将输入的点数据均匀分成8组，并行输入给FFT运算单元，进行FFT运算。通过对蝶形运算单元进行优化设计，所设计的点FFT处理器模块较之以往的FFT模块，节省了硬件资源，提高了运算效率。通过ModelSim仿真实验证明，在外部工作时钟频率为40 MHz下，对随机生成的序列进行点FFT运算处理，运算时间为10 μs，缩短了现有FFT模块的运算时间。 1 按频率抽取的基----4FFT算法原理

对于序列长度为N(N为2的整数次幂)的FFT算法主要有基-2 FFT和基-4 FFT两种。计算一次基-2 FFT需要二次复乘和两次复加；计算一次基-4 FFT需要三次复乘和八次复加。从运算次数上看，基-2 FFT较为简单，但是因为基-2 FFT的复数运算较为复杂，所以在硬件实现上反而要比基-4 FFT占用的资源更多。为了满足对数据高速处理的要求，在此选择在FPGA上实现基-4 FFT的算法。

根据定义，对于长度为N的序列x(N)(0≤N≤N-1)，它的DFT可表示为:

k=0,1,2,…,N-1 (1)

式中：称为旋转因子。直接计算DFT，需要的计算量为N2次复乘和N(N-1)次复加。当N很大时，运算量相当大，无法满足实时处理的要求。因此利用旋转因子的对称性、周期性和可约性，把长序列分解成为短序列来进行快速傅里叶变换[1]。 由式(1)可以得到4个子序列: (2)

利用旋转因子的特性，如：将A，B，C，D作为复数操作数进行运算，由式(2)可得简化计算式: (3)

式(3)就是在FPGA上实现基-4 FFT算法的基本运算法则。

不同于以往的基-4 FFT算法，这里是将输入的点数据以8位输入数据为一组，共分成8组的方式输入给FFT运算单元进行FFT运算的。完整的FFT蝶形运算共分6级，经历196个循环状态。将来自存储单元的数据输入到FFT运算单元中，前三级是按8位1组的方法，分为8组进行运算；后三级是将前三级运算所得到的中间数据送入运算单元进行运算。经过FFT运算后，将所得到运算结果写入存储单元中保存。结果以倒位序方式输出，需要经过调整位序变换成为自然顺序输出。 2 FFT运算器设计 2.1 系统的整体结构

一个完整的FFT运算单元应该包括以下几个组成部分：

全局控制单元 包括控制器和地址产生单元，用于整个FFT运算系统，生成蝶形运算单元以及其他子单元所需的地址，控制各子单元时序，保证其正常有序地工作；

蝶形运算器单元 由蝶形运算器和旋转因子存储单元(ROM)组成，负责将送入的输入数据进行蝶形运算，是FFT运算器的核心单元；

存储寄存器单元 采用两个RAM乒乓通信，通过通信接口单元接收总线控制信号，负责存储输入数据、中间数据和运算所得最终结果。 系统整体框图如图1所示。 图1 系统整体框图 2.2 各功能单元介绍

(1) 控制单元。控制单元由控制器和地址总线组成。地址产生单元提供各个功能单元所需要的地址，保证数据存储、读写的顺利进行。在此，采用三位二进制编码来定义每个子单元的地址，并将所得的地址汇总，生成地址图表。由于每个单元模块的地址是惟一的，这就确保了在同一时刻、同一存储单元只能对数据进行单向通信，避免数据间的相互干扰，提高了精度。在时钟信号的控制下，控制器发出控制信号，控制整个FFT运算单元FFT运算。此外，系统中还添加一个复位信号RST。在此信号的激励下，FFT运算单元复位，并在下一时钟信号来临时，重新记录输入数据，开始新的点FFT运算。

(2) 蝶形运算单元。蝶形运算单元是实现FFT算法最为重要的部分[6]。蝶形运算主要有两种实现方式:传统的蝶形运算通常以输入倒位序，输出自然顺序，输出数据采用同址运算的方式进行存储，以节省存储单元空间,但是由于这种方式每级蝶形运算的计算单元都是变换位序的，从具体操作上难以实现，不便于扩展；另一种运算是采用输入自然顺序，输出倒位序的方式，这种方式中每级运算的计算单元都是固定的，实现上比较容易，只要对不同级的蝶形运算输入不同的旋转因子，即改变

相对应旋转因子ROM的地址，就可以实现扩展[7]。

旋转因子ROM能储存固定地址的旋转因子，给蝶形运算提供所需的乘积项。旋转因子ROM在运算系统中实际上就是用于存放sin和cos的值。三角函数在第二、三、四象限的函数值可以通过第一象限的函数值转化得来，所以对于每一级运算所需要的旋转因子都可以从旋转因子表中得到，无需另外添加存储单元。因此，系统只是在ROM单元中存储第一级的旋转因子数据，其他的旋转因子通过转换得到，从而可节省存储单元ROMR的资源[8]。

(3) 存储单元。FFT存储单元采用两个并行的双口RAM“乒乓操作”的设计方法。“乒乓操作”的原理是在时钟和控制信号的控制下，数据流在两个RAM之间交替读写。按此方式，数据流不会产生延迟，从而提高存储效率[9]。输入数据先存入存储器中，再导入FFT处理器中，处理结束后写回存储器中。同时系统使用D触发器对原始信号进行延迟，每个D触发器延迟一个时钟周期，由4个周期组成，包括3个周期的FFT运算以及之后把运算结果回写给存储器所占用的1个周期。 每个输入数据的长度是32位(实部为16位，虚部为16位)，并行输入给存储器单元。在全局控制单元的下，从存储单元读取的输入数据经过判别后，进入蝶形运算单元，与旋转因子表中相应位置的旋转因子乘积运算后得出结果，将所得的输出结果经过判别后，写入RAM1中，同时，前一个时钟周期所得的运算结果由RAM2输出[10]。

通常数据格式的表示方法有浮点、定点和块浮点三种。浮点数是用两组固定的bit表示指数和小数，可以表示的动态范围比较大，不会出现数据的溢出问题，但是实现浮点运算的电路却很复杂；定点数是用固定的bit表示整数和小数，表示的动态范围比较小，容易出现数据溢出，但是其运算电路简单，运算速度也快；块浮点数是介于二者之间的数据表示方法。

在此采用定点数，为了保证数据不会溢出，从蝶形运算单元输出的运算结果被2

整除，然后送入存储单元保存以备输出。

综合式(2)、式(3)两个部分，可以组合生成蝶形运算单元部分，蝶形运算单元结构内图如图2所示。 3 实验结果验证

这里的FFT运算器通过硬件描述语言VHDL代码进行编写，在ModelSimSE PLUS 6.1f环境下完成系统仿真，波形仿真如图3所示。 图2 蝶形运算单元结构内图 图3 波形仿真图

由波形仿真图可以看出，地址控制单元以3位二进制编码定义各子单元的地址，存储的数据在时序信号和地址总线单元控制下进行FFT运算。实验证明，当外部时钟频率为40 MHz时，可以对随机生成的点序列进行FFT定点运算，运算时间为10 μs。 4 结 语

这里的FFT运算器采用定点数处理，当处理浮点数时，系统存在处理异常、数据溢出等问题。但是由于可以迅速处理多点数信号， 因此在数字图像处理、实时通信系统的调试和解调等方面具有一定的实际意义，达到了使用FPGA实现DSP算法的目的。

本文在以下方面有所创新：

(1) 输入的位数据以8位共8组的方式并行输入，将FFT运算流程分为6级，整个FFT运算过程清晰，结构合理，提高了运行效率。

(2) 使用2块双口RAM作为存储器，采用“乒乓操作”，在一个时钟周期内保证数据传递的单向性，减少了数据传输的冗余，提高了精度。

(3) 将整个FFT运算器进行模块化设计，在控制模块的调配下，各个子模块准确工作，保证了运算的可靠性。

参 考 文 献

[1] 程佩青.数字信号处理教程[M].2版.北京:清华大学出版社,2004. [2] 潘明海,刘英哲,于维双.一种基于FPGA实现的FFT结构[J].微计算机信息,2005(2):156-158.

[3] McAllister J,Woods R,Fischaber S,et al.Rapid Implementation and Optimization of DSP Systems on FPGA-Centric Heterogeneous Platform[J].Journal of Systems Architecture,2007,53:511-523.

[4] 侯卫华,郭晖,刘明峰,等.一款基于MVR-CORDIC的高速点基-4FFT处理器[J].电子与封装,2008,8(5):22-25.

[5] 赵梅,丁晓磊,朱恩.高速点FFT芯片设计技术[J].电子工程师,2007,33(3):13-17.

[6] Sansaloni T,Perez-Pascual A,Valls J.Area-efficient FPGA-based FFT Processor[J].Electronics Letters,2003,39(19):1 369-1 370. [7] 田丰.邓建国,贾治华,等.FFT算法的一种FPGA实现[J].现代电子技术,2005,28(8):97-99.

[8] 刘小明,吴曼青,洪一.基于FPGA的基-16 FFT模块的实现[J].合肥工业大学学报,2006,29(5):536-539.

[9] 付宜利,王保国,靳保.基于FPGA的高速实时FFT处理器设计[J].微计算机信息,2007(2):194-195.

[10] 樊光辉,许茹,王德清.基于FPGA的高速流水线FFT算法实现[J].电子工程师,2008,34(3):38-40.