FFT算法的應(yīng)用

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

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

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

關(guān)于蝶形結(jié)運(yùn)算的具體原理及其推導(dǎo)可以參照講義，在此就不再贅述。按頻率抽取的FFT的原理也可查閱相關(guān)資料，這里就不再推導(dǎo)了。

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

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