FFT原理

由於計算機技術的快速發展，在70年代中期，美國和日本的一些電子設備企業開始設計和生產數字式傅里葉分析儀，但是由於離散傅里葉變換的計算量較大，直到DFT的快速算法(FFT)發現之後，有限離散傅里葉變換(DFT)才真正獲得了廣泛的應用 ^[2]  。

FFT是一種DFT的高效算法，稱為快速傅里葉變換（fast Fourier transform）。FFT算法可分為按時間抽取算法和按頻率抽取算法，先簡要介紹FFT的基本原理。從DFT運算開始，説明FFT的基本原理。

DFT的運算為：

式中

由這種方法計算DFT對於X（K）的每個K值，需要進行4N次實數相乘和（4N-2）次相加，對於N個k值，共需N*N乘和N（4N-2）次實數相加。改進DFT算法，減小它的運算量，利用DFT中

的週期性和對稱性，使整個DFT的計算變成一系列迭代運算，可大幅度提高運算過程和運算量，這就是FFT的基本思想。

FFT基本上可分為兩類，時間抽取法和頻率抽取法，而一般的時間抽取法和頻率抽取法只能處理長度N=2^M的情況，另外還有組合數基四FFT來處理一般長度的FFT。

所謂抽選，就是把長序列分為短序列的過程，可在時域也可在頻域進行。最常用的時域抽選方法是按奇偶將長序列不斷地變為短序列，結果使輸入序列為倒序，輸出序列為順序排列，這就是Coolly—Tukey算法 ^[3]  。

設N點序列x(n),

,將x(n)按奇偶分組，公式如圖2所示：

改寫為：

一個N點DFT分解為兩個 N/2點的DFT，

繼續分解，迭代下去，其運算量約為

其算法有如下規律：

兩個4點組成的8點DFT：

四個2點組成的8點DFT：

按時間抽取的8點DFT：

原位計算

當數據輸入到存儲器中以後，每一級運算的結果仍然儲存在同一組存儲器中，直到最後輸出，中間無需其它存儲器。

序數重排

對按時間抽取FFT的原位運算結構，當運算完畢時，這種結構存儲單元A(1)、A(2)，…，A(8)中正好順序存放着X(0)，X(1)，X(2)，…，X(7)，因此可直接按順序輸出，但這種原位運算的輸入x(n)卻不能按這種自然順序存入存儲單元中，而是按X(0)，X(4)，X(2)，X(6)，…，X(7)的順序存入存儲單元，這種順序看起來相當雜亂，然而它也是有規律的。當用二進制表示這個順序時，它正好是“碼位倒置”的順序。

蝶形類型隨迭代次數成倍增加。

每次迭代的蝶形類型比上一次蝶代增加一倍，數據點間隔也增大一倍。

頻率抽取2FFT算法是按頻率進行抽取的算法。

設N=2^M，將x(n)按前後兩部分進行分解，

按K的奇偶分為兩組，即

得到兩個N/2 點的DFT運算。如此分解，並迭代，總的計算量和時間抽取（DIT）基2FFT算法相同。

算法規律如下：

蝶形結構和時間抽取不一樣但是蝶形個數一樣，同樣具有原位計算規律，其迭代次數成倍減小。

N≠2^M時，可採取補零使其成為N=2，或者先分解為兩個p、q的序列，其中p*q=N，然後進行計算。

前面介紹，採用FFT算法可以很快算出全部N點DFT值，即z變換X（z）在z平面單位圓上的全部等間隔取樣值。實際中也許①不需要計算整個單位圓上z變換的取樣，如對於窄帶信號，只需要對信號所在的一段頻帶進行分析，這時希望頻譜的採樣集中在這一頻帶內，以獲得較高的分辨率，而頻帶以外的部分可不考慮，②或者對其它圍線上的z變換取樣感興趣，例如語音信號處理中，需要知道z變換的極點所在頻率，如極點位置離單位圓較遠，則其單位圓上的頻譜就很平滑，這時很難從中識別出極點所在的頻率，如果採樣不是沿單位圓而是沿一條接近這些極點的弧線進行，則在極點所在頻率上的頻譜將出現明顯的尖峯，由此可較準確地測定極點頻率。③或者要求能有效地計算當N是素數時序列的DFT，因此提高DFT計算的靈活性非常有意義。

螺旋線採樣是一種適合於這種需要的變換，且可以採用FFT來快速計算，這種變換也稱作Chirp-z變換。

DFT變換則説明對於時間有限的信號（有限長序列），也可以對其進行頻域採樣，而不丟失任何信息。所以只要時間序列足夠長，採樣足夠密，頻域採樣也就可較好地反映信號的頻譜趨勢，所以FFT可以用以進行連續信號的頻譜分析。

當然，這裏作了幾次近似處理：

1、用離散採樣信號的傅里葉變換來代替連續信號的頻譜，只有在嚴格滿足採樣定理的前提下，頻譜才不會有畸變，否則只是近似；

2、用有限長序列來代替無限長離散採樣信號。

線性卷積是求離散系統響應的主要方法之一,許多重要應用都建立在這一理論基礎上,如卷積濾波等。

以前曾討論了用圓周卷積計算線性卷積的方法歸納如下:

將長為N₂的序列x(n)延長到L,補L-N₂個零

將長為N₁的序列h(n)延長到L,補L-N₁個零

如果L≥N₁+N₂-1,則圓周卷積與線性卷積相等，此時，可有FFT計算線性卷積，方法如下:

a.計算X(k)=FFT[x(n)]

b.求H(k)=FFT[h(n)]

c.求Y(k)=H(k)Y(k) k=0～L-1

d.求y(n)=IFFT[Y(k)] n=0～L-1

可見，只要進行二次FFT,一次IFFT就可完成線性卷積計算。計算表明,L>32時,上述計算線性卷積的方法比直接計算線卷積有明顯的優越性,因此,也稱上述圓周卷積方法為快速卷積法

互相關和自相關函數的計算可利用FFT實現。由於離散付裏葉變換隱含着週期性，所以用FFT計算離散相關函數也是對週期序列而言的。直接做N點FFT相當於對兩個N點序列x(n)、y(n)作週期延拓，作相關後再取主值（類似圓周卷積）。而實際一般要求的是兩個有限長序列的線性相關，為避免混淆，需採用與圓周卷積求線性卷積相類似的方法，先將序列延長補0後再用上述方法。

信號是實數序列，任何實數都可看成虛部為零的複數，例如，求某實信號y(n)的復譜,可認為是將實信號加上數值為零的虛部變成覆信號(x(n)+j0)，再用FFT求其離散付裏葉變換。這種作法很不經濟，因為把實序列變成復序列，存儲器要增加一倍，且計算機運行時，即使虛部為零，也要進行涉及虛部的運算，浪費了運算量。合理的解決方法是利用複數據FFT對實數據進行有效計算，下面介紹方法。

一個N點FFT同時計算兩個N點實序列的DFT

設x₁(n)，x₂(n)是彼此獨立的兩個N點實序列,且X₁(k)=DFT[x1(n)]，X₂(k)=DFT[x2(n)]

可通過一次FFT運算同時獲得X₁(k)，X₂(k)。算法如下：

首先將x₁(n)，x₂(n)分別當作一復序列的實部及虛部,令

x(n)=x₁(n)+jx₂(n)

通過FFT運算可獲得x(n)的DFT值 X(k)=DFT[x1(n)]+jDFT[x2(n)]=X₁(k)+jX₂(k)

利用離散付裏葉變換的共軛對稱性

X₁(K)=1/2*[X(k)+[X(N-k)共軛]]

X₂(K)=1/2*[X(k)-[X(N-k)共軛]]

有了x(n)的FFT運算結果X(k),由上式即可得到X₁(k),X₂(k)的值。