1. 项目概述在数字信号处理领域快速傅里叶变换FFT的地位无需赘言它就像一把万能钥匙能让我们在时域和频域之间自由穿梭。无论是你手机里的4G/5G信号还是正在播放的音乐背后都有FFT在默默工作。然而当标准化的2的幂次方FFT算法遇上非标准点数时事情就变得棘手了。这正是中国数字多媒体广播地面标准DMB-T中TDS-OFDM系统所面临的挑战它需要一个3780点的FFT处理器。3780这个数拆开看是60乘以63它既不是2的幂也不是简单的质数乘积直接套用经典的基-2或基-4算法是行不通的。传统的解决方案比如基于Good-Thomas质因子算法PFA结合Winograd傅里叶变换算法WFTA的架构虽然能完成任务但代价不菲。大量的复数乘法运算意味着需要消耗海量的数字信号处理器DSP资源硬件成本高功耗也大。对于需要大规模部署的消费电子或通信设备来说这无疑是个沉重的负担。因此我们一直在寻找一种更“经济”的方案目标很明确在保证性能如系统信噪比和延迟满足DMB-T标准的前提下尽可能地“砍掉”那些昂贵的乘法器用更廉价的加法和移位操作来替代。经过一番探索和实验我们提出并实现了一种新颖的3780点FFT处理器方案。其核心思路是“两板斧”第一板斧用迭代WFTA架构彻底替换传统的PFA架构来构建60点和63点FFT模块第二板斧用一个精心优化的CORDIC模块来替代最后一级的旋转因子乘法单元。实测下来这套方案效果显著与传统PFA方案相比乘法运算量直降45%而加法运算量仅微增1%。更重要的是在FPGA实现中我们成功地将所有专用DSP模块替换为了CORDIC和ROM大幅节约了硬件逻辑资源。无论你是正在钻研通信物理层实现的工程师还是对高效数字信号处理架构感兴趣的研究者这篇文章将为你详细拆解这个优化设计背后的每一个技术细节、设计权衡和实操要点。2. 核心思路与方案选型为什么是迭代WFTACORDIC面对3780点这个特殊的FFT需求设计之初我们首先要回答几个关键问题现有的方案痛点在哪里我们的优化方向是什么为什么迭代WFTA和CORDIC是更优的选择2.1 传统PFAWFTA方案的瓶颈分析在早期设计中如参考文献中提到的典型方案处理3780点FFT的主流方法是将其分解为互质的603×4×5和637×9两个大点数FFT然后再用Cooley-Tukey算法结合。对于60点和63点FFT其内部进一步采用PFA分解为更小的质数点如3,4,5,7,9WFTA模块。这套流程听起来很清晰但硬件实现上却有几个硬伤计算复杂度高PFA虽然避免了旋转因子在分解阶段的乘法但其整体计算量尤其是乘法次数依然可观。因为WFTA中的C矩阵对角阵乘法是实打实的复数乘法即使部分系数是纯实数或纯虚数也需要实数乘法器来实现。硬件资源消耗大大量的复数乘法直接转化为对DSP硬核在FPGA中或乘法器单元在ASIC中的巨额需求。DSP硬核是FPGA中的稀缺资源占用过多会限制其他逻辑功能的实现也推高了芯片成本。结构相对固化PFA与WFTA的结合方式在数据流和缓冲管理上不够灵活中间缓存用于数据重排序较多增加了存储资源开销和访问延迟。我们的优化目标就是直击这些痛点降低乘法次数、减少专用乘法器DSP使用、优化数据流和存储结构。2.2 迭代WFTA用“分而治之”的矩阵思想替代PFAWFTA算法的精髓在于它将DFT计算表达为三个矩阵的连乘X S * C * T * x。其中S和T是元素仅为0、1、-1的稀疏矩阵对应着加/减运算成本极低C是对角矩阵其乘法对应着核心的乘法运算。对于小点数N如3,4,5,7,9我们已经有了最优或接近最优的S、C、T矩阵。传统PFA在处理复合点数如60时是将其视为多个小点数DFT的“嵌套”需要额外的索引映射和组合步骤。而迭代WFTA提供了一个更优雅的思路利用克罗内克积Kronecker Product。如果一个大点数N可以分解为两个互质因子N1和N2那么其对应的WFTA矩阵可以表示为小点数矩阵的克罗内克积S_N S_N2 ⊗ S_N1,C_N C_N2 ⊗ C_N1,T_N T_N2 ⊗ T_N1。这意味着我们可以直接用小点数如3,4,5的S、C、T矩阵通过克罗内克积“合成”出大点数如60的WFTA计算流图。这样做的好处是结构化规整整个计算过程可以组织成清晰的级联结构T阶段 - C阶段 - S阶段易于流水线设计。乘法器集中化所有必需的乘法都集中在C阶段而C矩阵是对角阵其乘法本质上是数据与一组固定常数的乘法。这为我们后续用CORDIC等特殊乘法单元来优化提供了便利。减少中间缓存相比于PFA的多级分解与重组迭代WFTA的数据流路径更直接有可能减少不必要的中间数据转置和缓存。因此我们决定用60点和63点的迭代WFTA模块取代传统方案中基于PFA的60点和63点FFT模块。2.3 CORDIC用“旋转”替代“乘法”的魔法FFT中最后一级将60点和63点FFT结果合并为3780点结果时需要乘以大量的旋转因子Twiddle Factors。这是复数乘法最密集的地方。直接用复数乘法器实现资源消耗巨大。CORDIC算法是我们的“杀手锏”。它的核心思想是通过一系列固定的、越来越小的角度旋转每次旋转只需加法和移位来逼近任意角度的旋转。一个复数乘以旋转因子e^(jθ)本质上就是将该复数在复平面上旋转角度θ。这正是CORDIC能做的事情。采用CORDIC模块替代复数乘法器的优势极其明显无需硬件乘法器CORDIC核心里只有加法器、移位器和查找表ROM完全避开了昂贵的专用乘法单元。精度可控通过增加迭代次数旋转级数可以逼近所需的计算精度。对于DMB-T系统的要求我们通过仿真确定了18级CORDIC就能满足信噪比SNR要求。预计算优化旋转因子是固定的因此驱动每次旋转方向的符号序列σ_i可以预先计算好并存储在ROM中。由于旋转因子的对称性ROM的存储量甚至可以减半。将迭代WFTA和CORDIC结合我们的方案就形成了前端用高度结构化的迭代WFTA完成60点和63点的大点数FFT计算后端用高度优化的CORDIC阵列完成旋转因子乘法。前者优化了计算流程本身后者优化了最耗资源的运算单元。3. 迭代WFTA模块的详细设计与实现理论很美好但要把迭代WFTA在硬件上高效地跑起来需要解决一系列工程问题数据如何映射和排序矩阵运算如何映射到硬件结构资源如何估算3.1 数据索引映射简单映射与CRT映射迭代WFTA的基础是二维DFT分解。对于一个N N1 × N2N1与N2互质的DFT我们需要将一维输入序列x[n]映射到二维数组x[n1, n2]计算完二维DFT后再将结果X[k1, k2]映射回一维序列X[k]。这里涉及两种关键的映射输入简单映射Simple Mappingn ≡ N2 * n1 N1 * n2 (mod N)。这保证了输入数据的一维索引n与二维索引(n1, n2)是一一对应的。在硬件上这意味着我们需要一个输入缓存Cache I来完成这种数据重排确保数据正确的顺序进入迭代WFTA计算单元。输出中国剩余定理映射CRT Mappingk ≡ N2 * T1 * k1 N1 * T2 * k2 (mod N)。其中T1和T2是满足N2 * T1 ≡ 1 (mod N1)和N1 * T2 ≡ 1 (mod N2)的系数。这个映射确保了计算结果的一维输出顺序符合预期。同样需要一个输出缓存Cache II来进行重排序。以63点N19, N27为例计算得T14, T24因为7428≡1 mod 9, 9436≡1 mod 7。输入映射n ≡ 7*n1 9*n2 (mod 63)。n10..8, n20..6。输出映射k ≡ 28*k1 36*k2 (mod 63)。k10..8, k20..6。在硬件设计中这两个缓存通常用双端口RAM实现。设计的关键在于设计高效的地址生成器根据映射公式实时计算读/写地址。3.2 硬件架构T-C-S三级流水线迭代WFTA模块的硬件结构清晰地对应其矩阵运算X (S_N2 ⊗ S_N1) * (C_N2 ⊗ C_N1) * (T_N2 ⊗ T_N1) * x。我们将其设计为三级流水线对应图4的结构T阶段加法/减法网络功能实现T_N * x的运算。T_N是稀疏矩阵元素仅为0, ±1。实现这是一个由可配置加法器/减法器组成的网络。矩阵T_N的每一行定义了如何对输入向量x的元素进行加权求和系数为1或-1或直接通过系数为0。这些系数预先存储在ROM中。操作输入数据流实部和虚部分开按顺序进入一组寄存器。每个时钟周期根据从ROM中读出的当前行的系数控制相应的加法器/减法器进行运算。由于T_N的大小是M×NMN每个加法器需要工作M个周期才能处理完一个数据块。C阶段常数乘法阶段功能实现C_N * (T_N * x)的运算。C_N是对角矩阵其对角线元素是复数常数实部或虚部可能为0。实现这是整个WFTA中唯一需要乘法运算的地方。但由于C_N是对角阵每个输出只与一个输入乘以一个常数相关。这些常数预先存储在ROM中。优化因为常数可能是纯实数、纯虚数或一般复数我们可以优化乘法器。对于纯实数或纯虚数乘法只需一个实数乘法器对于一般复数乘法需要四个实数乘法器。我们可以根据常数的具体值动态选择或复用乘法单元或者更进一步将这一阶段的乘法也纳入后续CORDIC的范畴进行统一优化本设计未采用仍使用实数乘法器。S阶段加法/减法网络功能实现S_N * (C_N * T_N * x)的运算。S_N同样是元素仅为0, ±1的稀疏矩阵。实现结构与T阶段类似也是一个由ROM系数控制的加法器/减法器网络。区别在于S阶段的输入是C阶段的输出且矩阵S_N的大小是N×M。以63点迭代WFTA模块为例我们需要9点和7点的小N WFTA矩阵S9, C9, T9和S7, C7, T7。通过克罗内克积生成63点矩阵S63 S7 ⊗ S9(63×99),C63 C7 ⊗ C9(99×99),T63 T7 ⊗ T9(99×63)。这意味着T阶段有99个加法器单元每个处理63个输入数据C阶段需要进行99次常数乘法S阶段有63个加法器单元每个处理99个中间结果。实操心得系数ROM的存储优化S和T矩阵的系数只有0, 1, -1可以用很少的比特位如2位编码存储。C矩阵的常数是浮点数需要根据系统精度要求确定位宽如16位。在FPGA中这些ROM可以用Block RAM或分布式RAM实现。设计时要注意ROM的读取地址生成逻辑与数据流严格同步避免出现流水线气泡。3.3 计算复杂度与资源评估根据论文中的公式推导迭代WFTA的计算复杂度乘法和加法次数有其规律。 对于一个N N1 × N2点的迭代WFTA设其子模块的乘法、加法次数为M1, A1和M2, A2则合并后的复杂度为乘法次数M M1 * M2加法次数A A2 * N1 M2 * A1对于63点来自7点和9点7点WFTA: M79, A7369点WFTA: M911, A94463点迭代WFTA: M63 911 99, A63 369 11*44 324 484 808? (论文中给出的是704这里存在差异可能源于对“加法”定义的不同或是优化后的S/T矩阵减少了操作数。我们以论文最终采用的优化后数据为准M6399, A63704)对于60点来自3、4、5点3点WFTA: M33, A364点WFTA: M44, A485点WFTA: M56, A517先计算15点(3×5)迭代WFTA: M153618, A15173 6*6 513687再计算60点(15×4)迭代WFTA: M6018472, A60815 4*87 120348468? (论文中给出的是396同样以论文优化后数据为准M6072, A60396)可以看到迭代WFTA显著减少了乘法次数63点从158降到9960点从192降到72但加法次数有所增加。在硬件上加法器的成本远低于乘法器因此这是一个非常划算的交换。4. CORDIC模块的优化设计与实现CORDIC模块是我们砍掉DSP硬核的关键。它的任务是为3780个旋转因子乘法W_{3780}^{n2*k2}提供计算服务。4.1 CORDIC原理与旋转模式CORDIC在圆周旋转模式下通过一系列微旋转来逼近目标角度θ。每次微旋转的角度是α_i arctan(2^{-i})。迭代公式为x_{i1} x_i - σ_i * y_i * 2^{-i} y_{i1} y_i σ_i * x_i * 2^{-i} z_{i1} z_i - σ_i * α_i其中σ_i ∈ {1, -1}是旋转方向由剩余角度z_i的符号决定。经过b次迭代后输出需要乘以一个固定的伸缩因子K_c Π cos(α_i)。对于FFT中的旋转因子乘法(x jy) * e^{jθ}我们设定初始值z_0 θ输入向量为(x, y)。CORDIC迭代完成后输出(x_b, y_b)再乘以K_c就得到了旋转后的结果。4.2 针对FFT的优化预计算符号序列传统的CORDIC在每个数据计算时都需要实时判断σ_i根据z_i的符号。这需要反馈路径不利于高速流水线设计。我们的关键优化在于预计算。由于FFT中的旋转因子角度θ -2π * (n2*k2) / 3780是固定的对于给定的n2, k2组合因此对应的符号序列{σ_0, σ_1, ..., σ_{b-1}}也是固定的我们可以预先为所有需要的旋转因子计算好其符号序列并存储在ROM中。优化带来的巨大好处流水线化去除了反馈依赖CORDIC模块可以设计成完全流水线的结构每个时钟周期都能输出一个结果吞吐量高。ROM共享旋转因子具有对称性W^{k} -W^{kN/2}等因此我们只需要存储一半旋转因子的符号序列另一半可以通过简单变换得到节省了近一半的ROM存储空间。简化控制逻辑无需复杂的角度比较和符号判断逻辑只需一个地址发生器按顺序读取ROM中的符号序列即可。4.3 18级CORDIC硬件实现我们采用了18级迭代来满足系统精度要求输出信噪比SNR 65dB。硬件结构如图5所示是一个18级深度、每级都包含移位器和加法器的流水线。移位器实现乘以2^{-i}。在硬件上这仅仅是线位的重连不消耗任何逻辑资源只是引入固定的布线延迟。加法器/减法器根据符号位σ_i决定进行加法还是减法。这是主要的逻辑消耗。缩放因子补偿所有18级cos(α_i)乘积K_c是一个常数。我们可以在最后一级使用一个固定的乘法器可以用一个常数乘法器优化或者甚至将缩放合并到后续处理中进行补偿。由于K_c是常数这个乘法也可以用一系列加法和移位来近似实现。模块工作流程输入复数的实部x_in、虚部y_in以及对应的旋转因子索引用于查找符号序列ROM。流水线第一级根据σ_0计算x1 x0 - σ_0 * (y0 0),y1 y0 σ_0 * (x0 0)。注意i0时移位为0。后续第i级 (i1 to 17)根据σ_i计算x_{i1} x_i - σ_i * (y_i i),y_{i1} y_i σ_i * (x_i i)。最后一级将(x_18, y_18)乘以预存的常数K_c得到最终输出(x_out, y_out)。注意事项位宽增长与截断CORDIC迭代过程中数据位宽会增长以防止溢出。我们需要仔细进行定点仿真确定每一级所需的整数位和小数位。在最后输出时可能需要截断或舍入到目标位宽如16位。不恰当的位宽处理会引入额外误差影响系统SNR。5. 系统集成与性能分析将迭代WFTA模块和CORDIC模块组合起来就构成了完整的3780点FFT处理器。数据流如图3所示输入数据经过输入共轭处理后进入缓存I进行重排序然后送入63点迭代WFTA模块其输出再经过缓存II重排序送入60点迭代WFTA模块最后60点和63点模块的结果进入CORDIC模块进行旋转因子乘法得到最终的3780点FFT结果再经输出共轭处理后送出。5.1 整体计算复杂度对比根据第3.3节计算出的子模块复杂度结合Cooley-Tukey算法合并60点和63点FFT的公式可以计算出整个3780点FFT的复杂度乘法次数 M_3780 N63M60 N60M63 6372 6099 4536 5940 10476(复数乘法)加法次数 A_3780 N63A60 N60A63 63396 60704 24948 42240 67188(复数加法)由于WFTA中的乘法是实数/复数乘法通常一次复数乘法需要4次实数乘法。因此传统PFA方案的实数乘法约为50,712次而我们迭代WFTA方案的实数乘法约为14,256 * 2 28,512次假设所有复数乘法都用4个实数乘法实现实际上部分纯数乘法可优化。乘法运算量降低了约45%。加法次数从传统方案的约140,184次实数加法变为134,376次仅增加约1%。5.2 硬件资源与性能评估我们在Altera Stratix II EP2S90 FPGA上使用Verilog HDL实现了该设计并用Quartus II进行综合和仿真。逻辑资源总共消耗了3,343个自适应查找表ALUT。作为对比参考文献中其他设计消耗的逻辑单元LE从4,000到7,000多不等。我们的设计在逻辑资源利用率上具有明显优势。DSP块最显著的成果是DSP块使用数量为0。所有乘法操作包括WFTA中C阶段的常数乘法和最后的旋转因子乘法都被CORDIC模块和优化的常数乘法网络替代了。这为FPGA设计释放了宝贵的DSP硬核资源用于其他功能。存储器主要消耗在输入/输出重排序缓存Cache I/II以及存储S、C、T系数和CORDIC符号序列的ROM上。总缓存需求约为136,080 bits少于传统设计因为我们移除了多个小N WFTA模块之间的中间缓存。最大时钟频率综合后报告的最大时钟频率为98.14 MHz。延迟处理一个完整的OFDM符号3780点的总延迟为7,873个时钟周期。在DMB-T标准的7.56 Msps符号率下这相当于约1042 μs的延迟完全满足系统实时性要求。系统信噪比SNR通过定点Matlab仿真在输入数据为5位I/Q分量输出为16位I/Q分量的配置下系统SNR达到67.9 dB远超TDS-OFDM系统的要求。下表对比了本文方案与其他几种公开方案的性能方案/架构实数乘法次数实数加法次数时钟周期逻辑单元(ALUT/LE)存储器(bits)DSP块Camarda et al., 2009 (7×5×4×3×3×3)30,28940775,112,56844未明确未明确Cheng and Su, 2010 (7×9×5×3×4)未明确未明确未明确约6,300 (估算)未明确24Yang et al., 2010 (27×7×5×4)33,000236,446未明确未明确未明确未明确Yang et al., 2002 (典型PFA设计)50,712140,1848,064未明确141,612未明确本文方案 (63×60 迭代WFTACORDIC)28,512134,3767,8733,343136,0800从对比中可以清晰看出本文提出的迭代WFTA结合CORDIC的方案在计算复杂度尤其是乘法次数和硬件资源消耗零DSP、较低逻辑用量方面取得了非常好的平衡是一种非常适合在资源受限的FPGA或ASIC上实现的高效3780点FFT处理器架构。6. 常见问题与实现避坑指南在实际的RTL实现和调试过程中我们遇到并解决了一系列问题。这里分享一些关键的经验和排查技巧。6.1 数据路径的位宽管理与溢出这是定点FFT实现中最常见也最棘手的问题。WFTA的C阶段乘法和CORDIC迭代都会导致数据位宽扩展。问题现象系统仿真SNR远低于预期或者输出出现大量非理性值。排查思路逐级定点仿真在Matlab中建立完整的定点模型精确模拟硬件中每一级运算后的截断或舍入行为。对比定点结果与浮点结果的误差找到误差突增的环节。监控动态范围在RTL仿真中添加监控逻辑记录关键节点如C阶段乘法后、CORDIC每级迭代后数据的最大值和最小值判断是否发生溢出。渐进式增加位宽从输出端开始反向推导。先确定最终输出需要的位宽和精度如16位有符号数其中整数部分几位小数部分几位。然后为CORDIC输出、CORDIC每级、WFTA的S/C/T阶段输出等逐步增加保护位Guard Bits。一个经验法则是每次乘法操作至少增加log2(最大系数绝对值)个整数位。我们的设置输入5位有符号整数I/Q各5位。WFTA内部C阶段乘法后数据扩展至13位考虑了系数动态范围。CORDIC内部采用18级迭代内部数据位宽从13位逐步增长到约20位以防止迭代过程中的精度损失和溢出。输出16位有符号数。最终截断前确保有足够的富余避免饱和失真。6.2 控制逻辑与数据流的精确同步迭代WFTA的T和S阶段是受ROM系数控制的可配置加法网络CORDIC的流水线也需要精确的符号序列控制。任何同步错误都会导致计算结果完全错误。问题现象输出数据完全混乱或每隔固定周期出现错误。排查技巧生成确定性测试向量使用全1、递增序列、单频正弦波等作为输入其FFT结果是可以预知的。对比RTL输出与Matlab黄金参考模型的输出。分段验证首先单独验证60点和63点迭代WFTA模块。为其提供简单的测试数据如单位脉冲并手动计算或用小点数FFT核验证其输出是否正确。然后再将两个模块联调。深度调试信号在Vivado/Quartus的仿真器中将关键的控制信号如ROM读地址、加法器选择信号、CORDIC每级的符号σ_i以及中间数据总线全部拉出来观察。检查ROM地址生成逻辑是否与数据流计数器匹配是否存在差1错误。注意缓存延迟输入/输出缓存Cache I/II会引入延迟。确保整个数据流的启动间隔Initiation Interval, II是稳定的并且下游模块在正确的时间读取缓存中的数据。6.3 CORDIC精度与迭代次数的权衡CORDIC的精度随迭代次数增加而提高但面积和延迟也线性增加。问题选择多少级迭代解决方法进行系统级的定点仿真。在Matlab中用不同迭代次数的CORDIC模型替换理想的复数乘法器运行完整的3780点FFT并计算输出信噪比SNR。绘制SNR随迭代次数变化的曲线。选择SNR刚刚满足系统要求并留有一定裕量如3-5dB时的最小迭代次数。我们的实验表明对于DMB-T应用18级迭代在实现复杂度和67.9dB的SNR之间取得了良好平衡。缩放因子补偿K_c的乘法会引入额外误差。可以采用规范的常数乘法器或者使用更精确的、基于加法和移位的多项式近似。务必在定点仿真中评估这种近似带来的误差。6.4 资源优化与时序收敛目标是零DSP且逻辑用量最小。常数乘法优化WFTA的C阶段有很多常数乘法。使用CSDCanonic Signed Digit编码来优化这些常数乘法将乘法分解为少量的加法和移位操作可以节省大量逻辑。共享加法器在WFTA的T和S阶段虽然理论上需要很多加法器但许多加法器在不同时间计算的是不同数据路径的求和。可以通过时分复用的方式用一组数量较少的物理加法器配合多路选择器来实现以面积换速度或反之。时序关键路径CORDIC的流水线级数深但每级只是“移位加法”关键路径通常较短。关键路径可能出现在WFTA的加法树或最后的缩放乘法器上。如果时序不满足可以考虑对宽位加法器进行流水线打拍。将最后的常数乘法K_c也拆分成多级流水线。使用FPGA提供的专用进位链Carry Chain资源来实现高速加法。ROM实现选择S/T系数ROM很小用分布式RAMLUTRAM实现即可访问速度快。C系数和CORDIC符号序列ROM较大使用Block RAMBRAM更经济。合理规划ROM的端口和深度确保能在一个周期内读出所需数据。这个基于迭代WFTA和CORDIC的3780点FFT处理器设计从理论分析到工程实现是一套完整且经过验证的优化方案。它成功地将算法创新迭代WFTA与硬件优化技术CORDIC相结合在满足严苛的通信标准性能要求的同时大幅降低了硬件实现成本为零DSP或低DSP资源的FFT/IP设计提供了一个优秀的范例。在实际项目中根据具体的芯片平台和性能要求还可以在此基础上进行进一步的流水线深度调整、存储器架构优化以及功耗优化。