LTE上行DFT/IDFT的一種設計實現

劉少雄，林平分

（北京工業大學 北京市嵌入式系統重點實驗室，北京100122）

為了降低手機終端的功率損耗[1]，LTE上行鏈路采用基于DFT擴頻OFDM（DFTS_OFDM）的單載波傳輸，又稱為單載波FDMA（SC_FDMA）。DFTS_OFDM方案的基本結構如圖1所示。3GPP協議規定[2]上行PUSCH信道產生SC_FDMA符號要求DFT點數滿足式(1)。

由幾個參數的變化可以得到最小12點、最大1 296點共35種模式的DFT[3]。現在已有的研究方法(如質因子分解結合 WFTA算法)解決非 2n點 DFT，但此法不夠靈活，不適合長度可變的DFT。在數字電視DTMB系統中，3 780點FFT的處理采用分裂基與質因子分解結合WFTA算法實現，但對于LTE上行可配置長度DFT的實現還沒有一個成熟有效的方法。

根據LTE實時系統需求采用pipeline流水線結構實現高速可配置的DFT設計，同時在結構和資源利用上進行優化，最后給出仿真圖形以及綜合結果，為上行LTE設計提供一種參考。

1 算法推導

由 3GPP協議可以看出，LTE中的DFT點數由 4、2、5、3小因子構成，可以將其分解成如式(2)形式：

對于LTE系統來說最多的級數是1 200點，N=1200=4×4×5×5×3=r1r2r3r4r5， 所以這里以一個 5 級的分而治之DFT推導為例，采用正位序進倒位序出的方式對參數k、n進行重新組織：

2 總體結構及技術實現

2.1 整體結構框圖

LTE DFT的模塊化總體結構如圖3所示，根據算法分析可以知道LTE DFT的分而治之需要幾個階段才能完成，每個階段需要做多次小因子點的DFT，所以圖示是一個循環的形式。由狀態機控制這些階段的完成，直到最后一個循環結束輸出數據。

其中前處理進入WFTA模塊的包括對4個雙端口RAM的讀取控制以及對旋轉因子ROM的讀取，還有旋轉因子地址的計算。飽和操作根據系統的最大bit數限定，對經過WFTA計算后的數據進行飽和處理，超過的bit數直接截取掉。

2.2 技術實現

2.2.1 4 個雙端口RAM的數據存儲

為保證pipeline地處理每次循環的數據，這里采用4個雙端口RAM對數據進行存取。對4、2、5、3四種小因子的WFTA計算來說，選4個RAM最方便，如果需要進行4點的WFTA計算，則從每個RAM中讀出一個數據，這僅需要一個時鐘就可讀出4個數據。對2點的WFTA計算，則可以一個時鐘讀出兩組的2點WFTA進行計算。對3點的用一個時鐘，對于5點的用兩個時鐘讀取。

在基于原位計算的基礎上進行改進，加入旋轉數據模塊，是為了將本來是在一個RAM中的數據在填入RAM前進行旋轉，使其在不同的RAM中便于下一階段pipeline讀取。圖4展示了一個最簡單的12點的填寫RAM實例，在開始第一階段前先將12點的輸入數通過載入buffer模塊用12個clk按圖3順序載入4個RAM中，也就是將數據倒位序放入4個RAM中。將倒位序之后的數據重新標號，即1對應載入buffer的3，2對應6等。這樣做的目的是為了方便計算地址。例如，在第一階段讀的過程中，0、1、2、3通過右移 2 bit， 即除以 4可以算出地址為0，它們分別對應4個RAM的第0地址；同理 4、5、6、7除以 4可以得到 1，即對應 1地址，依此類推。

根據公式4的推導可知在第一階段DFT的處理中不需要乘以旋轉因子，所以旋轉因子為0，在第一階段和第二階段中需要先乘以旋轉因子，旋轉因子按照公式推導處理列出在表中。在第一階段先處理 0、1、2、3四點的WFTA，然后按原位順序填入 4個RAM，接著處理4、5、6、7四點的 WFTA，本來應該也按原位填入 RAM中，但是注意到在第二階段需要處理 0、4、8三點的WFTA，如果還按照原位填入，則0、4、8三個數據在同一個RAM中，要讀取這3個數需要3個clk，顯然不適應pipeline的處理。 所以在做完 4、5、6、7四點的 WFTA之后將數據旋轉再寫入 4個RAM中，同樣將 8、9、10、11四點的結果也旋轉，如圖4所示。這樣的讀寫RAM操作可以保證pipeline的處理。

2.2.2 旋轉因子的存取

根據式(4)的推導，每一級之間需要先乘以旋轉因子，對于旋轉因子的地址計算依據式(4)的推導。由于要實現35種可配置模式的DFT設計，所以在實現時要盡可能地考慮旋轉因子的共享存儲，從而盡可能地減少存儲這些旋轉因子的ROM大小。

(1)根據 2的冪次方關系特性，將 35種模式的 DFT旋轉因子分成10組，并存儲這10組中最大的點的八分之一構成一個ROM。對于N點（對應組中最大的點），只存儲「N/8?個地址數據；

(2)對于計算出的旋轉因子地址K，根據它所處的DFT 模式，選擇它所屬的組，10 組分別用{R0，R1，R2，…，R9}表示；

(3)如果 K在 R5，則 R0+R1+R2+R3+R4為它的偏移地址offset；

(4)12點的DFT需要用此組中最大的768點ROM表來找數，則地址K有可能是[0，…，11]×768/12中的一個作為有效地址eff_dft_addr；

(5)對 于 算 出 的 eff_dft_addr，根 據 對 「N×1/8?，… ，「N×7/8?的比較找出它處于 768點中的哪個位置（此處N為 768），即哪個 1/8象限；

(6)找出所處的象限后，再找出其在第一個1/8對稱的位置值 dft_8_addr，計算出 dft_addr=offset+dft_8_addr，然后在ROM表中找出對應的值，再根據對稱性還原其原來的所屬象限的值。如圖5所示，展示一個點的查找方式。通過查找A″的值來得到A的值。

2.2.3 WFTA的運算單元

WFTA 算 法 對 2、3、4、5、7、8、9、16 等 小 N 點有 較快速處理能力，它將小N點DFT轉換為循環卷積，利用多項式理論使卷積計算盡可能減少乘法。

一個 N點的 DFT可以表示為 X=Wx，W為 N×N的旋轉因子矩陣，Winograd證明那幾個小N點的W矩陣可以表示為 W=CGB，C表示為 N×J的矩陣，G表示為J×J的對角矩陣，B表示為J×N的矩陣。CB矩陣的元素都是比較簡單的數(0、±1、±2等)，G矩陣元素一般為實數或純虛數。LTE只用到 4、2、5、3四點，下面給出 3點的WFTA算法[5]：

由圖6所示3點的WFTA信號流圖可知，用了6個加減法，通過化簡并移位，實際只用了一個乘法。

2.2.4 塊浮點的數據處理

定點運算的特點是速度快但動態范圍小。浮點運算的特點則是動態范圍大但占用資源大。塊浮點具有兩種運算的優點，是兩種運算的折中，讓一組數具有共同的階碼，這個階碼是同組數中最大的那個數的階碼，簡化系統資源提高運算的精度[6]。

表1 塊浮點處理

如表1所示，因為每次WFTA運算后都有數據位寬的擴展，本結構具有3 bit的擴展。為保持輸入wfta_top的模塊數據始終為18 bit，這里用塊浮點動態截取的方法對每一級的WFTA結果進行處理，動態截取的位寬決定下一級的數據寬度，同時循環累加每個階段的階碼，在數據輸出時進行還原操作。

3 仿真綜合

圖7所示為12點DFT的仿真圖形，dft模式是第一種，首先data_in_vld為高時開始數據輸入，然后用12個clk將數據讀入4個RAM，之后計算第一級RAM讀取地址將數據讀出，處理3次4點的 DFT，處理后將數據寫入RAM，需要3個clk；再后讀出數據做4次3點的DFT，處理后將數據寫入 RAM，需 4個 clk；最后將數據讀出做壓縮還原處理，data_out_vld為高后pipeline出數，需要 12個clk。理論上需要31個 clk，但是在處理中需要處理與其他模式的共享，還要有打拍延時等操作，實際用掉 98個 clk。120點的 DFT實際用 502個 clk，理論上是 120×2+30+30+24+40=364個 clk，說明處理的點數越多冗余clk比例越小。

使用stratix III EP3SL340F1517I3芯片，運用Quartus II綜合后的結果為：7 824個組合 ALUT，0個內存 ALUT，8 699個邏輯寄存器，可達到時鐘 124.64 MHz，滿足 LTE系統時鐘122.88 MHz的要求。

文章在介紹LTE上行SC_FDMA的基礎上，對35種模式的DFT預編碼進行算法分析，提出并用FPGA實現了一種高速可配置的方案。文中對數據存儲、WFTA運算單元和塊浮點處理進行簡單表述，根據旋轉因子特性，詳細介紹了旋轉因子的優化，大大降低了35種模式旋轉因子的存儲大小。最后給出的仿真綜合結果表明該方案具有較好的性能。

[1]DAHLMAN E.3G evolution:HSPA and LTE for mobile broadband.Published by Elsevier Ltd.2007：75-81.

[2]3GPP TS 36.211.Evolved universal terrestrial radio access(E-UTRA).Physical channels and modulation.

[3]Xilinx.LogiCORE IP discrete fourier transform v3.1.DS615.2009.

[4]何小敏.LTE系統中DFT快速算法研究[DB/OL].(2009-12-24).中國科技論文在線.http://www.paper.edu.cn/paper.php?serial_number=2009/2-937.

[5]胡廣書.數字信號處理——理論、算法與實現[M].北京：清華大學出版社，2003.

[6]陳麗安,張培銘.定點 DSP塊浮點算法及其實現技術[J].福州大學學報，2004，32(6)：689-693.