一種基于DAB正交頻分復(fù)用系統(tǒng)的變長度高速FFT處理器的硬件設(shè)計
2007-11-14
作者：宋連國, 余寧梅, 王 定
摘 要：從分析對比現(xiàn)有FFT實(shí)現(xiàn)技術(shù)的角度出發(fā)，選擇采用基2/4/8的單步延遲FFT結(jié)構(gòu)、16位的定點(diǎn)Q15數(shù)據(jù)表示格式，完成了一種FFT處理器的設(shè)計。通過三個選擇器實(shí)現(xiàn)了變長度設(shè)計，同時還進(jìn)行了乘法單元的優(yōu)化，用Altera公司的StratixⅡ系列FPGA綜合驗證了其功能。最終基于Charter標(biāo)準(zhǔn)單元庫的0.35?滋m CMOS工藝進(jìn)行了實(shí)現(xiàn)，采用Synopsis Design Compiler進(jìn)行了綜合，結(jié)果表明后仿真功能正確，在50MHz的工作頻率" title="工作頻率">工作頻率下，完成2 048、1 024、512點(diǎn)FFT分別僅需40.94?滋s、20.46?滋s和10.22?滋s，達(dá)到了高速設(shè)計的目的。
關(guān)鍵詞：OFDM?FFT? 并行結(jié)構(gòu)" title="并行結(jié)構(gòu)">并行結(jié)構(gòu)?? 基2/4/8
?
數(shù)字音頻廣播（DAB）是近幾年發(fā)展起來的繼調(diào)頻調(diào)幅之后的新一代廣播體制。DAB可以提供更優(yōu)質(zhì)的語音質(zhì)量、更新的數(shù)據(jù)業(yè)務(wù)以及更高的頻譜效率，它提供的語音質(zhì)量可以與CD音質(zhì)相媲美。DAB應(yīng)用了包括信源編碼、信道編碼等關(guān)鍵技術(shù)，其中特別應(yīng)用了正交頻分復(fù)用調(diào)制（OFDM）技術(shù)。
DAB系統(tǒng)的OFDM調(diào)制部分主要完成對DAB傳輸幀信號的符號映射、差分調(diào)制和OFDM調(diào)制等功能，參考文獻(xiàn)[1]介紹了在硬件設(shè)計中OFDM調(diào)制、解調(diào)可以通過IFFT、FFT來實(shí)現(xiàn)的原理。在實(shí)際設(shè)計中，兩者可以復(fù)用一個FFT模塊，因此OFDM設(shè)計的核心為FFT模塊。高速度、低功耗是硬件設(shè)計的追求目標(biāo)。作為DAB通信系統(tǒng)中的主干模塊，高速是首要條件，并且IEEE802.11a明確規(guī)定在OFDM系統(tǒng)中完成一個64點(diǎn)的FFT需時3.2?滋s。
本文在分析對比國內(nèi)外現(xiàn)有FFT的實(shí)現(xiàn)技術(shù)優(yōu)劣的基礎(chǔ)上，對比采用并行結(jié)構(gòu)、定點(diǎn)Q15數(shù)據(jù)格式和CORDIC算法，并基于Charter標(biāo)準(zhǔn)單元庫的0.35?滋m CMOS工藝完成了一種高速FFT處理器設(shè)計。該設(shè)計控制簡單、運(yùn)算速度快。當(dāng)前應(yīng)用較多的尤里卡147標(biāo)準(zhǔn)的DAB系統(tǒng)有三種點(diǎn)數(shù)[2]，分別對應(yīng)不同的參數(shù)，本文設(shè)計的是變長度的、通過選擇器可以實(shí)現(xiàn)三種點(diǎn)數(shù)的FFT處理器。
1 FFT結(jié)構(gòu)的選擇
FFT的實(shí)現(xiàn)結(jié)構(gòu)主要有兩種：蝶形單元式和多個處理單元式。目前國內(nèi)采用較多的是前者，即不管多少點(diǎn)數(shù)的FFT，都是通過復(fù)用一個蝶形單元來完成。這種設(shè)計考慮的是FFT蝶形單元是相對獨(dú)立的并且具有原址運(yùn)算的特點(diǎn)，而且多采用流水線結(jié)構(gòu)。碟形單元式FFT結(jié)構(gòu)如圖1所示。它的優(yōu)點(diǎn)是控制和設(shè)計都簡單。但這種結(jié)構(gòu)的設(shè)計隨著科技的發(fā)展其實(shí)用價值小于研究的價值，因為該結(jié)構(gòu)一個無法克服的劣勢是數(shù)據(jù)串行地共用一個碟形單元,這樣會因為FFT的多級運(yùn)算導(dǎo)致運(yùn)算時間比較長，大基數(shù)會導(dǎo)致運(yùn)算周期增大一個或幾個數(shù)量級。以1 024點(diǎn)為例，一個蝶形單元在采用合理流水線結(jié)構(gòu)后，能在一個時鐘內(nèi)完成。如果在不考慮流水線延遲的情況下，采用基2結(jié)構(gòu)，共10級，從輸入到第一個結(jié)果開始輸出，理論上是1 024×10+1 024個時鐘，基4結(jié)構(gòu)是5級，也就是1 024×5+1024個時鐘。而如果采用圖2所示的并行結(jié)構(gòu)，理論情況下，完成一次1 024點(diǎn)FFT僅需1 024+10個時鐘。
?
?
?
?
碟形單元式復(fù)用一個碟形單元的格式必然需要多個觸發(fā)器，這不便于減小面積。許多專家根據(jù)算法特點(diǎn)提出了結(jié)構(gòu)上的優(yōu)化方案，例如通過改進(jìn)蝶形單元結(jié)構(gòu)來減少運(yùn)算單元[3]和面積，但運(yùn)算時間不會減少。有的通過并行蝶形單元[4]、數(shù)據(jù)并行輸入蝶形單元[5]來減小時間，前者可以減少一半時間，后者盡管時間減少更多，但每級之間要留有足夠的延遲時間，況且這兩種方法本質(zhì)上來說都是采用并行算法。因此不如采用并行結(jié)構(gòu)，即多個處理單元式。
并行結(jié)構(gòu)的FFT處理器，采用并行結(jié)構(gòu)來完成FFT，這也是大勢所趨，是發(fā)展的最終方向。這種結(jié)構(gòu)針對不同基數(shù)分別有單步延遲、多步延遲兩種。圖2[6～7]分別是16點(diǎn)基2多步延遲處理器（R2MDC）和16點(diǎn)基2單步延遲處理器（R2SDF）、256點(diǎn)基4單步延遲處理器（R4SDF）的結(jié)構(gòu)示意圖。
從R2MDC、R2SDF對比來看，單步延遲比多步延遲更能有效利用存儲單元，同樣一個16點(diǎn)的FFT，多步時延結(jié)構(gòu)耗用存儲器的深度為22，而單步延遲結(jié)構(gòu)耗用存儲器的深度只需15。基2的控制簡單，而基4結(jié)構(gòu)使用的乘法單元較少。同理，基8結(jié)構(gòu)使用的乘法單元更少，但它的控制就很復(fù)雜。
參考文獻(xiàn)[8]提到了一種基2/4/8的結(jié)構(gòu)，該結(jié)構(gòu)將運(yùn)算進(jìn)行一些必要的變化，將一個8的冪的點(diǎn)數(shù)的FFT結(jié)構(gòu)轉(zhuǎn)換為多個處理單元的結(jié)構(gòu)，如圖3所示（具體推理過程見參考文獻(xiàn)[8]）。該結(jié)構(gòu)利用的規(guī)律是重復(fù)利用3個PE單元（PE1、PE2、PE3），每3個PE之間不必與旋轉(zhuǎn)因子進(jìn)行相乘，只在每3個完成后進(jìn)行一次相乘，如圖4所示。五種結(jié)構(gòu)的硬件實(shí)現(xiàn)情況對比表如表1所示。從表1可以看出基2/4/8結(jié)構(gòu)既減少了乘法器" title="乘法器">乘法器數(shù)量和存儲器長度，又有相對簡單的控制器。本設(shè)計即采用這種結(jié)構(gòu)。
?
?
?
2 數(shù)據(jù)格式的選擇
目前FFT中數(shù)據(jù)的表示格式有兩種：浮點(diǎn)數(shù)和定點(diǎn)數(shù)。浮點(diǎn)數(shù)表示格式的優(yōu)點(diǎn)是精度相對比較高，32位浮點(diǎn)數(shù)理論上的精度是2-150次方，但如果采用浮點(diǎn)表示完成一次加法和乘法，即使采用流水線結(jié)構(gòu)，至少也得一個時鐘，并且浮點(diǎn)數(shù)占用資源明顯大于定點(diǎn)數(shù)的資源。在APEX20KE系列FPGA上，分別設(shè)計了兩種加法器進(jìn)行對比，采用32位浮點(diǎn)流水線結(jié)構(gòu)設(shè)計的加法器占用912個邏輯資源，而一個16位的定點(diǎn)加法器僅需91個邏輯資源，相差一個數(shù)量級。所以本設(shè)計選擇16位定點(diǎn)數(shù)格式，即實(shí)、虛部分別采用16位來表示。根據(jù)標(biāo)準(zhǔn)， 調(diào)制映射方式采用QPSK，這樣數(shù)據(jù)的范圍就可以判斷在-1～+1之間，因此本設(shè)計采用Q15表示法。Q15的數(shù)值范圍為-1～0.9999695，精度為1/32768= 0.00003051，符合要求。軟件模擬FFT進(jìn)程時，由于在運(yùn)算過程中存在溢出，本設(shè)計采用了傳統(tǒng)的控制簡單、速度快的1/2截尾法，在每一級插入衰減1/2，溢出總共減少至1/211倍，最后結(jié)果再乘上衰減的因子得到正確結(jié)果。這些過程全部通過移位完成。
3 基2/4/8 FFT的工作流程及設(shè)計
DAB標(biāo)準(zhǔn)含三種點(diǎn)數(shù)的FFT，分別是512、1 024、2 048，依次遞增。為實(shí)現(xiàn)變長度設(shè)計，在512點(diǎn)結(jié)構(gòu)的前端加入兩個基2的PE單元（結(jié)構(gòu)與基2/4/8的PE3相同），通過兩個選擇器實(shí)現(xiàn)變長度，結(jié)構(gòu)如圖5所示。
?
圖中左邊RAM深度為1 024，右邊的為512，兩個PE單元分別為模塊11和模塊10。本設(shè)計中兩個選擇器共用一個兩位地址選擇信號,即模式選擇信號，如果模式選擇信號為01，數(shù)據(jù)流直接輸入模塊11，即2 048點(diǎn)；如果為10，則跳過模塊11輸入模塊10；如果為11，則跳過模塊10，分別得到1 024點(diǎn)和512點(diǎn)。本設(shè)計地址信號設(shè)為01，即以2 048點(diǎn)為例敘述工作流程。
按照DAB標(biāo)準(zhǔn)，數(shù)據(jù)流在經(jīng)過QPSK調(diào)制映射、頻率交織、差分調(diào)制后成為復(fù)數(shù)數(shù)據(jù)流。 32位（16位輸入會增加數(shù)據(jù)的讀入讀出時間）的2 048個數(shù)據(jù)開始輸入時，模塊11開始工作；第1 025個數(shù)據(jù)輸入時，模塊11開始輸出，模塊10開始工作。當(dāng)模塊10讀入模塊的數(shù)據(jù)到第513個時，模塊10開始輸出，模塊9開始工作，……依次類推。數(shù)據(jù)在模塊11、10；10、9；6、7和3、4之間分別經(jīng)過一個乘法器，完成當(dāng)時輸入和數(shù)據(jù)與從ROM（ROM存儲的是旋轉(zhuǎn)因子表）中讀出數(shù)據(jù)的乘積（見圖4）。
3.1 PE單元
三種PE采用組合邏輯設(shè)計來提高運(yùn)算速度，其結(jié)構(gòu)如圖6所示。考慮到模塊直接相連路徑延時較長，所以在每個模塊的輸出都加入寄存器，并采用流水線形式，來減小路徑延時，提高工作頻率。實(shí)驗證明，盡管增加了資源，但僅這單方面的優(yōu)化措施所提高的工作頻率就接近一倍（由47MHz提高到90MHz）。
3.2 控制器
本設(shè)計中的控制器采用全局計數(shù)器來實(shí)現(xiàn)控制，加入了一個模式選擇信號。如果實(shí)現(xiàn)變長度，通常要引入多個多路選擇器產(chǎn)生各個模塊的控制信號，這樣會使面積增加，計數(shù)信號扇出過高。為克服這一缺點(diǎn)，本設(shè)計在輸入開始由模式選擇信號控制計數(shù)器，如果是2 048點(diǎn)，則從0開始計數(shù)；如果是1 024點(diǎn)，則從1 025開始計數(shù)；如果是512點(diǎn)，則從1 038開始計數(shù)。這樣其他控制信號就不用改變，只需一個計數(shù)器就可以完成。
3.3 乘法單元
基2/4/8結(jié)構(gòu)中有兩種乘法單元的設(shè)計：
?(1)存在下面兩個運(yùn)算的設(shè)計：
?
?
?(2)兩個復(fù)數(shù)的相乘的設(shè)計。處理有兩種情況：假定兩個復(fù)數(shù)分別為a+bj、A+Bj,在FPGA功能驗證" title="功能驗證">功能驗證階段，相乘運(yùn)算可作如下相應(yīng)的變化，這樣本來需要四次乘法，經(jīng)過如下公式優(yōu)化后只需三次。
?(a+bj)×(A+Bj)=aA-bB+j(aB+bA)
?=a(A+B)-B(a+b)+j(a(A+B)-A(a-b))
?其中的乘法直接利用FPGA中自帶的乘法器資源，在做ASIC前端設(shè)計時，本設(shè)計根據(jù)FFT中的復(fù)數(shù)乘法規(guī)律，采用CORDIC（坐標(biāo)旋轉(zhuǎn)數(shù)字計算機(jī)）算法將復(fù)雜的乘法轉(zhuǎn)化成簡單的加減、移位運(yùn)算。根據(jù)CORDIC的迭代原理本設(shè)計采用了20級流水線來提高運(yùn)算速度，直接算出結(jié)果。相比booth乘法器，實(shí)現(xiàn)更簡單。
3.4 RAM和ROM的處理
本設(shè)計總共用了11塊RAM、4塊ROM。在做FPGA功能驗證時，ROM中存儲的是角度的正弦、余弦值，在做ASIC前端設(shè)計時，存儲的是角度值。在ROM1、ROM2中的數(shù)據(jù)，本設(shè)計借用MATLAB工具進(jìn)行了驗證，得到的ROM1、ROM2數(shù)據(jù)均與基2結(jié)構(gòu)的旋轉(zhuǎn)因子表的生成規(guī)律一致。
FPGA功能驗證階段所采用的RAM、ROM均為FPGA自帶的。在做DC綜合時，RAM、ROM全部作為黑盒子，然后應(yīng)用廠商提供的Rapidcompiler工具進(jìn)行單獨(dú)綜合，得到的模型再與DC綜合網(wǎng)表一起進(jìn)行綜合后仿真。
4 電路功能驗證
整個系統(tǒng)使用Verilog HDL完成了設(shè)計，在Modisim 6.0平臺上進(jìn)行了仿真，利用測試平臺法驗證其功能的正確性，仿真結(jié)果如圖8所示。
?測試平臺采用的時鐘周期" title="時鐘周期">時鐘周期為20ns，圖8中時鐘線上30ns、20 930ns（1 024個時鐘周期+20個CORDIC流水線時鐘周期+1個截尾時鐘周期）、4 1010ns（1 984個時鐘周期+60個CORDIC流水線時鐘周期+5個截尾時鐘周期）、42 590ns（2 040個時鐘周期+80個CORDIC流水線時鐘周期+8個截尾時鐘周期），分別是PE11、PE10、PE6、PE3開始輸入時間。本設(shè)計選用Altera公司的StratixⅡ系列FPGA來綜合進(jìn)行功能驗證，最終采用基于Charter標(biāo)準(zhǔn)單元庫的0.35微米 CMOS工藝來設(shè)計實(shí)現(xiàn)。在SUN工作站上利用Synopsis Design Compiler進(jìn)行綜合，得到工作頻率為53MHz，規(guī)模大約12萬門，對綜合網(wǎng)表、Rapidcompiler生成的RAM、ROM進(jìn)行后仿真，功能均正確。
本系統(tǒng)中FFT處理器2 048點(diǎn)從數(shù)據(jù)開始輸入，不考慮流水線延遲到開始輸出結(jié)果共需1 024+512+256+128+64+32+16+8+4+2+1=2 047個時鐘, 計算可得在50MHz的工作頻率下只需40.94微秒即可完成。同理，1 024、512點(diǎn)分別需要20.46微秒和10.22微秒。五種FFT設(shè)計的完成時間對比如表2所示。由表可以看出，達(dá)到了高速設(shè)計的目的。
?
?本文應(yīng)用Verilog語言對一種DAB正交頻分系統(tǒng)中的變長度FFT處理器進(jìn)行了ASIC的前端設(shè)計。 通過對比FFT實(shí)現(xiàn)的兩種結(jié)構(gòu)，以高速為首要原則設(shè)計了一種高速實(shí)現(xiàn)的結(jié)構(gòu)。通過分析驗證，采用了合適的數(shù)據(jù)表示格式，并就結(jié)構(gòu)中的乘法單元進(jìn)行了優(yōu)化，最終完成了一種性能較高的設(shè)計。
參考文獻(xiàn)
[1] 佟學(xué)儉，羅濤.OFDM移動通信技術(shù)原理與應(yīng)用[M].北京：人民郵電出版社,2003.
[2] ETSI EN 300 401(V1.3.3)[S]；Radio broadcasting systems;digital audio broadcasting(DAB)to mobile,portable and fixed?receivers[s].Europeanm Telecommunication Standard Institute,2001.
[3] 趙忠武, 陳禾,韓月秋.基于FPGA的32位浮點(diǎn)FFT處理器的設(shè)計[J].電訊技術(shù),2003;(6):73-77.
[4] 韓穎, 王 旭,吳嗣亮.FPGA實(shí)現(xiàn)高速FPGA處理器的設(shè)計[J]. 電訊技術(shù), 2003,(2):74-78.
[5]?萬紅星, 陳禾, 韓月秋.一種高速并行的FFT處理器的VLSI結(jié)構(gòu)設(shè)計[J]. 電子技術(shù)應(yīng)用, 2005,(5):45-48.
[6] HE S, TORKELSON M. A new approach to pipeline FFT?processor. IEEE Proc. Of IPPS,1996.
[7] HE S, ORKELSON M. Designing pipeline FFT processor?for OFDM(de)modulation.ISSSE,1998.
[8] JIA L, GAO Y, ISOAHO J, et al. A new VLSI-oriented?FFT algorithm and implementation.Proc.IEEE ASIC Conf,
????1998.