高速3780 點FFT處理器的設計與實現

解春云，劉光輝，牛俊峰

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

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

1 3780點FFT算法

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

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

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

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

1.1 混合基算法

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

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

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

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

1.2 素因子算法(PFA)

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

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

式(3)轉化為

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

1.3 Winograd小點數DFT算法

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

一個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}時，復數矩陣 WN能以下列方式分解

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

1.4 3780點FFT算法

3780 可分解為3780 =7×5×3×3×3×2×2，在考慮到WFTA 算法提出的16，9，8，7，5，4，3，2 幾種小點數 DFT 算法，且優先使用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的混合基算法分解方案比較，該方案可節省3780 個旋轉因子的存儲。

2 3780點FFT處理器設計

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

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

2.1 3780 點FFT處理器結構

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

圖2 3780 點FFT處理器框圖

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

2.2 輸入緩存單元

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

圖3 輸入緩存內部結構圖

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

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

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

2.3 27點FFT單元

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

圖4 27點FFT單元結構

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

2.4 140點 FFT單元

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

圖5 140點FFT單元結構

7點、5點和4點WFTA單元分別以7路、5路和4路的輸入并行度進行DFT運算，不同基WFTA單元間吞吐率的協調原則是，高并行度運算單元的處理速度同步于低并行度處理單元。以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路數據并行輸出要求，內部采用4個深度為945的雙口RAM，以地址累加的方式對輸入數據進行緩存。為保證流水線處理的高速進行，輸出緩存單元采用兩組存儲器進行乒乓存儲操作，每組存儲器結構如圖6所示。

圖6 輸出緩存內部結構圖

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

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

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

2.6 WFTA算法FFT單元

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

N=3時，WFTA計算公式為

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

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

圖73 點WFTA信號流圖

其硬件結構如圖8所示。

圖8 WFTA硬件結構圖

其中，D為寄存器，AC為累加器，B，G，C為矩陣系數產生器。

3 綜合及分析

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

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

表1 1次3780 點FFT運算所需時鐘數比較

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

4 結束語

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

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

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

［3］崔振，王永賀，門愛東.DMB－T系統中FFT模塊的設計與實現［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系統中3780點FFT處理器的算法設計及FPGA實現［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數字系統設計教程［M］.北京:北京航空航天大學出版社，2003.