摘? 要： 在比較已有FFT實(shí)現(xiàn)方法的基礎(chǔ)上，提出一種基于FPGA的通用FFT處理器的設(shè)計(jì)方案。這種FFT實(shí)現(xiàn)結(jié)構(gòu)根據(jù)不同的輸入數(shù)據(jù)長(zhǎng)度動(dòng)態(tài)配置成相應(yīng)的處理器，可以支持多種基數(shù)為2、3、5的FFT計(jì)算，硬件資源得到了優(yōu)化，處理速度及數(shù)據(jù)精度滿足LTE系統(tǒng)中SC-FDMA基帶信號(hào)的生成要求。

　　LTE所選擇的上行傳輸方案是一個(gè)新變量：SC-FDMA(單載波-頻分多址)相比于傳統(tǒng)OFDMA其優(yōu)點(diǎn)是既有單載波的低峰均功率比(PAPR)，又有多載波的可靠性。在上行鏈路這點(diǎn)特別重要，較低的PAPR可在傳輸功效方面極大提高移動(dòng)終端的性能，因此可延長(zhǎng)電池使用壽命。代表LTE物理上行共享信道(PUSCH)的基帶信號(hào)產(chǎn)生過(guò)程如圖1所示[1]。

　　圖1中的轉(zhuǎn)換預(yù)編碼是由一種對(duì)稱(chēng)形式DFT完成，其種類(lèi)及變換長(zhǎng)度L=2k1×3k2×5k3(L≤1 200)見(jiàn)表1。

　　轉(zhuǎn)換預(yù)編碼是根據(jù)不同的輸入長(zhǎng)度L動(dòng)態(tài)地執(zhí)行表1中的一種DFT。其主要特點(diǎn)是包含的DFT種類(lèi)多、規(guī)模龐大，這給硬件設(shè)計(jì)帶來(lái)挑戰(zhàn)。以前的文獻(xiàn)大都以基2或單個(gè)混合基FFT[6]為重點(diǎn)進(jìn)行闡述，而以多種混合基FFT為核心的文章還很難發(fā)現(xiàn)。本文提出一種基于FPGA的轉(zhuǎn)換預(yù)編碼解決方案。

1 算法選擇

　　Cooley-Tukey算法和Good-Thomas算法是當(dāng)前流行的FFT算法，文獻(xiàn)[2]中已對(duì)其原理進(jìn)行過(guò)深入討論，這里不再贅述。

　　(1)Cooley-Tukey算法具有良好的模塊性，并且可以實(shí)現(xiàn)原位計(jì)算，對(duì)輸入數(shù)據(jù)以及旋轉(zhuǎn)因子的抽取具有規(guī)律性。文獻(xiàn)[3]提出的一種基3 FFT算法是Cooley-Tukey算法應(yīng)用在基3 FFT中的另一種表述。這一算法區(qū)別于其他FFT算法的一個(gè)重要事實(shí)就是因子可以任意選取，通用性強(qiáng)，且所有的運(yùn)算單元均相同，易于實(shí)現(xiàn)。

　　(2)Good-Thomas算法只適合因子互質(zhì)的情況，由于避免了中間級(jí)乘旋轉(zhuǎn)因子的運(yùn)算，因此比Cooley-Tukey算法的運(yùn)算次數(shù)少得多。FFT點(diǎn)數(shù)越大，越能體現(xiàn)其在節(jié)省資源方面的優(yōu)點(diǎn)。

　　文獻(xiàn)[4]提出一種基于Cooley-Tukey算法的傳輸預(yù)編碼解決方案。此方案的優(yōu)點(diǎn)是操作簡(jiǎn)單、模塊規(guī)則、利于編程實(shí)現(xiàn)；缺點(diǎn)是需要做的級(jí)間旋轉(zhuǎn)因子乘法較多(最多達(dá)幾百)，乘法器和存儲(chǔ)器等硬件資源開(kāi)銷(xiāo)較大，同時(shí)將大大增加系數(shù)初始化的工作量。對(duì)幾種不同長(zhǎng)度FFT運(yùn)算量進(jìn)行比較見(jiàn)表2。

　　表2中的混合算法指Good-Thomas算法與Cooley-Tukey算法相結(jié)合?？梢钥闯觯珿ood-Thomas算法與Cooley-Tukey算法相結(jié)合與文獻(xiàn)[4]相比，減少了級(jí)間旋轉(zhuǎn)因子乘法數(shù)，可以有效降低運(yùn)算量，這些運(yùn)算量的降低對(duì)整個(gè)系統(tǒng)的實(shí)現(xiàn)起著至關(guān)重要的作用，而其付出的代價(jià)只是復(fù)雜度的略微提升。

　　綜上所述，在實(shí)現(xiàn)混合FFT時(shí)，選擇Good-Thomas算法與Cooley-Tukey算法相結(jié)合，且優(yōu)先選擇Good-Thomas算法，其次為Cooley-Tukey算法，系統(tǒng)設(shè)計(jì)將從Good-Thomas算法出發(fā)。

　　2 總體結(jié)構(gòu)設(shè)計(jì)

　　從表1中看出，LTE上行轉(zhuǎn)換預(yù)編碼要進(jìn)行的FFT變換種類(lèi)多，但每一種變換的架構(gòu)是相似的，都是由基2及非基2點(diǎn)FFT的公共模塊組成?；?有點(diǎn)數(shù)為4，8，16，32，64，128，256的模塊，非基2的有點(diǎn)數(shù)為3，9，15，27，45，75，81，135，225和243的模塊，只要抽出這些公共模塊并精心設(shè)計(jì)，再合理地調(diào)用，就會(huì)順利完成這個(gè)看似繁瑣的工作。

　　圖2所示總體結(jié)構(gòu)框圖中，模塊A和C分別為數(shù)據(jù)輸入和輸出模塊；模塊B為數(shù)據(jù)處理模塊，其主要思想是動(dòng)態(tài)配置和公共模塊的復(fù)用，內(nèi)部FFT模塊事先單獨(dú)生成，MUX1，MUX2是選擇器，在不同輸入點(diǎn)數(shù)的情況下動(dòng)態(tài)配置不同的內(nèi)部FFT模塊來(lái)組合成外層FFT，這樣內(nèi)部FFT模塊就可以達(dá)到復(fù)用的目的，可以大大減少總體資源耗用，而處理速度也與單獨(dú)執(zhí)行各FFT相當(dāng)。

3 硬件實(shí)現(xiàn)

　　在實(shí)際應(yīng)用中，一般由FPGA完成需要快速和較為固定的運(yùn)算，由DSP完成靈活多變和運(yùn)算量較大的任務(wù)[7]。Xilinx Virtex-5 SXT平臺(tái)針對(duì)具有低功耗串行連接功能的DSP和存儲(chǔ)器密集型應(yīng)用進(jìn)行了優(yōu)化，具有硬件結(jié)構(gòu)可重構(gòu)的特點(diǎn)，適合算法結(jié)構(gòu)固定、運(yùn)算量大的前端數(shù)字信號(hào)處理，可以大量卸載這些功能，釋放DSP帶寬以處理其他功能，所有這一切都使得FPGA在數(shù)字信號(hào)處理領(lǐng)域顯示出自己特有的優(yōu)勢(shì)。

　　3.1 地址映射

　　以1 080點(diǎn)FFT在圖2所示系統(tǒng)中的實(shí)現(xiàn)過(guò)程分析系統(tǒng)工作原理。因?yàn)? 080=8×135，且8和135互質(zhì)，故外層采用Good-Thomas算法。

　　輸入地址映射：

　　FPGA內(nèi)嵌Block RAM的使用可以大大節(jié)省FPGA的可配置邏輯功能塊（CLB）資源。Good-Thomas算法需要對(duì)輸入輸出數(shù)據(jù)進(jìn)行排序，輸入輸出端處理方法相同，這里只介紹輸入端處理。在輸入端，鑒于Block RAM的特征，設(shè)置一個(gè)ROM和RAM，如圖2模塊A所示。對(duì)于不同長(zhǎng)度的FFT，ROM不同，但RAM可以共用。在ROM里預(yù)先存放輸入數(shù)據(jù)在RAM1中的位置序號(hào)，此位置序號(hào)由（1）式得到，在時(shí)鐘沿到來(lái)時(shí)，先順序讀出存儲(chǔ)在ROM中的位置序號(hào)，將此數(shù)作為RAM1的地址輸入，就能將輸入數(shù)據(jù)存放到RAM1中的不同位置。這樣在輸入數(shù)據(jù)的同時(shí)完成了數(shù)據(jù)的排序，一舉兩得。1 080點(diǎn)FFT的輸入和輸出端地址索引如圖2所示，其邏輯時(shí)序圖見(jiàn)圖3。圖3中，RAM_in由測(cè)試數(shù)據(jù)xn_i和xn_r進(jìn)行位拼接后輸入。

　　3.2 內(nèi)部FFT處理單元

　　當(dāng)進(jìn)行圖2模塊B中的操作時(shí)，內(nèi)部FFT模塊先單獨(dú)生成。Xilinx提供的FFT IP核適用于基2點(diǎn)的FFT變換，其所采用的算法為Cooley-Tukey算法，變換長(zhǎng)度為N=pow2(m)，m=3~16，數(shù)據(jù)采樣精度和旋轉(zhuǎn)因子精度都為8~24，故模塊B的8、16、32、64、128及256點(diǎn)FFT都可用IP核生成。選擇“Pipelined,streaming I/O”生成基2點(diǎn)FFT模塊，可以減少整體處理時(shí)間。15、45、75、135、225點(diǎn)FFT模塊的外層算法是Good-Thomas算法，其余采用Cooley-Tukey算法實(shí)現(xiàn)。

　　具體到1 080點(diǎn)FFT，將RAM1中的數(shù)據(jù)順序讀出，由MUX1選擇進(jìn)行8點(diǎn)FFT變換，完成第一級(jí)操作后，所得中間結(jié)果順序存儲(chǔ)在RAM2中；然后再將RAM2中的中間結(jié)果取出，由MUX2選擇進(jìn)行135點(diǎn)FFT變換，共操作8次，完成第二級(jí)操作，所得結(jié)果按模塊C中ROM指示的順序存儲(chǔ)在RAM1中；最后順序輸出RAM1中的內(nèi)容就是1 080點(diǎn)FFT的結(jié)果。

3.3 乘法器設(shè)計(jì)

　　量化效應(yīng)在數(shù)字信號(hào)處理技術(shù)實(shí)現(xiàn)時(shí)是很重要的問(wèn)題，主要包括運(yùn)算量化效應(yīng)、系數(shù)量化效應(yīng)等，前者的影響大于后者[5]。運(yùn)算中還可能出現(xiàn)溢出，造成更大的誤差。上述問(wèn)題對(duì)乘法器的設(shè)計(jì)提出了要求，由上文知，基2 FFT由IP核生成，故此處的乘法器設(shè)計(jì)只針對(duì)非基2 FFT有效。

　　Xilinx的XC5VSX95T內(nèi)部共有640個(gè)DSP48E，每個(gè)DSP48E包含一個(gè)25×18 乘法器。在調(diào)用乘法器IP時(shí)，將乘數(shù)設(shè)為寬度為25和18的signed型（旋轉(zhuǎn)因子位寬為18），輸出截取結(jié)果的[41：17]共25 bit，乘法器輸入輸出寬度相等，在結(jié)果輸出的同時(shí)對(duì)結(jié)果進(jìn)行縮放，這樣利于程序模塊化，但前提是要保證數(shù)據(jù)不溢出。由于輸入采樣數(shù)據(jù)寬度只有16 bit，而轉(zhuǎn)換預(yù)編碼輸入數(shù)據(jù)最大長(zhǎng)度只有1 200點(diǎn)，再考慮旋轉(zhuǎn)因子系數(shù)小于1，可以斷定25 bit位寬可使乘法器結(jié)果不溢出，且運(yùn)算精度也可滿足要求。

　　4 性能分析

　　程序利用Verilog HDL硬件描述語(yǔ)言編寫(xiě)，在Xilinx公司的高性能設(shè)計(jì)開(kāi)發(fā)工具ISE10.1i中編譯成功。當(dāng)FPGA芯片選為XC5VSX95T時(shí)，在Synplify Pro 9.6.1中進(jìn)行邏輯優(yōu)化與綜合后顯示其最大時(shí)鐘頻率為105.6 MHz，F(xiàn)Fs耗用29 150/58 880，LUTs耗用37 625/58 880，乘法器耗用414/640，Block Ram耗用176/488，各項(xiàng)指標(biāo)都合符要求。布局布線成功后，在Matlab中產(chǎn)生一實(shí)正弦測(cè)試信號(hào)，經(jīng)采樣量化成1 200點(diǎn)數(shù)據(jù)后輸入Modelsim SE 6.1d對(duì)程序進(jìn)行后仿真，然后輸出結(jié)果回送至Matlab，得到仿真圖如圖4。

　　由圖4可以看出FFT處理器處理后的結(jié)果和Matlab計(jì)算的理論結(jié)果基本一致，都在頻率為15 Hz和335 Hz處取得最大FFT絕對(duì)值，兩者之間的誤差正是數(shù)字信號(hào)處理量化效應(yīng)的體現(xiàn)。從整體看，這些誤差是數(shù)據(jù)在經(jīng)過(guò)采樣量化和截?cái)嗵幚砗蟛豢杀苊獾那沂强梢匀萑痰?，因此可以判斷測(cè)試結(jié)果符合精度指標(biāo)。

　　本文討論了應(yīng)用在LTE上行轉(zhuǎn)換預(yù)編碼中的多種FFT的軟硬件實(shí)現(xiàn)。與各種FFT單獨(dú)處理或只采用Cooley-Tukey算法的方法相比，本設(shè)計(jì)巧妙地將Good-Thomas算法與Cooley-Tukey算法結(jié)合起來(lái)，在硬件資源和成本消耗上都有很大的節(jié)省，速度上也能滿足要求，而且這種結(jié)構(gòu)很容易進(jìn)行功能擴(kuò)展，只需要調(diào)整內(nèi)部FFT單元的種類(lèi)和數(shù)目即可。這種大規(guī)模混合基FFT的實(shí)現(xiàn)方法對(duì)其他場(chǎng)合的大規(guī)模FFT有一定的普適性。