第5章離散變換與快速算法

1DFT的應(yīng)用DFT是一種算法，可以用硬件實(shí)現(xiàn)，也可以用軟件實(shí)現(xiàn)主要有兩方面用途：一、LTI系統(tǒng)地實(shí)現(xiàn)二、信號(hào)的頻譜分析2一、利用DFT實(shí)現(xiàn)LTI系統(tǒng)出發(fā)點(diǎn)：線性時(shí)不變系統(tǒng)可以用線性卷積和來實(shí)現(xiàn)和描述；圓周卷積和在滿足一定約束的條件下可以得到線性卷積；圓周卷積和可以利用DFT來完成3在許多應(yīng)用場(chǎng)合（如語音濾波）輸入信號(hào)時(shí)無限長(zhǎng)的。盡管目前可以存儲(chǔ)幾乎所有的輸入信號(hào)，但是這樣的一種DFT是不現(xiàn)實(shí)的；輸入和輸出之間的長(zhǎng)度嚴(yán)重不對(duì)稱，需要對(duì)FIR濾波器的單位沖激進(jìn)行大量補(bǔ)零，浪費(fèi)大量運(yùn)算量；采集完所有輸入樣本后才能計(jì)算濾波輸出，導(dǎo)致有很大的處理延遲，損失實(shí)時(shí)性；存在的問題4采用塊卷積將輸入信號(hào)分割成多段，對(duì)每段信號(hào)利用DFT進(jìn)行處理，適當(dāng)處理后進(jìn)行銜接塊卷積的方法主要有兩種重疊相加法重疊保留法解決方法5設(shè)h(n)的點(diǎn)數(shù)為M，x(n)為很長(zhǎng)的序列。將x(n)分解為很多段，每段為L(zhǎng)點(diǎn)，L選擇成和M的數(shù)量值級(jí)相同用xi(n)表示第i段：1）重疊相加法（Overlap)6由于xi(n)為L(zhǎng)點(diǎn)，而yi(n)為（L+M-1）點(diǎn)（設(shè)N=L+M-1），相鄰兩段輸出序列yi(n),

yi+1(n)必然有（M-1）個(gè)點(diǎn)發(fā)生重疊前一段的后（M-1）個(gè)點(diǎn)的后一段的前（M-1）個(gè)點(diǎn)重疊輸出重疊問題7892）重疊保留法(Oversave)與重疊相加法相同，先將x(n)分段，每段L個(gè)點(diǎn)不同之處是輸入序列xi(n)中不再補(bǔ)零，而是在每一段的前邊補(bǔ)上前一段保留下來的（M-1）個(gè)輸入序列值，組成L+M-1點(diǎn)序列。每段圓周卷積結(jié)果的前（M-1）個(gè)點(diǎn)的值不滿足因果系統(tǒng)的要求，不等于線性卷積值101112二、利用DFT的信號(hào)分析DFT的主要應(yīng)用之一是分析連續(xù)信號(hào)的頻譜如語音信號(hào)頻率分析用于音腔辨識(shí)與建模采樣分析前同樣需要抗混疊濾波：采樣后信號(hào)頻譜周期拓展，要想保持頻譜不混疊，被采樣信號(hào)必須帶限。由于實(shí)際的信號(hào)總不是嚴(yán)格帶限的，并且自然界中總存在著噪聲(其頻譜是寬帶的)，在采樣之前需要加入抗混疊濾波器，使混疊減小到最低程度。

13一、DFT對(duì)CTFT的逼近連續(xù)時(shí)間非周期信號(hào)的傅里葉變換為：

用DFT方法對(duì)該變換逼近的方法如下：141、將在t軸上等間隔（寬度為T）分段，每一段用一個(gè)矩形脈沖代替，脈沖的幅度為其起始點(diǎn)的抽樣值。則CTFT可以近似為：時(shí)域離散化152、將序列x(n)=xc(nT)

截?cái)喑蓮膖=0開始長(zhǎng)度為T0=NT的有限長(zhǎng)序列，包含有N個(gè)采樣，即時(shí)域加矩形窗，則上式又可以進(jìn)一步近似為：由于時(shí)域采樣，采樣頻率為，則頻域產(chǎn)生以fs為周期的周期延拓。時(shí)域截?cái)?63、由于數(shù)值計(jì)算的限制，在頻域上也只能計(jì)算離散點(diǎn)（頻域抽樣）上的數(shù)值。我們將頻域的一個(gè)周期中也分成N段，即。每個(gè)頻域采樣點(diǎn)間的間隔為。則上式可以進(jìn)一步化簡(jiǎn)為：頻域離散化1718同時(shí)，由于頻域的抽樣，那么ICTFT就可以近似成:若要由及求連續(xù)的及方法，則可利用頻域抽樣定理的插值公式和時(shí)域抽樣定理的插值公式分別求得。ICTFT19連續(xù)時(shí)間周期號(hào)的傅里葉級(jí)數(shù)對(duì)為：

要將連續(xù)周期信號(hào)的傅立葉級(jí)數(shù)與DFS聯(lián)系起來，就需要對(duì)時(shí)域抽樣：二、對(duì)CTFS的逼近20取一個(gè)周期內(nèi)的N個(gè)點(diǎn)，即，則傅立葉級(jí)數(shù)近似為：從而可以得到反變換的近似公式：由于DFS的頻率是周期重復(fù)的，其主值區(qū)間內(nèi)的頻率已經(jīng)足以描述整個(gè)頻域內(nèi)的特性，所以可以用DFT來代替上面的DFS運(yùn)算。21三、信號(hào)DFT分析的步驟222324離散信號(hào)的離散頻率值：由于采樣的緣故，所得到的離散頻率與信號(hào)的原始頻率之間的關(guān)系為：

所以對(duì)應(yīng)于信號(hào)的連續(xù)域頻率為：

上式說明我們只能通過數(shù)字頻域上的離散頻點(diǎn)來觀察模擬頻域，這樣就好像通過柵欄觀察一樣，因此稱為柵欄效應(yīng)。25所觀察模擬頻點(diǎn)間隔為：雖然上式最初由頻點(diǎn)間隔引出，但卻表達(dá)了信號(hào)處理的模擬頻率的分辨率（頻率分辨力）。從上式看出，其模擬頻率分辨率僅僅決定于時(shí)間窗的截取長(zhǎng)度L當(dāng)時(shí)間窗的長(zhǎng)度固定時(shí)，如果采取加密采樣點(diǎn)數(shù)N，減小采樣周期T是不能提高模擬頻率分辨率，也不能提高數(shù)字頻率分辨率通過補(bǔ)零的方法，可以提高數(shù)字頻率的分辨率，減小柵欄效應(yīng)。但同樣不能提高模擬頻率分辨率。數(shù)字頻率分辨率（頻率步進(jìn)）和模擬頻率分辨率的存在根本區(qū)別，它們之間沒有必然聯(lián)系。模擬頻率分辨能力26

由于DFT是對(duì)有限長(zhǎng)序列的處理，因此在計(jì)算DFT之前，需將序列進(jìn)行截?cái)?，即時(shí)域上加窗。由于時(shí)域上截?cái)嗟拇?，必然在頻域有一定的帶寬，同時(shí)呈現(xiàn)托尾現(xiàn)象。時(shí)域上的截?cái)啵ㄏ喑耍?，在頻域上表現(xiàn)為周期卷積，這將會(huì)對(duì)信號(hào)的頻譜起平滑作用，也就是能量的分散，即頻譜泄漏，如圖(f)所示。加窗對(duì)頻譜的影響27利用加窗采樣信號(hào)段DFT來反映輸入信號(hào)的傅里葉變換，會(huì)受到許多因素的影響和干擾，必須十分小心。同時(shí)要能夠?qū)Φ玫降慕Y(jié)果給出正確的解釋，也就是要清楚所得到的頻譜中哪些屬于信號(hào)本身的，哪些是加窗處理所帶來的。28正弦信號(hào)的離散時(shí)間傅里葉變換是在頻域上對(duì)稱的沖激函數(shù)對(duì)。利用DFT分析正弦信號(hào)時(shí)，加窗使得沖激函數(shù)平滑或展寬，因此很難精確確定頻率。加窗降低了頻率上靠近的正弦信號(hào)的分辨能力。現(xiàn)在來觀察由兩個(gè)正弦分量組成的連續(xù)時(shí)間信號(hào)在加窗之下的DTFT頻譜。令信號(hào)為：

其傅立葉變換有兩個(gè)頻率，四個(gè)對(duì)稱頻點(diǎn):正弦信號(hào)加窗（分辨率降低、譜泄漏）29其不失真采樣之后的離散序列為：

其DTFT為：OA1A0幅度譜如下圖所示： 30DTFT沒有對(duì)幅度譜的形狀產(chǎn)生畸變。然而加窗后序列DTFT為：OA1A03164點(diǎn)的矩形窗的幅度譜函數(shù)32不同組合的雙頻信號(hào)333435時(shí)間窗對(duì)頻譜分析的影響分辨率降低和頻譜泄漏是信號(hào)加窗的兩種影響。分辨率主要受窗函數(shù)主瓣寬度的影響；頻譜的泄漏主要指副瓣能量泄漏，一般不指主瓣能量的泄漏，主要取決于窗函數(shù)的主瓣和副瓣幅值相對(duì)比例。進(jìn)行頻譜分析時(shí)，往往希望有高分辨率和頻譜泄漏，也就是希望有小的主瓣寬度和相對(duì)旁瓣幅度。在具體選擇窗函數(shù)時(shí)，要在兩者之間進(jìn)行折衷。如矩形窗函數(shù)在給定長(zhǎng)度時(shí)具有最小的主瓣寬度，但是卻有最大的相對(duì)旁瓣幅度。36Kaiser和Schafer證明，相對(duì)旁瓣幅度基本上與窗的長(zhǎng)度無關(guān)，只取決于窗的形狀，即取決于，它們之間的近似表達(dá)式為：

主瓣寬度主要取決于窗的長(zhǎng)度。主瓣寬度、相對(duì)旁瓣幅度和窗長(zhǎng)度之間的折衷關(guān)系的近似表達(dá)式為：

37信號(hào)分析與濾波器設(shè)計(jì)的區(qū)別38譜采樣的影響加窗后的DTFT已經(jīng)有了頻譜的泄漏，分辨率的降低。而利用DFT來計(jì)算頻譜，實(shí)際是在DTFT的數(shù)字連續(xù)譜線上進(jìn)行采樣，這種采樣好比是我們通過一個(gè)“柵欄”觀看景象一樣，只能在離散點(diǎn)上看到真實(shí)的景象，稱之為“柵欄效應(yīng)”。雖然可以通過補(bǔ)零的方法減小這種效應(yīng)，但這種固有的頻譜采樣仍然可能給出信號(hào)（連續(xù)未加窗）真實(shí)譜的錯(cuò)誤導(dǎo)向或不準(zhǔn)確的頻譜圖。對(duì)應(yīng)于上面圖（c）的情況，我們進(jìn)行64點(diǎn)的DFT，其DTFT頻譜和采樣譜線圖如下所示：39幅度畸變及衍生頻率40純凈的假象41逼近真實(shí)用序列補(bǔ)零將頻譜采樣點(diǎn)增加為12842滿足頻率分辨率要求的N點(diǎn)DFT能夠給出誤導(dǎo)性的頻譜抽樣圖。人們常常使用補(bǔ)零的方法，這樣可以對(duì)頻譜充分地過采樣，將一些重要的特性表現(xiàn)出來?？梢钥闯?，補(bǔ)零后的DFT得到了較密的譜線圖，更清楚的反應(yīng)真實(shí)情況。但我們必須清醒地認(rèn)識(shí)到：補(bǔ)零并不能提高分辨率，分辨率在序列進(jìn)行加窗處理時(shí)已經(jīng)決定了，分辨率僅取決于截取信號(hào)時(shí)真正窗的長(zhǎng)度和形狀。434445信號(hào)的分析，并不是在NT=L為固定值的情況下，N、T就可以任意取值。如果N太小，T太大，則無法完成信號(hào)的譜分析；若N太大，T太小，加大了運(yùn)算量而且沒必要。那么什么樣的N、T選擇比較合適呢？T的選取要滿足無失真采樣的條件：當(dāng)信號(hào)是帶限未知時(shí)，T越小越好；在信號(hào)帶限已知時(shí)，。在此基礎(chǔ)上再確定N，當(dāng)然要留有一定的余度。DFT分析參數(shù)的選取46考慮一個(gè)帶限連續(xù)信號(hào)，且當(dāng)時(shí)，。我們要利用上圖中的系統(tǒng)來估計(jì)連續(xù)時(shí)間譜。為了在盡可能少的基二FFT計(jì)算量的條件下使模擬頻率的分辨率不大于10Hz，則所需要截?cái)喽嚅L(zhǎng)的信號(hào)段？采樣周期T