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