一种高性能快速傅里叶变换的硬件设计

沈耀坡， 梁 煜， 张 为

(天津大学 微电子学院，天津 300072)

快速傅里叶变换(Fast Fourier Transform，FFT)作为时域数据变换为频域数据进行分析的快速方法，广泛应用于雷达和数字通信等多种领域中，成为信号处理的一种高效手段．随着无线电技术的高速发展，为了能够实时快速测量和分析信号的变化，需要FFT处理速度更快[1]．由于FFT计算量较大，为了满足实时处理的需要，必须采用硬件电路实现以提升计算速度．因此设计高效的快速傅里叶变换的硬件结构具有重要意义．

近年来，有众多学者对FFT的硬件实现展开了大量研究．文献[2]使用公式变换法将传统复数乘法器中的4个实数乘法器减少为3个，减小了一定的硬件开销，但乘法器关键路径较长而导致FFT整体计算速度提升并不大; 文献[3]使用数字信号处理(Digital Signal Processing，DSP)模块实现复数乘法器单元，计算速度有一定提升，但硬件开销仍然较大; 文献[4]使用正则有符号数(Canonic Signed Digit，CSD)乘法器取代了传统复数乘法器，同时也省去了只读存储器(Read Only Memory，ROM)存储单元，虽然大大节省了硬件开销，但是计算速度仍然不够高，达不到实际应用要求; 文献[5]提出了一种单路延时反馈(Single Delay Feedback，SDF)和单路延时转换(Single Delay Conversion，SDC)相结合的流水线结构，可以时分复用乘法器和加法器，计算速度有很大的提升，但是硬件资源消耗较大．

目前研究多集中于FFT算法构架研究和复数乘法器结构优化方面，而文中利用了FFT旋转因子乘法中一个乘数为常数的特点，提出用常数乘法器替代传统复数乘法器的方法来实现旋转因子相乘．另外，文中还提出一种新型常数乘法器设计方法即系数放大法，通过将旋转因子常系数放大的方法使相应的常数乘法器所需要的加法器数量减少到最低，同时也缩短了关键路径．对比现有其他构架，文中设计的16点SDF结构基22FFT大大减小了硬件资源消耗，提高了计算速度，使硬件效率大大提升．

1 基22SDF结构FFT原理分析

对于FFT算法的实现技术，按数据组合方式可以分为时域抽取和频域抽取，按数据抽取方式可分为基2、基4、基22和基24算法等[6]．其中，基22算法与基4算法具有相同的乘法复杂度，且具有基2算法的蝶形结构，即将基4算法进一步分解成更小的多级基2运算，从而便于硬件实现[7]．在实际应用中，随着对数字通信系统实时性要求的提高，已有多种硬件构架被提出．其中，流水线结构以其高实时性，较强的数据连续处理能力，较高的资源利用率等特性取得了广泛的应用．流水线结构FFT有多种实现方案，最常用的可分为3类: 多路径延时转换结构、单路径延时转换结构和单路径延时反馈结构[8]．文中重点研究基22频域抽取算法与单路径延迟反馈结构．

1.1 基22FFT算法的基本原理

FFT的实质是将较长序列的离散傅里叶变换(Discrete Fourier Transform，DFT)运算逐次分解为较短序列的DFT运算[9]．序列x(n)的DFT定义为

理论分析，式(1a)可以通过基22算法变换为

式(2)为基22算法的蝶形单元运算表达式，由此可以得到基22算法的蝶形结构如图1所示．

图1 基22算法的蝶形结构图2 16点基22SDF FFT的结构图

1.2 基22SDF结构FFT结构

图2给出了16点基22SDF FFT的结构图．共有4个蝶形单元[10]，4个延迟反馈单元，旋转因子存储ROM，旋转因子复数乘法器单元及计数器控制单元．SDF结构中只有1条数据通路，蝶形运算后的两个结果其中一个会暂时保存在延迟反馈单元中，另一个会输出到下一级．SDF结构的优势就是可以高效地利用存储器，减少硬件电路的复杂度．

2 新型常数乘法器

复数乘法器是FFT中最重要的运算单元之一，不仅占用最多的硬件资源，而且在一定程度上决定着FFT的计算速度，因此设计出一种高效的复数乘法器将对FFT的整体性能有很大的影响．FFT中的旋转因子复数乘法[11]可表示为

(xre+jxim)(cosα-j sinα)=(xrecosα+ximsinα)+j (ximcosα-xresinα) ．(3)

图3 复数乘法器架构图

复数乘法器架构图如图3所示．从图3中可以看出，复数乘法器共需要4个实数乘法器和两个加法器．由于实数乘法器占用硬件资源较多，导致复数乘法器对硬件资源的消耗较大．而从式(3)中可以看出，旋转因子系数 cosα和 sinα可以提前计算出来存储在ROM中供乘法计算使用．根据这个特点，可以将实数乘法器改为常数乘法器，常系数即为旋转因子系数．16点FFT的所有旋转因子系数如表1所示．

表1 16点FFT的旋转因子系数

从表1中可以看出，当θ=0时，旋转因子系数为1，此时输入数据不需要经过乘法器，直接送到下一级即可; 当θ= π/2 时，旋转因子系数为 -j，此时只要先将输入数据的实部取反，再将实部和虚部互换输出即可; 当θ为其他角度时，此时旋转因子系数有 ±0.923 9、±0.382 7 和 ±0.707 1，共6个，根据旋转因子的对称性[12]，只需要设计出 0.923 9、0.382 7 和 0.707 1 对应的3个常数乘法器，就可以完成所有旋转因子复数乘法操作．

文中提出了一种新型常数乘法器设计方法即系数放大法，可以进一步减小常数乘法器的硬件面积，缩短关键路径，提升其性能．方法步骤如下：考虑到实现小数常数乘法器会使用较多数量的加法器，而整数常数乘法器可以减少加法器的使用量，所以先通过将小数点向右移位和舍入操作将小数扩大并近似为一个整数，此整数的特点是可以通过较少的移位相加操作便可以实现其对应的常数乘法器；最后，再通过向左移位的方式将其还原为原来的小数，便可以实现加法器数量最少的小数常数乘法器．

右移位数的选定是通过右移小数点和舍入操作将小数近似为一个整数，故必然会存在一定的误差，而此误差与小数点右移位数有关．当右移位数较小时，误差较大; 当右移位较大时，误差较小，但此时会消耗更多的资源．以 0.382 7 为例，当小数点右移2位时，扩大为 1.530 8，舍入近似为2，此时的误差为 2/4- 0.382 7，即 0.117 3，误差较大; 当小数点右移9位时，扩大为 195.942 4，舍入近似为196，此时的误差为 196/ 512- 0.382 7，即 0.000 1，误差较小，但是 196= 27+ 26+ 22+ 21，需要3个加法器，资源消耗较大; 当小数点右移6位时，扩大为 24.492 8，舍入近似为24，此时误差为 24/ 64- 0.382 7，即 0.007 7，误差较小，且 24= 24+ 23，只需要1个加法器．0.923 9 和 0.707 1 的计算过程与此过程类似．故在权衡了资源消耗和误差的情况下，文中将移位操作选定为6位．

表2 旋转因子扩大后的系数值

表2为3个旋转因子系数小数点右移6位和舍入操作后的系数值．

通过表2中移位和舍入系数的分解，可以得到3个相应的新型常数乘法器的电路结构图，如图4所示．

图4 3个新型常数乘法器的电路结构图图5 新型复数乘法器

再根据图3和表1，用这3个新型常数乘法器便可以组成相应的复数乘法器，如图5所示．

从图5中可以看出，文中的0.923 9常数乘法器使用1个加法器，0.382 7 常数乘法器使用1个加法器，0.707 1 常数乘法器使用2个加法器，最后组成的新型复数乘法器共使用12个加法器; 而文献[4]中，0.923 9 常数乘法器使用4个加法器，0.382 7 常数乘法器使用2个加法器，0.707 1 常数乘法器使用4个加法器，最后组成的CSD复数乘法器共使用24个加法器．故文中提出的新型复数乘法器比CSD复数乘法器的加法器数量少了一半，节省了大量的硬件资源; 另外，新型复数乘法器的关键路径延约为两个加法器，有效提高了FFT的系统性能．

图6 16点FFT在0.18μm工艺下的版图

3 实验结果对比分析

文中设计了16点SDF基22FFT架构，将其用硬件描述语言Verilog HDL进行编码，并用Modelism进行功能仿真，采用中芯国际集成电路制造(上海)公司(Semiconductor Manufacturing International Corporation，SMIC) 0.18 μm 工艺进行了综合和布局布线．图6为文中设计的FFT在 0.18 μm 工艺下的版图．通过计算和仿真报告分析可知，文中设计的FFT在 0.18 μm 工艺下的最大时钟频率可达到约 710 MHz，面积约为 0.12 mm2，功耗约为 3.30 mW．表3为文中设计的FFT分别在专用集成电路(Application Specific Integrated Circuit，ASIC)、Spanrtan-3、Virtex-4和Virtex-5中和现有其他构架的电路性能与硬件开销的比较，相比之下，文中设计大大减少了FPGA中的基本逻辑单元(Slices)和查找表(Look Up Tables，LUTs)单元的使用，并提升了硬件效率．

表3 电路性能和硬件开销比较

4 结 束 语

文中设计了16点SDF基22FFT，使用常数乘法器代替了传统复数乘法器，并且用系数放大法设计了一种新型的常数乘法器，将所需加法器数量减少到最低．文中设计的16点FFT在 0.18 μm 工艺下的最大时钟频率可达 710 MHz，面积约为 0.12 mm2; 另外，文中在Xilinx Virtex-4上实现了 16 bit 16点FFT，所需Slices数量减少8%，单位Slices吞吐率为1.273，对比其他构架，提高了约1倍; 在Xilinx Virtex-5上实现了 16 bit 16点FFT， 所需LUTs数量减少44%，单位LUTs吞吐率为0.978，对比其他构架，提高了约1倍．

[1] 张亚洲, 张超, 王保锐, 等. 实时频谱分析仪中并行FFT算法的FPGA设计[J]. 单片机与嵌入式系统应用, 2016(5): 23-26.

ZHANG Yazhou, ZHANG Chao, WANG Baorui, et al. FPGA Design of Parallel FFT Algorithm in Real-time Spectrum Analyzer[J]. Microcontrollers & Embedded Systems, 2016(5): 23-26.

[2] ZHOU B, HWANG D. Implementations and Optimizations of Pipeline FFTs on Xilinx FPGAs[C]//Proceedings of the 2008 International Conference on Reconfigurable Computing and FPGAs. Piscataway: IEEE, 2008: 325-330.

[3] ZHOU B, PENG Y, HWANG D. Pipeline FFT Architectures Optimized for FPGAs[J]. International Journal of Reconfigurable Computing, 2009, 2009(5): 9.

[4] WANG H Y, WU J J, CHIU C W, et al. A Modified Pipeline FFT Architecture[C]//Proceedings of the 2010 International Conference on Electrical and Control Engineering. Piscataway: IEEE, 2010: 4611-4614.

[5] WANG Z, LIU X, HE B, et al. A Combined SDC-SDF Architecture for Normal I/O Pipelined Radix-2 FFT[J]. IEEE Transactions on Very Large Scale Integration Systems, 2015, 23(5): 973-977.

[6] 胡锦涛, 李路, 姚如贵, 等. 基于FPGA的面积有效FFT实现技术研究[J]. 电子设计工程, 2016, 24(8): 94-97.

HU Jintao, LI Lu, YAO Guru, et al. Research on the Effective Area FFT Implementation Based on FPGA[J]. Electronic Design Engineering, 2016, 24(8): 94-97.

[7] 吴金红, 曹建, 赵岩. 基于FPGA的OFDM改进调制解调器设计[J]. 计算机测量与控制, 2010, 18(12): 2815-2817, 2835.

WU Jinhong, CAO Jian, ZHAO Yan. Design of OFDM Improved Modulator and Demodulator Based on FPGA[J]. Computer Measurement & Control, 2010, 18(12): 2815-2817, 2835.

[8] 钟冠文, 卢亚伟, 付欣玮, 等. 基于FPGA的 1 024 点高性能FFT处理器的设计[J]. 微计算机信息, 2012, 28(8): 66-67.

ZHONG Guanwen, LU Yawei, FU Xinwei, et al. Design of 1 024 Point FFT Processor Based on FPGA[J]. Microcomputer Information, 2012, 28(8): 66-67.

[9] HE S, TORKELSON M. New Approach to Pipeline FFT Processor[C]//Proceedings of the 1996 IEEE Symposium on Parallel and Distributed Processing. Piscataway: IEEE, 1996: 766-770.

[10] QURESHI I A, QURESHI F, SHAIKH G M. Efficient FPGA-mapping of 1 024 Point FFT Pipeline SDF Processor[C]//Proceedings of the 2014 International Symposium on Parallel Architectures, Algorithms and Programming. Piscataway: IEEE, 2014: 29-34.

[11] TANG A, YU L, HAN F, et al. CORDIC-based FFT Real-time Processing Design and FPGA Implementation[C]//Proceedings of the 2016 IEEE 12th International Colloquium on Signal Processing and Its Applications. Piscataway: IEEE, 2016: 233-236.

[12] TRAN T H, KANAGAWA S, NGUYEN D P, et al. ASIC Design of MUL-RED Radix-2 Pipeline FFT Circuit for 802. 11ah System[J]. IEEE Low-Power High-Speed Chips, 2016, 1(3): 9-11.