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