基于混合基的類浮點可變點FFT 處理器的ASIC 實現

潘 于，田映輝，劉志哲，陳 濤，張 偉，申 奇

（1.海光信息技術股份有限公司，北京 100193；2.拓維電子科技（上海）有限公司，上海 201108；3.中國聯通智能城市研究院，北京 100048）

0 引 言

快速傅里葉變換（FFT）是數字信號處理領域應用最廣泛的算法，其廣泛應用于數字通信、雷達系統、成像系統以及圖像處理系統中。隨著現代數字信號處理技術的發展，系統對于FFT 的數據處理精度有著更高的要求。同時，不同的應用環境需要使用不同點數的FFT，對于當前的數字信號處理系統來說，也存在不同點數FFT 動態實時切換的應用場景。因此，需要高精度、點數可配置的FFT 處理器。

FFT算法發展成熟，存在多種FFT算法，如基2、基4、基8 以及混合基等算法[1-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-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

同樣，可將頻率變量k用式（3）表示：

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

按上述分解，得到32 點混合基信號流圖如圖1 所示。若要得到順序結果，需要對上式中X3(k0,k1,k2)進行倒位序操作。

2 FFT 處理器微架構

2.1 FFT 處理器整體架構及其運算流程

本文所述8~2 048 點可配置FFT 處理器核心架構如圖2 所示，其由5 級基4 模塊和1 級基2 模塊組成。

圖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 運算。

圖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 運算，其是基于流水線方式實現的。

圖3 各級蝶形運算數據流

2.2 類浮點蝶形運算的實現方案

采用傳統浮點運算會增加設計復雜度，采用傳統的塊浮點運算又存在數據精度的損失，為了降低設計復雜度，同時提高FFT處理器的精度，本文在蝶形運算設計時根據浮點運算的思路，提出了一種類浮點蝶形運算單元。

圖4 為四點基本基4 運算算法框圖。其中：a、b、c、d、A、B、C、D均為復數，根據輸入數據a、b、c、d得到基4運算的結果A、B、C、D如式（4）所示：

圖4 基本蝶形運算算法框圖

不同級數據輸入時，需要乘以蝶形因子，因此在進入基4 基本運算單元之前需要進行復數乘法。整體的基4 蝶形運算單元如圖5 所示。

圖5 基4 蝶形運算單元

對于8~2 048 點FFT 處理器，其輸入數據為16 bit有符號整數型數據，即輸入數據格式為int16。如采用傳統的基于定點的FFT處理器方法，隨著運算級數的增加，各級蝶形運算單元的輸入數據位寬也會隨之增加，如果進行2 048 點FFT 運算時，其最后一級輸入數據位寬為27 bit。當設計更大點數的FFT 處理器時，其輸入數據位寬會進一步增加，進而導致FFT處理器面積顯著增加。

當用塊浮點實現FFT 處理器時，通過對每一級FFT處理器進行動態的截位，可以使每一級蝶形運算單元的輸入數據位寬保持在16 bit，但是動態截位會使得運算結果的低位數據被直接截斷，造成低位數據丟失，進而影響運算精度。

為了減少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 類浮點蝶形運算單元

圖7 中的比較器用于對進行基4 蝶形運算的4 個輸入數據的4 個指數部分進行比較，獲得這4 個輸入數據指數部分的最大值，根據該指數最大值對4 個輸入數據歸一化到同一指數。

圖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 所示。

圖8 實部運算結果對比

其虛部結果與Matlab 黃金結果如圖9 所示。

圖9 虛部運算結果對比

8~2 048 點FFT 處理器功能仿真波形圖如圖10 中的verdi 波形所示，本仿真中8~2 048 點FFT 配置執行1 024 點FFT 運算。

圖10 8~2 048 點FFT 處理器功能仿真波形圖

3.2 性能比較

通過在關鍵路徑乘法器上插入寄存器，使得本文所設計的FFT 處理器能夠獲得較高的工作頻率。通過對乘法器使用門控單元，使得輸入為0 的數據不進行乘法運算；同時對0+0j、j、-1、-j 這4 種蝶形因子對應的乘法運算進行優化，使得乘法器的使用率進一步減少，進而降低功耗。

本文設計的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 的寄存器用于緩存輸入數據。

在每一級運算中，與輸入數據伴隨輸入到蝶形運算單元中的數據還有蝶形因子，蝶形因子存儲在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。

圖11 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 中文獻[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 處理器的有效方案。