3780點 FFT處理器的算法研究

徐曉青,楊霏,李建平

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

1 引言

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

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

2 3780點 FFT算法

2.1 混合基算法

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

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

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

2.2 素因子算法(PFA)

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

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

2.3 Winograd DFT algorithm(WFTA)

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

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

當(dāng) N∈{2,3,4,5,7,8,9,16}時,復(fù)數(shù)矩陣 W能夠以下列方式分解:

W=ODI,

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

如 N=3,WFTA如下:

可對 W進(jìn)行分解,其中 O,D,I分別為:

可見總過程只需 4次實數(shù)乘法和 6次復(fù)數(shù)加法。

2.4 算法實現(xiàn)過程及優(yōu)點

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

圖 1 3780點 FFT算法結(jié)構(gòu)圖

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

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

2.5 算法的改進(jìn)

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

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

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

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

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

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

圖 2為 3780點 FFT實現(xiàn)的流程圖:

圖 2 FFT實現(xiàn)流程圖

3 結(jié)果驗證

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

4 結(jié)束語

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

[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布萊赫特 .數(shù)字信號處理的快速算法[M].肖先賜,等,譯 .北京:科學(xué)出版社,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).