傅里葉級數的快速算法詳解幻燈片.ppt

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