DFT的計算量

離散傅里葉變換在實際應用中是非常重要的，利用它可以計算信號的頻譜、功率譜和線性卷積等。但是，如果使用定義式(3.20)來直接計算DFT，當N很大時，即使使用高速計算機，所花的時間也太多。因此，如何提高計算DFT的速度，便成了重要的研究課題。1965年庫利 (Cooley)和圖基(Tukey)在前人的研究成果的基礎上提出了快速計算DFT的算法，之后，又出現(xiàn)了各種各樣快速計算DFT的方法，這些方法統(tǒng)稱為快速傅里葉變換(FastFourier Transform)，簡稱為FFT。FFT的出現(xiàn)，使計算DFT的計算量減少了兩個數(shù)量級，從而成為數(shù)字信號處理強有力的工具。
快速傅里葉變換(FFT)是離散傅里葉變換(DFT)的快速算法。它是DSP領域中的一項重大突破，它考慮了計算機和數(shù)字硬件實現(xiàn)的約束條件、研究了有利于機器操作的運算結構，使DFT的計算時間縮短了1~2個數(shù)量級，還有效地減少了計算所需的存儲容量，F(xiàn)FT技術的應用極大地推動了DSP的理論和技術的發(fā)展。
在導出FFT算法之前，首先來估計一下直接計算DFT所需的計算量。

DFT的定義

將DFT定義式展開成方程組

將方程組寫成矩陣形式

用復數(shù)表示：

FFT算法是基于可以將一個長度為N的序列的離散傅里葉變換逐次分解為較短的離散傅里葉變換來計算這一基本原理的。這一原理產生了許多不同的算法，但它們在計算速度上均取得了大致相當?shù)母纳啤?/font>

在本章中我們集中討論兩類基本的FFT算法。
第一類 稱為按時間抽取(Decimation-in-Time)的基2FFT算法，它的命名來自如下事實：在把原計算安排成較短變換的過程中，序列x(n)(通常看作是一個時間序列)可逐次分解為較短的子序列。
第二類稱為按頻率抽取(Decimation-in-Frequency)的基2FFT算法，在這類算法中是將離散傅里葉變換系數(shù)序列X(k)分解為較短的子序列。

前面兩種算法特別適用于N等于2的冪的情況。
對于N為合數(shù)的情況，本章也將介紹兩種處理方法。