現代測控技術中的FFT算法探析

羅煥然

摘 要 本文闡述了頻率域抽取基2FFT算法。內容包括公式推導、蝶形運算單元、

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

關鍵詞 FFT 頻率抽取 蝶形單元 運算量

中圖分類號：TN919 文獻標識碼：A

1概述

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

基于FFT變換的不言而喻的重要性以及對其產生的濃厚興趣，深入學習了FFT變換的機理。所用教材給出了時間抽取（DIF）基2 FFT算法的詳細的推導過程，而對于頻率抽取（DIF）基2 FFT算法只是簡略的提及，并沒有做詳細的探討。為了深化對于FFT的認識，本文嘗試詳細給出頻率抽取（DIF）基2 FFT算法的推導過程，并作出相應的討論。

2頻率抽取（DIF）基2 FFT算法

2.1算法的推導

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

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

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

對（4—a）式的DFT，繼續將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點的DFT分成了四個N/4點的DFT。通過幾個中間變量的代換，算出了時間序列x（n）的8點DFT。

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

2.2算法的討論

（1）“級”的概念

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

圖2 第m級蝶形單位

（2）蝶形單元

在圖1中有大量的如圖2的蝶形運算單元，由于該運算結構的幾何形狀類似蝴蝶，所以有“蝶形運算單元”的名稱，在第m級，有

（9）

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

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

（10）

由圖2，在第m級，上下節點p，q之間的距離為

（11）

（3）碼位倒置

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

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

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

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

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

如果我們將X（k）的序號k=0，1，…，N-1寫成二進制，如N=8，X（0），…，X（7）對應是

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

將二進制數碼翻轉，得

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

它們對應的十進制序號分別是

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

也正是輸出端所得到的順序。掌握了這一規律，我們就可以做到正確的編程，FFT的軟件已經是通用程序，所以我們只要了解排序的規律就可以了。

參考文獻

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

[2] 胡廣書.數字信號處理——理論、算法與實現.北京：清華大學出版社，2002.