快速傅里叶变换（FFT）是数字信号处理领域应用最广泛的算法，其广泛应用于数字通信、雷达系统、成像系统以及图像处理系统中。随着现代数字信号处理技术的发展，系统对于FFT的数据处理精度有着更高的要求。同时，不同的应用环境需要使用不同点数的FFT，对于当前的数字信号处理系统来说，也存在不同点数FFT动态实时切换的应用场景。因此，需要高精度、点数可配置的FFT处理器。

FFT算法发展成熟，存在多种FFT算法，如基2、基4、基8以及混合基等算法[1,2,3,4,5,6,7,8,9,10,11,12]。对于基2算法，FFT的运算级数长、运算时间长，但优点在于硬件实现简单；对于基8算法，FFT的运算级数短，其运算所需时间短，但其硬件实现复杂度高；基4算法的运算时间和硬件复杂度介于两者之间。基2算法可以实现任意2n点FFT运算；基4算法可以实现任意4n点FFT运算；基8算法可以实现任意8n点FFT运算。为了实现任意2n点FFT运算，且保证运算时间相对较快，本文采用基2-基4混合基实现对任意2n点FFT的运算。

为了加速FFT，存在多种硬件微架构来实现FFT处理器，其中最典型的就是基于存储器和蝶形运算单元共享（hardware-sharing）的FFT处理器[13,14]和基于流水线（pipelined）的FFT处理器[15,16,17]。对于hardware-sharing FFT处理器，其通常采用ping-pang RAM的方案实现[18,19]，该方案可有效地节省资源消耗，但其运算时间更长。pipelined FFT处理器比hardware-sharing FFT处理器面积大，但其运算时间更短，为了获得高速的FFT处理器，本文设计了一种基于pipelined的FFT处理器。

同时，为了提高运算精度，本文首次提出了类浮点的概念，设计了一种用于提高运算精度的类浮点运算单元，在不增加运算资源的条件下提高FFT的运算精度。传统的块浮点运算需要在每级进行动态截位，因此数据的低位信息被舍弃，导致数据精度下降。采用本文设计的类浮点运算方法，数据的低位信息可以得到有效利用。与传统pipelined FFT处理器以及经典块浮点FFT处理器相比，本文提出的类浮点方案具有更优的PPA性能。

1、算法背景

为了减少FFT的运算时间，同时实现任意2n点FFT运算，本文采用基于基2-基4混合基的FFT算法实现可配置FFT处理器。下面以32点FFT为例介绍其推导过程：

式中：N是一个复合数，N=r1×r2×r3，按照混合基的形式将N分解为N=4×4×2=32，进一步将n按式（2）表示：

式中：n0=0,1;n1=0,1,2,3;n2=0,1,2,3;n<N。

同样，可将频率变量k用式（3）表示：

式中：k0=0,1,2,3;k1=0,1,2,3;k2=0,1。

令上式中等号左边的，则X (k)进一步变化，如下式所示：

令上式中等号左边的，此时2⋅n1⋅k0为进入第2级的旋转因子。此外，由于N=32，因此上式中等号左边的，则X (k)进一步变化，如下式所示：

令上式中等号左边的，则X (k)进一步变化，如下式所示：

令上式中等号左边的，此时4⋅n0⋅k1+n0⋅k0为进入第3级的旋转因子。则X (k)进一步变化，如下式所示：

按上述分解，得到32点混合基信号流图如图1所示。若要得到顺序结果，需要对上式中X3(k0,k1,k2)进行倒位序操作。

2、FFT处理器微架构

2.1 FFT处理器整体架构及其运算流程

本文所述8～2 048点可配置FFT处理器核心架构如图2所示，其由5级基4模块和1级基2模块组成。

图1 32点基4/2混合基FFT信号流图  

图2中：第1个基4模块用于完成FFT信号流图对应的第一级基4运算；第2个基4模块用于完成FFT信号流图的第二级基4运算；第3个基4模块用于完成FFT信号流图的第三级基4运算；第4个基4模块用于完成FFT信号流图的第四级基4运算；第5个基4模块用于完成FFT信号流图的第五级基4运算；最后1个基2模块用于完成FFT信号流图的最后1级基2运算。

如果运算8点FFT，则只有第1个基4模块和最后一个基2模块一同工作，通过多路选择器使上述每个模块的输出作为下一个模块的输入，最后1个基2模块的输出作为8点FFT的运算结果输出；如果运算16点FFT，则只有前2个基4模块工作，每个模块的输出作为下一个模块的输入，第2个基4模块的输出作为16点FFT的运算结果输出；如果运算32点FFT，则前2个基4模块和最后一个基2模块一同工作，每个模块的输出作为下一个模块的输入，最后1个基2模块的输出作为32点FFT的运算结果输出；如果运算64点FFT，则只有前3个基4模块工作，每个模块的输出作为下一个模块的输入，第3个基4模块的输出作为64点FFT的运算结果输出；如果运算128点FFT，则前3个基4模块和最后一个基2模块一同工作，每个模块的输出作为下一个模块的输入，最后1个基2模块的输出作为128点FFT的运算结果输出。对于其余点数的FFT运算，如256点FFT、512点FFT、1 024点FFT以及2 048点FFT运算，其运算流程与上述类似，即通过利用图2中的两个多路选择器Mux1和Mux2，选择合适的数据通路以完成相应点数的FFT运算。

图2 8～2 048点可配置FFT处理器核心微架构   

图3详述了每个基4模块以及基2模块的具体结构以及数据流在基4模块和基2模块的运算流程。以32点FFT为例，对于第1个基4模块，32个输入数据顺次输入到基4模块。输入数据1～8存储到基4模块的第1个输入存储器中；输入数据9～16存储到基4模块的第2个输入存储器中；输入数据17～24存储到基4模块的第3个输入存储器中。之后，输入数据25～32顺次输入到基4模块，此时输入1～8、9～16、17～24顺次并行从存储器中输出，这四组数据同时输入给基4蝶形运算单元进行蝶形运算。蝶形运算8个周期会产生32个结果，每个周期会产生4个运算结果，其中每周期的第1个运算结果输出给下一级基4模块，第2～4个运算结果分别输出到输出存储器1～3中，当前8个数据输出完毕后，输出存储器1～3中存储的数据顺次输出给下一级基4模块。对于后续基4模块以及基2模块的运算，按照相似的办法进行。该执行过程与FFT信号流图一致，采用此方法即可完成FFT运算，其是基于流水线方式实现的。

2.2 类浮点蝶形运算的实现方案

采用传统浮点运算会增加设计复杂度，采用传统的块浮点运算又存在数据精度的损失，为了降低设计复杂度，同时提高FFT处理器的精度，本文在蝶形运算设计时根据浮点运算的思路，提出了一种类浮点蝶形运算单元。

图4为四点基本基4运算算法框图。其中：a、b、c、d、A、B、C、D均为复数，根据输入数据a、b、c、d得到基4运算的结果A、B、C、D如式（4）所示：

图3 各级蝶形运算数据流   

图4 基本蝶形运算算法框图   

不同级数据输入时，需要乘以蝶形因子，因此在进入基4基本运算单元之前需要进行复数乘法。整体的基4蝶形运算单元如图5所示。

对于8～2 048点FFT处理器，其输入数据为16 bit有符号整数型数据，即输入数据格式为int16。如采用传统的基于定点的FFT处理器方法，随着运算级数的增加，各级蝶形运算单元的输入数据位宽也会随之增加，如果进行2 048点FFT运算时，其最后一级输入数据位宽为27 bit。当设计更大点数的FFT处理器时，其输入数据位宽会进一步增加，进而导致FFT处理器面积显著增加。

当用块浮点实现FFT处理器时，通过对每一级FFT处理器进行动态的截位，可以使每一级蝶形运算单元的输入数据位宽保持在16 bit，但是动态截位会使得运算结果的低位数据被直接截断，造成低位数据丢失，进而影响运算精度。

图5 基4蝶形运算单元   

为了减少FFT处理器的面积，同时尽可能地提高FFT处理器的运算精度，本文借鉴IEEE 754中使用的尾数+指数的浮点数据表示方式，采用数据的整数部分+指数部分来表示INT型数据。文中称此种方法为类浮点方法，虽然称之为类浮点，但实际上是采用类似浮点的表示方式描述更大动态范围的整数数据。其输入数据的格式为：整数部分加上指数部分，如图6所示。

图6 类浮点数据表示方法  

在图6中，整数部分由16 bit有符号数表示，指数部分由4 bit无符号数表示。对于图6，如果其整数部分数据为x，指数部分数据为y，则其表示的真实INT型数据值为x⋅2y。如20 bit的16进制数据h00082，其整数部分数据为8，指数部分数据为2，则其表示的数据值为82，即64。对于本文提出的数据表示方法，其表示的INT数据的范围为-32 768×215～32 767×215，即-1 073 741 824～1 073 709 056之间的整数。

利用本文提出的数据表示方法，对于不同的指数项，其精度不同，即其精度为2y,y为指数项值。如果指数项为0，则精度精确到1；如果指数项为1，则精度精确到2；如果指数项为2，则精度精确到4，依此类推。选取4 bit作为指数项的原因在于进行2 048点FFT运算时最大的位扩展为11，因此用4 bit数据即可覆盖其扩展范围。类浮点蝶形单元具体硬件结构如图7所示。

图7中的比较器用于对进行基4蝶形运算的4个输入数据的4个指数部分进行比较，获得这4个输入数据指数部分的最大值，根据该指数最大值对4个输入数据归一化到同一指数。

图7 类浮点蝶形运算单元  

图7中选择移位器实质上是4个多路选择器，分别控制4路数据的整数部分进行移位，多路选择器的选择端为4个数据的最大指数值减去自身的指数，该值如果为0则整数部分不右移，如果为1则整数部分符号右移1位，为2则整数部分符号右移2位，以此类推。此过程完毕后，4个输入数据归一化到同一量程，其具有相同的指数。

将选择移位器的输出和旋转因子同时输入到图7所示复数乘法器中，由于旋转因子中绝对值最大的旋转因子为1，且为1的旋转因子必定存在，为了归一化量程，乘法器的运算结果直接截掉低位，此时输出数据为16 bit。

选择移位器的运算结果通过图7中的基本基4单元完成基本基4运算，基本基4单元只进行加法运算，其每个输出会产生3 bit数据扩展，输出结果为19 bit。

将基本基4单元的输出通过图7中的取绝对值模块，获得这组输出数据的绝对值。绝对值结果通过移位值产生器，将绝对值后的4路数据的高3 bit数据进行或运算，或运算的结果可获得有效数据的信息。根据或运算结果对基本基4单元的19 bit输出数据进行移位，如果最高位为1，则将这4路整数数据的高16 bit数据输出，同时输出3作为移位值；如果第18 bit为1，则输出[17∶2]，同时输出2作为移位值；如果第17 bit为1，则输出[16∶1]，同时输出1作为移位值；否则输出[15∶0]，同时输出0作为移位值。将此时获得的移位值与图7中比较器获得的4个数据的最大指数项相加获得最终运算结果的指数部分，此时运算结果再次表示为类浮点格式。

3、实验结果与分析

3.1 精度比较

利用Matlab对本文所使用的FFT处理器进行建模，其中复数乘法采用本文提出的类浮点方法。同时，利用Matlab对采用经典块浮点运算单元的FFT处理器进行建模。分别为类浮点模型和经典块浮点模型生成激励，并与FFT的黄金值进行比较。本设计为8～2 048点可配置FFT处理器，选择512点FFT进行精度比较。生成6组长度为512的激励数据作为512点FFT处理器的输入数据。第一组输入数据为2,3，…，513，是斜率为1的线性信号；第二组输入数据为20,30，…，5 130，是斜率为10的线性信号；第三组数据是128,128，…，128，是斜率为0的线性信号；第四组数据是32 768,32 768，…，32 768，是斜率为0的线性信号；第五组数据为正弦信号，其振幅为212-1；第六组数据也是正弦信号，其振幅为215-1。

如表1所示，当输入数据比较小时，两者具有相同的精度。但是，随着输入数据值的增加，本文采用的类浮点相比传统块浮点来说具有更高的精度。

表1 本文方案与传统块浮点方案实虚部误差分析%  

8～2 048点FFT处理器在执行512点FFT运算时，选择一组随机激励作为512点FFT的输入数据，其实部结果和Matlab黄金结果如图8所示。

其虚部结果与Matlab黄金结果如图9所示。

8～2 048点FFT处理器功能仿真波形图如图10中的verdi波形所示，本仿真中8～2 048点FFT配置执行1 024点FFT运算。

3.2 性能比较

通过在关键路径乘法器上插入寄存器，使得本文所设计的FFT处理器能够获得较高的工作频率。通过对乘法器使用门控单元，使得输入为0的数据不进行乘法运算；同时对0+0j、j、-1、-j这4种蝶形因子对应的乘法运算进行优化，使得乘法器的使用率进一步减少，进而降低功耗。

图8 实部运算结果对比   

图9 虚部运算结果对比  

本文设计的FFT处理器共有5个基4模块和1个基2模块。每个基4模块由3个复数乘法单元和4个复数加法单元组成；每个基2模块由1个复数乘法单元和1个复数加法单元组成，即本设计共有16个复数乘法单元和22个复数加法单元。每个复数乘法单元用于实现两个复数的乘法运算，每个复数加法单元产生一个复数运算结果。FFT运算的每一级都具备存储器用于存储这一级运算的输入数据和输出数据。每个基4模块有6个存储器，其中3个存储器用于存储输入数据，3个存储器用于存储输出数据。对于第1个基4模块，其每一个存储器的深度为512；对于第2个基4模块，其每一个存储器的深度为128；对于第3个基4模块，其每一个存储器的深度为32；对于第4个基4模块，其每一个存储器的深度为8；对于第5个基4模块，其每一个存储器的深度为2，此时使用寄存器即可。对于基2模块，其仅有一个深度为1的寄存器用于缓存输入数据。

图1 0 8～2 048点FFT处理器功能仿真波形图   

在每一级运算中，与输入数据伴随输入到蝶形运算单元中的数据还有蝶形因子，蝶形因子存储在ROM当中，其中基2模块中的ROM总深度为1 024；第2个基4模块中ROM总深度为16；第3个基4模块中ROM总深度为64；第4个基4模块中ROM总深度为256；第5个基4模块中ROM总深度为1 024。

本文所设计的8～2 048点可配置FFT处理器版图如图11所示。在55 nm工艺下，其工作频率为200 MHz，面积为1.1 mm2，工作电压为1.08 V，功耗为42.6 mW。

图1 1 8～2 048点FFT处理器版图   

表2给出了性能比较。为了公平比较，使用归一化公式（5）将各工艺下的面积归一化到同一标准。

表2展示了本文与经典块浮点FFT处理器以及传统pipeline型FFT处理器的性能比较。表2中文献[20]采用基于hardware-sharing的块浮点方法实现64点FFT处理器，其输入数据位宽为16，在180 nm工艺下，面积为0.626 7 mm2，最高工作频率为300 MHz，功耗为126.17 mW。利用归一化公式，将文献[20]归一化到55 nm工艺下，其归一化面积为0.058 mm2。考虑到文献[20]中FFT点数为64，而FFT的面积与FFT点数线性相关，如果采用文献[20]所示方法实现2 048点FFT，其归一化面积为1.856 mm2，且文献[20]使用的hardwaresharing方案本身是一种节省资源的方法，故本文相对于文献[20]面积更小。理论上，芯片制程越先进，其供电电压越低，动态功耗也越低。文献[20]在300 MHz下其功耗为126.17 mW，假设文献[20]采用55 nm工艺，则可近似认为其供电电压下降3.27倍，考虑到功耗与电压的平方相关，故可近似认为文献[20]在55 nm其功耗为11.79 mW；当其FFT点数变为2 048时，其功耗线性近似为377.28 mW，其功耗同样大于本文所述FFT的功耗。文献[20]具有更高的工作频率。综合比较本文与文献[20]的PPA性能，即频率/（面积*功耗），本文的PPA值为0.43，文献[20]的PPA值为4.26，故相对于经典块浮点FFT处理器，本文所提出的FFT处理器具有更好的综合性能。同时根据前述Matlab分析，本文相对于块浮点还具有精度优势。 

表2 性能比较  

表2中文献[21]为传统FFT处理器，其采用传统方法实现。文献[21]中的FFT处理器为输入数据位宽为32 bit的1 024点FFT处理器，其在65 nm下面积为3.6 mm2，其归一化面积为3.04 mm2；由于FFT点数与面积线性相关，采用文献[21]的方法实现2 048点FFT时，其等效归一化面积为6.09 mm2；进一步FFT数据位宽与面积线性相关，采用文献[21]方法实现20 bit输入数据，其最终等效面积为3.8 mm2，故本文相对于文献[21]面积更小。文献[21]在600 MHz下其功耗为60.3 mW，采用前述比较方法，得到文献[21]在相同标准（工艺、FFT点数、FFT输入数据位宽）下的等效功耗为54.2 mW，其功耗同样大于本文FFT的功耗。文献[21]具有更高的工作频率。综合比较本文与文献[21]的PPA性能，即频率/（面积*功耗），文献[21]的PPA值为2.91，故相对于文献[21]所述的经典FFT处理器，本文所提出的FFT处理器具有更优的综合性能。

综上所述，本文设计是实现FFT处理器的一种有效实现方案。

4、结语

本文采用类浮点运算单元实现基于流水线的FFT处理器，首次提出类浮点的数据格式，相比于传统的块浮点运算单元，在不增加资源消耗的情况下，采用类浮点运算单元的FFT处理器的运算精度得到了有效提高。同时，相比于传统块浮点FFT处理器和经典FFT处理器，本文所实现的FFT处理器具有更优的综合性能。此外，采用本文使用的基2/基4混合基流水线方法，使得该FFT处理器可以实现任意2n点的FFT运算，提高了其适用范围。因此本文所述方案是一种实现高精度、可变点流水线型FFT处理器的有效方案。

参考文献:

[20]吴斌,姜鑫,周玉梅.基于802.11a的FFT/IFFT处理器设计[J].微电子学与计算机,2011,28(4):61-64.

文章来源:潘于,田映辉,刘志哲等.基于混合基的类浮点可变点FFT处理器的ASIC实现[J].现代电子技术,2024,47(01):163-170.