王 丹，許 虎

（重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶400065）

在數(shù)字信號(hào)處理中，離散傅里葉變換(DFT)是常用的變換方法，它在各種數(shù)字信號(hào)處理系統(tǒng)中扮演著重要的角色?？焖俑道锶~變換(FFT)[1-2]是離散傅里葉變換的快速算法，它是根據(jù)離散傅里葉變換的奇、偶、虛、實(shí)等特性，對(duì)離散傅里葉變換的算法進(jìn)行改進(jìn)獲得的，兩者都是為了將信號(hào)變換到頻域并進(jìn)行相應(yīng)的頻譜分析。對(duì)于實(shí)時(shí)性要求很強(qiáng)的信號(hào)處理來說，運(yùn)算速度對(duì)整個(gè)處理的影響是顯而易見的。因?yàn)镕FT擁有很高的運(yùn)算能力，使其在無線通信和數(shù)字通信、高速圖像處理、匹配濾波等領(lǐng)域得到極為廣泛的應(yīng)用。

LTE作為準(zhǔn)4 G技術(shù)，以正交頻分復(fù)用OFDM和多輸入多輸出MIMO技術(shù)為基礎(chǔ)，下行采用正交頻分多址（OFDM）技術(shù)，上行采用單載波頻分多址（SC-FDMA）技術(shù)，在20 MHz頻譜帶寬下能夠提供下行100 Mb/s和上行 50 Mb/s的峰值速率[3]。

頻域分析比時(shí)域分析更優(yōu)越，不僅簡單，且易于分析復(fù)雜信號(hào)[4]。在LTE系統(tǒng)中，F(xiàn)FT算法主要應(yīng)用于基帶信號(hào)生成、信號(hào)的接收和檢測等，將時(shí)域信號(hào)轉(zhuǎn)移到頻域進(jìn)行處理。

1 FFT算法分析

設(shè)x(n)為N點(diǎn)的有限長度序列，其DFT正變換為：

假設(shè)輸入序列x(n)長度為N=2M，M是正整數(shù)。如果不滿足這個(gè)條件，在序列尾部人為地加上若干零值點(diǎn)，使其達(dá)到這一要求。將序列x(n)按n的奇偶分解為兩個(gè)N/2點(diǎn)的子序列：

按以上步驟繼續(xù)分為奇偶組，直到分解兩個(gè)點(diǎn)的DFT為止。圖1是使用FFT算法和直接DFT算法總運(yùn)算量與抽樣點(diǎn)數(shù)N的關(guān)系圖。

序列x(n)逆變換（IDFT）連續(xù)取兩次共軛有：

這樣逆變換也可以直接調(diào)用FFT子程序。

2 FFT算法的DSP實(shí)現(xiàn)

2.1 硬件

MS320C6000系列DSP是TI公司推向市場的高性能DSP，綜合了目前性價(jià)比高、功耗低等優(yōu)點(diǎn)。TMS320C64系列提高了時(shí)鐘頻率，在體系結(jié)構(gòu)上采用了VelociTI甚長指令集 VLIW（Very Long Instruction Word）結(jié)構(gòu)[5]，芯片內(nèi)有8個(gè)獨(dú)立功能單元的內(nèi)核，每個(gè)周期可以并行執(zhí)行8條32 bit指令，最大峰值速度為4 800 MIPS，2組共64個(gè)32 bit通用寄存器，32 bit尋址范圍，支持8/16/32/40 bit的數(shù)據(jù)訪問，芯片內(nèi)集成大容量SRAM，最大可達(dá)8 Mb。由于出色的運(yùn)算能力、高效的指令集、大范圍的尋址能力，使其特別適用于無線基站、測試儀表等對(duì)運(yùn)算能力和存儲(chǔ)量要求高的應(yīng)用場合。

2.2 FFT算法的DSP實(shí)現(xiàn)

FFT算法作為一個(gè)子函數(shù)模塊且輸入序列長度不盡相同，所以，方案定義了輸入輸出變量及其調(diào)用格式。調(diào)用格式：Turbo_Code(int*，int，int，char*，char*，int*)，其中，int分別表示輸入序列的長度和FFT的級(jí)數(shù)；int*分別表示輸入序列的首地址和輸出序列的首地址；char*分別表示旋轉(zhuǎn)因子的余弦的首地址和旋轉(zhuǎn)因子的正弦的首地址。

FFT算法具體實(shí)現(xiàn)流程如下：

(1)時(shí)間抽取法的FFT中，每個(gè)蝶形的輸入、輸出數(shù)據(jù)節(jié)點(diǎn)在一條水平線上，所以每個(gè)蝶形的輸出數(shù)據(jù)可以立即存入原輸入數(shù)據(jù)所占用的存儲(chǔ)單元。這種原位計(jì)算可節(jié)省大量的內(nèi)存，并且理論上減少不同寄存器之間存取數(shù)據(jù)的時(shí)間。

(2)N點(diǎn)時(shí)間抽取法FFT運(yùn)算中，每級(jí)都有N/2個(gè)蝶形，每個(gè)蝶形都有旋轉(zhuǎn)因子WPN。第 L級(jí)共有 2(L-1)個(gè)不同的旋轉(zhuǎn)因子。對(duì)于N=2M的一般情況，第L級(jí)的旋轉(zhuǎn)因子為：

第L級(jí)中的每個(gè)蝶形的輸入數(shù)據(jù)相距B=2L-1個(gè)點(diǎn)，同一旋轉(zhuǎn)因子對(duì)應(yīng)著間隔為2L點(diǎn)的2M-L個(gè)蝶形。

(3)在FFT運(yùn)算中，旋轉(zhuǎn)因子為：

由于求正弦和余弦函數(shù)值的計(jì)算量很大，所以編程時(shí)，采用旋轉(zhuǎn)因子查表法。在FFT程序開始前預(yù)先計(jì)算出所有的旋轉(zhuǎn)因子并存放在內(nèi)存中，程序執(zhí)行時(shí)直接查表得到所需的旋轉(zhuǎn)因子值。這種方法大大提高了運(yùn)算速度，不足之處是占用內(nèi)存較多。

使用C語言編寫主函數(shù)，匯編語言編寫FFT算法的實(shí)現(xiàn)函數(shù)。程序中假設(shè)輸入數(shù)據(jù)最大長度為1 024，由于DSP C6455可以直接存取處理32 bit，所以在內(nèi)存中定義了長度為8 192 bit作為存放輸出序列的內(nèi)存空間。為了提高運(yùn)算精確度，輸入數(shù)的實(shí)部和虛部分別占用一個(gè)字，在程序中進(jìn)行復(fù)數(shù)相乘操作是采用匯編指令MPY-HI。內(nèi)存定義了長度為2 048 bit的Tempsequence作為存放倒序序列，并且建立了2張旋轉(zhuǎn)因子查找表，分別為Wr和 Wi。

外循環(huán)中，在每次內(nèi)循環(huán)之前從輸入比特序列中取出32 bit放入一個(gè)寄存器，作為一個(gè)內(nèi)循環(huán)的輸入，內(nèi)循環(huán)結(jié)束后，取下一個(gè)32 bit輸入比特更新這個(gè)寄存器。

內(nèi)循環(huán)中，計(jì)算蝶形過程采用查表的方式。對(duì)于每一級(jí)，計(jì)算出需要的旋轉(zhuǎn)因子個(gè)數(shù)以及相同旋轉(zhuǎn)因子相距的間隔。計(jì)算蝶形過程時(shí)，首先提取出X(k)，根據(jù)相同旋轉(zhuǎn)因子間隔找到X(k+B)完成蝶形計(jì)算。考慮到旋轉(zhuǎn)因子的對(duì)稱性，在內(nèi)存中存放旋轉(zhuǎn)因子時(shí)只存放一半，剩余的數(shù)據(jù)根據(jù)對(duì)稱性進(jìn)行處理。圖2給出了FFT算法實(shí)現(xiàn)計(jì)算流程圖。

按時(shí)間抽取法的FFT輸入序列是倒序，輸出序列是自然順序；按頻率抽取法的FFT輸入序列是自然順序，輸出序列是倒序的。不管采用哪種方法進(jìn)行FFT計(jì)算，都需要倒序處理。倒序是整個(gè)FFT計(jì)算的重要部分，進(jìn)行匯編程序時(shí)，按自然順序?qū)⑤斎霐?shù)據(jù)存入到存儲(chǔ)單元內(nèi)，通過變址運(yùn)算，將自然順序的序列按時(shí)間抽取法要求進(jìn)行倒位。

重新排序之前，存儲(chǔ)單元Y中依次存放輸入數(shù)據(jù)，I表示當(dāng)前輸入數(shù)據(jù)比特的順序數(shù)的十進(jìn)制數(shù)值，I的取值從0到N-I；J表示當(dāng)前倒序數(shù)的十進(jìn)制數(shù)值。輸入序列的第一個(gè)和最后一個(gè)數(shù)的位置不需要倒序處理，完成倒序的外循環(huán)的次數(shù)為N-2。為了保證調(diào)換數(shù)據(jù)的正確性，需要檢測一下是否 I＜J，只有當(dāng) I＜J，才將 Y(I)與Y(J)的內(nèi)容互換。形成倒序數(shù)J以后，就可以實(shí)現(xiàn)變址功能，按照自然順序存放在存儲(chǔ)單元的數(shù)據(jù)重新按照倒序排列。圖3給出了實(shí)現(xiàn)倒序的匯編流程圖。

3 性能分析與總結(jié)

在DSP軟件實(shí)現(xiàn)中，通過指令并行，盡量優(yōu)化程序循環(huán)體，減少或消除程序中的’NOP’指令[6]。通過程序仿真運(yùn)行，得到統(tǒng)計(jì)結(jié)果如表1所示。

表1 不同數(shù)據(jù)長度的FFT算法速率

從表中可以看出，當(dāng)運(yùn)用TMS320C64×DSP芯片實(shí)現(xiàn)時(shí)，由于處理器的超高主頻一般為1 GHz，一個(gè)指令周期耗時(shí)為1 ns，其運(yùn)算速率非常快，完全可以滿足實(shí)時(shí)性信號(hào)處理。因此，采用旋轉(zhuǎn)因子查表法的實(shí)現(xiàn)方案不僅簡化了程序?qū)崿F(xiàn)方法，還減少了模塊程序代碼編寫，節(jié)約了系統(tǒng)存儲(chǔ)空間。

本文提出了一種簡單有效的FFT算法實(shí)現(xiàn)方案，詳細(xì)介紹了算法在DSP的實(shí)現(xiàn)方法，并在TMS320C64x芯片上加以實(shí)現(xiàn)。程序運(yùn)行結(jié)果表明，該算法能夠滿足TD-LTE系統(tǒng)的需求，具有可行性和高效性。該方案已應(yīng)用于LTE-TDD無線綜合測試儀表的開發(fā)中。

[1]丁玉美.數(shù)字信號(hào)處理[M].西安：西安電子科技大學(xué)出版社，2002.

[2]何方白，張德民.數(shù)字信號(hào)處理[M].北京：高等教育出版社，2009.

[3]3GPP TS 36.211 v9.0.0.Evolved universal terrestrial radio access(E-UTRA)physical channels and modulation(Release 9)[S].2009-12.

[4]SAIDI A.Decimation-in-time-frequency FFT algorithm[M].Manuscript,To be published.1993.

[5]Texas Instruments Incorporated.TMS320C64x/C64x+DSP CPU and instruction set referenceguide[EB/OL].Http://www.ti.com.cn,2008.

[6]Texas Instruments Incorporated.TMS320C6000系列DSP編程工具與指南[M].田黎育，何佩琨，朱夢(mèng)宇，譯.北京：清華大學(xué)出版社，2006.