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

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