摘  要： 在數(shù)字信號(hào)處理中，FFT運(yùn)算具有非常重要的作用。傳統(tǒng)FFT算法具有原位計(jì)算的特點(diǎn)，原位FFT算法在自然序輸入時(shí)輸出呈逆序狀態(tài)，因此為了得到自然序的結(jié)果數(shù)據(jù)，就必須對(duì)全部FFT輸出數(shù)據(jù)進(jìn)行整序。使用查找表整序是從FFT的逆序輸出結(jié)果中直接讀取自然序結(jié)果數(shù)據(jù)。試驗(yàn)證明，在獲取全部FFT結(jié)果數(shù)據(jù)時(shí)，查找表整序相比傳統(tǒng)整序在時(shí)間效率上可以提高一倍，并且在連續(xù)FFT分析的情況下，優(yōu)勢(shì)會(huì)更明顯。

　　關(guān)鍵詞： FFT；逆序；整序；查找表

0 引言

　　在原位FFT運(yùn)算過(guò)程中，當(dāng)輸入數(shù)據(jù)為自然序時(shí)，由于FFT算法過(guò)程對(duì)輸入數(shù)據(jù)的多次“奇偶抽取”，使得輸出數(shù)據(jù)呈逆序狀態(tài)，即輸出數(shù)據(jù)的索引和自然序索引的二進(jìn)制表示呈相互位逆序狀態(tài)[1]。因此必須對(duì)輸出數(shù)據(jù)進(jìn)行整序，才能得到自然序的結(jié)果。即一次FFT分析包括FFT計(jì)算和對(duì)FFT逆序輸出的整序。FFT分析幾乎都在DSP處理器中完成，DSP處理器通過(guò)內(nèi)部CPU逐條執(zhí)行軟件指令來(lái)完成各種運(yùn)算和邏輯功能[2]。因此，在DSP內(nèi)執(zhí)行一次FFT算法，必須順序執(zhí)行FFT計(jì)算和整序操作[3-5]。研究者為提升整序效率進(jìn)行了多種改進(jìn)，有的是對(duì)整序過(guò)程中的逆序數(shù)計(jì)算進(jìn)行了多種改進(jìn)，比如逆序數(shù)生成法[6-7]和分組數(shù)據(jù)交換法[8]，但這些改進(jìn)只關(guān)注了整序過(guò)程中的逆序數(shù)計(jì)算這一個(gè)方面；有的將逆序數(shù)計(jì)算與整序結(jié)合在一起，比如任意基的快速整序算法[9-10]，但這種方法理解起來(lái)很困難[11]。

　　在實(shí)際應(yīng)用中，所感興趣的目標(biāo)FFT數(shù)據(jù)，無(wú)論是全部FFT數(shù)據(jù)還是部分?jǐn)?shù)據(jù)，都可看作全部自然序的FFT結(jié)果中的一段，那么可以設(shè)法從FFT逆序輸出中直接獲取這一段目標(biāo)數(shù)據(jù)。即首先明確目標(biāo)數(shù)據(jù)段在整序后的FFT結(jié)果中的位置，計(jì)算這些位置索引值的逆序數(shù)并存儲(chǔ)在一個(gè)查找表中，然后根據(jù)此查找表就可以在FFT的逆序輸出數(shù)據(jù)中直接提取目標(biāo)數(shù)據(jù)。采用此算法將逆序數(shù)的計(jì)算從整序過(guò)程中剝離，簡(jiǎn)化整序過(guò)程，提高整序效率。使用查找表整序的方式易于理解，操作簡(jiǎn)單，并且在需要進(jìn)行連續(xù)FFT分析的情況下會(huì)體現(xiàn)出很大的優(yōu)勢(shì)。

1 FFT算法的原位計(jì)算的特點(diǎn)

　　圖1是8點(diǎn)的時(shí)域抽取基-2的原位FFT算法流程，輸入數(shù)據(jù)是自然序的，輸出數(shù)據(jù)為逆序狀態(tài)[4]。

　　對(duì)圖1中FFT的輸入數(shù)據(jù)和輸出數(shù)據(jù)的索引變化在表1中予以反映。

　　由表1可見，原位FFT的輸入數(shù)據(jù)為自然序，輸出數(shù)據(jù)為逆序，并且將自然序索引二進(jìn)制表示的比特排列順序完全逆過(guò)來(lái)，就得到逆序索引的二進(jìn)制表示[5]。因此為了得到自然序的FFT結(jié)果，就需要對(duì)FFT的逆序輸出結(jié)果進(jìn)行整序。傳統(tǒng)的整序算法是在原位FFT計(jì)算完畢后依自然序遍歷每一個(gè)輸出數(shù)據(jù)，先通過(guò)“比特倒序”運(yùn)算計(jì)算自然序索引的逆序數(shù)，此逆序數(shù)就是輸出數(shù)據(jù)的正確索引值，再以逆序數(shù)為索引調(diào)整這個(gè)FFT數(shù)據(jù)的位置，最后得到全部自然序的FFT結(jié)果數(shù)據(jù)。在DSP內(nèi)只能使用高級(jí)語(yǔ)言編碼實(shí)現(xiàn)位逆序時(shí)，傳統(tǒng)做法是利用產(chǎn)生逆序數(shù)的十進(jìn)制運(yùn)算規(guī)律，采用循環(huán)迭代計(jì)算逆序數(shù)[4-5]。

　　一次傳統(tǒng)的N點(diǎn)原位FFT分析需要計(jì)算N個(gè)索引值的逆序數(shù)才能得到全部的自然序結(jié)果，進(jìn)而才能獲取自然序結(jié)果中的某一段目標(biāo)FFT數(shù)據(jù)。對(duì)于需要連續(xù)進(jìn)行FFT分析的情況，無(wú)論是獲取全部FFT數(shù)據(jù)還是一段FFT數(shù)據(jù)，每一次N點(diǎn)FFT分析都需要重新計(jì)算一遍N個(gè)索引值的逆序數(shù)。對(duì)于重復(fù)計(jì)算，可以只計(jì)算一次，因此可以優(yōu)化FFT分析中的整序過(guò)程。

2 基于查找表整序算法

　　無(wú)論所需要的目標(biāo)數(shù)據(jù)是全部FFT結(jié)果還是部分FFT結(jié)果，都可以事先計(jì)算目標(biāo)數(shù)據(jù)在整個(gè)FFT結(jié)果中位置索引的逆序數(shù)，并將這些逆序數(shù)存儲(chǔ)在一個(gè)查找表中，然后根據(jù)此查找表在FFT逆序輸出數(shù)據(jù)中直接提取自然序的目標(biāo)數(shù)據(jù)。在需要對(duì)信號(hào)進(jìn)行連續(xù)FFT分析的環(huán)境中，查找表的計(jì)算可以在FFT分析前完成，并且只需計(jì)算一次。這種整序方式可以省去FFT分析過(guò)程中計(jì)算逆序數(shù)的時(shí)間，縮短單次FFT分析時(shí)間，提高單位時(shí)間內(nèi)的FFT分析次數(shù)，提高信號(hào)分析效率。

　　設(shè)N點(diǎn)原位FFT運(yùn)算，對(duì)目標(biāo)數(shù)據(jù)在全部自然序的FFT結(jié)果中的位置索引進(jìn)行逆序操作，由于自然序和逆序索引的二進(jìn)制表示之間是比特倒置關(guān)系，于是需要將每個(gè)自然序索引值二進(jìn)制表示的最低位移向最高位，次低位移向次高位直到完成這個(gè)自然序索引值的位逆序過(guò)程。將一個(gè)索引值的位逆序函數(shù)設(shè)為BitReverse（intiSourceIndex，intiBitNum），其返回值為一個(gè)逆序數(shù)；所獲取的查找表設(shè)為IndexArray。位逆序的計(jì)算流程圖如圖2所示。

　　圖2中，iSourceIndex是待逆序的索引值，iBitNum是FFT計(jì)算點(diǎn)數(shù)的二進(jìn)制位數(shù)，iDesIndex是BitReverse（）函數(shù)返回的逆序數(shù)。構(gòu)造FFT結(jié)果的數(shù)據(jù)查找表的流程圖如圖3所示。

　　圖3中，iStart為目標(biāo)數(shù)據(jù)在整個(gè)FFT自然序結(jié)果中的起始位置，iDataLen為目標(biāo)數(shù)據(jù)的長(zhǎng)度，由BitReverse（）函數(shù)的返回值iDesIndex構(gòu)成一個(gè)位置查找表IndexArray。于是，通過(guò)查找表從位置索引為iDesIndex的FFT逆序輸出中獲取自然序的目標(biāo)結(jié)果數(shù)據(jù)。相比于傳統(tǒng)的整序方式，使用查找表整序可以省去FFT分析過(guò)程中逆序數(shù)的計(jì)算過(guò)程。下面的試驗(yàn)在FFT計(jì)算完畢后，統(tǒng)計(jì)了傳統(tǒng)整序和使用查找表整序所消耗的時(shí)鐘周期個(gè)數(shù)，進(jìn)而比較兩種整序方式的時(shí)間效率。

3 試驗(yàn)

　　試驗(yàn)環(huán)境是TI公司提供的高效C編譯器和集成開發(fā)環(huán)境Code Composer Studio，選擇C67xx CPU Cycle Accurate Simulator處理器。在獲得相同整序結(jié)果的前提下，比較傳統(tǒng)整序和使用查找表整序的耗時(shí)情況。試驗(yàn)中，N點(diǎn)自然序數(shù)據(jù)作為FFT的輸入，目標(biāo)數(shù)據(jù)為全部FFT結(jié)果數(shù)據(jù)。在FFT計(jì)算完畢后，對(duì)FFT的逆序輸出數(shù)據(jù)采用不同的整序方式得到自然序結(jié)果數(shù)據(jù)，統(tǒng)計(jì)兩種整序方式所消耗的時(shí)鐘周期數(shù)，并通過(guò)對(duì)比時(shí)鐘周期數(shù)得到兩種整序過(guò)程在時(shí)間效率上的差別。

　　記錄N點(diǎn)FFT中傳統(tǒng)整序和查找表整序所消耗的時(shí)鐘周期個(gè)數(shù)，并計(jì)算后者與前者的百分比以觀察時(shí)間效率的改善情況。運(yùn)行情況記錄如表2所示。

　　由表2可見，單獨(dú)就整序過(guò)程而言，使用查找表整序比傳統(tǒng)的整序在時(shí)間效率上可以提高一倍多。如果僅需要得到某一段FFT結(jié)果數(shù)據(jù)，傳統(tǒng)整序首先要對(duì)N點(diǎn)FFT的全部逆序輸出進(jìn)行整序，然后再截取目標(biāo)數(shù)據(jù)，而使用查找表整序則可以從FFT逆序輸出數(shù)據(jù)中直接獲取任意長(zhǎng)度的目標(biāo)數(shù)據(jù)，并且目標(biāo)數(shù)據(jù)的長(zhǎng)度越短，查找表長(zhǎng)度越短，獲取目標(biāo)數(shù)據(jù)的時(shí)間效率就越高。

　　對(duì)于N點(diǎn)原位FFT運(yùn)算，傳統(tǒng)整序需要計(jì)算N點(diǎn)索引的逆序數(shù)。使用查找表進(jìn)行整序，假設(shè)目標(biāo)數(shù)據(jù)長(zhǎng)度為M（M≤N），則查找表內(nèi)索引個(gè)數(shù)為M，索引數(shù)據(jù)類型設(shè)為32 bit整型，那么所需分配的空間為M×32 bit。計(jì)算查找表時(shí)可以在FFT分析前進(jìn)行，這部分時(shí)間不占用FFT分析時(shí)間。對(duì)于單次FFT分析，增加M（M≤N）點(diǎn)數(shù)據(jù)空間可以為FFT計(jì)算節(jié)省N次逆序數(shù)的計(jì)算時(shí)間；對(duì)于連續(xù)FFT分析，不妨設(shè)連續(xù)分析n次，可以節(jié)省n×N次逆序數(shù)的計(jì)算時(shí)間。

4 結(jié)論

　　本文在充分理解原位FFT的計(jì)算特點(diǎn)后，在FFT分析前，對(duì)目標(biāo)數(shù)據(jù)在全部FFT結(jié)果中的位置索引計(jì)算逆序數(shù)，并將計(jì)算結(jié)果存儲(chǔ)為一個(gè)查找表，然后通過(guò)此查找表從FFT的逆序輸出中獲得自然序結(jié)果。試驗(yàn)結(jié)果證明，相比于傳統(tǒng)的整序，使用查找表整序時(shí)間高效并且簡(jiǎn)單實(shí)用，具有普遍的實(shí)用價(jià)值。比如，在軟件無(wú)線電領(lǐng)域，一般的無(wú)線電信號(hào)帶寬比較窄，頻率范圍比較寬，通常使用帶通采樣，因此對(duì)無(wú)線電信號(hào)進(jìn)行FFT計(jì)算時(shí)，只關(guān)心某一段結(jié)果數(shù)據(jù)；并且在需要對(duì)無(wú)線電信號(hào)進(jìn)行連續(xù)監(jiān)測(cè)的環(huán)境中，系統(tǒng)希望快速獲取每一次的FFT分析結(jié)果，在這種情況下，使用查找表整序處理FFT的逆序輸出就具有很大的優(yōu)勢(shì)。于是，使用查找表整序節(jié)省了FFT分析的整序時(shí)間，從而提高了FFT分析的時(shí)間效率。

參考文獻(xiàn)

　　[1] 方志紅，張長(zhǎng)耀，俞根苗.利用逆序循環(huán)實(shí)現(xiàn)FFT運(yùn)算中倒序算法的優(yōu)化[J].信號(hào)處理，2004，20（5）：533-535.

　　[2] 劉衛(wèi)新.實(shí)現(xiàn)FFT整序方法的研究[D].南京：南京理工大學(xué)，2003.

　　[3] 高麗，劉衛(wèi)新，張學(xué)智.FFT標(biāo)準(zhǔn)移序算法的優(yōu)化[J].探測(cè)與控制學(xué)報(bào)，2004，26（2）：62-64.

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

　　[5] 姚天任.數(shù)字信號(hào)處理[M].北京：清華大學(xué)出版社，2011.

　　[6] 張學(xué)智，蔡暉.快速實(shí)現(xiàn)FFT的逆序方法[J]．探測(cè)與控制學(xué)報(bào)，2001，23（2）：62-64.

　　[7] 喬春明，朱冰蓮.快速傅里葉變換中逆序數(shù)計(jì)算的一種快速算法[J].信息技術(shù)，2011（8）：164-165.

　　[8] 張學(xué)智，毛俊.無(wú)須逆序數(shù)的FFT整序的一個(gè)新方法[J].探測(cè)與控制學(xué)報(bào)，2002，24（2）：61-63.

　　[9] 林水生，黃順吉.一種實(shí)現(xiàn)任意基的快速整序算法[J].電子科技大學(xué)學(xué)報(bào)，1998，27（4）：343-346.

　　[10] 林水生，黃順吉.改進(jìn)的任意基FFT整序算法[J].信號(hào)處理，1999，15（2）：163-165.

　　[11] 賈淵，王俊波，姬長(zhǎng)英.FFT快速整序算法的對(duì)比、改進(jìn)及實(shí)現(xiàn)[J].電子科技大學(xué)學(xué)報(bào)，2009，38（2）：292-295.