引 言

超宽带技术广泛应用于短距离高速的数据传输。本文介绍了一种低硬件开销的128点FFT处理器方案用于超宽带系统。FFT处理器作为超宽带系统中关键单元模块，消耗着相当大的硬件资源。因此，如何降低FFT单元模块所占用的硬件资源成为近年来的研究热点。

基-2算法作为最著名的FFT算法，由于其简单的蝶形架构应用于FFT模块的硬件实现，可以降低硬件资源的开销，但是随着FFT点数的增加，它所需要的复杂乘法运算量会变得相当巨大^[1]。随后，基-22,基-23,和基-24相继被提出，以上这些算法被统称为基-2k算法^[2,3,4]。基-2k算法具有与基-2算法一样简单的蝶形架构，同时又能够大大降低旋转因子(Twiddle factor, TF)的计算量，因此，非常适合FFT的硬件实现。不过，随着k值的增加基-2k算法的优势变得越来越小，这是由于所能利用的对称子项变得越来越少^[5]。而且，高k值的基-2k算法可以用低k值的混合基-2k算法替代，表1为512点混合基-24-23算法和改良基-25算法^[6]的详细旋转因子分布。仔细观察表1的旋转因子序列，容易发现如果以W512为轴，将两边的旋转因子互换位置，就会得到同样旋转因子序列的分布。因此，本文的设计方案只考虑当k≤4时的基-2k算法。

在以往的研究过程中，不同的FFT架构被提出。在这些架构中，流水线架构由于其较高的吞吐量以及适中的硬件成本得到了广泛的应用。流水线FFT处理器架构一般分为两类：多路径延迟转换(Multi-path delay commutator, MDC)和单路径延迟反馈(Single-path delay feedback, SDF)^[7]。MDC架构同时支持M路并行输入数据，数据吞吐量是SDF架构的M倍，但是其对数据路径、FFT点数以及基-2k算法都有限制。另外，MDC架构中所需的存储器和复杂乘法器都比SDF架构多。所以，MDC架构能完成较高数据吞吐率，而SDF架构需要较少的存储器和硬件成本。为了获取更低的硬件开销，本文的设计方案使用SDF架构。

一般来说，对于N点FFT(N>64)都会采用布斯乘法器来处理序列与旋转因子WNi的复数乘法运算。本文提出了一种新型串接CSD常数乘法器来实现序列与W128i的运算，一方面能够进一步降低硬件资源的开销，另一方面无需任何只读存储器(Read only memory, ROM)对旋转因子常数值进行存储。

1 算法选择

利用基-2k算法实现128点FFT包括6个旋转因子序列，表2给出了针对基-2k算法的详细旋转因子序列分布以及复数乘法的运算量。其中-j的运算为普通运算，只需对输入序列实部和虚部的位置进行交换，再对虚部求反即可。

复数乘法运算量可由下列公式进行计算

式中：N代表FFT点数；s代表旋转因子所在的阶段；k代表基2k算法的指数；n代表基2k算法所合并出来常数旋转因子W_constant的指数，例如，基23算法合并出来的W8，其n值为3(2n=8→n=3)。

以计算基23算法128点FFT为例，其中W8为算法合并出来的W_constant,需要利用式(2)计算它的复数乘法运算量,而W128和W16为普通旋转因子，其复数乘法运算量用式(1)来计算。因此W8的复数乘法运算量为32，W128的复数乘法运算量为104，W16的复数乘法运算量48。从表2可以看出，混合基-24-23算法拥有最简单的旋转因子序列，同时复数乘法的运算量也是最少的。因此，本文的设计方案采用混合基-24-23算法。

2 设计方案

图1所示为混合基-24-23算法的128点SDF流水线结构图。图中⨂代表复数乘法运算；BFI和BFII代表两种类型的蝶形运算单元；CLK是整个架构的控制时钟，它由7位计数器产生。在整个设计过程中，复数乘法运算都采用CSD常数乘法器来实现。

图1 混合基-24-23算法128点SDF结构图

Fig.1 Block diagram of 128-point FFT with mixed radix-24-23 algorithm

2.1　蝶形单元

图2所示为两种类型的蝶形单元详细架构，作为FFT处理器中必不可少的部分，主要用来执行复杂的加法和减法操作，图2中的xr(n)和xr(n+N/2)对应与输入复数序列实部，而xi(n)和xi(n+N/2)则对应输入复数序列的虚部。Zr(n),Zr(n+N/2),Zi(n)和Zi(n+N/2)对应于输出复数序列的实部和虚部。值得注意的是，I型蝶形单元对输入序列只进行简单的复数加减法运算，而II型蝶形单元除了需要进行必要的复数加减法运算以外，还需要额外的 “-j”运算。因此，在硬件实现上比I型蝶形单元多出了选择单元与相应的控制逻辑电路。

图2 蝶形单元架构

Fig.2 Block diagram of butterfly structure

2.2　W8i-CSD常数乘法器单元

实现输入序列与旋转因子W8i的复数乘法运算，只需要考虑3个旋转因子常数值W81,W82，W83，由于W82=-j,它的复数乘法运算由蝶形单元即可完成，而W83等于-jW81。因此，只需知道常数值W81即可。基于最小化硬件资源消耗的考虑，采用CSD表示法以及子模块共享方案来降低硬件成本。为了保持一定的量化信噪比，将旋转因子参数设置为12位字长。如果继续提高旋转因子参数的字长，量化信噪比并无显著的提高，反而会大大增加硬件开销^[1]。图3为计算旋转因子W8i的12位字长的CSD表示，椭圆圈起的部分为子表达式共享模块“101”。图4所示为W8i-CSD常数乘法器架构图，映射电路只需2个2选1数据选择器就可获得相应正确的结果。编译报告显示W8i-CSD常数乘法器资源消耗只有布斯乘法器的11%。

图3 12位字长W8i的CSD表示

Fig.3 CSD representation for W8i with 12-bit word-length

图4 W8i-CSD常数乘法器架构

Fig.4 Structure of W8i-CSD constant multiplier

2.3　W16i-CSD常数乘法器单元

对于输入序列与旋转因子W16i的乘法运算，总共需要考虑7个旋转因子常数值：W160，W161，W162，W163，W164，W166，和W169。其中W160和W164分别等于1和-j，它们的复数乘法运算通过蝶形单元就可以完成。而对于剩下的旋转因子而言，只需知道3个相关数值：0.923 9，0.382 7和0.707 1即可。这3个数值正好对应于W161，W162，和W163 3个复数的实部数值Re{W161}，Re{W162}和Re{W163}。表3所示为所有7个旋转因子常数值与Re{W161}，Re{W162}和Re{W163}关系式。

图5所示为旋转因子计算W16i的12位字长的CSD表示，其中椭圆圈起的“101”和“1¯01¯”部分为子表达式共享模块。图6所示为W16i常数乘法器详细的架构图，从图中可知，选择恰当的控制信号“SEL”和“SEL2”，便可以得到输入序列与旋转因子W16i计算后的结果。编译报告显示，W16i-CSD常数乘法器只有布斯乘法器的28%。由此可见，随着CSD常数乘法器所需旋转因子常数个数的增加，乘法器所要消耗的资源也会不断提高。

图5 12位字长W16i的CSD表示

Fig.5 CSD representation for W16i with 12-bit word-length

图6 W16i-CSD常数乘法器架构

Fig.6 Structure of W16i-CSD constant multiplier

2.4　新型W128i串接CSD常数乘法器单元

图7所示为旋转因子的1/8特性，根据此特性可将旋转因子的常数值的个数降低为原来的1/8。对于WNi来说，利用此特性，所需旋转因子常数值的个数仅仅为N/8。

图7 旋转因子对称性映射图

Fig.7 Symmetric region mapping of twiddle factor

一般来说，当旋转因子常数值的个数过多，直接利用CSD常数乘法器处理输入序列与旋转因子的复数乘法运算往往比普通布斯乘法器在硬件资源消耗上更高。因此，为了减少旋转因子常数值个数，提出了新型串接CSD常数乘法器的方案。串接CSD常数乘法器将复数乘法运算拆解成两阶段复数乘法运算，以达到降低旋转因子常数值个数的目的，从而降低乘法器的资源消耗。虽然串接CSD常数乘法器能够减少旋转因子常数值的个数，但是仅仅局限于完成输入序列、旋转因子与W128i,W256i和W512i的复数乘法运算。

以本文设计对象128点串接CSD乘法器为例，首先，利用1/8对称特性，将旋转因子常数值的个数降低到16个。然后，对旋转因子的指数i进行分解，分解方案为i=4i1+i2,i1=1~4,i2=0~3，旋转因子常数值的个数由16个减少为8个。如果要实现输入序列与W12813进行复数乘法运算，令i1=3，i2=1(W12813=W1284×3W1281),输入序列先与W12812进行复数乘法运算，再与W1281进行复数乘法运算，得到最终的输出结果。图8所示为计算旋转因子W128i 12位字长的CSD表示，其中椭圆圈起的部分是3组子表达式共享模块：椭圆圈起的“101”，椭圆圈起的“101¯”和椭圆圈起的“10001¯”。

图8 12位字长W128i的CSD表示

Fig.8 CSD representation for W128i with 12-bit word-length

图9(a)所示为W128i串接CSD乘法器的详细架构图，其中子表达式共享模块由加法单元和位移单元实现，长方形的箱体模块为右移单元，通过简单的硬件连接被放置在乘法器单元恰当的位置，10个4选1数据选择器为选择正确的输出结果。为了减少关键路径(Critical path, CP)，在两阶段CSD乘法器单元中间插入了流水线寄存器，如图9(b)所示。因此，FFT处理器的计算时间大大缩短，能够满足实时处理的需求。利用映射电路模块获得其他区域(如图7所示B~H区域)的旋转因子与输入序列相乘的结果。编译报告显示，本文提出的新型串接128点CSD乘法器硬件资源消耗只有普通布斯乘法器的59%，而且无需ROM对旋转因子的常数值进行存储，进一步降低了硬件资源的消耗。

图9 128点串接CSD常数乘法器详细架构

Fig.9 Detailed structure of 128-point cascade CSD constant multiplier

3 结果与比较

本文方案基于QUARTUS PRIME工具软件进行开发，使用Verilog语言进行设计。表4所示为不同方案128点FFT计算量的比较，包括了布斯乘法器使用量，CSD常数乘法器使用量，复数加法器使用量，计算时间以及延迟的比较。本文的设计方案计算时间为6TA+3TMUX+2TN,表4中TA代表加法单元运算所需时间，TMUX代表选择器单元运算所需要时间，TN代表取补码运算所需时间，TM代表乘法单元运算所需时间。由于本文的设计方案只利用CSD常数乘法器来完成复数乘法运算，因此只需考虑加法单元，取补码单元以及选择单元的计算时间。由于乘法单元计算所需时间要高于加法单元计算所需时间。因此，本文方案的计算时间同其他方案一样能够满足128点FFT处理器实时处理的需求。表5所示为不同设计方案逻辑单元使用量，寄存器使用量，记忆体单元使用量和动态功耗的比较。设计的输入字长设置为12位，输出字长设置为22位，器件家族选择的是 Cyclone 10 LP，功率评估等级(Power estimation confidence,PEC)为高。编译报告显示，对比于其他方案^[8,9,10,11]，本文的设计方案至少可节省逻辑单元使用量40%,寄存器使用量3%，记忆体单元的使用量14%。同时，基于本文设计方案的128点FFT处理器的动态功耗仅仅为5.59mW。图10所示为基于MODELSIM RTL级仿真结果(输入序列的实部和虚部设定为1~128),与MATLAB计算的结果一致，证实了本设计方案的有效性。

图10 基于本文方案的128点FFT处理器RTL级仿真结果

Fig.10 RTL level simulation result of 128-point FFT processor based on proposed scheme

4 结束语

本文针对于128点FFT处理器的设计，算法上采用了混合基-24-23算法,硬件实现上采用了SDF架构，新型串接CSD常数乘法器替代传统的布斯乘法器完成与旋转因子W128i的复数乘法运算，使得整个FFT处理器的复数乘法运算均由CSD常数乘法器完成，大幅降低了硬件资源消耗和功耗。同时，给出了复数乘法运算量的计算公式，让设计者可以更容易地选择适合的基-2k算法对FFT处理器进行设计。编译报告的结果显示本文的设计方案对比于已存在的设计方案在实现128点FFT上有较大优势。

参考文献