FFT算法的應用

一． 數字濾波器設計：
（一）基—2按時間抽取FFT算法
對于有限長離散數字信號{x[n]}，0  n  N-1，其離散譜{x[k]}可以由離

散付氏變換（DFT）求得。DFT的定義為
可以方便的把它改寫為如下形式：
不難看出，WN是周期性的，且周期為N，即

WN的周期性是DFT的關鍵性質之一。為了強調起見，常用表達式WN取代W以便明確其周期是N。
由DFT的定義可以看出，在x[n]為復數序列的情況下，完全直接運算N點DFT需要（N-1）2次復數乘法和N（N-1）次加法。因此，對于一些相當大的N值（如1024）來說，直接計算它的DFT所作的計算量是很大的。FFT的基本思想在于，將原有的N點序列序列分成兩個較短的序列，這些序列的DFT可以很簡單的組合起來得到原序列的DFT。例如，若N為偶數，將原有的N點序列分成兩個（N/2）點序列，那么計算N點DFT將只需要約[(N/2)2 •2]=N2/2次復數乘法。即比直接計算少作一半乘法。因子（N/2）2表示直接計算（N/2）點DFT所需要的乘法次數，而乘數2代表必須完成兩個DFT。上述處理方法可以反復使用，即（N/2）點的DFT計算也可以化成兩個（N/4）點的DFT（假定N/2為偶數），從而又少作一半的乘法。這樣一級一級的劃分下去一直到最后就劃分成兩點的FFT運算的情況。比如，一個N = 8點的FFT運算按照這種方法來計算FFT可以用下面的流程圖來表示：

關于蝶形結運算的具體原理及其推導可以參照講義，在此就不再贅述。按頻率抽取的FFT的原理也可查閱相關資料，這里就不再推導了。

二． 使用到的MATLAB命令：
函數fft(x)可以計算R點序列的R點DFT值；而fft(x,N)則計算R點序列的N點DFT，若R>N，則直接截取R點DFT的前N點，若R<N，則x先進行補零擴展為N點序列再求N點DFT。函數ifft(X)可以計算R點的譜序列的R點IDFT值；而ifft(X,N)同fft(x,N)的情況。

四、實驗目的：
離散傅氏變換（DFT）的目的是把信號由時域變換到頻域，從而可以在頻域分析處理信息，得到的結果再由逆DFT變換到時域。FFT是DFT的一種快速算法。在數字信號處理系統中，FFT作為一個非常重要的工具經常使用，甚至成為DSP運算能力的一個考核因素。
本實驗通過使用MATLAB函數中的FFT命令計算離散時間信號的頻譜，以加深對離散信號的DFT的理解及其FFT算法的運用。
五、實驗內容：
(1) 計算一個實數序列 的1024點FFT，注意使用將此序列組合成一復數序列后再計算的方法。
(2) 分別計算兩個實數序列 和 的128點FFT，注意使用將此二序列組合成一復數序列后再計算的方法。
(3) 利用DFT的方式計算下面兩序列的線性卷積：
g[n]={3, 4, -2, 0, 1, -4},h[n]={1, -3, 0, 4, -2, 3}
六、實驗器材（設備、元器件）：
七、實驗步驟：
對實驗內容中給定的序列求給定點數N的FFT和IFFT，利用MATLAB編程完成計算，繪出相應圖形。并與理論計算相比較，說明實驗結果的原因。
八、實驗數據及結果分析：
程序：
結果：
九、實驗結論：
十、總結及心得體會：
十一、對本實驗過程及方法、手段的改進建議