【原创论文栏目提醒】:网学会员为广大网友收集整理了,论文原创性声明(2) - 其它论文,希望对大家有所帮助!
论文原创性声明本人郑重声明:此处所呈交的
论文《基于FPGA的新型浮点FFT处理器设计》是本人在导师指导下进行研究工作所取得的研究成果。
据我所知,除了文中特别加以标注的地方外,
论文中不包含其他人已经发表或撰写过的研究成果。
本声明的法律结果将完全由本人承担。
作者签字:范 展 2008 年 3 月 9 日 1 基于 FPGA 的新型浮点 FFT 处理器设计 范 展 梁国龙,刘 洋 (哈尔滨工程大学 水声工程学院黑龙江 150001)摘 要:针对现有 FFT 算法结构复杂、难以并行扩展的问题,提出了一种改进的 FFT 算法,在此基础上设计了一种基于浮点运算的 FFT 处理器,并进行了仿真验证。
结果表明,新算法大大简化了系统结构,减少了系统的硬件开销,非常容易并行实现,且显著提高了运算效率,完成一次 N 点的 FFT 运算只需要 N/2 个时钟,完全满足实时信号处理的要求。
关键词:改进的 FFT 算法;浮点运算;实时信号处理中图分类号:TN409 文献标识码:A 文章编号: Design of a New Floating-point FFT processor Based on FPGA Fan Zhan,Liang Guo-long,Liu Yang College of Underwater Acoustical Engineering Harbin Engineering University Harbin 150001 ChinaAbstract:Aiming at the problem in the existing FFT algorithm structure which is not only complex butdifficultly to realize parallel expansion a way of improved FFT algorithm is proposed and a new floating-pointFFT processor is designed in this paper. Simulation based on the Modelsim has carried on. The results indicatedthat the new algorithm is able to simplify the system structure greatly reduce hardware consumption and is easyto carry out parallel realization. Completing an N points of FFT only needs N/2 clock periods it may satisfy therequests of real-time signal processing.Key words:Improved FFT algorithm Floating-point operate real-time signal processing1 引言 1 FFT作为数字信号处理的关键技术之一,在信号处理领域扮演着非常重要的角色 。
目前用于实现FFT的硬件平台主要有DSP、 ASIC和FPGA。
用DSP实现FFT的处理速度相对较慢,往往难以满足高速实时信号处理的要求;ASIC虽然速度很快,但外围电路相对复杂,不易扩展,且价格昂贵;采用FPGA实现FFT兼有二者的优点。
ALTERA公司推出的新一代FPGA内部嵌入了大量高速数字信号处理模块和RAM模块,容易借助全并行流水线技术实现FFT,不但性能稳定、经济性好,而且可以大大缩短计算耗时。
目前已经有不少学者进行了这方面的研究,文献2–9均以FPGA为硬件平台实现了FFT算法,系统的运算速度相比于DSP有了很大提高,基本能够满足某些高速实时信号处理的要求。
但是这些算法的实现过程较为复杂,这主要因为各流水线级的数据流向不一致, 所以需要为每级单独设计地址产生程序, 这使系统的控制时序变得复杂,开发难度增大,不利于算法的扩展,也限制了它的推广和应用。
本文在详细分析现有基 2 FFT 算法的基础上,根据其所存在的一些问题, 对算法流程进行了适当改进, 使之更加适合流水线方式下的并行处理。
在此基础上设计了一种切实可行的32 位浮点 FFT 处理器。
该处理器的特点是结构简单,非常容易设计实现,易于扩展,且运算速度进一步提高,系统稳定工作后,完成一次 N 点的 FFT 变换只需要 N/2 个时钟,可实时进行 50重复的 FFT 运算。
RAM 模块的设计是本 FFT 处理器的一大关键,因为它的存取速度直接关系到系统的性能。
Stratix 系列 FPGA 内部嵌入了大量 RAM 模块,为设计带来了便利,但这些 RAM 一个时钟最多只能进行一次读数和一次写数操作,本文结合改进后的算法对 RAM 模块进行适当改进,在不需要额外增加 RAM 资源的情况下,改进后的 RAM可以在一个时钟完成两次读数和两次写数操作。
为了验证 FFT 处理器的性能, 采用 Modelsim 2软件结合 Matlab 软件做了详细的仿真分析, 该 仿真结果表明, FFT 处理器不仅运算速度快,而且精度很高,可以广泛应用于对精度要求较高的实时数字信号处理领域。
2 改进的并行 FFT 算法 蝶形运算是基 2 FFT 算法的基本运算单位,为了进一步提高 FFT 处理器的性能,本文从两个方面对基本蝶形运算进行了改进:1) 对流水线级作了更细的划分,将基本蝶形运算单元分成两级进行,分别完成复数乘法运 算和复数加法运算。
2) 各加法运算级的运算结果不再顺序存储,而是将偶地址和奇地址单元对应的运算结果分 别顺序存入存储空间的上下两个半区。
以 N ( N 2 M , M 为整数)点的 FFT 运算为例,采用 2 M 1 级流水线实现。
用 y j 表示第 j 级流水线的运算结果。
当 j 2r 1 r ∈1 M 时,该流水线级只进行复数加法运算,其运算过程可表示为: y j 1 2i y j 1 2i 1 i ∈ 0 N / 2 y j i y j 1 2i N y j 1 2i 1 N i ∈ N / 2 N 从上式可以看出,每个加法运算级需要完成 N 次复数加法运算。
而当 j 2 r r ∈ 1 M 时,该流水线级只进行复数乘法运算,其运算过程可表示为: y j 2 i y j 1 2 i i ∈ 0 N / 2 y j 1 2 i 1 i ∈ 0 S j y j 2 i 1 y j 1 2 i 1W N i ∈ S j N / 2 di 式中,S j N 2 j/2 / 2 ,di S j ceili 1 / S j 1 ,ceil 是对括号中的内容取整。
可以看出,第 j 级流水线需要完成 N 1 2 j / 2 / 2 次复数乘法运算。
针对 8 点的 FFT 运算,图 1 给出了改进后的算法数据流。
将整个数据处理流程分成 5级流水线,第一、三、五级只进行复数加法运算,第二、四级进行复数乘法运算。
图中虚线箭头只表示数据的存储方向,不进行任何算术运算。
x0 X0 x4 X1 x2 X2 W81 x6 X3 x1 X4 x5 W82 W82 X5 x3 X6 x7 W 82 W83 X7 输入 第一级 第二级 第三级 第四级 第五级 输出 图 1 改进后的 FFT 算法数据流 3 改进后,由于基本蝶形运算的复数乘法运算和复数加法运算分成两级进行, 所以各流水线级的运算量与改进前相比变小了,这使各级由运算产生的硬件延时变小, 所以系统可以在更高的时钟频率下正常工作。
另一方面,所有加法运算级的数据流已经变得完全一致, 因此,所有加法运算级可以复用一个运算模块, 而不再需要为每级单独设计控制程序,这大大简化了 VHDL 的开发工作,而且系统的稳定性也得到了提高。
同时,各乘法运算级的运算规律也很明显,所有乘法运算只在该级的奇地址单元进行,而且是到最后一个单元结束。
这些特点增强了乘法运算级的继承性,使系统总体的控制时序得到简化,开发工作变得简单。
3 FFT 处理器设计 在 FFT 处理器工作方式的设计上,充分利用 Stratix 系列 FPGA 内嵌乘法器和存储器资源丰富的特点,采用全并行流水线方式实现。
FFT 处理器的结构如图 2 所示,从图中可以看出该处理器包括:输入和输出处理模块、加法运算单元、乘法运算单元、旋转因子存储器ROM、数据存储器 RAM 和控制器。
图中输入信号 Din 和输出信号 Dout 都是 32 位浮点数,采用 IEEE 754 标准。
EN 是系统使能信号,当 EN 为‘1’时,系统开始正常工作。
CLK 是系统时钟信号。
ISync 为输入帧同步信号,OSync 为输出帧同步信号。
以下将详细介绍各部分的功能。
Din Dout 输入处理 各级 输出处理 模块 RAM 模块 ROM 模块 加法运算 乘法运算 单元 单元 CLK 控 制 器 OSync EN ISync 图 2 FFT 处理器结构图3.1 输入和输出处理模块设计 本文设计的 FFT 处理器采用时域抽取法实现,处理器的输入数据在时域上按一定的倒序规则打乱,经变换后,输出的 FFT 频域信号是顺序排列的。
输入处理模块从总线 Din 读取数据 , (输入的 32 位复数据的实部和虚部) 并在 CLK 的上升沿对数据进行倒序存储。
ISync是输入帧同步信号,ISync 由‘0’变为‘1’时表示输入数据帧的第一个数开始输入。
对于50重复的 FFT 运算,每一帧输入数据都包含 50的历史数据。
在流水方式下,为了保证数据的连续操作,在输入模块中建立两组大小相同的 RAM 同时存储输入数据。
两组 RAM的写操作控制时序完全一样, 但是写数地址不同,对于 N 点的 FFT 运算,二者正好相差 N/2。
这样,每次输入 N/2 个数据后就会有一组 RAM 存满,从下一个时钟开始,这组已经存满的RAM 将提供给下一级运算单元进行处理。
当一帧数据变换完成后, 控制器产生一个输出帧同步信号 OSync, 变换结果会通过输出数据总线 Dout 顺序输出。
本文设计的 FFT 处理器每个时钟会产生两个运算结果,这两个运算结果的地址分别指向上下两个半区,见图 1。
对于离散付氏变换,输出的频域信号总是以中点为轴对称分布,所以前 N/2 个点已经包含了所有频域信息。
基于以上原因,在输出处理模块,每个时钟周期只需要输出第一个数即可, 所以一帧数据经过 FFT 变换后只会输出 N/2个数据。
43.2 加法运算级设计 加法运算级包括加法运算单元和 RAM 模块两个部分,加法运算单元执行浮点加法运算,RAM 模块则保存运算产生的中间结果。
浮点加法器的设计是难点,也是关键,它除了要保证运算速度,使得每个时钟完成一次浮点加法运算,还需要保证运算精度;另外,如何保证运算速度与数据存取速度相互匹配也是设计的关键。
由前面的分析可以看出,本 FFT 处理器的运算速度是数据存取速度的两倍,这就要求设计的 RAM 模块每个时钟需要完成两次读数和两次写数操作。
3.2.1 加法运算单元设计 进行浮点加法运算时,由于两个操作数的指数往往不相等,所以要将尾数对齐后再运算。
为了实现尾数对齐,可以右移较小的数也可以左移较大的数。
这两种操作都会导致数字丢失,一般来说,右移较小的数而丢失的数字所造成的影响要小一些。
浮点加法运算的具体 10过程归纳如下 :1) 阶码相减:比较阶码大小,将两个数的阶码作差得到 E E A E B ;2) 交换操作数的位置:根据第 1 步中的比较结果,交换两个浮点数的位置,使得大数总是 以被加数的形式出现。
这样做的目的在于减少硬件的需求量,在下一步中仅需要一个移 位逻辑就可以完成运算;3) 有效数移位对阶:根据 E 的结果,把较小的浮点数有效数右移,前端补零,使得两个 操作数具有相同的指数;4) 有效数相加:根据移位后的有效数和操作数的符号完成有效数的加减运算;5) 转换:当有效位的结果为负数时,转换为符号、有效数的表示方式。
因为有效数采用原 码表示,所以转换需要一个求补操作,即包括一个加法步骤;6) 前导零检测:对于减法,判断由于减法结果产生的左移数量;对于加法,可能需要右移 一位或不移。
对前导零判定的结果进行编码以确定规格化移位;7) 规格化:根据前导零的检测结果对浮点有效数字计算结果作规格化处理,有效数字左移、 指数相应调整。
对于 N 点的 FFT 运算,加法运算级一共需要进行 N 次复数加法运算。
每个时钟周期,加法运算单元要从上一个流水线级读取两个数据, 并对这两个数分别进行复数加法运算, 然后将运算产生的两个结果同时存入 RAM 模块中。
通常,完成一次复数加法运算需要进行两次实数加法, 所以需要为每个加法运算级分配 4 个浮点加法器,最终可以保证 N/2 个时钟完成一帧数据的处理。
3.2.2 RAM 模块设计 为了与加法运算单元的速度相匹配,RAM 模块必须在每个时钟周期完成两次读数和两次写数操作。
而 FPGA 内部的 RAM 一个时钟周期最多只能进行一次读数和一次写数操作,这便成了系统的速度瓶颈。
通过观察发现,每个时钟周期,加法运算单元产生的两个运算结果分别存入了 RAM 的上下两个半区,而下一个流水线级读取的两个数据分别从该 RAM 模块的奇地址和偶地址单元顺序取出, 基于这些特点,设计了一种能在一个时钟完成两次读数和两次写数操作的 RAM,它的具体实现过程是:将整个 RAM 分成容量相等的四个部分,如图 3 所示(图中,除了作为控制信号的地址线外,其他地址总线均被省略)。
存储数据时,第一个数存入 RAM1 或 RAM2 中,第二个数存入 RAM3 或 RAM4 中,存数地址的最低位(waddrLSB)作为所有 RAM 的控制信号;读取数据时,第一个数从 RAM1 或 RAM3 读出,第二个数从 RAM2 或 RAM4 读出,读数地址的最高位(raddrMSB)作为所有 RAM 5的控制信号。
图中,三角形符号表示对该信号取非,通过这种简单的逻辑控制即可实现各个RAM 模块之间的数据切换。
waddrLSB wr raddrMSB RAM rd wdata1 rdata1 1 wr rd RAM rdata2 2 wr rd RAM wdata2 3 wr rd RAM 4 图 3 RAM 模块设计 根据改进后 FFT 算法的流程可以看出,加法运算单元产生的运算结果并不是按原址存储的,如果采用单组 RAM,会造成数据还没有被完全读取就被新数据覆盖的冲突。
为了解决这个冲突,采用乒乓结构的 RAM 模块进行数据存取,即建立 2 组大小相同的 RAM,如图 4 所示。
当数据往 A 组 RAM 中存储时,下一级运算单元从 B 组 RAM 中读取上次存储的结果。
通过组选择信号实现 A、 两个 RAM 模块之间的切换。
B 组选择信号是一个方波信号,N/2 个时钟进行一次切换。
组选择信号 A RAM 输入数据 输出数据 B RAM 图 4 乒乓结构的 RAM 模块 在上述基本定义的基础上,在 Quartus II 软件环境下对 RAM 模块进行了设计综合与时序仿真,图 5 是仿真时序图。
图中 chipselect 信号是组选择信号,raddr 是读数地址,waddr是写数地址,rdata1_Re、rdata1_Im 和 rdata2_Re、rdata2_Im 分别是从 RAM 中读出的第一个数和第二个数的实部与虚部, wdata1_Re、 wdata1_Im 和 wdata2_Re、 wdata2_Im 是写入 RAM的第一个数和第二个数的实部与虚部,从图中时序可以看出,该 RAM 模块的设计完全满足实际需求。
图5 RAM 模块仿真时序图 63.3 乘法运算级设计 乘法运算单元是 FFT 处理器的关键路径,其运算速度直接关系到系统的整体性能。
与浮点加法器相比,浮点乘法器的结构更为简单,而且 Stratix 系列 FPGA 内部嵌入了大量乘法器资源, 每个乘法器都可以在一个时钟周期内完成一次实数乘法运算, 这给设计带来了便利。
浮点乘法运算主要有如下几个步骤:1) 阶码相加:将两个乘数的阶码部分相加,这里可能会出现溢出的情况,如出现上溢,就 将结果置为浮点格式所能够表示的最大的数;如出现下溢,则将该浮点数置0;2) 尾数相乘:将两个乘数的尾数部分添 l 后相乘,根据乘法结果的最高位调整阶码。
由于 乘法结果最多只需一次左移就可以规格化,因而如果最高位为l,则不需调整阶码,如果 为0,阶码只需减 l 即可;3) 规格化尾数,完成浮点格式输出:将尾数规格化处理,并确定浮点的符号和阶码,将最 终乘积的符号位、指数位和尾数位表示成32位浮点数的格式输出。
由改进后的 FFT 算法流程可以看出,每个乘法运算单元最多只需完成 N/2 次复数乘法运算,且每个时钟周期最多进行一次。
通常,完成一次复数乘法运算需要进行 4 次实数乘法和 2 次实数加法运算,所以,需要为乘法运算单元分配 4 个浮点乘法器和 2 个浮点加法器,这样便可以保证乘法运算级在 N/2 个时钟完成一帧数据的处理。
如何正确存取运算结果同样也是乘法运算单元非常关键的问题。
从图 1 给出的算法数据流中可以看出, 每个乘法运算级都是从上一个流水线级顺序读取数据, 而运算结果是按原址产生的。
利用这一特点,可以将运算结果直接送给下一个流水线级,而不需要保存到 RAM模块中,这便大大简化了系统结构,而且节省了 RAM 资源。
这种方案的具体实现方法是:乘法运算单元提前一个时钟从上一级的 RAM 中读取两个数据, 并与控制单元提供的旋转因子进行浮点乘法运算, 然后将运算结果直接送给下一级。
这种设计可以保证对数据的连续操作,因为相邻两级之间的时序是完全匹配的。
3.4 ROM 模块设计 ROM 模块用来存储乘法运算级所需的旋转因子。
Quartus II 软件中的 MegaWizardPlug–In Manager 工具可以将.mif 格式文件中的数据固化到 ROM 模块中。
具体的实现方法是:先通过 MATLAB 计算出所有旋转因子的实部和虚部,并按 32 位浮点数的格式存储到.mif 文件中,在 Quartus II 软件环境下,利用 MegaWizard Plug–In Manager 工具建立一个ROM 元件,然后选择指定的.mif 文件作为该 ROM 的配置文件,这样便完成了对 ROM 的初始化。
当初始化完成后,只需要.