FPGA实现高速FFT处理器的设计

文章编号 :1001 - 893X(2003) 02 - 0074 - 05 FPGA 实现高速 FFT处理器的 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 3Ξ 韩　颖 ,王　旭 ,吴嗣亮 (北京理工大学电子 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 系 ,北京 100081) 摘 　要 :介绍了采用 Xilinx 公司的 Virtex - II系列 FPGA 设计高速 FFT处理器的实现方法及技巧。充 分利用 Virtex - II芯片的硬件资源 ,减少复杂逻辑 ,采用流水方式对复数数据实现了加窗、FFT、求模 平方三种运算。整个设计采用流水与并行方式尽量避免瓶颈的出现 ,提高系统时钟频率 ,达到高速 处理。实验表明此处理器既有专用 ASIC 电路的快速性 ,又有 DSP 器件的灵活性的特点 ,适合用于高 速数字信号处理。 关键词 :数字信号处理 ;现场可编程门阵列 ;快速傅里叶变换 ;加窗运算 ;求模平方运算 中图分类号 :TN911172 　　文献标识码 :A The Design of High - speed FFT Processors Based on FPGA HAN Ying , WANG Xu , WU Si - liang (Department of Electronic Engineering , Beijing Institute of Technology , Beijing 100081 ,China) Abstract :The implementation method and skill of a design for high - speed FFT processor based on Xilinx Vir2 tex - II FPGA is introduced in this paper. To use sufficiently hardware resource of the Virtex - II FPGA and to reduce the complex logic , the serial mode is adopted to put the complex data into three operations which include multiplying window ,performing FFT , computing module - square. By using the serial and parallel architecture in the whole design ,the bottleneck is avoided ,the frequency of the system clock is increased and high - speed performance is achieved. The experiment proves that the processor has not only the high - speed performance of ASIC circuit ,but also the flexibility of the DSP and it is suitable for high - speed digital signal processing. Key words :Digital singnal processing ;FPGA ;FFT;Multiplying window ;Computing module - square 一、引　　言 在高速数字信号处理中 ,FFT 处理器的处理速 度和精度是最主要的性能指标 ,但定点算法和浮点 算法使设计在速度与精度之间存在矛盾 ,针对实际 的信号处理中需要的高速度与高精度的要求 ,本设 计采用在灵活性和扩展性方面很强的 FPGA(现场可 编程门阵列) 实现 FFT(快速傅里叶变换) 运算。由 于 FPGA 器件速度快、密度高、功耗低、可配置性强 , 现已在许多领域得到广泛的应用。本设计可以用 Xilinx公司近年推出的 Virtex - II 系列完成 ,除了具 有 FPGA 在线可编程的特点外 ,Virtex - II 系列还有 4 个主要特点[1 ]使它适合实现高速 FFT运算 : (1) 具 有大量的片内同步寄存器、锁存器、查找表、多路选 择器等灵活的逻辑资源 ,便于实现流水结构以及逻 辑运算 ; (2) 内部时钟速度可达 420 MHz ,且带有时 钟管理块 DCM 和专用的时钟信号线 ,可以解决时钟 扭曲问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ; (3) 有为算术运算而特别设计的硬件结 构 ,如 18 bit ×18 bit 嵌入式高速乘法器、快速进位逻 ·47· Ξ 收稿日期 :2003 - 01 - 17 　电讯技术　2003 年第 2 期 　　　　　　　　　　　研究与开发RESEARCH & DEVELOPMENT © 1995-2003 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 辑链等 ; (4) 具有大量的存取速度很快的内部块状 RAM ,并且可以根据用户定义决定它的容量、是否双 口等等 ,这不但有利于简化设计 ,减少外围电路 ,而 且有利于提高系统性能。可见这一系列的 FPGA 适 合实现高速 FFT 运算这种需要乘法器、大量块 RAM、寄存器的设计。 针对高速与高精度的处理要求 ,采用高性能的 Virtex - II 系列 FPGA 设计的处理器具有以下 3 个特 点 : (1) 利用内部块 RAM 存取速度快的性能特点采 用“双蝶形”结构并行处理 ,使处理速度提高一倍 ; (2)采用了块浮点算法不仅可以解决精度问题 ,且硬 件实现的结构和控制都很简单 ; (3) 利用 FPGA 具有 的可以进行模块化的设计、易于扩展的特点 ,此处理 器还能在对数据实现 FFT运算前对数据进行去直流 分量、加窗处理 ,FFT 运算后进行求模平方运算 ,这 几种处理在数字信号处理中常常是必要的 ,因此在 一个芯片内实现是有意义的。 二、FFT算法的具体结构 由于对数据的去直流分量处理、加窗运算、求模 平方运算的算法实现相对简单 ,而实现 FFT 运算则 比较复杂 ,所以下面对实现 FFT运算的 FFT运算模 块的实现结构及原理进行详细的说明。 1. 递归结构与并行结构的结合 实现 FFT运算的结构如图 1 所示。 图 1 　FFT的递归结构 由图 1 可见这一结构仅由一个“双蝶形运算单 元”作为整体的运算单元 ,每级蝶形运算按递归方式 运行 ,递归结构实现起来占用资源少 ,而且控制简 单。由于处理 512 点数据 ,所以采用基 - 2 算法 ,同 时为了提高处理速度 ,本设计采用 2 个“基 - 2 蝶形 单元”并行处理 ,它的吞吐率是一个“基 - 2 蝶形单 元”的 2 倍 ,也等于一个“基 - 4 蝶形单元”的吞吐 率[2 ] 。此外蝶形单元内部采用流水与并行方式 ,能 有效减小运算时钟的周期 ,提高系统的整体速度。 2. 蝶形单元结构 按时间抽取 (DIT) 的基 - 2 蝶形运算算法可以 表示为[3 ] X ( n) = x ( n) + x ( n + 2 p- s) Wn2 s X ( n + 2 p- s) 2x ( n) - x ( n + 2 p- s) Wn2 s (1) 　　其中 s 是蝶形运算单元的级数 ,n = b2·2s + b1 ,s = 1 ,2 , ⋯,p ,b1 取遍 0 ,1 , ⋯,2s - 1 - 1 ,b2 取遍 0 ,1 , ⋯,2p - s - 1。 上式是 FPGA 实现基 - 2 FFT算法的基础 ,根据 它不仅可以构建蝶形单元框图 ,而且可以得出抽取 数据与相应的旋转因子的地址。由上式可见实现一 个基 - 2 蝶形运算需一次复乘 ,两次复加。采用改 进的蝶形单元可以实现用 2 个实数乘法器在 2 个节 拍内完成复乘 ,乘法器采用片内专门乘法器 ,不仅减 小了流水深度 ,而且提高了处理速度。图 2 给出了 改进型基 - 2 蝶形运算框图[2 ] 。 图 2 　基 - 2 蝶形单元结构图 图 2 中主要由寄存器、乘法器、加法器、延时器 组成 ,其中延时器是由 4 个寄存器搭建的。图中未 标明时钟信号的寄存器的时钟为 CLK。 蝶形单元工作过程如下 :复数数据按 x ( n + 2p - s) ,x (n) 顺序进入数据口 ,旋转因子按 Wn2sR ,Wn2sI 顺序进入系数口 ,Phi1 控制 x (n + 2p - s) 与旋转因子 进行复乘 ,由式 (1)可见 x (n) 不参加复乘运算 ,所以 由 Phi2 控制直接经延时单元到达加法器。 本结构简单紧凑 ,流水与并行方式的应用避免 了瓶颈出现 ,达到了高速处理的需求。 3. 双蝶形运算单元 双蝶形单元是由 2 个结构相同的蝶形单元组 成 ,双蝶形单元接口图见图 3。CLK 与 CLK-180 必 须有 180°的相位差 ,CLK 与 CLK-180 的频率是系统 时钟频率 ,且它们的频率是地址单元及存储器的时 钟 CLKX2 的频率的二分之一。只有这样 ,数据才能 ·57· 　电讯技术　2003 年第 2 期 　　　　　　　　　　　研究与开发RESEARCH & DEVELOPMENT © 1995-2003 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 被正确地送入相对应的蝶形单元中。 图 3 　双蝶形运算单元的接口方框图 4. 存储单元 利用 FPGA 内含大量块 RAM 以及 FFT 运算是 原位运算的特点 ,可以采用 TMS(Triple - Memory - Space) 模式对数据进行存储 ,这种模式有 3 组块 RAM存取单元 :输入数据存取单元 X、中间数据存 取单元 Y和输出数据存取单元 Z。当中间处理数据 存取于 Y时 ,X可以接受片外新数据 ,而 Z始终存取 最后一级处理结果。TMS结构的详细的配置图如图 4 所示。TMS模式可以实现在处理当前一组数据的 同时将下一组片外数据输入到片内块 RAM 中 ,从而 保证数据及时的供给运算单元 ,没有因等待数据的 I/ O 操作而浪费计算周期 ,提高了整体处理速度。 TMS方式放宽了对 I/ O 操作速度的要求 ,使外围电 路可以不必工作于 FPGA 系统时钟 ,从而降低了整 个系统造价。 图 4 　内部 RAM配置连接图 　　此外 ,Virtex - II大量块 RAM 也使窗函数及蝶形 运算的旋转因子可以直接存于片内块 RAM ,这样不 仅减少了外围电路 ,而且也有利于运算速度的提高。 5. 地址单元 地址产生及控制单元负责产生所有的 RAM , 包 括片外 DPRAM及片内的块 RAM 的接口信号和控制 运算单元工作的信号。这一部分主要由计数器、地 址线交换器、寄存器和延时器组成。FFT 运算是混 序算法 ,故 FFT运算的地址产生是整个算法的关键。 另外由于采用双蝶形单元并行处理 ,所以这一运算 单元的数据的读写时钟频率必须是系统时钟频率的 2 倍。9 级蝶形运算地址线变换器的连接图如图 5 和图 6 所示。 图 5 　FFT数据地址产生单元 ·67· 　电讯技术　2003 年第 2 期 　　　　　　　　　　　研究与开发RESEARCH & DEVELOPMENT © 1995-2003 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 图 6 　旋转因子地址产生单元 其中 count 表示 9 位计数器的输出并将低 2 位 调换得的 9 位数据。为了使读者清楚 ,表 1 对第一 级蝶形运算的前 4 个数据的地址产生做了说明。 表 1 　用双蝶形单元进行第一级蝶算的前 4 个数据 的抽取地址 计数器 低两位调换(count) 低位取反 数据地址 (data - address) 旋转因子 地址 000000000 000000000 000000001 100000000 000000000 000000001 000000010 000000011 100000001 000000000 000000010 000000001 000000000 000000000 000000000 000000011 000000011 000000010 000000001 000000000 需注意的是 FFT变换结果是按二进制逆序存于 RAM Z的 ,读取结果地址单元需有逆序处理。此外 , 由于 FFT变换属于原位运算 ,蝶形运算的写地址与 抽取数据的地址完全相同。 由 Active - HDL 软件仿真的蝶形运算单元的数 据读写地址及控制信号的部分时序图如图 7 所示。 读操作是在信号 ENB 有效时开始 ,写操作是在信号 ENA/ WEA 有效时开始。 图 7 　双蝶形运算单元的第一级蝶形运算数据的读写地址及控制信号时序图 6. 块浮点运算单元 除了以上各主要单元外 , FFT 运算模块还有一 个重要的单元 ———块浮点防溢出单元。从设计复杂 性、运算精度与运算速度方面折中考虑 ,本设计采用 了参考文献 [ 4 ]提出的块浮点防溢出算法。这一算 法应用于本设计的主要思路是在蝶算过程中采用扩 充一位符号位的补码加法器 ,以保证运算过程中不 发生溢出 ,这样基 - 2 蝶算输出数据用 18 位表示。 由有限状态机构成的溢出 检测 工程第三方检测合同工程防雷检测合同植筋拉拔检测方案传感器技术课后答案检测机构通用要求培训 单元对蝶形运算输出 数据的高三位进行溢出检测 ,蝶形运算结果中绝对 值最大的那个数的高三位决定了该级蝶形运算完成 后有限状态机的状态 ,由此可确定下一级蝶算时如 何从 18 位数据中选择 16 位数据进入蝶形单元 ,并 有移位累加单元实现对每一级移位次数的累加 ,以 便给出 FFT运算结束后总的移位次数 ,由此可确定 最后结果的指数位。蝶形输出数据的高三位与“溢 出检测”的状态之间关系分为以下 3 种情况 : (1) 000 (或 111) (无溢出 ,状态 S1) ; (2) 001 (或 110) (1 比特溢出 ,状态 S2) ; (3) 01x(或 10x) (2 比特溢出 ,状态 S3) 。 状态转换图如图 8 所示。 图 8 　溢出检测单元状态图 实验表明这种算法实现简单 ,适合硬件实现 ,可 以最大限度地降低截断误差的影响。 三、系统总体结构 综上 FFT运算模块的各主要单元的设计 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 得 出系统总体框图如图 9 所示。 系统工作过程如下 :原始数据一边顺序写入 FP2 GA 芯片内部的“原始数据存储器 X”,一边进入“求 均值单元”进行累加求和 ,并将 512 点数据的累加结 果右移 9 位后得到 512 点数据的平均值 ,然后“加窗 地址单元”开始工作 ,它负责产生加窗运算数据的地 址给“原始数据存储器 X”,从存储器 X 中读出的数 据首先经减法器 ,将均值减掉 ,以实现去直流分量的 处理 ,然后进入“加窗运算单元”进行加窗运算 ,加窗 的结果写入“中间数据存储器 Y”,加窗运算结束后 , ·77· 　电讯技术　2003 年第 2 期 　　　　　　　　　　　研究与开发RESEARCH & DEVELOPMENT © 1995-2003 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. “加窗地址单元”唤醒“FFT 地址单元”,它负责产生 FFT运算数据及旋转因子地址 ,并将 FFT 结果存于 “FFT结果存储器 Z”,然后唤醒“求模平方地址单元” 读取 FFT处理结果进行求模平方运算 ,模平方结果 存于“模平方结果存储器”。 图 9 　系统方框图 四、性能分析 1. 处理精度 输入信号为无噪复指数信号 cos ( 2πi51230) + j × sin ( 2πi51230) ,所加的窗函数是汉明窗 ,处理器得到的 功率谱值作为试验值 ,同时将采用双精度浮点运算 得到的功率谱值作为真值 ,2 种结果的比较图如图 10 所示 ,图中“+ ”代表真值 ,“o”代表试验值。 图 10 　无噪复指数信号的功率谱 (实验值和真值对比图) 谱图是归一化谱图。可见 ,采用块浮点算法具 有很高的运算精度。 2. 处理速度 系统时钟采用 50 MHz ,FFT运算的内部块 RAM 读写时钟及地址单元工作时钟达 100 MHz 时 ,每组 执行时间 (从 RESET 有效到模平方结果全部输出结 束)为 85μs ,达到了设计高速的要求。 五、结束语 本文给出的方案经过实验验证能达到设计的要 求 ,如果用多个蝶形单元并行处理 ,控制实现比较复 杂 ,但处理速度可以有更大的提高。实验表明 ,随着 可编程器件规模、速度的不断提高 ,采用 FPGA 实现 高速数字信号处理的算法具有可行性和优越性。 参 　考 　文 　献 [1 ] 　Xilinx Inc. Virtex - II 1. 5V Field - Programmable Gate Ar2 rays datasheet[ S] , 2002. [2 ] 　Liu zhen - yu ,Han yue - qiu. dual butterfly matched filter A2 SIC design[J ] . Chinese Journal of Electronics ,2001 ,10(4) : 563～566. [3 ] 　王世一. 数字信号处理 [ M] . 北京理工大学出版社 , 1997. [4 ] 　刘朝晖 ,韩月秋 . 专用 FFT处理器设计及 CFAR检测器 脉动阵列的研究 (博士学位论文) [D ] . 北京理工大学 , 1999. [5 ] 　李广军 ,孟宪元 . 可编程 ASIC 设计及应用 [M] . 电子科 技大学出版社 ,2000. 作者简介 : 韩　颖 (1977 - ) ,女 ,吉林人 ,硕士研究生 ,主要研究方 向为高速实时数字信号处理技术 ; 王 　旭 (1974 - ) ,男 ,山东人 ,博士研究生 ,讲师 ,主要研 究方向为高速实时数字信号处理技术 ; 吴嗣亮 (1964 - ) ,男 ,安徽人 ,教授 ,博士生导师 ,中国电子 学会高级会员 ,曾获 4 项部科技进步奖 ,发表论文 30 余篇。 ·87· 　电讯技术　2003 年第 2 期 　　　　　　　　　　　研究与开发RESEARCH & DEVELOPMENT © 1995-2003 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.