數字信號處理筆記3FFT

FFT

1直接計算DFT演算法存在的問題及改進途徑。

要進行N次複數乘法+(N-1)次複數加法

利用DFT運算的係數 的固有對稱性和周期性，改善DFT的運算效率。

合併法：合併DFT運算中的某些項。

分解法：將長序列DFT利用對稱性和周期性，分解為短序列DFT。

?2.多種DFT演算法(時間抽取演算法DIT演算法，頻率抽取演算法DIF演算法，線性調頻Z變換即CZT法)?按「基數」分：基-2FFT演算法；基-4FFT演算法；混合基FFT演算法；分裂基FFT演算法

基--2按時間抽取的FFT演算法Decimation-in-Time(DIT)(Coolkey-Tukey)

?設輸入序列長度為N=2^M(M為正整數，將該序列按時間順序的奇偶分解為越來越短的子序列，稱為基2按時間抽取的FFT演算法。也稱為Coolkey-Tukey演算法。

?其中基數2----N=2^M，M為整數.若不滿足這個條件，可以人為地加上若干零值（加零補長）使其達到 N=2^M.

演算法步驟

按時間抽取的FFT演算法與直接計算DFT運算量的比較

? 由前面介紹的按時間抽取的FFT運算流圖可見：

每級都由N/2個蝶形單元構成，因此每一級運算都

需要N/2次復乘和N次復加（每個結加減各一次）。這

樣（N=2M)M級運算共需要：

? 可以得出如下結論：

按時間抽取法所需的復乘數和復加數都是與

成正比。而直接計算DFT時所需的復乘數與復加數則都

是與N2成正比.(復乘數md=N2,復加數ad=N(N-1)≈N^2)

按時間抽取 FFT 演算法的特點

?根據DIT基2-FFT演算法原理，能得出任何N=2m點的FFT信號流圖，並進而得出FFT計算程序流程圖。最後總結出按時間抽取法解過程的規律。

?1.原位運算（in-place)

?原位運算的結構，可以節省存儲單元，降低設備成本。

定義：當數據輸入到存儲器以後，每一組運算的結果，仍然存放在這同一組存儲器中直到最後輸出

?2.碼位倒讀規則

我們從輸入序列的號及整規律得到碼位倒讀規則。由 N=8 蝶形圖看出：原位計算時， FFT 輸出的 X(k) 的次序正好是順排列， 即X(0)…7), 但輸入 x(n) 都不能按自然順序 存入到儲單元中，而是按 x(0),4),2), x(0),4),2),

x(6)…. 的順序存入儲單元即為 亂序輸入 亂序輸入 亂序輸入 亂序輸入 ， 順序輸出 順序輸出 順序輸出 。這種順序看起來相當雜亂，然而 。這種順序看起來相當雜亂，然而 。這種順序看起來相當雜亂，然而

故有：輸入是自然順序而輸出是亂序，輸入和輸出都是自然順序

基--2按頻率抽取的FFT演算法Decimation-in-Frequency(DIF)(Sander-Tukey)

演算法原理：

?設輸入序列長度為N=2^M(M為正整數，將該序列的頻域的輸出序列X(k)(也是M點序列，按其頻域順序的奇偶分解為越來越短的子序列，稱為基2按頻率抽取的FFT演算法。也稱為Sander-Tukey演算法。

(a)輸入自然順序，輸出亂序且滿足碼位倒置規則。

(b)根據時域、頻域互換，可知：輸入亂序，輸出自然順序。

?不同之處：

（1）DIF與DIT兩種演算法結構倒過來。

DIF為輸入順序，輸出亂序。運算完畢再運行「二進位倒讀」程序。

DIT為輸入亂序，輸出順序。先運行「二進位倒讀」程序，再進行求DFT。

（2）DIF與DIT根本區別：在於蝶形結不同。

DIT的複數相乘出現在減法之前。

DIF的複數相乘出現在減法之後。

IFFT運算方法

線性調頻Z變換

?Z變 換 採用 螺 線 抽 樣, 可 適用 於 更 一 般 情 況 下 由 x(n) 求X(zk) 的 快 速 算 法, 這 種 變 換 稱 為 線 性 調 頻 Z 變 換 ( 簡 稱 CZT).

?3.FFT的應用

?凡是利用付里葉變換來進行分析、綜合、變換…的地方，都可以利用FFT演算法來減少其計算量。

?FFT主要應用在

（1）快速卷積

（2）快速相關

（3）頻譜分析

推薦閱讀：