基于多旋转CORDIC的FPGA可配置浮点FFT加速器研究报告
一、研究概述
本研究由来自中国长沙国防科技大学（National University of Defense and Technology，NUDT）计算机学院的陈继阳、雷元武、彭元喜、何婷婷和邓子烨共同完成。该研究成果以《Configurable Floating-point FFT Accelerator on FPGA Based Multiple-rotation CORDIC》为题，于2016年11月发表在《Chinese Journal of Electronics》（中国电子学报）第25卷第6期上。研究得到了中国航天科学基金（项目号：2013ZC88003）和国家自然科学基金（项目号：61402499）的资助。本文是一项单一原创性研究，提出了一种新型的基于坐标旋转数字计算机（Coordinate Rotation Digital Computer，CORDIC）算法的可配置浮点快速傅里叶变换（Fast Fourier Transform，FFT）加速器，并在现场可编程门阵列（Field-Programmable Gate Array，FPGA）上完成了原型验证。
二、研究背景与研究目标
FFT是数字通信、传感器信号处理以及合成孔径雷达（Synthetic Aperture Radar，SAR）等领域的基础算法，通常是实时通信系统中耗时最长的部分。不同的通信标准，如IEEE 802.11a/g、WiMAX和DVB-T，其所需的FFT点数从64点到8192点不等，这要求FFT加速器必须同时具备高性能和高灵活性，以支持可变大小的FFT计算。然而，随着FFT点数的增加，存储消耗和资源利用率会成为降低FPGA性能的瓶颈。蝶形单元是FFT结构中的基本模块，其面积和吞吐量至关重要。CORDIC算法作为一种仅通过加法器和移位器即可完成乘法运算，从而替代传统乘法器的方法，被认为是实现蝶形运算的有效途径，但它需要大量的迭代次数，导致硬件成本高昂。
针对上述挑战，本研究旨在实现一种新型的可配置浮点FFT加速器，以提升其在FPGA上的处理能力并满足不同应用的需求。研究的核心目标是：通过改进CORDIC算法，减少迭代次数和延迟，降低硬件成本；同时，通过优化的存储和地址生成机制，提升数据吞吐量并显著减少存储资源的消耗，尤其是在大规模FFT计算中。
三、研究的详细工作流程与实现方法
为实现上述目标，本研究设计并实现了一个包含四大模块的FFT加速器架构，并在CORDIC算法层面提出了多项创新。
1. 整体加速器架构设计 所提出的FFT加速器由四个主要部分组成：地址生成单元（Address-generating Unit）、FFT控制器、数据存储静态随机存取存储器（Data-storing SRAM）和蝶形单元（Butterfly Unit）。为提高并行度，SRAM和蝶形单元均包含多个独立的子单元。地址生成单元负责生成数据提取地址和实时计算CORDIC旋转所需的旋转因子角度。数据存储SRAM用于存储初始数据、更新中间结果和保存最终结果，其读写速度对整个加速器的性能影响巨大。蝶形单元是整个系统的核心计算模块，集成了本研究提出的多项关键算法改进。
2. 实时旋转因子角度生成与地址生成单元 传统的FFT加速器需将旋转因子角度预先存储在只读存储器（Read-Only Memory，ROM）中，这导致硬件成本随FFT点数增加而急剧上升。本研究提出了一种基于提取地址实时生成旋转因子角度的方法。在FFT的每一级，旋转因子是固定的，因此角度主要由FFT级数和数据地址两个因素决定。研究者推导并建立了以基2（Radix-2）算法为例的数据提取规则与旋转角度之间的精确对应关系，使得角度可以在数据被读取时即时计算，从而省去了用于存储角度的大规模ROM。
3. 基于双端口内置RAM的数据存储优化 蝴蝶单元的输入和输出都需要通过SRAM。本研究利用FPGA的内置双端口RAM（Built-in Dual-port RAM）来构建数据存储模块，使得读和写操作可在同一RAM内完成，大大提高了数据吞吐量。然而，一个蝶形单元需要两个读端口和两个写端口，而单个双端口RAM无法满足。为解决地址冲突并保证流水线的连续性，研究者提出了一种将数据存储RAM划分为多个子RAM的方案。以包含一个蝶形单元的基2 FFT为例，偶数地址数据存入RAM1，奇数地址数据存入RAM2。在计算的不同阶段，通过精心设计的读写调度策略，使得在奇数周期从RAM1读写数据，在偶数周期从RAM2读写数据，从而最大化了双端口RAM的利用率。
4. 蝶形单元与多重CORDIC旋转的改进 这是本研究最核心的创新部分。传统的蝶形单元使用四个乘法器和六个加法器，而本研究的结构仅使用两个CORDIC单元和四个加法器。为了克服传统CORDIC算法因迭代次数多而导致的速度慢和面积大的缺点，研究者提出了三项关键优化技术：
5. 多重CORDIC旋转单元的整体结构 整个多重CORDIC旋转单元由预处理器、CORDIC处理器和后处理器三部分构成。预处理器负责将IEEE-754浮点格式的输入转换为定点格式，并将其与一个固定的增益因子K相乘，同时根据旋转角度所在的象限对输入数据进行预处理，以确保角度落在CORDIC算法[-99.911°, 99.911°]的收敛域内。CORDIC处理器则按上述的分段并行的方式完成64次旋转。后处理器将计算完成的定点结果转换回IEEE-754浮点格式，并根据预处理规则对结果的实部和虚部进行修正。
四、主要实验结果与分析
研究团队在Xilinx Virtex-5 XC6VLX760 FPGA芯片上对所提出的FFT加速器进行了实现和验证，并通过四个实验全面评估了其性能。
实验一：双精度浮点加速器资源与频率 实验结果（表3）显示，在配置四个并行蝶形单元时，加速器占用33230个寄存器（3%）和143006个查找表（30%），最高时钟频率可达122MHz。随着蝶形单元数量的增加，资源占用也相应增加，这是因为RAM的读写控制更加复杂，地址生成单元也需要在每个周期产生更多的提取地址和旋转角度。
实验二：单精度与双精度浮点加速器性能对比 对比实验一和实验二（表3与表4）的结果发现，双精度浮点FFT加速器的资源开销仅为单精度的约2.5倍，远低于理论上的4倍。这一显著优势归功于在最后32次旋转中采用固定乘法器替代传统CORDIC迭代的优化方法，节省了大量硬件资源。
实验三：与其他研究工作的性能比较 通过与K. Kalyani、R. Bhakt和G. Zhang等人提出的FFT结构进行对比（表5），本研究的加速器显示出巨大优势。它不仅是可配置的，而且由于使用了内置RAM和实时生成旋转因子，硬件开销（如寄存器、查找表）远小于未使用这些技术的同类设计。同时，改进的CORDIC算法使其能够达到与高资源消耗设计可比拟的高频率。
实验四：批量FFT原型系统验证 为评估实际应用性能，研究团队构建了一个包含四个FFT加速器模块、两个DDR控制器的批量FFT原型系统。该原型能够处理同尺寸的批量FFT，是合成孔径雷达和二维FFT的核心计算模式。在Xilinx Virtex-5 XC5VLX330 FPGA上，该原型共消耗49305个寄存器和153106个查找表（最受限资源），最高频率为109.4MHz。对于一个1024×1024点的批量FFT任务，总运行时间为80.4毫秒，其中FFT纯计算时间仅占25.1%。
性能评估公式与实际计算周期 FFT计算的总周期数可由公式 (N * log2(N)) / (2 * B) + L 精确表达，其中N为点数，B为蝶形单元数，L为流水线清空延迟。实际测试周期（表7）完美印证了该公式。例如，采用四个蝶形单元（r2b4）的4个并行结构执行一个8192点的双精度FFT，仅需13331个周期，远少于其他研究中数千乃至上万个周期的耗时。
五、研究结论与价值
本文成功地设计并实现了一种基于多重旋转CORDIC的高效、可配置浮点FFT加速器。其科学价值在于提出了一套完整的CORDIC算法优化方案，包括旋转方向预测、分段并行迭代和压缩迭代，从理论上减少了迭代次数和单次迭代延迟，并以极低的额外开销将计算精度从单精度扩展到双精度。其应用价值极为显著，该加速器具有高度灵活性，可配置不同数量的蝶形单元以在速度与资源间取得平衡，并支持从64点到8192点的可变大小FFT运算。它消耗的存储资源极小，尤其适用于大规模FFT计算，并可直接用于构建高性能的批量FFT处理系统。这项工作为实时信号处理、雷达成像等领域提供了一种高性能、低成本的硬件加速解决方案。
六、研究亮点