離散傅里葉變換及其快速算法.ppt

離散傅里葉變換及其快速算法概述傅里葉變換實現(xiàn)了從時域到時域到頻域的變換，廣泛應用于連續(xù)信號和離散信號處理技術(shù)領(lǐng)域。為了用計算機計算傅里葉變換，對信號和頻譜要求如下：信號和頻譜的數(shù)據(jù)長度應該是離散的。本節(jié)介紹如何將傅立葉級數(shù)和傅立葉變換分析方法應用于離散時間信號，這是從傅立葉變換發(fā)展而來的一種變換方法。離散傅里葉變換和快速傅里葉變換從理論上解決了計算機進行傅里葉分析的問題。在離散時間序列中，數(shù)字計算機只能處理有限長度的數(shù)字信號。因此，連續(xù)變化的模擬信號必須先轉(zhuǎn)換成有限的離散時間序列，然后才能被計算機處理。這種轉(zhuǎn)換稱為模擬信號數(shù)字化。X(t)的采樣間隔為，x(t)的離散值在時間t=k時寫為xk。xk，k=，-1，0，1，2，3，稱為離散時間序列。周期序列的離散分析，連續(xù)周期函數(shù)x(t)，采樣間隔T=T/N，周期序列的離散傅里葉級數(shù)，連續(xù)周期函數(shù)的傅里葉級數(shù)x(t):采樣間隔T=T/N，周期函數(shù)的離散傅里葉級數(shù)：離散傅里葉級數(shù)的性質(zhì)，離散傅里葉系數(shù)是由N個獨立的諧波分量組成的傅里葉級數(shù)，離散傅里葉系數(shù)也是離散周期的，周期是N，離散傅里葉級數(shù)的性質(zhì)， 公式上的DFS變換表明，雖然一個周期序列是一個無限序列，但只要知道一個周期的內(nèi)容(一個周期中信號的變化)，根據(jù)DFS的周期性，其余周期的所有值都可以得到，所以這個無限序列實際上只有n個序列值的信息是有用的，所以周期序列與有限序列有著本質(zhì)的關(guān)系。 非周期序列的離散時間傅里葉變換(DTFT)/序列的傅里葉變換，將序列x(n)的離散時間傅里葉變換(DTFT)定義為：序列x(n)的離散時間傅里葉逆變換(IDTFT)，傅里葉變換對的總結(jié)，傅里葉級數(shù)(FS)(時域：連續(xù)周期；頻域：非周期性離散傅里葉變換(時域：連續(xù)非周期性；頻域：非周期性連續(xù))離散傅立葉級數(shù)(時域：離散周期；頻域：周期性離散)離散時間傅立葉變換(DTFT)(時域：離散非周期性；頻域：周期連續(xù)性)、離散傅立葉變換(DFT)和傅立葉變換對不適用于計算機操作。因為從數(shù)字計算的角度來看，我們對時域和頻域都是離散的情況感興趣。然而，在我們的工作中經(jīng)常需要對有限長度序列進行頻譜分析，這就是我們將在這里討論的離散傅立葉變換。離散傅立葉變換可以由離散傅立葉變換定義。其思想如下：(1)將時域周期序列視為有限長序列x(n)的周期延拓；(2)將頻域周期序列視為有限長序列X(k)的周期延拓；(3)這樣，只要DFS定義公式的兩邊(時域和頻域)分別取主值區(qū)間，就可以得到有限長序列在時頻域的相應變換對離散傅里葉變換。離散傅里葉變換的定義和基本概念?，F(xiàn)在，有限長序列的傅里葉分析是借助于有限差分法的概念來進行的。設(shè)x(n)是一個有限長序列：正變換：逆變換：一般來說，密度泛函簡化為上述兩個方程，它們可以寫成矩陣形式。離散傅立葉變換和DTFT的區(qū)別在于，DTFT是任意序列的傅立葉分析，其譜是連續(xù)函數(shù)。然而，離散傅立葉變換將有限長度序列作為周期序列的一個周期。對于有限長度序列的傅立葉分析，離散傅立葉變換的特征在于在時域和頻域都是有限長度序列。離散傅立葉變換提供了一種用計算機分析信號和系統(tǒng)的方法，特別是快速傅立葉變換，它是離散傅立葉變換的一種快速算法，已被廣泛應用于科學技術(shù)的許多領(lǐng)域，促進了數(shù)字信號處理技術(shù)的快速發(fā)展。例如，一個4點序列的離散傅里葉變換解是用離散傅里葉變換的矩陣表達式得到的：x(n)和X(k)的波形圖如下：非周期函數(shù)的離散傅里葉變換的物理和邏輯過程，(a)原始函數(shù)，(b)截斷后的保留部分，(c)周期延拓，(d)離散采樣，(e)離散傅里葉變換后的離散頻譜，離散傅里葉變換的混疊問題，采樣間隔t，采樣頻率。如果采樣頻率太小，高頻部分可能與低頻部分重疊，形成“混頻”。fs=f，采樣頻率等于信號頻率；恢復信號的頻率為0，波形嚴重失真。采樣頻率fs=1/9f。恢復信號的頻率為1/9f，波形失真。香農(nóng)采樣定理，如果信號中的最高頻率是fmax，為了不產(chǎn)生混頻，信號的頻率分量可以被正確恢復，并且采樣頻率fs必須保證大于fmax的兩倍，即如果采樣頻率fs增加，采樣時間將會減少，導致頻率分辨率f的粗化。信號可以通過低通濾波器使濾波后的信號中的最高頻率為fmax，然后可以根據(jù)采樣定理確定采樣頻率fs。通常fs是fmax的34倍，fN=fs/2稱為奈奎斯特頻率，或稱混疊頻率，以及離散傅里葉變換的泄漏。在實際應用中，觀測到的信號通常被限制在一定的時間間隔內(nèi)，也就是說，信號在時域中被截斷，或者加上一個時間窗，也就是說，時間窗函數(shù)被用來乘以信號，也就是說，從卷積定理來看，時域中的乘法和頻域中的卷積有時會導致能量色散，這被稱為頻譜泄漏。余弦信號被矩形窗口截斷以形成泄漏。對于連續(xù)的周期函數(shù)，在符合采樣定理的條件下，保證窗函數(shù)b(t)的周期等于截斷函數(shù)的周期t的整數(shù)倍，從而使原始波形經(jīng)過逆變換后能夠準確恢復而不泄漏。對于隨機振動信號(非周期函數(shù))，泄漏控制方法是利用特定的窗函數(shù)來達到旁瓣控制的效果。常用窗口函數(shù)，(1)矩形窗口w (t)=1 (2) hanning窗口w (t)=1-cos (2t/t)，(3)Kaiser-Bessel w(t)=1-2.4 cos(2t/t)0.244 cos(4t/t)-0.00305 cos(6t/t)(4)平頂w(t)=1-1.93 cos(2t/t)1.29 cos(4t/t)-0.388 cos(t) 當窗長等于周期信號的整個周期時的漢寧窗：純隨機平頂窗：周期或準周期信號力窗或指數(shù)衰減窗：當用錘擊法、快速傅里葉變換測量頻率響應函數(shù)時的力信號和脈沖響應信號，當直接用傅里葉變換進行頻譜分析時，有一個突出的矛盾，即當序列長度n大時，計算量大，計算時間長， 數(shù)據(jù)占用大量內(nèi)存，用離散傅立葉變換很難進行實時處理，其應用受到很大限制。1965年，庫利和圖基提出了一種快速的離散傅立葉變換算法快速傅立葉變換。 快速傅里葉變換算法大大減少了計算量和計算時間，尤其是當序列長度n較大時。快速傅里葉變換不是一種新的變換形式，它只是快速傅里葉變換的一種快速算法。根據(jù)序列分解和選擇方法的不同，產(chǎn)生了不同的快速傅里葉變換算法。快速傅里葉變換在離散傅里葉逆變換、線性卷積和線性相關(guān)中也有重要的應用。有限長序列x(n)的離散傅立葉變換是：離散傅立葉變換的定義被擴展成方程并被寫入矩陣形式，并且通過向量表示的復數(shù)表示的X(k)值的計算需要N個復數(shù)乘法和(N-1)個復數(shù)加法，因此N個X(k)需要N2復數(shù)乘法和N(N-1)個復數(shù)加法。每個復數(shù)乘法包括4個實數(shù)乘法和2個實數(shù)加法，并且每個復數(shù)加法包括2個實數(shù)加法，因此計算N點的DFT需要4N2個實數(shù)乘法和(2N2個2N(N-1)個實數(shù)加法，例如，當N=2048時，計算量為419萬次。快速傅立葉變換原理，快速傅立葉變換算法主要使用兩個屬性：分解過程遵循兩個規(guī)則：對時間執(zhí)行奇偶分解并按時間提取的快速傅里葉變換算法；對頻率進行前向-后向分解并按頻率提取的快速傅里葉變換算法；對于按時間提取的快速傅立葉變換算法，設(shè)置N=2M，m為正整數(shù)；如果N=23=8，也就是說，根據(jù)規(guī)則，離散時間信號被分成奇數(shù)和偶數(shù)組，一組序列號是偶數(shù)，另一組序列號是奇數(shù)，也就是說，它們分別被表示為，根據(jù)密度泛函的定義，由于上述公式中的G(k)和H(k)是N/2點的密度泛函，注意，G(k)和H(k)只有N/2點，而X(k)需要N點。如果所有的X(k)都由G(k)和H(k)表示，則應該使用G(k)和H(k)的兩個重復周期。有：G(k)和H(k)的周期性和WN的對稱性可以得到：因此，X(k)的所有關(guān)系可以由G(k)和H(k)來確定：以N=8為例，有：根據(jù)上述結(jié)論，可以得出如下的信號流程圖：每個N/2點密度泛函的計算可以進一步分解為兩個N/4點密度泛函的計算： 將得到