高速3780 點FFT處理器的設(shè)計與實現(xiàn)

解春云，劉光輝，?？》?/p>

(電子科技大學(xué)電子工程學(xué)院，四川 成都 610054)

地面數(shù)字電視廣播經(jīng)過多年的發(fā)展，取得了很多成果，目前已經(jīng)提出的地面數(shù)字電視廣播標(biāo)準(zhǔn)有:歐洲的DVB－T、美國的ATSC和日本的ISDB－T。在此背景下，2006年8月國家標(biāo)準(zhǔn)化管理委員會頒布了中國數(shù)字電視地面廣播傳輸系統(tǒng)標(biāo)準(zhǔn) GB20600—2006［1］，即中國的DTMB。DTMB系統(tǒng)包括單載波和多載波兩種模式，其中，多載波傳輸模式采用時域同步正交頻分復(fù)用(TDSOFDM)作為核心技術(shù)。在DTMB接收機(jī)中，為實現(xiàn)TDSOFDM技術(shù)，需要進(jìn)行多次快速傅里葉變換(FFT)，F(xiàn)FT處理器占據(jù)了大量的運(yùn)算時間及資源，在很大程度上決定了DTMB接收機(jī)的功耗和復(fù)雜度，必須采用復(fù)用的方式來減少資源的占用。因此，尋求一種高速有效的3780 點FFT處理器，對整個DTMB接收機(jī)系統(tǒng)具有重要的現(xiàn)實意義。

1 3780點FFT算法

目前，關(guān)于FFT的計算，主要是基于基－2和基－4的算法，對于基－2和基－4的FFT，算法仿真和硬件實現(xiàn)都已有很多種成熟的算法。3780 點FFT不是以2或4為基，所以在實現(xiàn)時主要有兩種方法［2］:

一種方法是把3780 點通過內(nèi)插得到4096 點，利用現(xiàn)已成熟的基－2和基－4的FFT算法計算4096 點FFT，再抽取得到3780 點的FFT。

另一種方法是綜合利用混合基算法、素因子算法(PFA)和Winograd傅里葉變換算法(WFTA)算法將3780 分解實現(xiàn)3780 點FFT的計算。

第一種方法沒有計算準(zhǔn)確的3780 點FFT，必然會帶來計算誤差，且采樣速率發(fā)生改變，將增加OFDM系統(tǒng)中同步的復(fù)雜度，故不予考慮。本文重點對后者進(jìn)行研究。下面先對混合基算法、素因子算法及WFTA算法進(jìn)行介紹，并在此基礎(chǔ)上，給出本文3780 點FFT的算法設(shè)計。

1.1 混合基算法

混合基算法［3］是一種將長點數(shù)的DFT轉(zhuǎn)換為短點數(shù)DFT組合的算法。設(shè)有N點序列經(jīng)x(n)，其傅里葉變換(DFT)定義［3］為

若N=N1×N2(N1，N2可有公因子)，通過映射得到

式中:＜＞N表示對N取模運(yùn)算。將式(1)轉(zhuǎn)化為

式中:將 x(n1，n2)和 X(k1，k2)看作二維數(shù)組，對 x(n1，n2)的行(列)作DFT得到X'，再對X'的列(行)作DFT就得到X(k)。其中N1，N2可以繼續(xù)利用上述特征進(jìn)行二層分解以減少運(yùn)算量。

1.2 素因子算法(PFA)

當(dāng)混合基算法［3］中的 N1，N2互素時，可以通過選擇n1，n2，k1，k2前的特殊系數(shù)消去旋轉(zhuǎn)因子，進(jìn)一步簡化FFT的計算。通過映射得到

當(dāng) A，B，C，D 滿足下列條件時

式(3)轉(zhuǎn)化為

與混合基算法相比，素因子算法減少了中間的旋轉(zhuǎn)因子，不僅減少了運(yùn)算量，也減少了旋轉(zhuǎn)因子的存儲。其中N1，N2可以繼續(xù)利用上述特征進(jìn)行二層分解以減少運(yùn)算量。

1.3 Winograd小點數(shù)DFT算法

Winograd小點數(shù)DFT算法［3］是一種高效的DFT算法，其特點在于乘法次數(shù)顯著減少。

一個N點DFT可以寫成矩陣的形式為

式中:WN是N×N的矩陣，第k行n列元素為WnkN，x=［x(0)…x(N －1)］T，X=［X(0)…X(N －1)］T。Winograd證明，當(dāng) N ∈ {2，3，4，5，7，8，9，16}時，復(fù)數(shù)矩陣 WN能以下列方式分解

式中:G為對角矩陣，且對角線上元素為實數(shù)或純虛數(shù);B，C為平凡矩陣，僅由0，－1，1或一些小點數(shù)構(gòu)成。

1.4 3780點FFT算法

3780 可分解為3780 =7×5×3×3×3×2×2，在考慮到WFTA 算法提出的16，9，8，7，5，4，3，2 幾種小點數(shù) DFT 算法，且優(yōu)先使用PFA的基礎(chǔ)上，給出如圖1所示的算法方案。

圖1 本文算法方案分解圖

將3780 點先通過素因子算法分解成27×140點，再對27點和140點分別采用混合基算法和素因子算法分解成9×3點和7 ×5×4點，其中9，3，7，5，4點FFT 利用WFTA 算法計算。與文獻(xiàn)［4－7］中的3780 =60×63的混合基算法分解方案比較，該方案可節(jié)省3780 個旋轉(zhuǎn)因子的存儲。

2 3780點FFT處理器設(shè)計

DTMB系統(tǒng)采用TDS－OFDM技術(shù)，在長時延環(huán)境下，符號間干擾(ISI)會嚴(yán)重影響接收機(jī)性能。文獻(xiàn)［8］提出了一種迭代門限檢測(ITD)與判決反饋均衡(DFE)相結(jié)合的算法，該算法能夠有效消除ISI干擾，獲得精確的信道狀態(tài)信息(CSI)，同時復(fù)雜度也相對較低。然而迭代的檢測CSI需要增加FFT/IFFT運(yùn)算次數(shù)，F(xiàn)FT次數(shù)與迭代次數(shù)的關(guān)系為:NFFT=2+3×N迭代次數(shù)。采用1次迭代操作即要求5次FFT/IFFT運(yùn)算，因此，F(xiàn)FT處理器在DTMB接收機(jī)中需消耗大量的運(yùn)算時間及資源，必須尋求一種高速有效的3780 點FFT處理器，以復(fù)用的方式來減少邏輯資源的占用。

文獻(xiàn)［4－7］均對DTMB系統(tǒng)中3780 點FFT處理器進(jìn)行了詳細(xì)介紹，其處理器內(nèi)部WFTA運(yùn)算單元均采用串行數(shù)據(jù)處理方式進(jìn)行硬件設(shè)計，吞吐率只能滿足1幀時間內(nèi)的2次復(fù)用條件。為提高系統(tǒng)吞吐率，本文將對上述3780 點FFT處理器的實現(xiàn)結(jié)構(gòu)進(jìn)行改進(jìn)，其內(nèi)部WFTA單元改用并行處理方式，吞吐率提高為上述文獻(xiàn)中處理器的4倍，實現(xiàn)了高速3780 點FFT處理器的設(shè)計目標(biāo)。在硬件實現(xiàn)過程中，由于內(nèi)部WFTA基本運(yùn)算單元以不同并行度進(jìn)行DFT運(yùn)算，所以需要協(xié)調(diào)不同WFTA模塊間的吞吐率。同時，為滿足并行處理要求，存儲模塊需采用內(nèi)存分組方式提高數(shù)據(jù)并行度。下面對該3780 點FFT處理器的設(shè)計進(jìn)行詳細(xì)描述。

2.1 3780 點FFT處理器結(jié)構(gòu)

為了使3780 點FFT處理器在DTMB接收機(jī)系統(tǒng)中能充分復(fù)用，在第1.4節(jié)算法基礎(chǔ)上，采用流水線結(jié)構(gòu)進(jìn)行3780 點FFT處理器的硬件設(shè)計，且為進(jìn)一步提高系統(tǒng)吞吐率，其內(nèi)部WFTA單元采用并行數(shù)據(jù)處理方式進(jìn)行硬件實現(xiàn)。處理器結(jié)構(gòu)如圖2所示，其中1，9，7，4表示各單元的輸入輸出并行度。

圖2 3780 點FFT處理器框圖

3780 點FFT處理器內(nèi)部27點FFT和140點FFT運(yùn)算分時交替進(jìn)行，矩陣轉(zhuǎn)置模塊不需要采用雙緩存結(jié)構(gòu)，只需要存儲3780 個中間變換結(jié)果。輸入、輸出緩存模塊則分別采用兩組雙口RAM，以乒乓操作方式實現(xiàn)數(shù)據(jù)緩存及順序調(diào)整。下面對圖2中各單元的設(shè)計依次進(jìn)行詳細(xì)介紹。

2.2 輸入緩存單元

由于27點FFT模塊以9路輸入并行度進(jìn)行DFT運(yùn)算，所以輸入緩存單元需要完成數(shù)據(jù)緩存、順序調(diào)整及9路數(shù)據(jù)并行輸出功能。為保證流水線處理的高速進(jìn)行，輸入緩存單元采用兩組存儲器進(jìn)行乒乓存儲操作，每組存儲器結(jié)構(gòu)如圖3所示。

圖3 輸入緩存內(nèi)部結(jié)構(gòu)圖

由1.2節(jié)可知，3780 =27×140時，一層分解采用PFA算法，相應(yīng)的一層映射公式為

又27=9×3，二層分解采用混合計算法，相應(yīng)的二層映射公式為

根據(jù)式(9)～(10)，用Matlab對下標(biāo)如何調(diào)整進(jìn)行仿真，生成存儲地址映射表，通過查表方式，將串行接收的數(shù)據(jù)存儲到9個深度為420的存儲器中，并可按地址累加的方式輸出9路并行數(shù)據(jù)，送入27點FFT模塊進(jìn)行運(yùn)算，以滿足27點FFT模塊的9點并行度處理要求。

2.3 27點FFT單元

27點FFT運(yùn)算分9點FFT和3點FFT兩級，由混合基算法實現(xiàn)9點FFT和3點FFT的級聯(lián)，其實現(xiàn)結(jié)構(gòu)如圖4所示，其中9點和3點FFT采用第2.6節(jié)WFTA運(yùn)算單元。

圖4 27點FFT單元結(jié)構(gòu)

圖4中Cache1以乒乓操作方式完成混合基算法所需要的整序［2］。9點和3點WFTA單元分別以9路和3路輸入并行度進(jìn)行DFT運(yùn)算，為解決不同基WFTA單元間吞吐率的協(xié)調(diào)問題，內(nèi)部同時采用3個3點WFTA單元，使整個27點FFT單元以9路數(shù)據(jù)并行度進(jìn)行DFT運(yùn)算。

2.4 140點 FFT單元

140點FFT單元內(nèi)部由素因子算法實現(xiàn)7點、5點和3點FFT的級聯(lián)，其實現(xiàn)結(jié)構(gòu)如圖5所示，其中Cache2、Cache3以乒乓操作方式完成素因子算法所需要的整序［2］，7點、5點和3點FFT采用第2.6節(jié)WFTA運(yùn)算單元。

圖5 140點FFT單元結(jié)構(gòu)

7點、5點和4點WFTA單元分別以7路、5路和4路的輸入并行度進(jìn)行DFT運(yùn)算，不同基WFTA單元間吞吐率的協(xié)調(diào)原則是，高并行度運(yùn)算單元的處理速度同步于低并行度處理單元。以35=7×5為例，完成1次35點FFT運(yùn)算，7點和5點WFTA單元各需5個和7個時鐘周期，可通過控制信號，占用每7個時鐘周期中的5個完成1次7點WFTA運(yùn)算，使35點FFT的運(yùn)算速度同步于5點WFTA單元。同理，140點FFT運(yùn)算速度同步于4點WFTA單元。

2.5 輸出緩存單元

該模塊完成3780 點FFT結(jié)果存儲及整序輸出功能。為了匹配140點FFT單元的4路數(shù)據(jù)并行輸出要求，內(nèi)部采用4個深度為945的雙口RAM，以地址累加的方式對輸入數(shù)據(jù)進(jìn)行緩存。為保證流水線處理的高速進(jìn)行，輸出緩存單元采用兩組存儲器進(jìn)行乒乓存儲操作，每組存儲器結(jié)構(gòu)如圖6所示。

圖6 輸出緩存內(nèi)部結(jié)構(gòu)圖

由1.2節(jié)可知，3780 =27×140時，一層分解采用PFA算法，相應(yīng)的一層映射公式為

又140=35×4，二層分解采用混合計算法，相應(yīng)的二層映射公式為

根據(jù)式(11)～(12)，用Matlab對下標(biāo)如何調(diào)整進(jìn)行仿真，生成存儲地址映射表，通過查表方式，將緩存數(shù)據(jù)以串行方式輸出，實現(xiàn)3780 點FFT輸出整序功能。

2.6 WFTA算法FFT單元

為了提高吞吐率，WFTA運(yùn)算單元采用并行數(shù)據(jù)處理方式進(jìn)行硬件實現(xiàn)。3，4，5，7，9點WFTA模塊結(jié)構(gòu)相似，以3點為例說明其實現(xiàn)過程。

N=3時，WFTA計算公式為

X=Wx，對 W 分解得 X=CGBx，C，G，B 分別為

3點WFTA信號流如圖7所示。

圖73 點WFTA信號流圖

其硬件結(jié)構(gòu)如圖8所示。

圖8 WFTA硬件結(jié)構(gòu)圖

其中，D為寄存器，AC為累加器，B，G，C為矩陣系數(shù)產(chǎn)生器。

3 綜合及分析

編寫Verilog程序［9］，輸入復(fù)隨機(jī)數(shù)據(jù)，采用Modelsim進(jìn)行功能仿真，用 ISE軟件并選用 Xilinx Virtex－5 XC5VLX330t芯片來進(jìn)行綜合。將1000 次仿真輸出數(shù)據(jù)導(dǎo)入Matlab分析，當(dāng)輸入為10 bit數(shù)據(jù)，輸出為18 bit數(shù)據(jù)時，系統(tǒng)信噪比可達(dá)69 dB，滿足TDS_OFDM系統(tǒng)對信噪比的要求。在對信噪比有更高要求的應(yīng)用場合，可以在WFTA運(yùn)算模塊后加入塊浮點模塊來提高處理精度。

文獻(xiàn)［4－7］及本文處理器完成一次3780 點FFT運(yùn)算所需時鐘數(shù)Nclk如表1所示。其中，若3780 點FFT分1，2，…，n 級計算，且各級并行度為 vi(i=1，2，…，n)，則有

表1 1次3780 點FFT運(yùn)算所需時鐘數(shù)比較

從表1可以看出，本文3780 點FFT處理器的吞吐率是文獻(xiàn)［4－7］中處理器吞吐率的4.5倍。但是與文獻(xiàn)［5］中處理器相比，該處理器所占邏輯資源是其1.5倍，即該設(shè)計的3780 點FFT處理器，是用高1.5倍的邏輯資源換取4.5倍的高吞吐率。

4 結(jié)束語

綜合利用混合基算法、素因子算法及WFTA算法實現(xiàn)3780 點FFT運(yùn)算，滿足了系統(tǒng)的高計算精度要求;為提高系統(tǒng)吞吐率，在采用流水線結(jié)構(gòu)進(jìn)行硬件實現(xiàn)的基礎(chǔ)上，其內(nèi)部小點數(shù)WFTA單元采用并行數(shù)據(jù)處理方式進(jìn)行硬件實現(xiàn)，使系統(tǒng)吞吐率提高為串行處理方式時的4.5倍。

［1］GB 20600—2006，數(shù)字電視地面廣播傳輸系統(tǒng)幀結(jié)構(gòu)、信道編碼和調(diào)制［S］.2006.

［2］楊旭霞，歸琳，余松煜.3780點FFT處理器的研究［J］.電視技術(shù)，2005，29(11):32－34.

［3］崔振，王永賀，門愛東.DMB－T系統(tǒng)中FFT模塊的設(shè)計與實現(xiàn)［J］.電視技術(shù)，2008，32(S1):6－7.

［4］YANG Zhixing，HU Yupeng，PAN Changyong，et al.Design of a 3780－point IFFT processor for TDS－OFDM［J］.IEEE Trans.Broadcasting，2002，48(1):57－61.

［5］余飛.DTMB系統(tǒng)中3780點FFT處理器的算法設(shè)計及FPGA實現(xiàn)［D］.武漢:武漢理工大學(xué)，2008.

［6］上海明波通信技術(shù)有限公司.3780點快速傅里葉變換處理器及運(yùn)算控制方法:中國，200810043761.X［P］.2010－03－10.

［7］復(fù)旦大學(xué).流水線結(jié)構(gòu)的3780點快速傅里葉變換處理器:中國，200710044716.1［P］.2008－03－05.

［8］LIU Guanghui.ITD－DFE based channel estimation and equalization in TDS－OFDM receivers［J］.IEEE Trans.Consumer Electronics，2007，53(2):304－309.

［9］夏宇聞.Verilog數(shù)字系統(tǒng)設(shè)計教程［M］.北京:北京航空航天大學(xué)出版社，2003.