于 建 趙炅柱

（1.河北民族師范學(xué)院物理與電子工程系，承德，067000；2.韓國圓光大學(xué)，益山，54538）

引 言

超寬帶技術(shù)廣泛應(yīng)用于短距離高速的數(shù)據(jù)傳輸。本文介紹了一種低硬件開銷的128點FFT處理器方案用于超寬帶系統(tǒng)。FFT處理器作為超寬帶系統(tǒng)中關(guān)鍵單元模塊，消耗著相當(dāng)大的硬件資源。因此，如何降低FFT單元模塊所占用的硬件資源成為近年來的研究熱點。

基-2算法作為最著名的FFT算法，由于其簡單的蝶形架構(gòu)應(yīng)用于FFT模塊的硬件實現(xiàn)，可以降低硬件資源的開銷，但是隨著FFT點數(shù)的增加，它所需要的復(fù)雜乘法運算量會變得相當(dāng)巨大[1]。隨后，基-22,基-23,和基-24相繼被提出，以上這些算法被統(tǒng)稱為基-2k算法[2-4]?；?2k算法具有與基-2算法一樣簡單的蝶形架構(gòu)，同時又能夠大大降低旋轉(zhuǎn)因子(Twiddle factor,TF)的計算量，因此，非常適合FFT的硬件實現(xiàn)。不過，隨著k值的增加基-2k算法的優(yōu)勢變得越來越小，這是由于所能利用的對稱子項變得越來越少[5]。而且，高k值的基-2k算法可以用低k值的混合基-2k算法替代，表1為512點混合基-24-23算法和改良基-25算法[6]的詳細旋轉(zhuǎn)因子分布。仔細觀察表1的旋轉(zhuǎn)因子序列，容易發(fā)現(xiàn)如果以W512為軸，將兩邊的旋轉(zhuǎn)因子互換位置，就會得到同樣旋轉(zhuǎn)因子序列的分布。因此，本文的設(shè)計方案只考慮當(dāng)k≤ 4時的基-2k算法。

在以往的研究過程中，不同的FFT架構(gòu)被提出。在這些架構(gòu)中，流水線架構(gòu)由于其較高的吞吐量以及適中的硬件成本得到了廣泛的應(yīng)用。流水線FFT處理器架構(gòu)一般分為兩類：多路徑延遲轉(zhuǎn)換(Multi-path delay commutator,MDC)和單路徑延遲反饋(Single-path delay feedback,SDF)[7]。MDC架構(gòu)同時支持M路并行輸入數(shù)據(jù)，數(shù)據(jù)吞吐量是SDF架構(gòu)的M倍，但是其對數(shù)據(jù)路徑、FFT點數(shù)以及基-2k算法都有限制。另外，MDC架構(gòu)中所需的存儲器和復(fù)雜乘法器都比SDF架構(gòu)多。所以，MDC架構(gòu)能完成較高數(shù)據(jù)吞吐率，而SDF架構(gòu)需要較少的存儲器和硬件成本。為了獲取更低的硬件開銷，本文的設(shè)計方案使用SDF架構(gòu)。

一般來說，對于N點FFT(N＞64)都會采用布斯乘法器來處理序列與旋轉(zhuǎn)因子WiN的復(fù)數(shù)乘法運算。本文提出了一種新型串接CSD常數(shù)乘法器來實現(xiàn)序列與Wi128的運算，一方面能夠進一步降低硬件資源的開銷，另一方面無需任何只讀存儲器(Read only memory,ROM)對旋轉(zhuǎn)因子常數(shù)值進行存儲。

表1 512點混合基-24-23算法和改良基-25算法旋轉(zhuǎn)因子序列分布Tab.1 Sequence distribution of 512-point FFT twiddle factor for mixed radix-24-23and modified radix-25

1 算法選擇

利用基-2k算法實現(xiàn)128點FFT包括6個旋轉(zhuǎn)因子序列，表2給出了針對基-2k算法的詳細旋轉(zhuǎn)因子序列分布以及復(fù)數(shù)乘法的運算量。其中-j的運算為普通運算，只需對輸入序列實部和虛部的位置進行交換，再對虛部求反即可。

復(fù)數(shù)乘法運算量可由下列公式進行計算

式中：N代表FFT點數(shù)；s代表旋轉(zhuǎn)因子所在的階段；k代表基2k算法的指數(shù)；n代表基2k算法所合并出來常數(shù)旋轉(zhuǎn)因子Wconstant的指數(shù)，例如，基23算法合并出來的W8，其n值為3(2n=8 → n=3)。

表2 128點基-2k算法旋轉(zhuǎn)因子序列分布Tab.2 Sequence distribution of 128-point FFT twiddle factor for radix-2k

以計算基23算法128點FFT為例，其中W8為算法合并出來的Wconstant,需要利用式(2)計算它的復(fù)數(shù)乘法運算量,而W128和W16為普通旋轉(zhuǎn)因子，其復(fù)數(shù)乘法運算量用式(1)來計算。因此W8的復(fù)數(shù)乘法運算量為32，W128的復(fù)數(shù)乘法運算量為104，W16的復(fù)數(shù)乘法運算量48。從表2可以看出，混合基-24-23算法擁有最簡單的旋轉(zhuǎn)因子序列，同時復(fù)數(shù)乘法的運算量也是最少的。因此，本文的設(shè)計方案采用混合基-24-23算法。

2 設(shè)計方案

圖1所示為混合基-24-23算法的128點SDF流水線結(jié)構(gòu)圖。圖中?代表復(fù)數(shù)乘法運算；BFI和BFII代表兩種類型的蝶形運算單元；CLK是整個架構(gòu)的控制時鐘，它由7位計數(shù)器產(chǎn)生。在整個設(shè)計過程中，復(fù)數(shù)乘法運算都采用CSD常數(shù)乘法器來實現(xiàn)。

圖1 混合基-24-23算法128點SDF結(jié)構(gòu)圖Fig.1 Block diagram of 128-point FFT with mixedradix-24-23algorithm

2.1 蝶形單元

圖2 所示為兩種類型的蝶形單元詳細架構(gòu)，作為FFT處理器中必不可少的部分，主要用來執(zhí)行復(fù)雜的加法和減法操作，圖2中的xr(n)和xr(n+N/2)對應(yīng)與輸入復(fù)數(shù)序列實部，而xi(n)和xi(n+N/2)則對應(yīng)輸入復(fù)數(shù)序列的虛部。Zr(n),Zr(n+N/2),Zi(n)和Zi(n+N/2)對應(yīng)于輸出復(fù)數(shù)序列的實部和虛部。值得注意的是，I型蝶形單元對輸入序列只進行簡單的復(fù)數(shù)加減法運算，而II型蝶形單元除了需要進行必要的復(fù)數(shù)加減法運算以外，還需要額外的“-j”運算。因此，在硬件實現(xiàn)上比I型蝶形單元多出了選擇單元與相應(yīng)的控制邏輯電路。

圖2 蝶形單元架構(gòu)Fig.2 Block diagram of butterfly structure

圖3 12位字長的CSD表示Fig.3 CSD representation forwith 12-bit word-length

圖4 CSD常數(shù)乘法器架構(gòu)Fig.4 Structure of-CSD constant multiplier

表3 旋轉(zhuǎn)因子的7組常數(shù)值Tab.3 Sven constant values of twiddle factor

表3 旋轉(zhuǎn)因子的7組常數(shù)值Tab.3 Sven constant values of twiddle factor

常數(shù)值 關(guān)系式W0 16 W1 16 W2 16 W3 16 W4 16 W6 16 W9 16 1 Re{W1 16}-jRe{W3 16}Re{W2 16}-jRe{W2 16}Re{W3 16}-jRe{W1 16}-j(=-j×W0 16)-Re{W2 16}-jRe{W2 16}(=-j×W2 16)-Re{W1 16}+jRe{W3 16}(=-1×W1 16)

圖5 12位字長的CSD表示Fig.5 CSD representation forwith 12-bit word-length

圖6 -CSD常數(shù)乘法器架構(gòu)Fig.6 Structure of-CSD constant multiplier

2.4 新型串接CSD常數(shù)乘法器單元

圖7 所示為旋轉(zhuǎn)因子的1/8特性，根據(jù)此特性可將旋轉(zhuǎn)因子的常數(shù)值的個數(shù)降低為原來的1/8。對于來說，利用此特性，所需旋轉(zhuǎn)因子常數(shù)值的個數(shù)僅僅為N/8。

一般來說，當(dāng)旋轉(zhuǎn)因子常數(shù)值的個數(shù)過多，直接利用CSD常數(shù)乘法器處理輸入序列與旋轉(zhuǎn)因子的復(fù)數(shù)乘法運算往往比普通布斯乘法器在硬件資源消耗上更高。因此，為了減少旋轉(zhuǎn)因子常數(shù)值個數(shù)，提出了新型串接CSD常數(shù)乘法器的方案。串接CSD常數(shù)乘法器將復(fù)數(shù)乘法運算拆解成兩階段復(fù)數(shù)乘法運算，以達到降低旋轉(zhuǎn)因子常數(shù)值個數(shù)的目的，從而降低乘法器的資源消耗。雖然串接CSD常數(shù)乘法器能夠減少旋轉(zhuǎn)因子常數(shù)值的個數(shù)，但是僅僅局限于完成輸入序列、旋轉(zhuǎn)因子與,和的復(fù)數(shù)乘法運算。

圖7 旋轉(zhuǎn)因子對稱性映射圖Fig.7 Symmetric region mapping of twiddle factor

以本文設(shè)計對象128點串接CSD乘法器為例，首先，利用1/8對稱特性，將旋轉(zhuǎn)因子常數(shù)值的個數(shù)降低到16個。然后，對旋轉(zhuǎn)因子的指數(shù)i進行分解，分解方案為i=4i1+i2,i1=1～4,i2=0～3，旋轉(zhuǎn)因子常數(shù)值的個數(shù)由16個減少為8個。如果要實現(xiàn)輸入序列與進行復(fù)數(shù)乘法運算，令i1=3，i2=1(=),輸入序列先與進行復(fù)數(shù)乘法運算，再與進行復(fù)數(shù)乘法運算，得到最終的輸出結(jié)果。圖8所示為計算旋轉(zhuǎn)因子12位字長的CSD表示，其中橢圓圈起的部分是3組子表達式共享模塊：橢圓圈起的“101”，橢圓圈起的“10”和橢圓圈起的“1000”。

圖8 12位字長的CSD表示Fig.8 CSD representation forwith 12-bit word-length

3 結(jié)果與比較

本文方案基于QUARTUS PRIME工具軟件進行開發(fā)，使用Verilog語言進行設(shè)計。表4所示為不同方案128點FFT計算量的比較，包括了布斯乘法器使用量，CSD常數(shù)乘法器使用量，復(fù)數(shù)加法器使用量，計算時間以及延遲的比較。本文的設(shè)計方案計算時間為6TA+3TMUX+2TN,表4中TA代表加法單元運算所需時間，TMUX代表選擇器單元運算所需要時間，TN代表取補碼運算所需時間，TM代表乘法單元運算所需時間。由于本文的設(shè)計方案只利用CSD常數(shù)乘法器來完成復(fù)數(shù)乘法運算，因此只需考慮加法單元，取補碼單元以及選擇單元的計算時間。由于乘法單元計算所需時間要高于加法單元計算所需時間。因此，本文方案的計算時間同其他方案一樣能夠滿足128點FFT處理器實時處理的需求。表5所示為不同設(shè)計方案邏輯單元使用量，寄存器使用量，記憶體單元使用量和動態(tài)功耗的比較。設(shè)計的輸入字長設(shè)置為12位，輸出字長設(shè)置為22位，器件家族選擇的是Cyclone 10 LP，功率評估等級(Power estimation confidence,PEC)為高。編譯報告顯示，對比于其他方案[8-11]，本文的設(shè)計方案至少可節(jié)省邏輯單元使用量40%,寄存器使用量3%，記憶體單元的使用量14%。同時，基于本文設(shè)計方案的128點FFT處理器的動態(tài)功耗僅僅為5.59 mW。圖10所示為基于MODELSIM RTL級仿真結(jié)果(輸入序列的實部和虛部設(shè)定為1～128),與MATLAB計算的結(jié)果一致，證實了本設(shè)計方案的有效性。

圖9 128點串接CSD常數(shù)乘法器詳細架構(gòu)Fig.9 Detailed structure of 128-point cascade CSD constant multiplier

表4 不同方案128點FFT計算量比較Tab.4 Comparison of various schemes computation for 128-point FFT

表5 不同方案綜合結(jié)果比較Tab.5 Performance of the proposed scheme compared with previous implementation

圖10 基于本文方案的128點FFT處理器RTL級仿真結(jié)果Fig.10 RTL level simulation result of 128-point FFT processor based on proposed scheme

4 結(jié)束語

本文針對于128點FFT處理器的設(shè)計，算法上采用了混合基-24-23算法,硬件實現(xiàn)上采用了SDF架構(gòu)，新型串接CSD常數(shù)乘法器替代傳統(tǒng)的布斯乘法器完成與旋轉(zhuǎn)因子Wi128的復(fù)數(shù)乘法運算，使得整個FFT處理器的復(fù)數(shù)乘法運算均由CSD常數(shù)乘法器完成，大幅降低了硬件資源消耗和功耗。同時，給出了復(fù)數(shù)乘法運算量的計算公式，讓設(shè)計者可以更容易地選擇適合的基-2k算法對FFT處理器進行設(shè)計。編譯報告的結(jié)果顯示本文的設(shè)計方案對比于已存在的設(shè)計方案在實現(xiàn)128點FFT上有較大優(yōu)勢。