第5快速離散傅里葉變換

《第5快速離散傅里葉變換》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第5章快速傅里葉變換(FFT)快速傅里葉變換（FFT）是根據(jù)計算量的最小化原理來設(shè)計和實施離散傅里葉變換(DFT)計算的方法。1965年，庫利（T.W.Cooley）和圖基（J.W.tukey）發(fā)表了著名的《計算機計算傅里葉級數(shù)的一種算法》論文。從此掀起了快速傅里葉變換計算方法研究的熱潮。各種快速、高效的離散傅里葉變換計算方法伴隨著DSP技術(shù)的發(fā)展不斷出現(xiàn)，并促進了DSP技術(shù)的發(fā)展?？焖俑道锶~變換（FFT）的出現(xiàn)，實現(xiàn)了快速、高效的信號分析和信號處理，為離散傅里葉變換(DFT)的廣泛應(yīng)用奠定了基礎(chǔ)。本章主要講述快速傅里葉變換的原理和典型應(yīng)

2、用。按照快速傅里葉變換方法的引入、時域抽取基2FFT算法、頻域抽取基2FFT算法、高效率計算FFT的方法的探討、離散傅里葉反變換的FFT算法、線性調(diào)頻Z變換算法、典型FFT算法的MATLAB實現(xiàn)的順序進行講述。本章是數(shù)字信號處理的重點內(nèi)容之一，其中的時域抽取基2FFT算法和典型FFT算法的MATLAB實現(xiàn)是實現(xiàn)離散傅里葉變換(DFT)走向?qū)嵱没年P(guān)鍵性技術(shù)。5.1快速傅里葉變換方法的引入5.1.1離散傅里葉變換(DFT)的計算按照公式4.3.1，設(shè)x(n)是一個長度為M的有限長序列，則定義x(n)的N點離散傅里葉變換為(5.1.1)按照公

3、式5.1.1進行計算稱為DFT的直接計算方法。為了統(tǒng)計不同DFT計算的工作量，我們把2個復(fù)數(shù)的加法運算和乘法運算各稱為1次復(fù)數(shù)運算；對于2個復(fù)數(shù)的1次復(fù)數(shù)的加法運算和乘法運算的計算工作量視為相等。因為專用的DSP處理器進行復(fù)數(shù)加法和乘法運算的速度和效率基本相同。直接計算的工作量：對于一個固定的k值：復(fù)數(shù)乘法N次；復(fù)數(shù)加法N-1次；小計2N-1次復(fù)數(shù)運算。對于N個k值：復(fù)數(shù)乘法次；復(fù)數(shù)加法次；共計次復(fù)數(shù)運算。可以看出，當?shù)臅r候，，N點的DFT計算的工作量是。一般情況下，，DFT計算的工作量最少是次復(fù)數(shù)運算。短時間內(nèi)完成計算任務(wù)是困難的。因為

4、，N點的DFT計算的工作量是，點的DFT計算的工作量是，減少DFT計算的點數(shù)N可以減少DFT的計算量。減少運算量是提高運算速度的好方法。5.1.2減少DFT計算量的方法減少DFT的計算量的主要途徑是利用的性質(zhì)和計算表達式的組合使用，其本質(zhì)是減少DFT計算的點數(shù)N以便減少DFT的計算量。的性質(zhì)：（1）全周期對稱性：（m是整數(shù)）(5.1.2)（2）半周期反對稱性：(5.1.3)證明：（m是整數(shù)）證畢。利用的性質(zhì)把DFT的表達式進行化簡是減少計算量工作的第一步，DFT的表達式中的同類項合并是減少計算量工作的關(guān)鍵性一步。因為同類項的計算只需要進行

5、一次，而其它的同類項就不需要重復(fù)計算了。這樣就能有效地減少運算量。如何減少運算量，提高運算速度？我們通過一個例題進行說明。例題5.1.1計算，。解：(5.1.4)利用（m是整數(shù)）和的規(guī)律，對公式(5.1.4)進行優(yōu)化，得到公式(5.1.5)。(5.1.5)我們對公式(5.1.5)進行組合，得到公式(5.1.6)（a）(b)(5.1.6)(c)(d)我們對公式(5.1.6)進行分析，（a）式和(c)式的對應(yīng)部分可以只計算一次；同理，（b）式和(d)式的對應(yīng)部分可以只計算一次。計算量：復(fù)數(shù)加法8次，復(fù)數(shù)乘法4次，共計復(fù)數(shù)運算12次。如果我們對

6、公式(5.1.4)直接進行計算，計算量：復(fù)數(shù)加法12次，復(fù)數(shù)乘法16次，共計復(fù)數(shù)運算28次。通過上述例題，我們發(fā)現(xiàn)，利用的性質(zhì)和計算表達式的組合使用，可以大幅度減少運算量，提高計算速度。其本質(zhì)是減少DFT計算的點數(shù)N，以便減少DFT的計算量。例如公式(5.1.6)中的（a）式和(c)式的對應(yīng)部分，相同的表達式只需要計算一次。公式(5.1.6)（a）式（b）式中的和就是計算和的2點的DFT；和就是計算和的2點的DFT；公式(5.1.4)（a）式（c）式中的和就是計算和的2點的DFT。在這里，我們對公式5.1.6的解釋是從對的抽取、推導到的順

7、序進行的，其算法表現(xiàn)稱為時域抽取基2FFT算法。計算表達式的組合使用看起來復(fù)雜，但是有規(guī)律可循。請注意：公式(5.1.6)中的計算順序方法不是唯一的，這樣就產(chǎn)生了不同的FFT計算方法。最基本的FFT計算方法是時域抽取基2FFT算法、頻域抽取基2FFT算法。其它的FFT計算方法都可以從時域抽取基2FFT算法變化得到，以便滿足不同的工作需求。對此，我們分別進行講述。5.2時域抽取基2FFT算法N點DFT的計算量和成正比，減少參與DFT的點數(shù)N，就減少了DFT的計算量。的計算是最簡化的DFT計算。把N點DFT的計算轉(zhuǎn)化成若干2點的DFT的計算，

8、2點的DFT的輸入是在時域n上抽取的，我們稱之為時域抽取基2FFT算法。5.2.1時域抽取基2FFT算法原理設(shè)，，，M是正整數(shù)，取。(5.2.1)令：是長度為的DFT(5.2.2)是長度為的D