基于FPGA的32位多并行2DFFT处理器的设计

毛宇河 伍松

摘要：在分析研究FPGA的可并行运算性质及快速高效地进行二维快速傅里叶变换的计算过程的基础上，实现了FPGA支持的32位多并行2DFFT处理器的设计与仿真研究。设计利用ouanLlsII 13.0进行分析、布线与综合，利用Modelsim SE仿真平台进行仿真测试，并将结果与MATLAB计算结果进行对比验证。结果表明：该处理器充分利用FPGA的并行性和处理能力，解决了普通2DFFT处理器的计算缓慢问题，同时具有运算速度快，结构简易且可重构性能佳等特点。

关键词：现场可编程门阵列（FPGA）;二维快速傅里叶变换（2DFFT）：并行结构

中图分类号：TP332;TN911.7DOI：10.16375/j.cnki.cn45-1395/t.2020.01.013

0引言

随着2DFFT在声学、通信、医学、图像处理等领域中的不断发展，对于数字信号处理量的需求日益增大，而对于能处理超大容量数据的二维快速傅里叶变换在硬件实现方面的发展也越来越不容小视。到目前为止，2DFFT的硬件实现方式主要以3种为主：专用集成电路（ASIC）芯片、专用数字信号处理（DSP）芯片和现场可编程门阵列（FPGA）芯片。最初为满足计算的实时性，以定制高速ASIC的方式来完成FFT处理器的计算过程成为当时2DFFT硬件实现的主要方式。而随着技术发展，现今国内大多采用的则是DSP芯片技术，又由于多总线结构的加入，使DSP芯片技术的运行速度大大提高。但由于现代通信技术的兴起，DSP技术的计算速度和其他技术指标已渐渐无法满足工程师们的要求，于是FPGA技术应运而生。FPGA将DsP和ASCI的优点集聚一身，具有高速度、高精度、低功耗、成本低、开发周期短的特点，并且其资源富裕，拥有高强的可配置性，并行结构和流水线结构都易于在其芯片上进行实现，成为了高速实现2DFFT算法的不二选择。华南理工大学的黄俊彦等采用基于ARM7处理器实现基4-FFT的方法对FFT运算过程高效处理，但由于ARM处理器自身功能的局限性，难以对数据处理提供更高的速度，因此，采用ARM处理器实现FFT计算的快速性是难以做到的。华中科技大学的高英华则是利用ASIC处理器对大点数的二维FFT进行设计实现，但由于ASIC处理器的速度性、适用范围的局限性、以及自身无法媲美FPGA芯片性价比等诸多原因，逐渐被FPGA芯片所代替，因此该设计的实用性越来越低。云南大学的杨军等采用FPGA芯片完成了可实现高精度结果的二维FFT处理器的设计研究，但由于此研究过多的对处理器结果精度进行了把控，对处理器的快速性和高效性未能有更多的考虑，因此，该设计产生的处理器尚不完美。

本文分析研究了FPGA的可并行运算性质及快速高效地进行二维快速傅里叶变换的计算过程，同时实现了FPGA支持的32位多并行2DFFT处理器的设计与仿真研究。该数据处理器较普通的2DFFT处理器而言，极大程度地提高了处理器在FPGA上的运算能力，通过并行性提升了运算的快速性，并同时具有运算水平高，安全性能强，设计结构简易且可重构性能佳等特点。

1 2DFFT算法与并行结构

1.12DFFT算法原理

对于N₁行N₂列（其中N₁、N₂为2的自然数次幂）的二维空域均匀采样序列x（n₁，n₂），其二维DFT系数可为X_F（k₁，k₂），其定义式如下：

其中，x（n）为均匀采样序列，k=0，1，…，N-1.由此可知，2DFFT计算可进行分解，将其变为N₁个N₂点的FFT的运算过程，将二维的问题分解成一维问题。

由上面的定义式可知，二维快速傅里叶变换通常可采用行列分解算法进行计算，即利用其可分性，将二维的FFT拆分成行方向的FFT和列方向的FFT，然后按先后次序进行计算。通常而言，一维FFT算法的行列先后顺序对2DFFT运算结果没有很大影响，只要能保证2DFFT中行方向FFT和列方向FFT分别进行了计算即可。而通常2DFFT的处理过程如图1所示，其中①、②分别代表2DFFT中行方向和列方向的FFT计算过程。由图1可知，FFT的计算方法的优化过程，是提升2DFFT算法计算效率的关键因素。

1.2并行蝶形运算结构

22DFFT多并行处理器的总体设计

对于2DFFT的软件设计过程，主要是運用A1tera公司提供的Quartus II 13.0开发平台，采用VerilogHDL硬件描述语言来实现对于32位的2DFFT的IP核的研究与设计，再通过IP核的搭建来完成对于32位2DFFT数据处理器的总体设计。

为了便于对总体结构的描述，将着重以双蝶形运算模块并行结构进行叙述。双蝶形运算模块并行结构，其总体结构如图3所示。整个系统由状态控制器（FSM）、蝶形处理单元（BFU）、地址储存控制器（AddressStorage Control，ASC）、并行结构的蝶形运算计数器（Butterfly Counter，BFUC）、数据存储器（RandomAc-cess Memory，RAM）、旋转因子储存器（Twiddle Factor Storage，TFS）以及复数乘法（Multiplier，Mult）组成。当中，虚线框中区域，即蝶形运算单元及乘法器这两部分为此IP核的主要核心，合称为蝶形运算模块。该系统的设计，其优势之处在于程序进行了参数化设置，即可由实际情况，随时对旋转因子、初始数据、数据地址及蝶形运算单元个数进行灵活修改。

文中IP核的内部设计，其工作流程如图4所示，简述如下：Step 1由蝶形运算计数器BFUC为地址储存控制器ASC及状态控制器FSM发出计数信号;Step 2在状态控制器FSM发出的复位信号的控制下，IP核整体处于复位归零的准备状态;Step 3一方面在时钟信号的控制下，由FSM向具有并行结构的蝶形处理单元BFU和数据储存器RAM发出使能信号，另一方面由地址储存控制器ASC向数据存储器RAM和ROM旋转因子储存器TFS分别发出地址信号，再从ROM中按照地址提取所需数据信号，为蝶形运算单元提供计算所需的旋转因子W_n;Step 4在双方面的支持下，单次蝶形运算的计算流程如下：首先在RAM的使能信号的驱动下，由地址存储器为RAM输入的地址信号为蝶形运算模块提供两对输入数据，再在蝶形运算使能信号的驱使下，利用蝶形运算单元BFU及复数乘法器Mult的相互作用，以及ROM提供的旋转因子，同时完成两次蝶形运算，并将运算的结果重新返回到RAM中，替换原先输出的那两对数据，至此就完成了两对数据的运算;Step 5再在输入的使能信号的驱动下，继续完成下面两对数据的蝶形运算过程，循环往复，直至完成所有行方向的FFT，并通过地址存储控制器ASC的作用，将RAM当中的数据进行重新排序选择，实现32阶方阵的转置，将行方向变成列方向;继续循环进行蝶形运算过程，直至完成所有列方向FFT，至此得出2DFFT的最终计算结果。再将计算结果通过输出端口输出数据，完成整个计算的过程。

以上则是对双并行蝶形运算过程进行的过程说明，四并行蝶形运算的情况只需将双蝶形运算中的双蝶形运算结构模块变为四蝶形运算结构模块，其结果即可类似得到。

蝶形运算模块是本2DFFT的IP核运算过程的核心模块，本模块主要包含两部分，即蝶形运算单元（BFU）和复数乘法器（Mult）。蝶形运算部分的主要运算过程为复数的加减法和乘法，因此，本设计主要通过蝶形运算单元和复数乘法器来分别完成这两部分的计算，并通过蝶形运算单元与状态机、旋转因子储存模块和数据存储模块进行相互连接，形成与其他单元的相互联通，从而良性完成蝶形运算计算过程。另外，本模块采用的双并行、四并行的并行结构，可成倍有效地解决单蝶形带来的计算缓慢的问题，使RAM对于数据的吞吐效率得以显著提升。另外由于蝶形运算模块采用了并行结构，使得地址储存控制器ASC中命令的行数也成倍地减少，同时也让地址储存控制器的运行效率极大提高，使系统的运算处理能力大大加强。

3 21）FFT多并行处理器的RTL级描述

2DFFT多并行处理器是利用32位多并行2DFFT的IP核搭建来完成。因此，对于此IP核的RTL级描述过程将变得尤为重要。系统的RTL级描述过程，是作为了解整个系统硬件构成的主要途径。

通过使用OuartusII开发平台来完成对于IP核的RTL级硬件描述过程，以此得到所需的双并行和四并行蝶形运算的RTL级原理图。其中，双并行蝶形运算的RTL级原理图如图5所示。

如图5所示，①为状态控制单元，是本系统中的主要控制单元，用于向其他单元发送状态信号，控制单元模块的运行和清零;②为蝶形运算计数单元，主要用于驱动状态控制器单元和地址储存控制单元，通过其中的计‘数器的增加来使状态机和地址存储控制器进行运作，是主要的驱动单元;③为地址储存控制单元，用于为蝶形运算模块和旋转因子储存器发送数据地址，以便保持数据传输和接收的准确性;④为旋转因子储存单元，专门用于为蝶形运算模块输入旋转因子;⑤为RAM数据储存单元，主要用于存放、输入和输出数据;⑥为系统设计中的关键部分，它是拥有并行结构的蝶形运算模块单元，是2DFFT设计中的主要运算部分。由于在图5中⑥是由两个蝶形运算模块构成的总模块单元，因此系统采用的是双并行结构。而且并行结构只需将⑥中蝶形运算模块buff module的数量变为4个后，便类似可得。

4仿真验证及测试分析

为了验证并行结构的2DFFT的速度和性能是否达到要求，将利用OuartusII 13.0软件平台对本设计进行仿真测试。

本设计采用A1teraCvclorleIIILS作为目标开发板，对单蝶形运算系统、双并行蝶形运算系统和四并行蝶形运算系统将采用EP3CLS200F484C7作为目标芯片，在Ouartus II 13.0软件平台上进行分析、综合、布线、装配、时序分析等过程后，得到最终结果。由于最终结果共包含32×32个数据，数据过多，为了方便比较说明，仅将前三行仿真结果进行图像展示。单蝶形运算系统、双并行蝶形运算系统和四并行蝶形运算系统在Modelsim SE 10.4中在50MHz下的仿真计算的前三行结果分别如图6-图8所示。图中r₁、r₂、r₃、r₄、r₅、r₆、r₇、r₈为结果数据的实数部分，i₁、i₂、i₃、i₄、i₅、i₆、i₇、i₈为结果数据的虚数部分，且每个方块代表一行结果。

2DFFT在MArLAB中使用FFT2函数的前三行计算结果如图9所示，其中图9（a）为计算结果的实数部分，图9（b）为计算结果的虚数部分。

本系统的仿真计算时间测试结果如表1所不。

使用MATLAB中FFT2函数得到的运行时间结果如图10所示。

由图10可知，本设计的计算效率己远远超过了MArLAB的计算效率。

再将本文设计的双并行蝶形运算处理器和四并行蝶形运算处理器的仿真測试性能，同已有或不同算法的处理器的性能进行比较，如表2所示。

由表2可见：在相同频率相同FFT点数的情况下，本文的设计计算速度优于已有的很多FFT处理器，且随着并行倍数的增大，速度也在成倍的升高。

因此，通过图6-图9中的结果数据对比，可以说明，使用OuartusII 13.0设计出来的2DFFT的IP核，其计算能力与MATLAB相差不大，正负性保持一致，且结果基本相同;再通过对图10、表1中仿真计算时间测试结果与MATLAB中FFT2函数计算时间的对比以及与各已有处理器计算性能进行对比，可分析得出，将蝶形运算系统进行双并行或四并行的并行化处理后形成的并行结构体系，可为2DFFT提供非常快的运算速度，基本超过了绝大多数已有处理器的处理效率，远超MATLAB处理2DFFT的能力，达到了设计预期的快速性与高效性，实现了2DFFT处理器的高速处理能力。再通过对表1内部数据的对比，可分析得出，随着并行倍数的提高，蝶形运算模块处理数据的能力也成倍攀升，系统的运算效率也是不断提高，高速能力的体现也是越发的突出，因此能够说明，多倍的并行结构的确能够使系统达到高速能力，且能力也会随并行的倍数不断提升。

虽然计算速度较快，但结果仍有少许差异。造成差异的原因在于：由于蝶形运算所用到的旋转因子的数据类型是浮点数的，且在VHDL语言中很难使用浮点数进行四则运算，因此该设计在计算前将所有旋转因子扩大了128倍;但对数据进行了单次蝶形运算后，输送回来的数据，又将采用截断后7位的方法将结果缩小128倍，将所得到的结果覆盖掉原来从RAM输出的数据;后又按相同的方法再进行下一次的蝶形运算，直至RAM中该位置上的数据完成了行方向和列方向共10次的蝶形运算，即相当于一个最终结果在之前的过程中共被截断过10次，因此产生误差。但与MATLAB计算出的数据比较得知，通过IP核生成的数据与真实结果相差不大，且正负完全一致无误。后面需对设计进行进一步的优化，减小计算误差，使本设计系统更加实用化。

5结论

运用对蝶形运算模块采用并行结构的设计理念完成了一个高效快速的基于FPGA支持的32位多并行2DFFT处理器的研究设计。该处理器通过对程序的优化，实现不同倍数的蝶形运算并行结构，同时具有运算水平强，计算过程安全稳定性高，硬件结构简易和可重构性能高等特点。该设计不仅能发挥FPGA芯片的并行性能，同时也解决了高精度样本数据计算过程缓慢的问题，对工程应用具备一定的意义和价值。