郝小龙等 : 基于 F P G A的移位寄存器流水线结构 F F T处理器设计与实 基于 F P G A的移位寄存器流水线结构 F F T处理器设计与实现 郝 小龙 ,韦高,刘 娜(西北工业大学 电子信息学院 , 陕西 西安 7 1 0 1 2 9 ) 摘要:设计实现 了基 于FPGA的256点定点 F F T处理 器.处理 器以基一 2算法为基础 , 通过 采用 高效的 两路 输入 移位 寄存 器流 水线 结构 , 有效提 高了碟形运算单元的运算效 率, 减少了寄存 器资源的使 用, 提高了最 大工作 频率 , 增大 了数 据吞 吐量 , 并且使得处理器具有良好 的可扩展性 .详细描述 了具体设计 的算法结构和各 个模块 的实现.设计采 用VerilogHD L 作为硬件描述语言 , 采用 Q u a r t u s I I 设计 仿真 工具进 行设 计、综合 和仿 真, 仿真结果表 明, 处理 器工作 频率 为72MHz , 是一种高效 的FFT处理器 I P核..关键词:FFT处理器;流水线结构;FPGA;Q u a r t u s I I; Ve r i l o g HD L 中图分类号 : TP 3 9 1 文献标识码 : A 文章编号 : 1 0 0 4 — 3 7 3 X( 2 0 1 0 ) 0 9 — 0 1 7 2 — 0 5 De s i g n a n d I mp l e m e n t a t i o n o n FFT Pr o c e s s o r o f FPGA- b a s e d S h i f t Re g i s t e r Pi p e l i n e d Ar c h i t e c t u r e HAO Xi a o - l o n g,W E I Ga o ,L I U Na ( S c h o o l o f E l e c t r o n i c a n d I n f o r ma t i o n , No r t h we s t e r n P o l y t e c h n i c a l U n i v e r s i t y ,xi ' a n 7 1 0 1 2 9,C h i n a ) A b s t r a c t : A 2 5 6 p o i n t F PGA- b a s e d f i x e d - p o i n t FF T p r o c e s s o r i s d e s i g n e d . Th e p r o c e s s o r i s b a s e d o n r a d i x - 2 DI F a l g o — r i t h m. Th e o p e r a t i n g e f f i c i e n c y o f b u t t e r f l y a r i t h me t i c u n i o n i s e n h a n c e d,t h e u s e o f r e g i s t e r i s r e d a c e d a n d t h e ma x i mu m o p e r a t i n g f r e q u e n c y i s i mp r o v e d a n d t h e d a t a t h r o u g h p u t i s e n h a n c e d b y a d o p t i n g a n e f f i c i e n t s h i f t r e g i s t e r p i p e l i n e d a r c h i t e c — - t u r e .Th e d e s i g n e d FFr p r o c e s s o r a l s o h a s g o o d s e a l a b i l i t y .Th e a l g o r i t h m a r c h i t e c t u r e a n d t h e r e a l i z a t i o n o f e a c h mo d u l e a r e d e s c r i b e d i n d e t a i l .Th e d e s i g n u s e s Ve r i l o g HDL a s t h e h a r d wa r e d e s c r i p t i o n l a n gu a g e ,a n d u s e s Qu a r t u sⅡ f o r t h e d e s i g n, s y n t h e s i s a n d s i mu l a t i o n . Th e s i mu l a t i o n r e s u l t s s h o w t h a t t h e p r o c e s s o r i s a h i g h e f f i c i e n t F r p r o c e s s o r I P c o r e wi t h 72 M Hz wor k f r e qu e nc y . K e y wo r d s : F F T p r o c e s s o r ;p i p e l i n e d a r c h i t e c t u r e ;F P GA;Qu a r t u s I I;Ve r i l o g HDL 0 引言快速傅里叶变换( F F T) 在雷达 、 通信和电子对抗等 领域有 广 泛应 用 .近 年来 现场可编程门阵列 ( F P G A) 的飞 速发展 , 与DSP技术 相比,由于其 并 行信 号处 理结 构,使得FPGA 能够很好 地适 用于高速 信 号处 理 系统 . 由于 Al t e r a等公 司研 制的FFTIP核 , 价钱 昂贵 , 不适 合 大规模应 用,在特定 领域中, 设计 适合于自己领 域需要的FFT处理 器是较 为 实际 的选择 . 本 文设计 的FFT处理器,基于FPGA 技术,由于采用移 位寄存 器流 水线结 构,实现了两路数 据 的同时输 入, 相比传统的级联结构, 提高了蝶形运算单元的运算 效率, 减小了输 出延 时, 降低 了芯片资 源的使 用.在OF DM 系统 的实 际应用中[ 1 ] , 因它可以采 用快速傅里叶变换 , 能方便快捷地实现调制和解调 , 故结合 MI MO 收稿 日期 : 2 0 0 9 - 1 2 — 1 4 1 7 2 技术 , 设计 的FFT处理器 结构 , 可 以很 好地 应用于 2根 天线 的MI M0— 0F DM 系统 中. 1 F F T处 理的应 用及 D I F F F r算 法原 理图1给 出一个2根 天线MI MO- O F DM 系统中FFT的使 用 .快速 傅里叶变换算法基本上分为两大类:时域抽 取(DIT) 和频域抽取(DIF)[2],这里设计的FFT处理器采用基- 2 D I F算法. 图1FF T 处理器应用于一个2根 天线的MIMO- OF DM 系统 对于 N 点序列z( N) , 其傅里叶变换定义为 : J V —l x ( ) 一∑ ( ) w , k —o , 1 , 2 , …, N 一1 , 嚣0.Ⅳ一符(1)《现代电子技术) 2 o l o年第 9期总第 3 2 0 期 电子技术应用司 将z()分成 上、下两部 分,得:N/ 2 - -1 N/ 2 - -1 x ( 忌):==∑z(7z)w+∑ x ( n +N / 2 l g I T ~ . . $ X T . N k .( 2 ) 分 别令 k一2r,k一 2 r + 1 , r 一0,1,2,…,N/ 2 — 1 , 得:一[)++百 N X ( 2 r ) ) ] w ( 3 ) 一∑[z()+z ( + ) ] w ( 3 X ( 2 r +1 ) 一∑ [ z ( ) 一x ( n + ) ] 矿/.(4)这样将两个N点的DFT分成两个N/ 2点的DFT, 分 的方法是 将X( 忌)按序号 是的奇 、 偶分 开 .通过 这种 方式继续分下去,直到得到两点的DF T.采用DI F方法设计 的FFT, 其输入是正序, 输出是按照奇偶 分 开的倒 序.2移位寄存 器 流水线 结构 的FFT在传统 流水 线结 构的FFT中,需要将全 部数据输入寄存器后, 可开始蝶形运 算.在基一 2 DI F算法中可以发 现,当前 N/ 2 个 数据 进入 寄存 器后 , 运 算便 可以开始 , 此 后进 入 的第 N/ 2 +1个数 据 与寄存 器第一个 数 据进行蝶 形运算 , 以此类 推.由于采用频域抽取法 , 不需要对输入的数据进行倒 序处理 , 简化了地址控制 , 这样 , 可以采用移位寄存器的 方式,依次将前N/ 2个数据移入移位寄存器,在N/ 2 +1 时刻 , 第一个数据移出移 位寄存器,参与运算.相对 于传统的RAM读写方式,采用移位寄存器存储结构综合后的最大工作频率为 5 0 0 MHz , 远大于 RA M 方式的166MHz . 当移 位寄存 器 相继有 数据 移 出时 , 在移 位 寄存器 中会出现空 白位 .此时,引入 第二路数据 , 在第一路数 据 依次移 出进行蝶算时, 第二路数据依次补充到移位寄存 器的空白位 中, 为运算做准备.通过这样一种类似" 乒 乓操作" 的结构 , 可以使蝶形运算模块 中的数据不 问断 地 输入 , 运算效率 达到100.不 同 于传 统的" 乒乓操作"结构 , 由于 使用移位寄存器,不需要两块RAM , 可 以省掉一 半 的寄存 器 .图 2为256点 F F T处理 器 的第 一 级结构 . 基于上述基本原理, 将这种移位寄存器结构扩展到 整个 F F T 系统 的各 级,可以发 现各级使 用 的移 位 寄存 器数 量是递 减的.现 使用 一个 8点结 构来进 行说 明.如图3所示 , 数据 由输 入 1和输 入 2进 人第 一级.通过 开关进 行选 通控 制 .由于是 N=8的 运算 , 所 以各 级分别 加入 4级、2级和 1级 的移位 寄存器 . 输入l : : 竺I竺I竺I::.I/,1、 ① I I I I I 输入2一/y__1Ⅱ 奉 "蛹端特寄 . , , … , 图2N一2 5 6的FFT处理 器 的第 一级结构(1)(2)(3)4级移位 蝶形运算单元 蝶 彤运 算单元 蝶形运 算单元 厂r、、r1_1/一r、、n,,1、:小…t1J队'/① m l l ② A : f 、 > \ I A ' I\ 、 _ 一/\ < U 一/yi奉2级移 位/I一l级移位 + I / I 奇仔鼯 时钟脉冲/寄i//ll23I——一/避制计数器图3N= 8的FFT处理器整 体结构.'分两路来说明运算过程 : 存器中, 等到上路的四点运算 开始 , 第二级 的移位寄存 将K打到位 置①,第一路数据进入移位寄存器,器有空 白位 时,移入第 二级 , 为下 路 的四点运 算做 准备 . 待第一 路 的前 4个 数据存 人 4级移 位寄存 器后 , 第 一路 所以第一级蝶形 运算上路输出前N/ 4— 2个进入下进入的第 5 个数据与移位寄存器移 出的第 1个数据进 一级 寄存器 , 下路输 出的数据依次存入本级移位寄存 行蝶形 运算 . 器中. 由于输 出结 果有上下两路 , 第二级是一个四点 的 当第一级 的输 出前 N/ 4— 2 个 数据 z . ( 0 ) +X . ( 4 ) DF T, 所以对于上路 的输 出结果 . ( O ) + X . ( 4 )类似于 和.(1)+.(5)存人第二级移位寄存器时, 运算便可 第一级 , 直接存入下一级寄存器 , 为四点运算做准备 , 下 以开始 , 这时开关 K.打到位置 ② , 此 时第一级上路输 路 的输 出,(.(0)一z.(4))W先存入 本级 2级 移位 寄 出的数据 . ( 2 ) + X . ( 6 ) , 即第 一级上路 输 出的第 三个 】 7 3 郝小龙等 : 基于 F P GA的移位寄存器流水线结构 F F T处理器设计与实现 数据与第二级移位寄存器移出的第一个数据,即 z . ( O ) + . ( 4 )进行蝶形运算,输 出的第四个数据.(3).(7)与 z . ( 1 ) +X . ( 5 )进行蝶算. 在这个运算 过程中, 第一级的 2级移位寄存器移出数据依次移位存 人到第二级的移位寄存器产生的空 白位中. 两 个时钟 后,第一级 上路输 出的四个数 据完成 了蝶 形运算 , K .打到位置①,在接下来的两个 时钟 里,第一级 中 2级移 位寄存 器的输出依 次 与此 时第二级中2级移位寄存 器 的输 出数 据进 行 蝶形 运算 , 即(.(O)一Xo(4))W与(z.(2)一z . ( 6 ) ) V , ( z 0 ( 2 ) 一z . ( 6 ) ) wI 与(z.(3)一z.(7))w,完成 第一 级下 路输出的四个 数据的蝶 形运算 . 此时,第一路在第一级运算后的输出数据,在 第 二级 完成了全 部的蝶形运算 . 第二级的输 出结 果同第一级 一样 , 蝶形 运算 的上路输 出前 N/ 8 — 1 个进 入下 一 级寄存器, 后一个数据直接进入后一级进行碟算, 下路输出的数据存 入本 级移 位寄存 器中.第三级的运算与第二级和第一级类似, 即移入 1级 寄存 器 的数据 与其后 一个数 据进 行碟算 , 同时使前 一级 寄存 器 的输 出数 据进 入后一 级寄 存器 的空 白位 中, 然后 开关打到位置② , 对下路输出数据进行碟算. 对于第二路数据 , 通过开关控制, 在第二级 中, 待第 一 路第 一级 下路输 出数 据进 行蝶形 运算 时,移人 寄存器 的空 白位 , 为运算 做准 备,由于 前级 运算周期 是后级运算周 期 的两倍 , 对于第二 级 碟算 模块而言,数据 仍然是不间断输入 的.通过这样 两路 数据 的交 替运 算和存储 , 实现 " 乒乓操作" , 从而提高了蝶形运算模块的运算效率.图 4是 2 5 6点FFT的具体 运算输 入 和输 出时序 图.输入1 输入2 上蹿输 l I J 下路输 出图4两路 数据的输入和输出时 序图对于只有 一路 数据 的应 用 场合 , 可 以在 前级 加入,门控开关和数据缓冲寄存器分成两路数据, 实现一路数 据的不间断读入 . 由于采用 移位 寄存 器结梅 , 各级 寄存 器使用 的数量 都是固定 的,即为 N/ 2 +N/ 4 .其中,N为该级 DF T运 算的点数, 各级使用 的移位寄存器深度逐级递减, 从而 大大 降低 了寄存 器 的使用 数量 . ] 7 4 此外,由于各 级结 构 固定 , 所 以大点数 F F T 只是小 点数 F F T基础 上级 数 的增 加,而且 由于 移位 寄存 器的输出相 对于RAM 而言不 需要 复杂 的地址 控制 , 所 以这 种结构 的FFT处理 器具有 非常 好 的可扩展性 .比如 需要实现 5 1 2 点的FFT, 只需要在256点 的基 础上增加一级即可.3具体 模块 的设 计3.1控制与地址 产生模 块 由于两路 数据 同时输 入,为了防止 发生 两路数据 间 的串扰 , 对数据 的控 制显得 极其关 键 .从上 面的算法 结构分析 中知道 , 由 于后 级的DF T运算点数是 前 一级 的一半,所以后一 级 的开 关转 换周期也是 前一级的一半 , 基 于这种 关系,可以使用一 个8位计数 器 的每一位状 态 来对 各级 开关进 行控 制 .最高位控 制第 一级 , 同时 由于 上 一级数 据进入 下一 级需要 一个 时钟 , 所 以下一 级 的开 关转 换时 刻要 比上一 级延 迟一个 时钟周 期.对于移位寄存器 , 在实 现时 , 各级的前级 移位寄存 器 深度为 N/ 2 —1 , 从 本质 而言,是使 运算 开始 的时钟 上升沿到来时 , 数据 已经 出现在碟算模块 输入线 上,而不需要 下一个时钟 的驱动来 移 出寄存 器,比如第 二级 移位 寄存 器的级数为 6 3 .这样 , 运算周期 正好是 2的倍 数,从而方 便使用计数器 的各位 直接对开关进行控制 . 同时,计数器还可以用来产生所需旋转因子的RAM 地址 .根 据各级 蝶 形运 算 所需 旋转因子 的规 律,可以利 用计数 器 的高 位补 零来产生查 找表的地 址.比如,对于第一 级,因为需 要 在最 低 位第 一次出现 1时提 供W0 ~, 第二次出现 1时提供 w , …, 以此类推, 周期为 1 2 8 , 所以可以使 用计数器的低七位作为地址.对 于第二级 , 由于所需要的地址为偶数,可以由计 数器的[6:1]和最低位 置 0产 生 .表 1为 8点 时使用 三位计数 器输出旋 转 因子 的地 址情 况.表18点时使用三位计数器输 出旋转因子的地址情况 控 制和地 址产 生模块 的仿 真结果 如图5所示 , 其中sel代表 开关 控制 , a d d r 代表 产生 的地址 . 2 0 1 0年第9期 总第320图5控制和地址产生模块的仿 真结果3.2蝶形运算模 块 蝶算模块 由一 个 复数 加法器,一个复数减法器和一个旋转 因子 的复数乘 法器 构成 , 如图6所示 . 图6蝶形运算单元旋转 因子 乘法 器通常由4次 实数 乘法和2次 加/ 减法 运算 实现 , 但 因为 C O S 和sin的值 可 以预 先存储 , 通 过下 面 的算 法[ 4 可 以简化 复数 乘法器 : ( 1 )存 储如 下三个 系数 : C, C+ S, C— S ( 2 )计算 : E — X—y和Z:C*E— C*( X—y) ( 3 )用R一(C— S)*y+ Z, J一(C+ S )*X— Z, 得到需 要 的结 果.这种算法 使用了3次乘 法,1次 加法和2次 减法,但是需要 使用存 储 3个表 的ROM 资源.设计 中数据 的输 人为16位 复数,所以将 旋转因子 c o s ( 2 忌7c/N),sin(2五7c/N) 量化成带符号数的16位 二 进制数后 , 存储 到ROM 中,由于值域 不同,需要注意C+S 和C—S的表要 比 C表 多1位精度 . 运算 后的结果需要除以量化时乘以的倍数16b0111111111111111.具 体实现时由于除法运算在FPGA器件需要 消耗较多 的资源 , 设计中采用二进 制数移 位的方法来实 现除 法运 算 .为 了防止 数据 溢出,设计 对输出结 果除以2.图7为 蝶形运算模块的RTL级 结 构图 . 图7蝶形运算模块的 R TL结构图 3 . 3 倒序输出模 块 由频 域抽 取 的基一 2算法可知,运算结果需要倒序输出.可 以先将结果存储到RAM 中, 然后使用0~ 2 5 5的二进 制 数倒 序 产生 RAM 读取地址 , 依 次将 结果 读出,其中实现 一个 8位二 进制 数倒 序 的算 法如 下:(1)将 8位数 字 的相邻两 位交换 位置 ; ( 2 )将相 邻 的两位看 作1组,相邻两组 交换 位置 ; ( 3 )将相邻的 4位看作 1 组,相邻两组交换位置. 经过这 样 的交换位 置后 , 输 出即为 原来 8位二进 制数的倒 序.举例对 于 8位二 进制数10110110来 说,第一次交换位置 的结 果是01111001,第二次交换位置的结 果是11010110,最后 交换位置的结果是O1101101.可见 正 好是 原来 数字 的倒 序.另外 , 由于设计 的是 两路数据同时写 入,一路数据 读出,所以读取 的频 率是 写入频 率的2倍 , 使用 P L L实 现原始时钟的二倍频 , 用来读取 R AM.倒序模块仿真 结果 如图8所示 . 图8倒序模块仿真结果最终生 成的FFT处 理器模 块 图如 图 9所示 . 图9生成的FFT 处理 器模 块4仿真结 果各级间数 据 时序情 况如 图1O所示,设计的FFT处 理器仿真结果如图 1 1 所示.采用一路阶梯递增信号和 另一 路XXX X信 号进 行仿 真,通过 与Ma t l a b计算 结果 进行 对比,结果 基本 一致,可以满 足 系统 要求.系 统总的延 时 由延时 最大 的第一 级决 定,为第 一级 运算 的延 时 加上 倒序输 出的延 时,总共 是(256+1 2 8 ) *c l k , 相 对于 一般流水 线结构 ( 2 5 6 *读 人周 期+7*1 2 8 *蝶 算周 期+1 2 8 *读 人周期 ) , 系统延 时大 为减少 . 通过仿真可知, 系统最大频率由蝶形运算模块的最 大工作频率决定 .使用 Qu a r t u s I I 软件时序仿真后 , 得 到处理 器 的工作频 率为72MHz . 1 7 5 郝小龙等 : 基于 F P GA的移位寄存器流水线结构 F F T处理器设计与实现 图1O各级间两路 数据时序 情况图11FFT处理器仿 真结果5结语通过采用移位寄存器流水线结构, 可以有效地提高 F F T处理器中蝶形运算单元 的效率 , 减少寄存 器的使 用数量, 并且简化了地址控制 , 提高处理器 的工作频率, 具有 良好 的 可扩 展性,同时可以实现两 路数据的同时输入 , 从而增 大 了一倍 的数据 吞吐 量 .对 于工作 频率 要 求较 高,数据吞 吐量较 大,尤其对于需 要两路数 据输 入 的场合 , 比如 两天线的MI MO- OF D M 系统,具有很大的实用 价值 . 参考文献[13崔新瑞 , 张捷 , 张晶 , 等. O F DM 系统原理 及仿 真实现[ J ] . 信 息安全与通信保密 , 2 0 0 7 ( 1 2 ) : 6 8 - 6 9 . [ 2 ]丁玉美 , 高西全. 数字信号处理 [ M] . 西安:西安电子科技大 学 出版 社,2001.[3]戴明桢. 数 字信号处 理 的硬件实 现[ M] . 北京 : 航空 工业 出版社,1998.[41Uw e Me y e r - B a e s e . 数字信号处理的 F P G A 实现[ M] . 刘凌 , 译. 北京 : 清华 大学 出版社 , 2 0 0 2 . [ 5 ]S a mi r P a l n i t k a r . Ve r i l o g HD L数字 设计 与综 合[M] . 夏宇 闻,胡燕祥 , 刁岚松 , 译. 北京 : 电子工业 出版社 , 2 0 0 4 . [ 6 ]尹长川 , 罗涛,乐光 新. 多载 波 宽带 无线 通信 技术[ M] . 北京:北京邮 电大学出版社 , 2 0 0 4 . I - 7 ]李小进 , 初建 民, 赖宗声 , 等. 高速基 2 F F T处理器 的结构设 计与 F P G A实现[ J ] . 电路与系统学报 , 2 0 0 5 , 1 0 ( 5 ) : 4 9 — 5 3 . [ 8 ]余景华 , 郭 亨群. OF D M 系统中64点 F F T的FPGA设 计[J].通信技术 , 2 0 0 8 ( 1 2 ) : 1 0 9 一ii1.[9]王诚 , 吴 继华. Al t e r a F P GA/ C P L D设计 ( 基础 篇) [ M] . 北京:人民邮 电出版社 , 2 0 0 5 . [ 1 O ]Al t e r a C o r p r a t i o n . C y c l o n e I I d a t a s h e e t [ M] .US A:A l t e r a , · Co r p r a t i o n,20 06 . 作者简介 :郝小龙 男, 1 9 8 3年 出生 , 内蒙古 自治区鄂 尔多斯人 , 硕士研究生 .主要研 究方向为微 波通信 、 应用微波技 术. 韦高男, 1 9 6 3年 出生 , 山东单县人 , 教授 , 博士生导师.主要研 究方向为电磁计算 、 微 波测量 、 天线理论 与设计 . 刘娜女,1984年 出生 , 陕西 渭 南人 , 硕 士研 究生.主 要研究方向为天线理论 与设 计.(上接第171页) 参考文献[1]程钧 , 李信之. 高精度 轴角编码 器的多极旋 变选 用及结构 精 度设计口] . 电子机械工程 , 2 0 0 1 ( 5 ) : 8 - 1 0 . [ 2 ]刘华伟 , 肖汉. 基于HP I 接 口的导航计算机旋变信号采集 电 路设计 [ J ] . 弹箭 与制 导学报 , 2 0 0 4 ( 6 ) : 3 9 2 — 3 9 4 . E 3 ] 尚超 , 王淦泉 , 陈桂林. 跟踪型 R D C载波相位误 差和输入 噪 声的分析及应用 [ A ] . 高精度几何量光 电测量与校准技术研 讨 会论 文集 , 2 0 0 8 . [ 4 ]徐振刚. 基于龙伯格观测器 的Pd]C磁极 位置检测方 法[ J ] . 微特电机 , 2 0 0 7 ( 8 ) : 6 - 7 . [ 5 ] 黄仁欣. D S P 技术及应用[M] .北京:电子工业出版社,2007.[6]李声晋. 一种旋转变压器—— R D C测角系 统的数字标定及 补偿方法 [ J ] . 微特电机 , 2 0 0 7 ( 6 ) : 2 6 — 2 8 . [ 7 ]庞军. 基 于电压行波 的输 电线路故 障定位方 法研究 [ D ] . 重庆:重庆 大学 , 2 0 0 9 . [ 8 ]周婧婧. 基于 故障树 分析 的电力变 压器可 靠性评估 方法研 究[ D] . 重庆:重庆大学 , 2 0 0 9 . [ 9 ] 曲振江. R D C缓 冲电路 的技术分析[ J ] . 微特 电机 , 2 0 0 7 ( 6 ) : 2 6 — 2 8. [ 1 O ]方磊. 电力电缆故 障定位 方 法研 究 及在 线 检测装 置实现[D] . 长沙 : 长沙理工大学 , 2 0 0 9 . 作者简 介:王军平 男, 1 9 7 0年 出生 , 浙江建德人 , 在读博 士研 究生, 高级工程师.研 究方向为机 电一体化设计及控 制. 尚超男, 1 9 8 1年 出生 , 河南汝州人 , 博士, 工程师 .研 究方向为控制 电路设计 . l 7 6
下载该文档
文档格式：PDF
更新时间：2014-09-03
下载次数：0
点击次数：1
郝小龙等 : 基于 F P G A的移位寄存器流水线结构 F F T处理器设计与实 基于 F P G A的移位寄存器流水线结构 F F T处理器设计与实现 郝 小龙 ,韦高,刘 娜(西北工业大学 电子信息学院 , 陕西 西安 7 1 0 1 2 9 ) 摘要:设计实现 了基 于FPGA的256点定点 F F T处理 器.处理 器以基一 2算法为基础 , 通过 采用 高效的 两路 输入 移位 寄存 器流 水线 结构 , 有效提 高了碟形运算单元的运算效 率, 减少了寄存 器资源的使 用, 提高了最 大工作 频率 , 增大 了数 据吞 吐量 , 并且使得处理器具有良好 的可扩展性 .详细描述 了具体设计 的算法结构和各 个模块 的实现.设计采 用VerilogHD L 作为硬件描述语言 , 采用 Q u a r t u s I I 设计 仿真 工具进 行设 计、综合 和仿 真, 仿真结果表 明, 处理 器工作 频率 为72MHz , 是一种高效 的FFT处理器 I P核..关键词:FFT处理器;流水线结构;FPGA;Q u a r t u s I I; Ve r i l o g HD L 中图分类号 : TP 3 9 1 文献标识码 : A 文章编号 : 1 0 0 4 — 3 7 3 X( 2 0 1 0 ) 0 9 — 0 1 7 2 — 0 5 De s i g n a n d I mp l e m e n t a t i o n o n FFT Pr o c e s s o r o f FPGA- b a s e d S h i f t Re g i s t e r Pi p e l i n e d Ar c h i t e c t u r e HAO Xi a o - l o n g,W E I Ga o ,L I U Na ( S c h o o l o f E l e c t r o n i c a n d I n f o r ma t i o n , No r t h we s t e r n P o l y t e c h n i c a l U n i v e r s i t y ,xi ' a n 7 1 0 1 2 9,C h i n a ) A b s t r a c t : A 2 5 6 p o i n t F PGA- b a s e d f i x e d - p o i n t FF T p r o c e s s o r i s d e s i g n e d . Th e p r o c e s s o r i s b a s e d o n r a d i x - 2 DI F a l g o — r i t h m. Th e o p e r a t i n g e f f i c i e n c y o f b u t t e r f l y a r i t h me t i c u n i o n i s e n h a n c e d,t h e u s e o f r e g i s t e r i s r e d a c e d a n d t h e ma x i mu m o p e r a t i n g f r e q u e n c y i s i mp r o v e d a n d t h e d a t a t h r o u g h p u t i s e n h a n c e d b y a d o p t i n g a n e f f i c i e n t s h i f t r e g i s t e r p i p e l i n e d a r c h i t e c — - t u r e .Th e d e s i g n e d FFr p r o c e s s o r a l s o h a s g o o d s e a l a b i l i t y .Th e a l g o r i t h m a r c h i t e c t u r e a n d t h e r e a l i z a t i o n o f e a c h mo d u l e a r e d e s c r i b e d i n d e t a i l .Th e d e s i g n u s e s Ve r i l o g HDL a s t h e h a r d wa r e d e s c r i p t i o n l a n gu a g e ,a n d u s e s Qu a r t u sⅡ f o r t h e d e s i g n, s y n t h e s i s a n d s i mu l a t i o n . Th e s i mu l a t i o n r e s u l t s s h o w t h a t t h e p r o c e s s o r i s a h i g h e f f i c i e n t F r p r o c e s s o r I P c o r e wi t h 72 M Hz wor k f r e qu e nc y . K e y wo r d s : F F T p r o c e s s o r ;p i p e l i n e d a r c h i t e c t u r e ;F P GA;Qu a r t u s I I;Ve r i l o g HDL 0 引言快速傅里叶变换( F F T) 在雷达 、 通信和电子对抗等 领域有 广 泛应 用 .近 年来 现场可编程门阵列 ( F P G A) 的飞 速发展 , 与DSP技术 相比,由于其 并 行信 号处 理结 构,使得FPGA 能够很好 地适 用于高速 信 号处 理 系统 . 由于 Al t e r a等公 司研 制的FFTIP核 , 价钱 昂贵 , 不适 合 大规模应 用,在特定 领域中, 设计 适合于自己领 域需要的FFT处理 器是较 为 实际 的选择 . 本 文设计 的FFT处理器,基于FPGA 技术,由于采用移 位寄存 器流 水线结 构,实现了两路数 据 的同时输 入, 相比传统的级联结构, 提高了蝶形运算单元的运算 效率, 减小了输 出延 时, 降低 了芯片资 源的使 用.在OF DM 系统 的实 际应用中[ 1 ] , 因它可以采 用快速傅里叶变换 , 能方便快捷地实现调制和解调 , 故结合 MI MO 收稿 日期 : 2 0 0 9 - 1 2 — 1 4 1 7 2 技术 , 设计 的FFT处理器 结构 , 可 以很 好地 应用于 2根 天线 的MI M0— 0F DM 系统 中. 1 F F T处 理的应 用及 D I F F F r算 法原 理图1给 出一个2根 天线MI MO- O F DM 系统中FFT的使 用 .快速 傅里叶变换算法基本上分为两大类:时域抽 取(DIT) 和频域抽取(DIF)[2],这里设计的FFT处理器采用基- 2 D I F算法. 图1FF T 处理器应用于一个2根 天线的MIMO- OF DM 系统 对于 N 点序列z( N) , 其傅里叶变换定义为 : J V —l x ( ) 一∑ ( ) w , k —o , 1 , 2 , …, N 一1 , 嚣0.Ⅳ一符(1)《现代电子技术) 2 o l o年第 9期总第 3 2 0 期 电子技术应用司 将z()分成 上、下两部 分,得:N/ 2 - -1 N/ 2 - -1 x ( 忌):==∑z(7z)w+∑ x ( n +N / 2 l g I T ~ . . $ X T . N k .( 2 ) 分 别令 k一2r,k一 2 r + 1 , r 一0,1,2,…,N/ 2 — 1 , 得:一[)++百 N X ( 2 r ) ) ] w ( 3 ) 一∑[z()+z ( + ) ] w ( 3 X ( 2 r +1 ) 一∑ [ z ( ) 一x ( n + ) ] 矿/.(4)这样将两个N点的DFT分成两个N/ 2点的DFT, 分 的方法是 将X( 忌)按序号 是的奇 、 偶分 开 .通过 这种 方式继续分下去,直到得到两点的DF T.采用DI F方法设计 的FFT, 其输入是正序, 输出是按照奇偶 分 开的倒 序.2移位寄存 器 流水线 结构 的FFT在传统 流水 线结 构的FFT中,需要将全 部数据输入寄存器后, 可开始蝶形运 算.在基一 2 DI F算法中可以发 现,当前 N/ 2 个 数据 进入 寄存 器后 , 运 算便 可以开始 , 此 后进 入 的第 N/ 2 +1个数 据 与寄存 器第一个 数 据进行蝶 形运算 , 以此类 推.由于采用频域抽取法 , 不需要对输入的数据进行倒 序处理 , 简化了地址控制 , 这样 , 可以采用移位寄存器的 方式,依次将前N/ 2个数据移入移位寄存器,在N/ 2 +1 时刻 , 第一个数据移出移 位寄存器,参与运算.相对 于传统的RAM读写方式,采用移位寄存器存储结构综合后的最大工作频率为 5 0 0 MHz , 远大于 RA M 方式的166MHz . 当移 位寄存 器 相继有 数据 移 出时 , 在移 位 寄存器 中会出现空 白位 .此时,引入 第二路数据 , 在第一路数 据 依次移 出进行蝶算时, 第二路数据依次补充到移位寄存 器的空白位 中, 为运算做准备.通过这样一种类似" 乒 乓操作" 的结构 , 可以使蝶形运算模块 中的数据不 问断 地 输入 , 运算效率 达到100.不 同 于传 统的" 乒乓操作"结构 , 由于 使用移位寄存器,不需要两块RAM , 可 以省掉一 半 的寄存 器 .图 2为256点 F F T处理 器 的第 一 级结构 . 基于上述基本原理, 将这种移位寄存器结构扩展到 整个 F F T 系统 的各 级,可以发 现各级使 用 的移 位 寄存 器数 量是递 减的.现 使用 一个 8点结 构来进 行说 明.如图3所示 , 数据 由输 入 1和输 入 2进 人第 一级.通过 开关进 行选 通控 制 .由于是 N=8的 运算 , 所 以各 级分别 加入 4级、2级和 1级 的移位 寄存器 . 输入l : : 竺I竺I竺I::.I/,1、 ① I I I I I 输入2一/y__1Ⅱ 奉 "蛹端特寄 . , , … , 图2N一2 5 6的FFT处理 器 的第 一级结构(1)(2)(3)4级移位 蝶形运算单元 蝶 彤运 算单元 蝶形运 算单元 厂r、、r1_1/一r、、n,,1、:小…t1J队'/① m l l ② A : f 、 > \ I A ' I\ 、 _ 一/\ < U 一/yi奉2级移 位/I一l级移位 + I / I 奇仔鼯 时钟脉冲/寄i//ll23I——一/避制计数器图3N= 8的FFT处理器整 体结构.'分两路来说明运算过程 : 存器中, 等到上路的四点运算 开始 , 第二级 的移位寄存 将K打到位 置①,第一路数据进入移位寄存器,器有空 白位 时,移入第 二级 , 为下 路 的四点运 算做 准备 . 待第一 路 的前 4个 数据存 人 4级移 位寄存 器后 , 第 一路 所以第一级蝶形 运算上路输出前N/ 4— 2个进入下进入的第 5 个数据与移位寄存器移 出的第 1个数据进 一级 寄存器 , 下路输 出的数据依次存入本级移位寄存 行蝶形 运算 . 器中. 由于输 出结 果有上下两路 , 第二级是一个四点 的 当第一级 的输 出前 N/ 4— 2 个 数据 z . ( 0 ) +X . ( 4 ) DF T, 所以对于上路 的输 出结果 . ( O ) + X . ( 4 )类似于 和.(1)+.(5)存人第二级移位寄存器时, 运算便可 第一级 , 直接存入下一级寄存器 , 为四点运算做准备 , 下 以开始 , 这时开关 K.打到位置 ② , 此 时第一级上路输 路 的输 出,(.(0)一z.(4))W先存入 本级 2级 移位 寄 出的数据 . ( 2 ) + X . ( 6 ) , 即第 一级上路 输 出的第 三个 】 7 3 郝小龙等 : 基于 F P GA的移位寄存器流水线结构 F F T处理器设计与实现 数据与第二级移位寄存器移出的第一个数据,即 z . ( O ) + . ( 4 )进行蝶形运算,输 出的第四个数据.(3).(7)与 z . ( 1 ) +X . ( 5 )进行蝶算. 在这个运算 过程中, 第一级的 2级移位寄存器移出数据依次移位存 人到第二级的移位寄存器产生的空 白位中. 两 个时钟 后,第一级 上路输 出的四个数 据完成 了蝶 形运算 , K .打到位置①,在接下来的两个 时钟 里,第一级 中 2级移 位寄存 器的输出依 次 与此 时第二级中2级移位寄存 器 的输 出数 据进 行 蝶形 运算 , 即(.(O)一Xo(4))W与(z.(2)一z . ( 6 ) ) V , ( z 0 ( 2 ) 一z . ( 6 ) ) wI 与(z.(3)一z.(7))w,完成 第一 级下 路输出的四个 数据的蝶 形运算 . 此时,第一路在第一级运算后的输出数据,在 第 二级 完成了全 部的蝶形运算 . 第二级的输 出结 果同第一级 一样 , 蝶形 运算 的上路输 出前 N/ 8 — 1 个进 入下 一 级寄存器, 后一个数据直接进入后一级进行碟算, 下路输出的数据存 入本 级移 位寄存 器中.第三级的运算与第二级和第一级类似, 即移入 1级 寄存 器 的数据 与其后 一个数 据进 行碟算 , 同时使前 一级 寄存 器 的输 出数 据进 入后一 级寄 存器 的空 白位 中, 然后 开关打到位置② , 对下路输出数据进行碟算. 对于第二路数据 , 通过开关控制, 在第二级 中, 待第 一 路第 一级 下路输 出数 据进 行蝶形 运算 时,移人 寄存器 的空 白位 , 为运算 做准 备,由于 前级 运算周期 是后级运算周 期 的两倍 , 对于第二 级 碟算 模块而言,数据 仍然是不间断输入 的.通过这样 两路 数据 的交 替运 算和存储 , 实现 " 乒乓操作" , 从而提高了蝶形运算模块的运算效率.图 4是 2 5 6点FFT的具体 运算输 入 和输 出时序 图.输入1 输入2 上蹿输 l I J 下路输 出图4两路 数据的输入和输出时 序图对于只有 一路 数据 的应 用 场合 , 可 以在 前级 加入,门控开关和数据缓冲寄存器分成两路数据, 实现一路数 据的不间断读入 . 由于采用 移位 寄存 器结梅 , 各级 寄存 器使用 的数量 都是固定 的,即为 N/ 2 +N/ 4 .其中,N为该级 DF T运 算的点数, 各级使用 的移位寄存器深度逐级递减, 从而 大大 降低 了寄存 器 的使用 数量 . ] 7 4 此外,由于各 级结 构 固定 , 所 以大点数 F F T 只是小 点数 F F T基础 上级 数 的增 加,而且 由于 移位 寄存 器的输出相 对于RAM 而言不 需要 复杂 的地址 控制 , 所 以这 种结构 的FFT处理 器具有 非常 好 的可扩展性 .比如 需要实现 5 1 2 点的FFT, 只需要在256点 的基 础上增加一级即可.3具体 模块 的设 计3.1控制与地址 产生模 块 由于两路 数据 同时输 入,为了防止 发生 两路数据 间 的串扰 , 对数据 的控 制显得 极其关 键 .从上 面的算法 结构分析 中知道 , 由 于后 级的DF T运算点数是 前 一级 的一半,所以后一 级 的开 关转 换周期也是 前一级的一半 , 基 于这种 关系,可以使用一 个8位计数 器 的每一位状 态 来对 各级 开关进 行控 制 .最高位控 制第 一级 , 同时 由于 上 一级数 据进入 下一 级需要 一个 时钟 , 所 以下一 级 的开 关转 换时 刻要 比上一 级延 迟一个 时钟周 期.对于移位寄存器 , 在实 现时 , 各级的前级 移位寄存 器 深度为 N/ 2 —1 , 从 本质 而言,是使 运算 开始 的时钟 上升沿到来时 , 数据 已经 出现在碟算模块 输入线 上,而不需要 下一个时钟 的驱动来 移 出寄存 器,比如第 二级 移位 寄存 器的级数为 6 3 .这样 , 运算周期 正好是 2的倍 数,从而方 便使用计数器 的各位 直接对开关进行控制 . 同时,计数器还可以用来产生所需旋转因子的RAM 地址 .根 据各级 蝶 形运 算 所需 旋转因子 的规 律,可以利 用计数 器 的高 位补 零来产生查 找表的地 址.比如,对于第一 级,因为需 要 在最 低 位第 一次出现 1时提 供W0 ~, 第二次出现 1时提供 w , …, 以此类推, 周期为 1 2 8 , 所以可以使 用计数器的低七位作为地址.对 于第二级 , 由于所需要的地址为偶数,可以由计 数器的[6:1]和最低位 置 0产 生 .表 1为 8点 时使用 三位计数 器输出旋 转 因子 的地 址情 况.表18点时使用三位计数器输 出旋转因子的地址情况 控 制和地 址产 生模块 的仿 真结果 如图5所示 , 其中sel代表 开关 控制 , a d d r 代表 产生 的地址 . 2 0 1 0年第9期 总第320图5控制和地址产生模块的仿 真结果3.2蝶形运算模 块 蝶算模块 由一 个 复数 加法器,一个复数减法器和一个旋转 因子 的复数乘 法器 构成 , 如图6所示 . 图6蝶形运算单元旋转 因子 乘法 器通常由4次 实数 乘法和2次 加/ 减法 运算 实现 , 但 因为 C O S 和sin的值 可 以预 先存储 , 通 过下 面 的算 法[ 4 可 以简化 复数 乘法器 : ( 1 )存 储如 下三个 系数 : C, C+ S, C— S ( 2 )计算 : E — X—y和Z:C*E— C*( X—y) ( 3 )用R一(C— S)*y+ Z, J一(C+ S )*X— Z, 得到需 要 的结 果.这种算法 使用了3次乘 法,1次 加法和2次 减法,但是需要 使用存 储 3个表 的ROM 资源.设计 中数据 的输 人为16位 复数,所以将 旋转因子 c o s ( 2 忌7c/N),sin(2五7c/N) 量化成带符号数的16位 二 进制数后 , 存储 到ROM 中,由于值域 不同,需要注意C+S 和C—S的表要 比 C表 多1位精度 . 运算 后的结果需要除以量化时乘以的倍数16b0111111111111111.具 体实现时由于除法运算在FPGA器件需要 消耗较多 的资源 , 设计中采用二进 制数移 位的方法来实 现除 法运 算 .为 了防止 数据 溢出,设计 对输出结 果除以2.图7为 蝶形运算模块的RTL级 结 构图 . 图7蝶形运算模块的 R TL结构图 3 . 3 倒序输出模 块 由频 域抽 取 的基一 2算法可知,运算结果需要倒序输出.可 以先将结果存储到RAM 中, 然后使用0~ 2 5 5的二进 制 数倒 序 产生 RAM 读取地址 , 依 次将 结果 读出,其中实现 一个 8位二 进制 数倒 序 的算 法如 下:(1)将 8位数 字 的相邻两 位交换 位置 ; ( 2 )将相 邻 的两位看 作1组,相邻两组 交换 位置 ; ( 3 )将相邻的 4位看作 1 组,相邻两组交换位置. 经过这 样 的交换位 置后 , 输 出即为 原来 8位二进 制数的倒 序.举例对 于 8位二 进制数10110110来 说,第一次交换位置 的结 果是01111001,第二次交换位置的结 果是11010110,最后 交换位置的结果是O1101101.可见 正 好是 原来 数字 的倒 序.另外 , 由于设计 的是 两路数据同时写 入,一路数据 读出,所以读取 的频 率是 写入频 率的2倍 , 使用 P L L实 现原始时钟的二倍频 , 用来读取 R AM.倒序模块仿真 结果 如图8所示 . 图8倒序模块仿真结果最终生 成的FFT处 理器模 块 图如 图 9所示 . 图9生成的FFT 处理 器模 块4仿真结 果各级间数 据 时序情 况如 图1O所示,设计的FFT处 理器仿真结果如图 1 1 所示.采用一路阶梯递增信号和 另一 路XXX X信 号进 行仿 真,通过 与Ma t l a b计算 结果 进行 对比,结果 基本 一致,可以满 足 系统 要求.系 统总的延 时 由延时 最大 的第一 级决 定,为第 一级 运算 的延 时 加上 倒序输 出的延 时,总共 是(256+1 2 8 ) *c l k , 相 对于 一般流水 线结构 ( 2 5 6 *读 人周 期+7*1 2 8 *蝶 算周 期+1 2 8 *读 人周期 ) , 系统延 时大 为减少 . 通过仿真可知, 系统最大频率由蝶形运算模块的最 大工作频率决定 .使用 Qu a r t u s I I 软件时序仿真后 , 得 到处理 器 的工作频 率为72MHz . 1 7 5 郝小龙等 : 基于 F P GA的移位寄存器流水线结构 F F T处理器设计与实现 图1O各级间两路 数据时序 情况图11FFT处理器仿 真结果5结语通过采用移位寄存器流水线结构, 可以有效地提高 F F T处理器中蝶形运算单元 的效率 , 减少寄存 器的使 用数量, 并且简化了地址控制 , 提高处理器 的工作频率, 具有 良好 的 可扩 展性,同时可以实现两 路数据的同时输入 , 从而增 大 了一倍 的数据 吞吐 量 .对 于工作 频率 要 求较 高,数据吞 吐量较 大,尤其对于需 要两路数 据输 入 的场合 , 比如 两天线的MI MO- OF D M 系统,具有很大的实用 价值 . 参考文献[13崔新瑞 , 张捷 , 张晶 , 等. O F DM 系统原理 及仿 真实现[ J ] . 信 息安全与通信保密 , 2 0 0 7 ( 1 2 ) : 6 8 - 6 9 . [ 2 ]丁玉美 , 高西全. 数字信号处理 [ M] . 西安:西安电子科技大 学 出版 社,2001.[3]戴明桢. 数 字信号处 理 的硬件实 现[ M] . 北京 : 航空 工业 出版社,1998.[41Uw e Me y e r - B a e s e . 数字信号处理的 F P G A 实现[ M] . 刘凌 , 译. 北京 : 清华 大学 出版社 , 2 0 0 2 . [ 5 ]S a mi r P a l n i t k a r . Ve r i l o g HD L数字 设计 与综 合[M] . 夏宇 闻,胡燕祥 , 刁岚松 , 译. 北京 : 电子工业 出版社 , 2 0 0 4 . [ 6 ]尹长川 , 罗涛,乐光 新. 多载 波 宽带 无线 通信 技术[ M] . 北京:北京邮 电大学出版社 , 2 0 0 4 . I - 7 ]李小进 , 初建 民, 赖宗声 , 等. 高速基 2 F F T处理器 的结构设 计与 F P G A实现[ J ] . 电路与系统学报 , 2 0 0 5 , 1 0 ( 5 ) : 4 9 — 5 3 . [ 8 ]余景华 , 郭 亨群. OF D M 系统中64点 F F T的FPGA设 计[J].通信技术 , 2 0 0 8 ( 1 2 ) : 1 0 9 一ii1.[9]王诚 , 吴 继华. Al t e r a F P GA/ C P L D设计 ( 基础 篇) [ M] . 北京:人民邮 电出版社 , 2 0 0 5 . [ 1 O ]Al t e r a C o r p r a t i o n . C y c l o n e I I d a t a s h e e t [ M] .US A:A l t e r a , · Co r p r a t i o n,20 06 . 作者简介 :郝小龙 男, 1 9 8 3年 出生 , 内蒙古 自治区鄂 尔多斯人 , 硕士研究生 .主要研 究方向为微 波通信 、 应用微波技 术. 韦高男, 1 9 6 3年 出生 , 山东单县人 , 教授 , 博士生导师.主要研 究方向为电磁计算 、 微 波测量 、 天线理论 与设计 . 刘娜女,1984年 出生 , 陕西 渭 南人 , 硕 士研 究生.主 要研究方向为天线理论 与设 计.(上接第171页) 参考文献[1]程钧 , 李信之. 高精度 轴角编码 器的多极旋 变选 用及结构 精 度设计口] . 电子机械工程 , 2 0 0 1 ( 5 ) : 8 - 1 0 . [ 2 ]刘华伟 , 肖汉. 基于HP I 接 口的导航计算机旋变信号采集 电 路设计 [ J ] . 弹箭 与制 导学报 , 2 0 0 4 ( 6 ) : 3 9 2 — 3 9 4 . E 3 ] 尚超 , 王淦泉 , 陈桂林. 跟踪型 R D C载波相位误 差和输入 噪 声的分析及应用 [ A ] . 高精度几何量光 电测量与校准技术研 讨 会论 文集 , 2 0 0 8 . [ 4 ]徐振刚. 基于龙伯格观测器 的Pd]C磁极 位置检测方 法[ J ] . 微特电机 , 2 0 0 7 ( 8 ) : 6 - 7 . [ 5 ] 黄仁欣. D S P 技术及应用[M] .北京:电子工业出版社,2007.[6]李声晋. 一种旋转变压器—— R D C测角系 统的数字标定及 补偿方法 [ J ] . 微特电机 , 2 0 0 7 ( 6 ) : 2 6 — 2 8 . [ 7 ]庞军. 基 于电压行波 的输 电线路故 障定位方 法研究 [ D ] . 重庆:重庆 大学 , 2 0 0 9 . [ 8 ]周婧婧. 基于 故障树 分析 的电力变 压器可 靠性评估 方法研 究[ D] . 重庆:重庆大学 , 2 0 0 9 . [ 9 ] 曲振江. R D C缓 冲电路 的技术分析[ J ] . 微特 电机 , 2 0 0 7 ( 6 ) : 2 6 — 2 8. [ 1 O ]方磊. 电力电缆故 障定位 方 法研 究 及在 线 检测装 置实现[D] . 长沙 : 长沙理工大学 , 2 0 0 9 . 作者简 介:王军平 男, 1 9 7 0年 出生 , 浙江建德人 , 在读博 士研 究生, 高级工程师.研 究方向为机 电一体化设计及控 制. 尚超男, 1 9 8 1年 出生 , 河南汝州人 , 博士, 工程师 .研 究方向为控制 电路设计 . l 7 6