3780點 FFT處理器的算法研究

徐曉青,楊霏,李建平

(中國傳媒大學信息工程學院,北京 100024)

1 引言

時域同步正交頻分復用(TDS-OFDM)是地面數字電視標準(DMB-T)的核心技術,是屬于創新的多載波調制方式。它采用 8MHz的帶寬,使用3780個子載波來傳輸數字電視信號。TDS-OFDM技術中用于調制及解調的3780點 FFT處理器,關系到整個系統的效率和規模,是 DMB-T系統中不可缺少的重要模塊之一。目前最常用的實現方法是采用層層分解的總體思想[1]:先把 3780分解為 63×60,再把 63和 60分別分解為 7×9和 3×(5×4)。綜合利用混合基算法、素因子分解算法和 WFTA算法來求得 3780點的 FFT。

筆者提出一種新的分解方式,將 3780點先按素因子分解算法進行分解為 140×27,140點繼續按素因子分解算法分解為 7×5×4,27點則按混合基算法分解成 3 ×9,而 9、7、5、4、3點 FFT均采用 WFTA來實現。此種分解方式在硬件實現上減少了運算量和存儲空間。本論文同時對算法進行了改進,使用了同址順序的素因子算法,省去了最后的順序重排,且減少了存儲量和數據傳遞次數,提高了運算速度。

2 3780點 FFT算法

2.1 混合基算法

混合基(Cooley-Tukey)的快速傅里葉算法如下:

作 N點 FFT時,如 N可分解為 N=N1×N2,且N1,N2有公共因子。

設 x(n)為 N點有限長序列,其 DFT為:

2.2 素因子算法(PFA)

利用素因子分解算法[2],旋轉因子可通過選擇n1,n2,k1,k2前的特殊系數而消去,于是得到 N=M1M2…Ml點 FFT

式中 M1,M2…Ml相互互質,即任意兩個的最大公約數為 1,這樣可把 N點的 FFT化為 l級的M1,M2…Ml點的 FFT級聯來完成。算法中除了各個 Mi點的 DFT,沒有引入乘旋轉因子的運算,因此是一種高效的 FFT算法。

2.3 Winograd DFT algorithm(WFTA)

winograd DFT算法[3]是一種快速的短 N的 DFT算法,其核心思想是通過矩陣的降解,以實現 DFT最少的加減及乘除法運算。

N點 DFT可以用矩陣表示為 X=Wx,其中,

當 N∈{2,3,4,5,7,8,9,16}時,復數矩陣 W能夠以下列方式分解:

W=ODI,

其中,D為一個 J×J的對角矩陣,并且對角線上的元素為實數或者純虛數,O為一個 N×J的關聯矩陣,I為一個 J×N的關聯矩陣。與這樣的W相乘可以避免復數乘法,并且加法次數與 Cooley-Tukey的算法相近,因此 winograd提出的“小 N”DFT算法是一種高效的算法。

如 N=3,WFTA如下:

可對 W進行分解,其中 O,D,I分別為:

可見總過程只需 4次實數乘法和 6次復數加法。

2.4 算法實現過程及優點

在筆者的實現方案中,素因子分解用在實現140點和 27點的 FFT上,因為 140與 27互質。140點繼續按素因子分解算法分解為 7×5×4,7、5、4之間互質。由于 3與 9有公約數,所以 27則按照混合基算法分解成 3×9。而 9、7、5、4、3點 FFT均采用WFTA來實現。圖 1所示為此算法結構:

圖 1 3780點 FFT算法結構圖

由于 140×27采用了素因子算法進行分解,因此 140點和27點 FFT之間僅存在素因子地址映射,而不存在 3780點旋轉因子。但是該算法中 3×9采用的混合基算法同樣存在 3780點的旋轉因子,也就是說該分解方式并沒有減少旋轉因子的復數乘法。

經過計算發現,這種分解方式與 60×63的分解方式所需要的加法和乘法的次數是相同的。但是 3×9的混合基的旋轉因子不同的只有 27個值,3780個旋轉因子是 140組重復的 27個值,而 63×60的混合基的旋轉因子卻是 3780個不同的值。從硬件實現上面來說,明顯可以看出 140×27的分解方式比 60×63的分解方式節省了復數乘法的計算量和存儲空間。

2.5 算法的改進

這種分解方式也存在問題:素因子算法由于采用素因子分解,運算中省去了級間旋轉因子所需的乘法,運算量小,運算速度快,但由此會導致結果數據的亂序,在輸出時還要進行最后的整序工作,這一操作耗費的時間不容小視,而且增加了存儲空間的開銷。

于是,在研究方案中采用了同址、順序素因子算法。它省去了最后的順序重排,且減少了存儲量和數據傳遞次數,提高了運算速度。

為了得到順序的輸出,而避免通過整序來對變換的結果重新排序,在一維 DFT映射成 M維 DFT時,對n和 k沒有采用原先算法的下標映射關系,而是采用了相同的下標映射[4]:

這里 ＜＞N為模 N的意思。每個小 N點 DFT的輸出都是按照 ki′進行排序的,因此要得到順序的輸出,就要按照 ki′對每個小 N點 DFT的輸出重新排序。

順序的主要思想是:WFTA小 N因子 DFT的輸出按照 ki重新排序,得到的輸出對 ki′是正常順序。對每一個小 N的 DFT的重排序比較容易實現,并能節省運算量。這種算法將素因子算法最后的整序改為對每一個小 N的 DFT整序,程序仍具有通用性,而且能提高程序運行速度。

簡單的說,同址運算的思想就是:對于每一個運算的輸出數據,可將其存放在存儲輸入數據所對應的存儲單元,即用輸出覆蓋原來的輸入數據所占的RAM區域。因此值需要 N個復數的存儲單元,不但可存放輸入的原始數據,而且可存放中間結果,并還可以存放最后的運算結果。這種同址運算方式節省了大量的存儲單元,是一大優點.

圖 2為 3780點 FFT實現的流程圖:

圖 2 FFT實現流程圖

3 結果驗證

用 Matlab仿真該 FFT處理器,并與 Matlab提供的 FFT函數進行比較,可得到 FFT處理器的運算精度。輸入為 3780個 16QAM的隨機分布的值,圖 3顯示的是 matlab自帶的FFT函數運行后,選取前 100個數值的顯示圖,而圖4則是使用本文方案的算法設計后,所得結果與 matlab自帶函數算出結果的差值圖,從圖 4中,我們可以看出,它們的差值很小,數量等級達到了 10的 -13次方,所以這種誤差是可以忽略的。

4 結束語

本文介紹了一種新的 3780點 FFT處理器的算法分解方式,并采用了同址順序的素因子算法對算法進行了改進。仿真結果表明,這種分解方式是正確的。本文介紹的分解方法,非常適用于軟、硬件的實現。

[1] Zhi-Xing Yang,Yu-Peng Hu,Chang-Yong Pan,Lin Yang.Design of a 3780-point IFFT processor for TDS-OFDM[J].IEEE Tran Broadcasting,2002,48:57-61.

[2] R E布萊赫特 .數字信號處理的快速算法[M].肖先賜,等,譯 .北京:科學出版社,1992.

[3] Harvey F Silverman.An Introduction to Programming the Winograd Fourier Transform Algorithm(WFTA)[J].IEEE Transactions On A-coustics,Speech,and Signal Processing,1977,25(2).

[4] Sidney Burrus C,Eschenbacher P W.An In-Place,In-Order Prime Factor FFT Algorithm[J].IEEE Transactions on Acoustics,Speech,and Signal Processing,1981,29(4).