于 建 趙炅柱

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

引 言

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

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

在以往的研究過(guò)程中，不同的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)同時(shí)支持M路并行輸入數(shù)據(jù)，數(shù)據(jù)吞吐量是SDF架構(gòu)的M倍，但是其對(duì)數(shù)據(jù)路徑、FFT點(diǎn)數(shù)以及基-2k算法都有限制。另外，MDC架構(gòu)中所需的存儲(chǔ)器和復(fù)雜乘法器都比SDF架構(gòu)多。所以，MDC架構(gòu)能完成較高數(shù)據(jù)吞吐率，而SDF架構(gòu)需要較少的存儲(chǔ)器和硬件成本。為了獲取更低的硬件開(kāi)銷，本文的設(shè)計(jì)方案使用SDF架構(gòu)。

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

表1 512點(diǎn)混合基-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算法實(shí)現(xiàn)128點(diǎn)FFT包括6個(gè)旋轉(zhuǎn)因子序列，表2給出了針對(duì)基-2k算法的詳細(xì)旋轉(zhuǎn)因子序列分布以及復(fù)數(shù)乘法的運(yùn)算量。其中-j的運(yùn)算為普通運(yùn)算，只需對(duì)輸入序列實(shí)部和虛部的位置進(jìn)行交換，再對(duì)虛部求反即可。

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

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

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

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

2 設(shè)計(jì)方案

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

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

2.1 蝶形單元

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

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

圖3 12位字長(zhǎng)的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位字長(zhǎng)的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ù)值的個(gè)數(shù)降低為原來(lái)的1/8。對(duì)于來(lái)說(shuō)，利用此特性，所需旋轉(zhuǎn)因子常數(shù)值的個(gè)數(shù)僅僅為N/8。

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

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

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

圖8 12位字長(zhǎng)的CSD表示Fig.8 CSD representation forwith 12-bit word-length

3 結(jié)果與比較

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

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

表4 不同方案128點(diǎn)FFT計(jì)算量比較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點(diǎn)FFT處理器RTL級(jí)仿真結(jié)果Fig.10 RTL level simulation result of 128-point FFT processor based on proposed scheme

4 結(jié)束語(yǔ)

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