羅煥然

摘 要 本文闡述了頻率域抽取基2FFT算法。內(nèi)容包括公式推導(dǎo)、蝶形運(yùn)算單元、

快速傅立葉變換算法的信號流程圖。

關(guān)鍵詞 FFT 頻率抽取 蝶形單元 運(yùn)算量

中圖分類號：TN919 文獻(xiàn)標(biāo)識碼：A

1概述

在測控技術(shù)中，傳感器采集到的數(shù)字信號一般是時間序列，需要對這樣的數(shù)字信號進(jìn)行處理，通過離散傅立葉變換（Discrete Fourier Transform，簡稱DFT），可以將時域信號轉(zhuǎn)化為頻域信號?？焖俑盗⑷~變換（Fast Fourier Transform，簡稱FFT）是一種提高離散傅立葉運(yùn)算速度的快速算法，它使N點(diǎn)DFT的乘法計算量由N2次降為log2N次。以N=1024為例，計算量降為5120次，僅為原來的4.88%。人們公認(rèn)這一重要發(fā)現(xiàn)的問世是數(shù)字信號處理發(fā)展史上的一個轉(zhuǎn)折點(diǎn)，也可以稱之為一個里程碑。

基于FFT變換的不言而喻的重要性以及對其產(chǎn)生的濃厚興趣，深入學(xué)習(xí)了FFT變換的機(jī)理。所用教材給出了時間抽取（DIF）基2 FFT算法的詳細(xì)的推導(dǎo)過程，而對于頻率抽取（DIF）基2 FFT算法只是簡略的提及，并沒有做詳細(xì)的探討。為了深化對于FFT的認(rèn)識，本文嘗試詳細(xì)給出頻率抽?。―IF）基2 FFT算法的推導(dǎo)過程，并作出相應(yīng)的討論。

2頻率抽?。―IF）基2 FFT算法

2.1算法的推導(dǎo)

對N點(diǎn)序列x（n），它的DFT變換定義為：

X（K）=x（n） k=0，1，…，N-1，WN= （4—a）

于是我們將一個N點(diǎn)DFT分成了兩個N/2點(diǎn)的DFT，分的辦法是將X（k）按序號k的奇、偶性分開。

對（4—a）式的DFT，繼續(xù)將x（2r）按序列號分成上、下兩部分，得：

（4—b）

（5—a）

同理，對于（4—b）的DFT，可以得到：

（5—b）

分別令r=2l，r=2l+1，l=0，1，…，N/4-1，則（5—a）和（5—b）可以化為：

（6—a）

（6—b）

（6—c）

（6—d）

令 （7—a）

（7—b）

（7—c）

（7—d）

則 （8—a）

（8—b）

（8—c）

（8—d）

這樣，我們通過將X（2r）和X（2r+1）按r的奇、偶分開，把兩個N/2點(diǎn)的DFT分成了四個N/4點(diǎn)的DFT。通過幾個中間變量的代換，算出了時間序列x（n）的8點(diǎn)DFT。

若N=16，32或2的更高的冪，可按照前述的方法繼續(xù)分下去，直到化成兩點(diǎn)計算為止。以上算法是將頻率下標(biāo)k按奇、偶分開，故稱頻率抽取算法（Decimation in Frequency，DIF）?，F(xiàn)將上述過程表示于圖1。其基本運(yùn)算單元如圖2所示。

2.2算法的討論

（1）“級”的概念

上述過程，每進(jìn)行一次奇偶分離，就成為一“級”運(yùn)算，一共有M=Log2N級，如圖1所示。圖中從左至右，依次為m=0級，m=1級，…，m=M-1級。

圖2 第m級蝶形單位

（2）蝶形單元

在圖1中有大量的如圖2的蝶形運(yùn)算單元，由于該運(yùn)算結(jié)構(gòu)的幾何形狀類似蝴蝶，所以有“蝶形運(yùn)算單元”的名稱，在第m級，有

（9）

p，q是參與本蝶形單元運(yùn)算的上、下節(jié)點(diǎn)的序號。顯然，第m級序號為p，q的兩點(diǎn)只參與該蝶形單元的運(yùn)算，并在第m+1級輸出。該蝶形單元不會再涉及別的點(diǎn)。這個特點(diǎn)使得我們在計算機(jī)編程的時候，可以將蝶形單元的輸出仍然放在輸入數(shù)組里。這一特點(diǎn)稱為“同址運(yùn)算”。

由于每一級都含有N/2個蝶形單元，每一個蝶形單元需要一次復(fù)數(shù)乘法，兩次復(fù)數(shù)加法，所以完成M=Nlog2N級共需要復(fù)數(shù)乘法次數(shù)m1和復(fù)數(shù)加法次數(shù)m2分別是：

（10）

由圖2，在第m級，上下節(jié)點(diǎn)p，q之間的距離為

（11）

（3）碼位倒置

由圖1可以看出，輸入序列x（n）依照正序排列，但變換后的輸出序列X（k）的次序卻似乎被打亂了，這是由于對X（k）作奇、偶分開所產(chǎn)生的。對于N=8，自然序號為0，1，2，3，4，5，6，7。第一次按奇、偶分開，可得X（k）的序號為：

0，2，4，6， | 1，3，5，7

對每組再作奇、偶分開，這時應(yīng)該把每一組仍看作按自然順序排列，故抽取后得四組，每組的序號為：

0，4 ， | 2，6，| 1，5，| 3，7

這一順序正是圖1輸出端序列X（k）的排列次序，掌握這一規(guī)律，對N為2的更高次冪，我們都可以得到正確的抽取次序。

如果我們將X（k）的序號k=0，1，…，N-1寫成二進(jìn)制，如N=8，X（0），…，X（7）對應(yīng)是

X（000），X（001），X（010），X（011），X（100），X（101），X（110），X（111）

將二進(jìn)制數(shù)碼翻轉(zhuǎn)，得

X（000），X（100），X（010），X（110），X（001），X（101），X（011），X（111）

它們對應(yīng)的十進(jìn)制序號分別是

X（0），X（4），X（2），X（6），X（1），X（5），X（3），X（7）

也正是輸出端所得到的順序。掌握了這一規(guī)律，我們就可以做到正確的編程，F(xiàn)FT的軟件已經(jīng)是通用程序，所以我們只要了解排序的規(guī)律就可以了。

參考文獻(xiàn)

[1] 周耀華，汪凱仁.數(shù)字信號處理.上海：復(fù)旦大學(xué)出版社，1992.

[2] 胡廣書.數(shù)字信號處理——理論、算法與實(shí)現(xiàn).北京：清華大學(xué)出版社，2002.