傅里葉級(jí)數(shù)的快速算法詳解幻燈片.ppt

第二章離散傅里葉變換及其快速算法,1753年，Bernoulli就推斷一振動(dòng)的弦可以表示成正弦加權(quán)和的形式，但是他未能給出所需的加權(quán)系數(shù)。Jean-Baptiste-JosephFourier于1768年3月出生在法國的Auxerre，當(dāng)他8歲時(shí)不幸成了一名孤兒。Fourier對(duì)數(shù)學(xué)產(chǎn)生了濃厚的興趣。21歲那年，F(xiàn)ourier在巴黎學(xué)術(shù)界論述了有關(guān)數(shù)值方程解的著名論作，這一工作使他在巴黎的數(shù)學(xué)界出名。1798年，拿破侖侵略埃及，在侵略隊(duì)伍中一些有名的數(shù)學(xué)家和科學(xué)家，F(xiàn)ourier就是其中的一位，回國后，F(xiàn)ourier被任命為格勒諾布爾伊澤爾省的長(zhǎng)官，就是在此期間，F(xiàn)ourier完成了其經(jīng)典之作Theorieanalytiquedelachaleur(熱能數(shù)學(xué)原理)。在該著作中，他證明了任一周期函數(shù)都可以表示成正弦函數(shù)和的形式，其中正弦函數(shù)的頻率為周期頻率的整數(shù)倍。,Fourier,離散傅里葉變換不僅具有明確的物理意義，相對(duì)于DTFT他更便于用計(jì)算機(jī)處理。但是，直至上個(gè)世紀(jì)六十年代，由于數(shù)字計(jì)算機(jī)的處理速度較低以及離散傅里葉變換的計(jì)算量較大，離散傅里葉變換長(zhǎng)期得不到真正的應(yīng)用，快速離散傅里葉變換算法的提出，才得以顯現(xiàn)出離散傅里葉變換的強(qiáng)大功能，并被廣泛地應(yīng)用于各種數(shù)字信號(hào)處理系統(tǒng)中。近年來，計(jì)算機(jī)的處理速率有了驚人的發(fā)展，同時(shí)在數(shù)字信號(hào)處理領(lǐng)域出現(xiàn)了許多新的方法，但在許多應(yīng)用中始終無法替代離散傅里葉變換及其快速算法。,2.1離散傅里葉變換（DFT）,為了便于更好地理解DFT的概念，先討論周期序列及其離散傅里葉級(jí)數(shù)（DFS）表示。2.1.1離散傅里葉級(jí)數(shù)（DFS）一個(gè)周期為N的周期序列，即，k為任意整數(shù)，N為周期,周期序列不能進(jìn)行Z變換，因?yàn)槠湓趎=-到+都周而復(fù)始永不衰減，即z平面上沒有收斂域。但是，正象連續(xù)時(shí)間周期信號(hào)可用傅氏級(jí)數(shù)表達(dá)，周期序列也可用離散的傅氏級(jí)數(shù)來表示，也即用周期為N的正弦序列來表示。,將周期序列展成離散傅里葉級(jí)數(shù)時(shí)，只需取k=0到(N-1)這N個(gè)獨(dú)立的諧波分量，所以一個(gè)周期序列的離散傅里葉級(jí)數(shù)只需包含這N個(gè)復(fù)指數(shù)，,利用正弦序列的周期性可求解系數(shù)將上式兩邊乘以，并對(duì)一個(gè)周期求和,k=r,N=8,kr,N=8,上式中部分顯然只有當(dāng)k=r時(shí)才有值為1,其他任意k值時(shí)均為零,所以有或?qū)憺?1)可求N次諧波的系數(shù)2）也是一個(gè)由N個(gè)獨(dú)立諧波分量組成的傅里葉級(jí)數(shù)3）為周期序列，周期為N。,時(shí)域上周期序列的離散傅里葉級(jí)數(shù)在頻域上仍是一個(gè)周期序列。,是一個(gè)周期序列的離散傅里葉級(jí)數(shù)(DFS)變換對(duì)，這種對(duì)稱關(guān)系可表為,習(xí)慣上：記,假設(shè)都是周期為N的兩個(gè)周期序列，各自的離散傅里葉級(jí)數(shù)為：,1）線性,a,b為任意常數(shù),DFS的幾個(gè)主要特性：,證:因?yàn)榧岸际且訬為周期的函數(shù)，所以有,2）序列移位,由于與對(duì)稱的特點(diǎn)，同樣可證明,證:,同理:,對(duì)于復(fù)序列其共軛序列滿足,3）共軛對(duì)稱性,進(jìn)一步可得,共軛偶對(duì)稱分量,共軛奇對(duì)稱分量,4）周期卷積若則或,周期卷積,周期為5,x(n),h(n),n,n,周期卷積,x(k),h(0-k),k,y(0),n,周期卷積,x(k),h(1-k),k,y(1),n,周期卷積,x(k),h(2-k),k,y(2),n,周期卷積,x(k),h(3-k),k,y(3),n,周期卷積,x(k),h(4-k),k,y(4),n,周期卷積,y(n),n,先計(jì)算主值區(qū)間，再周期延拓，求得最終的周期卷積的結(jié)果，如下圖所示。,證：這是一個(gè)卷積公式，但與前面討論的線性卷積的差別在于，這里的卷積過程只限于一個(gè)周期內(nèi)（即m=0N-1），稱為周期卷積。例：、，周期為N=7,寬度分別為4和3，求周期卷積。結(jié)果仍為周期序列，周期為N=7。,由于DFS與IDFS的對(duì)稱性，對(duì)周期序列乘積，存在著頻域的周期卷積公式，若,則,2.1.2離散傅里葉變換（DFT）,我們知道周期序列實(shí)際上只有有限個(gè)序列值有意義，因此它的許多特性可推廣到有限長(zhǎng)序列上。一個(gè)有限長(zhǎng)序列x(n)，長(zhǎng)為N，為了引用周期序列的概念，假定一個(gè)周期序列，它由長(zhǎng)度為N的有限長(zhǎng)序列x(n)延拓而成，它們的關(guān)系：,周期序列的主值區(qū)間與主值序列：對(duì)于周期序列，定義其第一個(gè)周期n=0N-1，為的“主值區(qū)間”，主值區(qū)間上的序列為主值序列x(n)。x(n)與的關(guān)系可描述為：數(shù)學(xué)表示：RN(n)為矩形序列。符號(hào)(n)N是余數(shù)運(yùn)算表達(dá)式，表示n對(duì)N求余數(shù)。,例：是周期為N=8的序列，求n=11和n=-2對(duì)N的余數(shù)。因此,頻域上的主值區(qū)間與主值序列：,周期序列的離散傅氏級(jí)數(shù)也是一個(gè)周期序列，也可給它定義一個(gè)主值區(qū)間，以及主值序列X(k)。數(shù)學(xué)表示：,長(zhǎng)度為N的有限長(zhǎng)序列x(n)，其離散傅里葉變換X(k)仍是一個(gè)長(zhǎng)度為N的有限長(zhǎng)序列，它們的關(guān)系為：x(n)與X(k)是一個(gè)有限長(zhǎng)序列離散傅里葉變換對(duì)，已知x(n)就能唯一地確定X(k)，同樣已知X(k)也就唯一地確定x(n)，實(shí)際上x(n)與X(k)都是長(zhǎng)度為N的序列（復(fù)序列）都有N個(gè)獨(dú)立值，因而具有等量的信息。有限長(zhǎng)序列隱含著周期性。,DFT的矩陣方程表示,DFT特性：,以下討論DFT的一些主要特性，這些特性都與周期序列的DFS有關(guān)。假定x(n)與y(n)是長(zhǎng)度為N的有限長(zhǎng)序列，其各自的離散傅里葉變換分別為：X(k)=DFTx(n)Y(k)=DFTy(n)(1)線性DFTax(n)+by(n)=aX(k)+bY(k),a,b為任意常數(shù),(2)循環(huán)移位有限長(zhǎng)序列x(n)的循環(huán)移位定義為：f(n)=x(n+m)NRN(n)含義：1)x(n+m)N表示x(n)的周期延拓序列的移位：2)x(n+m)NRN(n)表示對(duì)移位的周期序列x(n+m)N取主值序列,所以f(n)仍然是一個(gè)長(zhǎng)度為N的有限長(zhǎng)序列。f(n)實(shí)際上可看作序列x(n)排列在一個(gè)N等分圓周上，并順時(shí)針旋轉(zhuǎn)m位。,循環(huán)移位,f(n)=x(n+2)NRN(n),循環(huán)移位,移位前,左移兩位后,證：利用周期序列的移位特性：實(shí)際上，利用WN-mk的周期性，將f(n)=x(n+m)NRN(n)代入DFT定義式，同樣很容易證明。,序列循環(huán)移位后的DFT為F（k）=DFTf（n）=x（k）,同樣，對(duì)于頻域有限長(zhǎng)序列X(k)的循環(huán)移位，有如下反變換特性：IDFTX(k+l)NRN(k)=x（n）,（3）循環(huán)卷積若F（k）=X（k）Y（k）則或,證：這個(gè)卷積可看作是周期序列卷積后再取其主值序列。將F（k）周期延拓，得：則根據(jù)DFS的周期卷積公式：因0mN-1時(shí)，x(m)N=x(m)，因此經(jīng)過簡(jiǎn)單的換元可證明：,這一卷積過程與周期卷積比較，過程是一樣的，只是這里只取結(jié)果的主值序列，由于卷積過程只在主值區(qū)間0mN-1內(nèi)進(jìn)行，所以實(shí)際上就是y（m）的循環(huán)移位，稱為“循環(huán)卷積”，習(xí)慣上常用符號(hào)“”表示循環(huán)卷積，以區(qū)別于線性卷積。,循環(huán)卷積,x(n),h(n),n,n,循環(huán)卷積,x(k),k,y(n)=x(n)*h(n),n,h(0-k),循環(huán)卷積,x(k),k,y(n)=x(n)*h(n),n,h(1-k),循環(huán)卷積,x(k),k,y(n)=x(n)*h(n),n,h(2-k),循環(huán)卷積,x(k),k,y(n)=x(n)*h(n),n,h(3-k),循環(huán)卷積,x(k),h(4-k),k,y(n)=x(n)*h(n),n,循環(huán)卷積,y(n)=x(n)*h(n),n,由有限長(zhǎng)序列x(n)、h(n)構(gòu)造周期序列,計(jì)算周期卷積,卷積結(jié)果取主值,如下圖所示。,同樣，若f(n)=x(n)y(n)，則,（4）有限長(zhǎng)序列的線性卷積與循環(huán)卷積（循環(huán)卷積的應(yīng)用）實(shí)際問題的大多數(shù)是求解線性卷積，如信號(hào)x(n)通過系統(tǒng)h(n)，其輸出就是線性卷積y(n)=x(n)*h(n)。而循環(huán)卷積比起線性卷積，在運(yùn)算速度上有很大的優(yōu)越性，它可以采用快速傅里葉變換（FFT）技術(shù)，若能利用循環(huán)卷積求線性卷積，會(huì)帶來很大的方便?，F(xiàn)在我們來討論上述x(n)與h(n)的線性卷積，如果x(n)、h(n)為有限長(zhǎng)序列，則在什么條件下能用循環(huán)卷積代替而不產(chǎn)生失真。,有限長(zhǎng)序列的線性卷積：,假定x(n)為有限長(zhǎng)序列，長(zhǎng)度為N，y(n)為有限長(zhǎng)序列，長(zhǎng)度為M，它們的線性卷積f(n)=x(n)*y(n)也應(yīng)是有限長(zhǎng)序列。因x(m)的非零區(qū)間：0mN-1，y(n-m)的非零區(qū)間：0n-mM-1，這兩個(gè)不等式相加，得：0nN+M-2，在這區(qū)間以外不是x(m)=0，就是y(n-m)=0，因而f(n)=0。因此，f(n)是一個(gè)長(zhǎng)度為N+M-1的有限長(zhǎng)序列。,循環(huán)卷積：,重新構(gòu)造兩個(gè)有限長(zhǎng)序列x(n)、y(n)，長(zhǎng)度均為L(zhǎng)maxN,M，序列x(n)只有前N個(gè)是非零值，后L-N個(gè)為補(bǔ)充的零值；序列y(n)只有前M個(gè)是非零值，后L-M個(gè)為補(bǔ)充的零值。為了分析x(n)與y(n)的循環(huán)卷積，先看x(n),y(n)的周期延拓：,根據(jù)前面的分析，f（n）具有N+M-1個(gè)非零序列值，因此，如果周期卷積的周期LN+M-1，那么f（n）周期延拓后，必然有一部分非零序列值要重疊，出現(xiàn)混淆現(xiàn)象。只有LN+M-1時(shí)，才不會(huì)產(chǎn)生交疊，這時(shí)f（n）的周期延拓中每一個(gè)周期L內(nèi)，前N+M-1個(gè)序列值是f（n）的全部非零序列值，而剩下的L（N+M-1）點(diǎn)的序列則是補(bǔ)充的零值。循環(huán)卷積正是周期卷積取主值序列：所以使圓周卷積等于線性卷積而不產(chǎn)生混淆的必要條件是：LN+M-1,比較線性卷積與循環(huán)卷積,例:設(shè)有兩個(gè)序列，x(n)為N=4矩形序列，y(n)為M=6矩形序列，觀察其線性卷積和圓周卷積。由線性卷積定義可直接驗(yàn)證，兩者的線性卷積f(n)=x(n)*y(n)具有N+M-1=9個(gè)非零值,其結(jié)果見下圖左半部分(c)，不同L下的圓周卷積結(jié)果在圖的右半部分。圖線性卷積和循環(huán)卷積圖中（d）、（e）、（f），反映了不同L下循環(huán)卷積與線性卷積之間的關(guān)系，圖（d）中L=6，產(chǎn)生嚴(yán)重的混淆，致使fl(n)與f（n）已完全不同，圖（e）中L=8，這時(shí)有兩點(diǎn)（n=0，n=8）發(fā)生混淆失真，只有圖（f）中，滿足條件LN+M-1=9，循環(huán)卷積與線性卷積相同（與圖（c）比較）。,（5）共軛對(duì)稱性設(shè)x*(n)為x(n)的共軛復(fù)數(shù)序列，則DFTx*(n)=X*(N-k)證：DFTx*(n)0kN-1由于因此，DFTx*(n),說明：當(dāng)k=0時(shí)，應(yīng)為X*(N-0)=X*(0)，因?yàn)榘炊xX（k）只有N個(gè)值，即0kN-1，而XN已超出主值區(qū)間，但一般已習(xí)慣于把X（k）認(rèn)為是分布在N等分的圓周上，它的末點(diǎn)就是它的起始點(diǎn)，即XN=X0，因此仍采用習(xí)慣表示式DFTx*（n）=X*（N-k）以下在所有對(duì)稱特性討論中，XN均應(yīng)理解為XN=X0，同樣，x(N)=x(0)。,2.復(fù)序列的實(shí)部與虛部的DFT變換以xr(n）和xi(n)表示序列x(n)的實(shí)部與虛部即x(n)=xr(n)+jxi(n)則,Xe(k)和X0(k)表示實(shí)部與虛部序列的DFT，則,顯然，Xe(k)與Xo(k)對(duì)稱性：故因此,Xe(k)具有共軛對(duì)稱性，稱為X(k)的共軛偶對(duì)稱分量。,用同樣的方法可得到X0(k)=-X*0(N-k)即Xo(k)具有共軛反對(duì)稱特性，稱其為X(k)的共軛奇對(duì)稱分量。對(duì)于純實(shí)數(shù)序列x（n），即x（n）=xr（n），X（k）只有共軛偶對(duì)稱部分，即X（k）=Xe（k），表明實(shí)數(shù)序列的DFT滿足共軛對(duì)稱性，利用這一特性，只要知道一半數(shù)目的X（k），就可得到另一半的X（k），這一特點(diǎn)在DFT運(yùn)算中可以加以利用，以提高運(yùn)算效率。,根據(jù)x(n)與X(k)的對(duì)稱性，同樣可找到X(k)的實(shí)部、虛部與x(n)的共軛偶部與共軛奇部的關(guān)系。分別以xe(n)及x0(n)表示序列x(n)的圓周共軛偶部與圓周共軛奇部：同樣應(yīng)從圓周意義上理解x(N-0)=x(0)?？勺C明:DFTxe(n)=ReX（k）DFTx0(n)=jImX（k）,（6）選頻性（對(duì)0有限制？）對(duì)復(fù)指數(shù)函數(shù)進(jìn)行采樣得復(fù)序列x(n)0nN-1其中q為整數(shù)。當(dāng)0=2/N時(shí)，x（n）=ej2nq/N,其離散傅里葉變換為寫成閉解形式可見，當(dāng)輸入頻率為q0時(shí)，變換X（K）的N個(gè)值中只有X（q）=N，其余皆為零，如果輸入信號(hào)為若干個(gè)不同頻率的信號(hào)的組合，經(jīng)離散傅里葉變換后，不同的k上，X（k）將有一一對(duì)應(yīng)的輸出，因此，離散傅里葉變換算法實(shí)質(zhì)上對(duì)頻率具有選擇性。,例:求余弦序列,的DFT,（7）DFT與Z變換有限長(zhǎng)序列可以進(jìn)行z變換比較z變換與DFT變換，可見，當(dāng)z=w-kN時(shí)，即,圖DFT與z變換,o,o,o,o,o,o,o,o,o,o,o,X(ej),X(k),o,Rez,jImz,o,變量,周期,分辨率,是z平面單位圓上幅角為的點(diǎn)，即將z平面上的單位圓N等分后的第k點(diǎn)。,1）X(k)也就是z變換在單位圓上等間隔的采樣值。2）X(k)也可看作是對(duì)序列傅氏變換X(ej)的采樣，采樣間隔為：N=2/N。即,結(jié)論：,采樣定律告訴我們，一個(gè)頻帶有限的信號(hào)，可以對(duì)它進(jìn)行時(shí)域采樣而不丟失任何信息；DFT變換進(jìn)一步告訴我們，對(duì)于時(shí)間有限的信號(hào)（有限長(zhǎng)序列），也可以對(duì)其進(jìn)行頻域采樣，而不丟失任何信息，這正反應(yīng)了傅立葉變換中時(shí)域、頻域的對(duì)稱關(guān)系。它有十分重要的意義，由于時(shí)域上的采樣，使我們能夠采用數(shù)字技術(shù)來處理這些時(shí)域上的信號(hào)（序列），而DFT的理論不僅在時(shí)域，而且在頻域也離散化，因此使得在頻域采用數(shù)字技術(shù)處理成為可能。FFT就是頻域數(shù)字處理中最有成效的一例。,（8）DFT形式下的Parseval定理,令k=0,得到,2.2利用DFT做連續(xù)信號(hào)的頻譜分析,利用DFT計(jì)算連續(xù)信號(hào)的頻譜,（1）混迭對(duì)連續(xù)信號(hào)xa(t)進(jìn)行數(shù)字處理前，要進(jìn)行采樣采樣序列的頻譜是連續(xù)信號(hào)頻譜的周期延拓，周期為fs，如采樣率過低，不滿足采樣定理，fs2fh，則導(dǎo)致頻譜混迭，使一個(gè)周期內(nèi)的譜對(duì)原信號(hào)譜產(chǎn)生失真，無法恢復(fù)原信號(hào)，進(jìn)一步的數(shù)字處理失去依據(jù)。,（2）泄漏處理實(shí)際信號(hào)序列x（n）時(shí)，一般總要將它截?cái)酁橐挥邢揲L(zhǎng)序列，長(zhǎng)為N點(diǎn)，相當(dāng)于乘以一個(gè)矩形窗w(n)=RN(n)。矩形窗函數(shù)，其頻譜有主瓣，也有許多副瓣，窗口越大，主瓣越窄，當(dāng)窗口趨于無窮大時(shí)，就是一個(gè)沖擊函數(shù)。我們知道，時(shí)域的乘積對(duì)應(yīng)頻域的卷積，所以，加窗后的頻譜實(shí)際是原信號(hào)頻譜與矩形窗函數(shù)頻譜的卷積，卷積的結(jié)果使頻譜延伸到了主瓣以外，且一直延伸到無窮。當(dāng)窗口無窮大時(shí)，與沖激函數(shù)的卷積才是其本身，這時(shí)無畸變，否則就有畸變。,例如，信號(hào)為，是一單線譜，但當(dāng)加窗后，線譜與抽樣函數(shù)進(jìn)行卷積，原來在0處的一根譜線變成了以0為中心的，形狀為抽樣函數(shù)的譜線序列，原來在一個(gè)周期（s）內(nèi)只有一個(gè)頻率上有非零值，而現(xiàn)在一個(gè)周期內(nèi)幾乎所有頻率