基于FPGA的FFT算法硬件实现

a叶投2010年第23卷第11期 Electronic Sci．& Tech．／Nov．15．2010 基于 FPGA的 FF-r算法硬件实现 童庆为，陈建春 (西安电子科技大学 电子 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 学院，陕西 西安 710071) 摘 要 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 了一种基于FPGA的1 024点16位 FFT算法，采用了基4蝶形算法和流水线处理方式，提高了系统 的处理速度，改善了系统的性能。提出了先进行前一级4点蝶形运算，再进行本级与旋转因子复乘运算的结构，合理 地利用了硬件资源。对 系统划分的各个模块使用Verilog HDL进行编码设计。对整个系统整合后的代码进行功能验证 之后 ，采用Quaaus II与 Matlab进行联合仿真，其结果是一致的。该系统既有 DSP器件实现的灵活性又有专用 FFTr芯 片实现的高速数据吞吐能力，在数字信号处理领域有广泛应用。 关键词 现场可编程门阵列；快速傅立叶变换；基4蝶形运算；硬件描述语言 中图分类号 TP301．6 文献标识码 A 文章编号 1007—7820(2010)11—113—04 Hardware Implementation of FFT Algorithm Based on FPGA Tong Qingwei，Chen Jianchun (School of Electronic Engineering，Xidian University，Xi’an 710071，China) Abstract A 1024-point FPGA—based 16-bit FFT algorithm is designed which is using the Radix-4 butterfly al- gorithm and pipeline operations to enhance the processing speed and improve the performance．A structure that the butterfly operation of the first level is made before the complex multiplication of the rotation factor of the second level is proposed，which is using of the hardware resources reasonably．The system is divided into several modules in Veril． og HDL．After testing the function of system，the results ofjoint simulation of Quartus II and Matlab is consistent．The system not only achieves the flexibility of DSP devices but also has the high-speed data throughput of dedicated FFT chips．This algorithm can be widely used in the field of digital sign al processing． Keywords FPGA；F丌 ；radix-4 butterfly algorithm；Verilog HDL FFTr(快速傅里叶变换)是一种非常重要的算法， 在信号处理、图像处理、生物信息学、计算物理、应 用数学等方面都有着广泛的应用。在高速数字信号处 理中，FF]r的处理速度往往是整个系统设计性能的关 键所在。FPGA(现场可编程门阵列)是一种具有大规模 可编程门阵列的器件，不仅具有 ASIC(专用集成电路) 快速的特点，更具有很好的系统实现的灵活性。基于 FPGA的设计可以满足实时数字信号处理的 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 ，在市 场竞争中具有很大的优势_】 J。因此，FPGA为高速 FfTr算法的实现提供了一个很好的平台 J。 1 FF．r算法的硬件实现 1．1 系统框图 本设计利用流水线技术来提高系统的性能，系统 框图，如图 1所示。其中，地址产生单元生成 RAM 收稿 日期：2009—12．21 作者简介：童庆为(1986一)，男，硕士研 究生。研究方向： 信号处理。 读写地址，写使能信号以及相关模块的启动、控制信 号，是系统的控制核心；4点蝶形运算单元的最后一 级输出不是顺序的；旋转因子产生单元生成复乘运算 中的旋转因子的角度数据；旋转因子 ROM中预置了 每一级运算中所需的旋转因子。 输入数据I实部RAM 虚部RAM 写 地 址 读 地 址 旋转因子产生单元 lel 4点蝶形运算单元 ，J 广] l Q 最后一 级输出 霎 旋转因子实部ROM I旋转因子虚部R0M 图 1 系统框 图 113 』 地生 一 童庆为，等：基于FPGA的FfTr算法硬件实现 在 FPGA设计中，为提高系统的运行速度，而将 指令分为几个子操作，每个子操作由不同的单元完 成，这样，每一级的电路结构得到简化，从而减少输 入到输出间的电路延时，在较小的时钟周期内就能够 完成这一级的电路功能。在下一个时钟周期到来时， 将前一级的结果锁存为该级电路的输人，这样逐级锁 存，由最后一级完成最终结果的输出。也就是说，流 水线技术是将待处理的任务分解为相互有关而又相互 独立、可以顺序执行的子任务来逐步实现 。本设计 中，4点蝶形运算单元、旋转因子复乘模块以及最后 的精度截取模块采用流水线技术来处理。 1．2 基4蝶形运算算法原理 ，(0) X。(1) X，(2) X (3) 1 1 1 -j 1 ——1 1 J x(o)wo X(2、 (1) (3) 式(1)为基4蝶形运算单元的一般 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 达式 j，其 中，W=e ，Ⅳ为 FfTr运算的点数，本设计中为 1 024，P为旋转因子 的相位角，其规律将在 1．4 节讨论。X(0)、X(1)、X(2)、 (3)为原始数据， 顺序输入RAM后蝶形倒序输出，与旋转因子复乘再 进行 4点蝶形运算，而 X (0)、X (1)、 (2)、X (3)即为第 1级蝶形运算的结果。此时 RAM存储的 原始数据已经清空，将第 1级蝶形运算结果再存回 RAM中，按照一定的地址输出后，与第 2级的旋转 因子复乘、4点蝶形运算，得到第 2级蝶形运算结 果，依此类推。由于蝶形运算为同址操作，所以第 2 级的RAM写地址即为第一级的RAM读地址，每一级 的RAM读地址规律将在 1．3节中讨论 J。 1 024点的基 4一FFT共需要 5级蝶形运算 ，每 级需要计算 256个蝶形，其传统实现框 图如图 2 所示 。 固 ⋯．睁 第一级 第五级 图2 传统 F 硬件 实现框 图 考虑到第一级蝶形运算不需要旋转因子，所以第 一 级的旋转因子复乘模块可以省略，但本设计的硬件 结构需要循环利用，一般情况下，可以对第一级数据 进行 ×1运算，再进行 4点蝶形运算。不过，考虑到 我们并不关心每一级蝶形运算后的结果，本文提出了 一 种蝶形运算的新结构：即先进行前一级的4点蝶形 114 运算，再进行本级的与旋转因子复乘运算，如图3 所示。 ⋯ -．唾匣鹾 第一级 第四级 第五级 图 3 本设计的 FF1 硬件 实现框图 可以看出，图3减少了一个旋转因子复乘模块， 不但节约了一次乘法运算时间，也省略了第一级旋转 因子，更好地利用了硬件结构。 首先，在 Quartus lI环境中对 4点蝶形运算时序 仿真，采用流水线设计，连续输入连续输出，仿真结 果如图4所示。 一 n ． ．：尸 ： 口 ：．『=[． 厂_] 广] r_1厂1一 —P■_．1 i ： ： ： ； 匣 I — ： 题垂 一 碡 f； ： r 0 固 口 0 X x‘tB9 X一{6 X一1B8 X 一 ： ： 口 匾Iou ：j： 01 1 ； ! !跫X 墼目X￡丝 扁 0oIl1 ： 0； ： i 鼾氯 面 酾丽 币 ； ： i l l； ： 图4 四点蝶 形运 算仿 真结果 由图4可以看出，输出比输入延时6个时钟，这 在系统的控制核心地址产生单元的设计中需要考 虑到。 1．3 地址产生与时序控制 对于 1 024点基4 FFr运算，需要5级蝶形运算， 每一级运算都要有写地址和读地址 ，根据 FFYr同址 运算的特点可知，当前的写地址即是上一级蝶形运算 的读地址。因此完成 F 运算需要设计 6级 RAM地 址。其中第 1级的写地址即是数据输入的顺序地址， 不予讨论。最后一级读地址为数据正序输出所需的地 址。其余 4级为 1 024点数据对应的F丌 蝶形运算。 第一级读取节点地址的顺序应该是：(0，256， 512，768)，(1，257，513，769)，⋯⋯，(255， 511，767，1 023)。易观察其读地址 的规律如下： 设读取次序的二进制编码为 bit[9：0]；则读地址的 二进制编码为}bit[1：0]，bit[9：2]}，并且依次可 以推出第 2、3、4级的读地址二进制编码分别为 {bit[9：8]，bit[1：0]，bit[7：2]}，{bit[9：6]， bit[1：0]，bit[5：2]}、{bit[9：4]，bit[1：0]， bit[3：2]}，而最后一级输出数据的地址二进制编码 则为：{bit[1：0]，bit[3：2]，bit[5：4]，bit[7：6]， bit[9：8]} 。图5给出了第 1级读地址和第2级 读地址的部分数据，也可以看出第2级的写地址即 是第 1级的读地址。 童庆为，等：P2P网络模式下的DRM体系架构 图 r~addr 圉 waddr 图5 RAM读写地址的部分数据 图1中的地址产生单元作为系统的控制核心，不 仅要生成每一级的RAM读写地址，还要产生RAM写 使能信号、输出有效信号以及4点蝶形运算单元和旋 转因子产生单元的启动信号，由于时序电路还需要考 虑器件延时，例如上文提到的4点蝶形运算输出比输 入延时6个时钟，以及 RAM存取数据输出比输入延 时1个时钟，这些都需要在控制核心中考虑到。 1．4 旋转因子产生 对于 1 024点 FFYr蝶形运算，需要 1 024个旋转 角度(即2盯的 1 024等份)，其中第一级不需要复乘 运算，第6级只是将数据进行整序没有运算单元，其 他4级都需要旋转因子。本设计采用将旋转因子预置 于 ROM中，通过查找表 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 得出每一级运算的所需 的旋转因子 。根据旋转因子的可约性，后几级运 算所需的旋转因子都可以在第一级运算的旋转因子中 找到，因此无需另外存储。旋转因子在 ROM中的存 储规律是：旋转因子相位角 P处存储旋转因子 W= e -j2 *p／N 。 定义一个 10 bit的计数器 count[9：0]，则 第 2、3、4、5级 ROM的相位角规律按照 Verilog语 法可表示为 {2'bo0，count[9：8]，6b’000000}：l：{count[1：0]}， {2'b00，count[7：6]，count[9：8]，4b'O000} {count[1：0]}， {2'b00，count[5：4]，count[7：6]，count[9：8]， 2b’00} {count[1：0]}， {2'boO，count[3：2]，count[5：4]，count[7：6]， count[9：8]} {count[1：0]}。 为了节省资源，本设计只在 ROM单元中存储了 前 256个旋转因子数据，即第一象限因子 1 024， 。M ， ⋯ ⋯ ， 其余象限的因子可通过象限转换 后得到，这样就大大节省了存储单元的硬件资源。图 6为旋转因子产生单元在 Quartus II环境中仿真结果的 部分数据。 图6 旋转因子产生单元仿真结果的部分数据 2 系统仿真结果 输入数据为 5=1 024 X COS(2盯xf in×t)，其中 f in=50 M，F =80 MHz，／7,=40，t=0：1／F ：(rt一 1)／F,，利用 Quartus 11软件对系统在 100 MHz的时钟 环境下进行了仿真，将仿真输出结果转换成 tbl文件 并利用Matlab软件读取后，得到如图7所示的频谱数 据图(实部数据部分)。 图7 FPGA仿真输出的实部数据 00 00 图8 Matlab仿 真输 出的买邵数据 图 8所示为 Matlab自带 F 函数对于输入相同 1 024点数 据 的 FFT计算 结果 (同样 为实 部数 据 部分)。 通过比较可以看到，本设计的仿真结果与Matlab 的仿真结果基本一致，可以正确高效地计算出 1 024 点FFT数据。 3 结束语 本设计全部由 Verilog HDL语言实现，采用 自顶 向下的设计方法，完成了一种基于 FPGA的 1 024点 l6位 F订 算法，共需要5级运算，每级需要计算 256 个蝶形。提出了将蝶形运算先进行前一级的蝶形加减 运算，再进行本级的与旋转因子复乘运算的结构。由 前所述，平均每个蝶形运算需要4个时钟周期，所以 理论上完成 1 024点 FFTr的总时钟周期为 N=256× 4×5=5 120；假设使用的时钟为100 MHz，那么将耗 时T=5 120×(1／100)=51．2 p,s，这与仿真结果 51．32 s基本一致。 (下转第 122页) 樊康旗，等：空间等离子体鞘层的时域特性研究 其工程计算[J]．环境技术，1999，59(2)：9—13． 朱光武，李保权．空间环境对航天器的影响及其对策研 究[J]．上海航天，2002(5)：9—16． 高炳荣，郝永强，焦维新．用盟特卡罗方法研究卫星内 部带电问题 [J]．空 间科学学报，2004，24(4)：289 — 294． 叶宗海．空间环境对航天活动的影响[J]．载人航天， 1997(1)：52—6O． 叶宗海．“神舟”四号中的空间环境研究 [J]．物理， 2004，33(1)：40—48． Grard R，Knott K，Pedersen． Spacecraft Charging Effects [J]．Space Science Reviews，1983，34(3)：289—304． Henry B C，Albe~ C W． Spacecraft Charging—An Update (上接第115页) 参考文献 Sansaloni T，Perez—pascual A，Vails J． Area—emcient FPGA—based FFT Processor『J]．Electronics Letters， 2003，39(19)：1369—1370． Shaditalab． Self—so~ing Radix一2 FFT on FPGAs Using Parallel Pipelined Distributed Arithmetic Blocks[J]．IEEE Symposium on FPGAs for Custom Computing Machines， 1998，56(5)：337～338． Yang Z X． Design of a 3780一point IFFT Processor for TDS — OFDM f J 1．IEEE Transactions Broadcast，2002，48 (1)：57—61． 段玉波，刘继新，刘树庆．基于 FPGA的快速傅里叶变 换(F )处理器的设计[J]．自动化技术与应用，2006， (上接第 118页) 分选效果优于PRI变换法。自适应 PRI变换法的分选 精度只与系统的分选精度和输人参数的测量精度有 关，不受人为因素的影响，是一种具有 自适应性的 算法。 3 结束语 自适应 PRI变换法可以有效的分析信号的PRI参 数特征，并且具有较好的分选效果和较高的 PRI估计 精度，它无需根据不同的信号环境人为设定分选参 数，具有良好的自适应性。 参考文献 [1] 梁睿海，吴叶楠，袁乃昌．常用脉冲重复间隔估计算法 122 [J]．IEEE Transaction on Plasma Science，2000，28(6)： 2017—2028． [9] Shu T L，Maurice F T．Aspects of Spacecraft Charging In Sunlight[J]．IEEE Transaction on Plasma Science，2006， 34(5)：2053—2061． [10]刘振兴．太空物理学[M]．哈尔滨：哈尔滨工业大学出 版社 ，2005． [11]毕 德 显．电磁 场 理论 [M]．北 京：电子 工业 出版 社 ，1985． [12]庞永江．地面实验室模拟空间等离子体环境及太阳能电 池片效应初步实验研究[D]．北京：中国科学院空间科 学与应用研究中心，2001． 25(4)：22—24． [5] 丁智泉，张红雨．高速浮点 FfTr处理器的 FPGA实现 [J]．四川理工学院学报：自然科学版，2006，19(1)： 60—63． [6] 刘桂华，傅佑麟，严平．Fn 实时谱分析系统的FPGA 设计和实现[J]．电子技术应用，2005(4)：65—67． [7] 刘朝晖，韩月秋．用FPGA实现FFT的研究[J]．北京 理工大学学报，1999，19(2)：234—238． [8] 韩泽耀，韩雁，郑为民．一种高速实时定点 FFT处理器 的设计[J]．电路与系统学报，2002，7(1)：l8—22． [9] 连冰，宫丰奎，张力，等．基于 FPGA的快速傅里叶变 换[J]．国外电子元器件，2003(12)：26—28． [10]杨靓，黄巾，刘红侠 ，等．一种高效的 FFr处理器地址 快速生成方法[J]．信号处理，2004(3)：251—257． [J]．航空计算技术，2005，35(2)：112—115． Mardia H K． New Technique for the Deinterleaving of Re— petifive Squences[J]．IEE Procedings，1989，136(4)： 149—154． Milojevic D J，Popovie B M．Improved Algorithm for the Deinterleaving of Radar Pulses [J]． IEE Proeedings， 1992，139(1)：98—104． Ken’Ichi Nishiguchi， Masaaki Kobayashi． Improved Algo— rithm for Estimating Pulse Repetition Intervals[J]．IEEE Transaetins on Aerospace and Electronic Systems，2000 (2)：409—421． 赵长虹．重频分选算法与跟踪算法研究[D]．西安：西 安电子科技大学，2003． 1J 1J 1j 1j r rL r} rL ]● ]J 1 j ] J 1 2 3 4 L二J 1j 1J 1J 1j 2 3 4 5 心