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

解春云，劉光輝，牛俊峰

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

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

1 3780點FFT算法

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

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

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

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

1.1 混合基算法

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

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

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

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

1.2 素因子算法(PFA)

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

當 A，B，C，D 滿足下列條件時

式(3)轉化為

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

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證明，當 N ∈ {2，3，4，5，7，8，9，16}時，復數(shù)矩陣 WN能以下列方式分解

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

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的基礎上，給出如圖1所示的算法方案。

圖1 本文算法方案分解圖

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

2 3780點FFT處理器設計

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

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

2.1 3780 點FFT處理器結構

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

圖2 3780 點FFT處理器框圖

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

2.2 輸入緩存單元

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

圖3 輸入緩存內部結構圖

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

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

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

2.3 27點FFT單元

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

圖4 27點FFT單元結構

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

2.4 140點 FFT單元

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

圖5 140點FFT單元結構

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

2.5 輸出緩存單元

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

圖6 輸出緩存內部結構圖

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

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

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

2.6 WFTA算法FFT單元

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

N=3時，WFTA計算公式為

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

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

圖73 點WFTA信號流圖

其硬件結構如圖8所示。

圖8 WFTA硬件結構圖

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

3 綜合及分析

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

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

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

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

4 結束語

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

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

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

［3］崔振，王永賀，門愛東.DMB－T系統(tǒng)中FFT模塊的設計與實現(xiàn)［J］.電視技術，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處理器的算法設計及FPGA實現(xiàn)［D］.武漢:武漢理工大學，2008.

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

［7］復旦大學.流水線結構的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)設計教程［M］.北京:北京航空航天大學出版社，2003.