于 建

(河北民族師范學(xué)院 物理與電子工程學(xué)院，河北 承德 067000)

0 引 言

隨著多媒體應(yīng)用在短距離無(wú)線傳輸方面日益增長(zhǎng)的需求，多年來(lái)針對(duì)60 GHz毫米波無(wú)線個(gè)人局域網(wǎng)(Wireless Personal Area Network,WPAN)通信技術(shù)的研究受到了廣泛的關(guān)注。IEEE802.15.3c任務(wù)組為60 GHz千兆比特WPAN系統(tǒng)制定了相應(yīng)標(biāo)準(zhǔn)，要求其提供超過(guò)2 Gb/s數(shù)據(jù)傳輸速率[1]。

在高速率WPAN系統(tǒng)的物理層設(shè)計(jì)中采用了正交頻分復(fù)用(Orthogonal Frequency Division Multiplexing,OFDM)調(diào)制技術(shù)，快速傅里葉變換(Fast Fourier Transform,FFT)處理器是OFDM系統(tǒng)中硬件復(fù)雜度最高的模塊。在基于OFDM調(diào)制技術(shù)的高速率WPAN系統(tǒng)中，一個(gè)OFDM符號(hào)一般由512個(gè)子載波組成，OFDM符號(hào)持續(xù)時(shí)間為222.22 ns。這就意味著要求所設(shè)計(jì)的FFT處理器至少提供2.304 Gsample/s的高數(shù)據(jù)吞吐量[2]。實(shí)際上為了獲得更好的帶寬效率，設(shè)計(jì)上FFT的點(diǎn)數(shù)一般都會(huì)超過(guò)512，這樣勢(shì)必導(dǎo)致需要更長(zhǎng)的字長(zhǎng)來(lái)維持一定的信號(hào)量化噪聲比(Signal to Quantization Noise Ratio,SQNR)，大幅增加了所需的硬件成本[3]。在實(shí)現(xiàn)高吞吐量的FFT處理器設(shè)計(jì)方面，許多研究都采用了多路徑負(fù)反饋流水線架構(gòu)(Multi-path Delay Feedback,MDF)[1-5]，其原理就是根據(jù)路徑數(shù)復(fù)制單路徑上的FFT處理器運(yùn)算模塊，但硬件成本會(huì)隨著路徑數(shù)的增加而成倍的增長(zhǎng)。因此，許多學(xué)者提出了不同的FFT算法用于降低單路徑上FFT運(yùn)算模塊的硬件復(fù)雜度，其中基-2k算法最為著名[6]?；?2k算法不論k值的大小，都擁有與基-2算法一樣簡(jiǎn)單的蝶形架構(gòu)，但不同的k值會(huì)導(dǎo)致其具有不同的旋轉(zhuǎn)因子復(fù)數(shù)乘法結(jié)構(gòu)[7],因此需要根據(jù)旋轉(zhuǎn)因子復(fù)數(shù)乘法的復(fù)雜度選擇最優(yōu)k值的基-2k算法用于優(yōu)化FFT處理器的設(shè)計(jì)。

為了有效降低硬件實(shí)現(xiàn)復(fù)雜度并保證高速率、高精度的數(shù)據(jù)傳輸，本文提出了一種基于改良基-26算法2 048點(diǎn)8路MDF FFT處理器設(shè)計(jì)方案，能夠提供2.6 Gsample/s高數(shù)據(jù)吞吐量并有效控制硬件成本,同時(shí)SQNR達(dá)到了36 dB。

1 算法選擇

N點(diǎn)離散傅里葉變換(Discrete Fourier Transform,DFT)定義如式(1)所示：

(1)

式中：WN為旋轉(zhuǎn)因子，其指數(shù)k和n分別代表頻域索引與時(shí)域索引。直接實(shí)現(xiàn)式(1)中的DFT會(huì)消耗大量的硬件成本和計(jì)算時(shí)間，因此眾多FFT算法被提出用于減少DFT的計(jì)算時(shí)間與硬件資源消耗。由于基-2k算法不但擁有與基-2算法一樣簡(jiǎn)單的蝶形單元架構(gòu)，同時(shí)還能減少旋轉(zhuǎn)因子復(fù)數(shù)乘法的運(yùn)算復(fù)雜度，因此常被用于FFT處理器的硬件實(shí)現(xiàn)上。本文提出了一種新型改良基-26算法用于2 048點(diǎn)FFT處理器的設(shè)計(jì)。

1.1 改良基-26 FFT算法

所提出的改良基-26算法采用7維度線性索引圖進(jìn)行表述，如式(2)和式(3)所示：

(2)

k=k1+2k2+4k3+8k4+16k5+32k6+64k7。

(3)

改良基-26算法可分為兩種方式進(jìn)行表達(dá)，方式1的因子計(jì)算公式如式(4)所示：

X(k1+2k2+4k3+8k4+16k5+32k6+64k7)=

(4)

(5)

X(k1+2k2+4k3+8k4+16k5+32k6+64k7)=

(6)

(7)

1.2 算法評(píng)估

由于負(fù)責(zé)旋轉(zhuǎn)因子復(fù)數(shù)乘法運(yùn)算的乘法器在FFT處理器中占用主要的硬件資源，因此選擇旋轉(zhuǎn)因子復(fù)雜度低的基-2k算法是十分必要的。表1所示為不同k值2 048點(diǎn)基-2kFFT算法旋轉(zhuǎn)因子復(fù)數(shù)乘法運(yùn)算分布。由表1可知，2 048點(diǎn)基-2kFFT算法一共包含了10個(gè)旋轉(zhuǎn)因子復(fù)數(shù)乘法運(yùn)算，其中‘-j’運(yùn)算為簡(jiǎn)單運(yùn)算，只需將復(fù)數(shù)序列的實(shí)部與虛部的位置進(jìn)行交換，再對(duì)虛部求反即可。由于旋轉(zhuǎn)因子W8、W16、W32和W64進(jìn)行復(fù)數(shù)乘法運(yùn)算所需的常數(shù)值個(gè)數(shù)少，因此為了節(jié)約硬件成本，在實(shí)現(xiàn)它們的復(fù)數(shù)乘法運(yùn)算采用了正則有符號(hào)數(shù)(Canonical Signed Digit,CSD)常數(shù)乘法器[8]，而對(duì)于旋轉(zhuǎn)因子W128、W256和W2048來(lái)說(shuō)，其所需常數(shù)值過(guò)多，已不適合利用CSD常數(shù)乘法器，因此采用常用的布斯乘法器進(jìn)行復(fù)數(shù)乘法運(yùn)算。仔細(xì)觀察表1，本文提出的改良基-26算法不論是方式1還是方式2與其他算法相比，在減少旋轉(zhuǎn)因子計(jì)算復(fù)雜度方面并無(wú)明顯優(yōu)勢(shì)?？紤]到改良基-26算法每6個(gè)階段為一個(gè)旋轉(zhuǎn)因子復(fù)數(shù)乘法循環(huán)周期，比較方式1和方式2的第一個(gè)循環(huán)周期的旋轉(zhuǎn)因子(前6個(gè)階段)，除了同樣的旋轉(zhuǎn)因子W2048和W64，方式1中剩下W16，方式2中剩下W8和W32，明顯方式1較方式2具有更簡(jiǎn)單的旋轉(zhuǎn)因子；同樣，在后續(xù)的4個(gè)階段中，方式2的旋轉(zhuǎn)因子W8和W32對(duì)比方式1的旋轉(zhuǎn)因子W16和W64更加簡(jiǎn)單。因此將方式1的前6個(gè)階段(表1中紅色矩形圈住的部分)與方式2的后4個(gè)階段(表1中藍(lán)色矩形圈住的部分)相結(jié)合，形成混合改良基-26算法，對(duì)比其他k值的基-2k算法擁有更簡(jiǎn)單的旋轉(zhuǎn)因子。

表1 2 048點(diǎn)基-2k算法旋轉(zhuǎn)因子運(yùn)算分布

表2所示為8路徑2 048點(diǎn)不同k值的基-2kMDF FFT架構(gòu)硬件復(fù)雜度比較，為了更直觀地評(píng)估，對(duì)于復(fù)數(shù)乘法器的邏輯單元(Logic Element,LE)使用量進(jìn)行了歸一化處理，用NLE表示，布斯乘法器所消耗的LE設(shè)定為1，那么完成旋轉(zhuǎn)因子W8、W16、W32和W64的CSD常數(shù)乘法器所消耗的LE分別為0.09、0.18、0.33和0.59。由表2可知，相較于其他k值的基-2k算法，新型改良混合基-26算法擁有最低的邏輯單元消耗量和最小的ROM存儲(chǔ)空間(本文第2節(jié)將給出詳細(xì)的ROM空間減少方案)，因此新型混合改良基-26算法在2 048點(diǎn)FFT處理器設(shè)計(jì)上更具優(yōu)勢(shì)。

表2 8路徑2 048點(diǎn)不同k值基-2k MDF FFT架構(gòu)設(shè)計(jì)硬件復(fù)雜度比較

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

圖1所示為混合改良基-26算法8路徑2 048點(diǎn)FFT處理器整體結(jié)構(gòu)圖。由圖1可知，本文所設(shè)計(jì)的FFT處理器由基本的蝶形單元、布斯乘法器、ROM、CSD常數(shù)乘法器以及控制邏輯所組成，其中左邊的模塊1用于完成混合改良基-26算法方式1前6個(gè)階段的運(yùn)算，右邊的模塊2用于完成混合改良基-26算法方式2后4個(gè)階段的運(yùn)算。

圖1 基于混合改良基-26算法的8路徑2 048點(diǎn)FFT處理器結(jié)構(gòu)圖

2.1 蝶形單元

蝶形單元是FFT處理器中最基本的運(yùn)算單元，主要用于復(fù)數(shù)序列的加法與減法。蝶形單元分為BFI型與BFII型，與前者不同的是后者需要進(jìn)行額外的‘-j’運(yùn)算[9]。蝶形單元的具體運(yùn)算過(guò)程如下：

輸入數(shù)據(jù)序列按照順序儲(chǔ)存到先進(jìn)先出寄存器中，直到第N/2個(gè)數(shù)據(jù)(N為FFT點(diǎn)數(shù))，接下來(lái)的輸入數(shù)據(jù)與先前存放在寄存器中的數(shù)據(jù)依次進(jìn)行復(fù)數(shù)加減法運(yùn)算。蝶形單元所進(jìn)行的復(fù)數(shù)加法運(yùn)算直接作為下一個(gè)階段的輸入數(shù)據(jù)，而減法運(yùn)算結(jié)果存入下一階段的先進(jìn)先出寄存器中。

2.2 布斯乘法器與ROM

由于布斯乘法器能將乘法的部分積減少一半，非常適合高速FFT處理器的復(fù)數(shù)乘法運(yùn)算。同時(shí)，考慮到量化誤差對(duì)整個(gè)FFT處理器SQNR的影響，本文的設(shè)計(jì)方案采用了文獻(xiàn)[10]的布斯乘法器誤差補(bǔ)償方案用于減少量化誤差。布斯乘法器在針對(duì)旋轉(zhuǎn)因子進(jìn)行復(fù)數(shù)乘法運(yùn)算時(shí)，需要ROM對(duì)旋轉(zhuǎn)因子的系數(shù)進(jìn)行存儲(chǔ)。本文采用了一種減少ROM存儲(chǔ)空間的方法[11]，能夠?qū)⒋鎯?chǔ)旋轉(zhuǎn)因子W2048系數(shù)的空間減少為原來(lái)的一半。具體方法如下:

ROM存儲(chǔ)空間的大小依賴于旋轉(zhuǎn)因子指數(shù)的最大值、最小值以及指數(shù)最小間隔步長(zhǎng)，而且ROM存儲(chǔ)空間大小為2的整次冪。例如，如果旋轉(zhuǎn)因子WN的指數(shù)i(i=nk)最小值為0，最大值為12，而指數(shù)之間的間隔為1，那么至少需要16 b的存儲(chǔ)空間(為了方便計(jì)算，這里不考慮旋轉(zhuǎn)因子序列的字長(zhǎng))，但如果指數(shù)最大值與最小值不變，最小間隔步長(zhǎng)變?yōu)?，那么根據(jù)旋轉(zhuǎn)因子的可約性，指數(shù)i的取值范圍縮小為原來(lái)的一半，此時(shí)只需8 b的存儲(chǔ)空間。由于本文的設(shè)計(jì)需要利用布斯乘法器來(lái)處理旋轉(zhuǎn)因子W2048的復(fù)數(shù)乘法運(yùn)算，因此為了確定所需ROM存儲(chǔ)空間大小，基于Matlab對(duì)2 048點(diǎn)不同k值的基-2k算法進(jìn)行了建模。

通過(guò)下面的代碼可獲得旋轉(zhuǎn)因子W2048所需的相應(yīng)指數(shù)：

exp=[0:N/2k];B=de2bi([0:2k],'left-msb');

C=fliplr(B);D=bi2de(C,'left-msb');

tw_r2k=exp.*D;

%其中N為FFT點(diǎn)數(shù)；k為基-2k算法的指數(shù)；%

表3所示為不同k值的基-2k算法針對(duì)旋轉(zhuǎn)因子W2048所需ROM存儲(chǔ)空間的比較。

表3 不同基-2k算法所需ROM存儲(chǔ)空間比較

圖模塊結(jié)構(gòu)圖

2.3 CSD常數(shù)乘法器

本文提出的設(shè)計(jì)方案需要4種不同的CSD常數(shù)乘法器來(lái)分別完成旋轉(zhuǎn)因子W8、W16、W32和W64的復(fù)數(shù)乘法運(yùn)算，表4給出了上述CSD常數(shù)乘法器所需的15個(gè)常數(shù)值以及其CSD表示。

表4 15組常數(shù)值CSD表示

圖3 CSD常數(shù)乘法器結(jié)構(gòu)圖(W8、W16、W32和W64)

3 不同方案FFT處理器性能比較

在FFT處理器的硬件實(shí)現(xiàn)之前，基于Matlab對(duì)序列字長(zhǎng)選擇以及量化誤差進(jìn)行了相關(guān)的評(píng)估。本文的設(shè)計(jì)采用定點(diǎn)字長(zhǎng)方案[12]，圖4所示為基-2k算法在不同字長(zhǎng)時(shí)計(jì)算2 048點(diǎn)FFT的SQNR表現(xiàn)。由圖4可知，不論基-2k算法的k值如何，當(dāng)序列內(nèi)部字長(zhǎng)增加到16 b時(shí)，SQNR達(dá)到了36 dB,繼續(xù)增加字長(zhǎng)，SQNR并無(wú)顯著提升，因此本文設(shè)計(jì)選擇16位內(nèi)部字長(zhǎng)。

圖4 基-2k算法SQNR比較

基于QUARTUS PRIME平臺(tái)對(duì)所提出的2 048點(diǎn)FFT處理器進(jìn)行了實(shí)現(xiàn)與仿真，使用Verilog HDL語(yǔ)言對(duì)設(shè)計(jì)進(jìn)行建模，器件選擇CYCLONE 10LP家族的10CL120ZF780I8G。表5所示為本文的方案對(duì)比其他已存在方案在面向WPAN應(yīng)用所設(shè)計(jì)的FFT處理器性能仿真結(jié)果比較。為了更加直觀地評(píng)估硬件成本的消耗，將邏輯單元使用量以及記憶體單元使用量(Memory Bit,MB)進(jìn)行了標(biāo)準(zhǔn)化處理，本文方案所消耗的LE與MB均設(shè)定為1。由表5可知，對(duì)比已有的設(shè)計(jì)方案，本文方案至少能夠節(jié)約23%LE以及12%MB，同時(shí)本文所設(shè)計(jì)的FFT處理器有著更好的SQNR表現(xiàn)，最高工作頻率達(dá)到了320 MHz,此時(shí)數(shù)據(jù)吞吐量為2.6 Gsample/s。利用QUARTUS PRIME平臺(tái)的Power Analyzer進(jìn)行功耗分析，本文所設(shè)計(jì)的FFT處理器動(dòng)態(tài)功耗最低，僅為33.8 mW。

表5 不同方案FFT處理器性能比較

圖5所示為MODELSIM得到的RTL級(jí)仿真結(jié)果幅度值與Matlab計(jì)算結(jié)果幅度值的比較(輸入序列的實(shí)部和虛部都設(shè)定為1～2 048)。圖5中的縮略圖截取了不同F(xiàn)FT點(diǎn)數(shù)位置上的計(jì)算結(jié)果，由四個(gè)縮略圖可知，RTL級(jí)仿真結(jié)果與Matlab計(jì)算結(jié)果全部吻合，驗(yàn)證了設(shè)計(jì)的有效性。

圖5 RTL級(jí)仿真結(jié)果與Matlab計(jì)算結(jié)果比較

4 結(jié) 論

本文設(shè)計(jì)了一種基于新型改良基-26算法的8路徑MDF架構(gòu)2 048點(diǎn)FFT處理器，能夠?yàn)閃PAN應(yīng)用提供高達(dá)2.6 Gsample/s的數(shù)據(jù)吞吐量。提出的改良基-26算法降低了旋轉(zhuǎn)因子復(fù)數(shù)乘法運(yùn)算的復(fù)雜度，為了降低硬件資源消耗，采用CSD常數(shù)乘法器替代傳統(tǒng)布斯乘法器完成了除旋轉(zhuǎn)因子W2048的所有復(fù)數(shù)乘法運(yùn)算，對(duì)比已有的方案，至少能夠節(jié)約23%LE與12%MB。同時(shí)，在16位內(nèi)部定點(diǎn)字長(zhǎng)的條件下SQNR達(dá)到了36 dB，動(dòng)態(tài)功耗僅為33.8 mW。另外，采用了一種減少存儲(chǔ)旋轉(zhuǎn)因子W2048系數(shù)ROM空間的方法，使得為布斯乘法器提供旋轉(zhuǎn)因子系數(shù)的ROM存儲(chǔ)空間減少為原來(lái)的一半。因此，本文所提出的方案在面向WPAN應(yīng)用的高吞吐量、低復(fù)雜FFT處理器設(shè)計(jì)上具有較大的優(yōu)勢(shì)。