1、第三章 付里葉分析,離散付氏級數(shù)的數(shù)學(xué)解釋(The Mathematical Explanation of DFS) 如前所述，連續(xù)信號x(t)或離散信號x(nT1)的頻譜： 都是連續(xù)譜，無法用計(jì)算機(jī)直接處理。要用計(jì)算機(jī)研究處理（數(shù)字信號處理）必須將： 無窮積分(求和)近似為有限積分(求和)； 頻率離散化。 本節(jié)主要討論如何進(jìn)行近似計(jì)算，和實(shí)施這些數(shù)學(xué)計(jì)算所需的一些必要的數(shù)學(xué)基礎(chǔ)。,離散付氏級數(shù)的數(shù)學(xué)解釋,泊松求和公式(The Poisson Sum Formula) 設(shè)一周期函數(shù) 是以f(t)為主值函數(shù)，以T為周期進(jìn)行周期延拓而得，如下圖左圖所示。 在第二章中已經(jīng)證明，若F()是f(t)的付

2、氏變換，則： 此系時域泊松求和公式，是將無窮積分變換成有限求和的基礎(chǔ)。,離散付氏級數(shù)的數(shù)學(xué)解釋,下面將用線性系統(tǒng)理論證明泊松求和公式，以此來說明其系統(tǒng)意義。 設(shè)某系統(tǒng)的傳遞函數(shù)為F()，對應(yīng)的沖激響應(yīng)為f(t)，如下圖所示。,離散付氏級數(shù)的數(shù)學(xué)解釋,若輸入為： 則由線性系統(tǒng)理論知，其輸出為： 另一方面，由付氏級數(shù)輸入信號可展開成： 將上式右端通過系統(tǒng)，得到響應(yīng)為：,離散付氏級數(shù)的數(shù)學(xué)解釋,此即時域泊松求和公式。另外，在頻域也有類似的公式成立： 設(shè) 為以F()為主值函數(shù)，以1為周期進(jìn)行周期延拓而得的周期函數(shù)，見前圖右圖。f(t)是F()的付氏反變換，則有頻域泊松求和公式：,離散付氏級數(shù)的數(shù)學(xué)解釋

3、,f(t)與F()為付氏變換對，而 與 不是付氏變換關(guān)系。 和 分別是f(t)和F()的周期延拓，其周期分別為T和1。 當(dāng)f(t)為因果函數(shù)時，利用頻域泊松求和公式(令=0)有： 利用泊松公式可以推導(dǎo)出一些有用的恒等式。,離散付氏級數(shù)的數(shù)學(xué)解釋,例3-10：已知變換對： 試求序列 的付氏展開式。 解：由頻域泊松公式有：,離散付氏級數(shù)的數(shù)學(xué)解釋,令=0和T1=1，有： 題給出的變換對和=0和T1=1 ，可得,離散付氏級數(shù)的數(shù)學(xué)解釋,付氏變換與付氏級數(shù)(Fourier Transform and Fourier Series) 由泊松公式可見，通過X()的樣本X(n0)可求得 的付氏級數(shù)系數(shù)(頻譜

4、)，即： 頻域取樣（離散化）后，x(t)就周期化了，而且0=2/T，當(dāng)0越小，則T越大；當(dāng)T時， 00； 若x(t)已知， 則可以精確地確定 ； 對于信號g(t)的截短函數(shù)：x(t)=g(t)Pa/2(t)，由上式可求得g(t)的付氏變換G ()的樣本的近似值。,離散付氏級數(shù)的數(shù)學(xué)解釋,X()為截短函數(shù)的付氏變換，一般情況下，它可近似G ()。 與時域取樣類似，若x(t)嚴(yán)格限制在有限區(qū)間內(nèi)，即x(t)滿足：當(dāng)|t|a/2時，x(t)=0；則有：若Ta，則 可由x(t)唯一地確定；若Ta， 將產(chǎn)生混疊。 用窗函數(shù)w(t)代替Pa/2(t)（矩形窗），通過選擇適當(dāng)?shù)膚(t)，可使誤差G(n0)-

5、X(n0)減小。這類截短問題在數(shù)字信號處理中有許多應(yīng)用，如數(shù)字濾波器設(shè)計(jì)和頻譜分析等。,離散付氏級數(shù)的數(shù)學(xué)解釋,付氏級數(shù)與離散付氏級數(shù)(Fourier Series and DFS) 通過對付氏級數(shù)與離散付氏級數(shù)關(guān)系的討論，將可用一個有限和式來近似計(jì)算付氏級數(shù)系數(shù)。 設(shè)一個周期函數(shù)： 若對 進(jìn)行取樣，取N為一任意整數(shù)，而且有T=NT1，即在一個周期內(nèi)取N點(diǎn)，則 的樣值 由下式確定：,離散付氏級數(shù)的數(shù)學(xué)解釋,式中，WN是1的N元根，稱作旋轉(zhuǎn)因子。 我們知道，在一個域內(nèi)取樣離散化，則在另一個域內(nèi)周期化，而k又可寫作： K=n+rN， n=0,1, ,N-1；r=,-1,0,1, 并且，旋轉(zhuǎn)因子具有

6、周期性： 和 ，所以上式又可寫作： 令： ，顯然 序列是周期的，即： 所以有：,離散付氏級數(shù)的數(shù)學(xué)解釋,上式說明，周期函數(shù) 的樣本值 由一組（一個周期） 來確定；而且， 也由一個周期內(nèi)的樣本值 來確定。 的付氏級數(shù)系數(shù)Cn與 由 來聯(lián)系。 例3-11：設(shè) ，N9；試求 解：因?yàn)閨n|10時，Cn=0，所以，由Cn與 關(guān)系式得：,離散付氏級數(shù)的數(shù)學(xué)解釋,一般而言， 不能確定Cn，除非僅有N個不為0的 。例如三角多項(xiàng)式為： 若N2M1，由Cn與 關(guān)系式知： Cn與 的圖形如下圖所示。這時，由 就能求出Cn。 由于 由 唯一地確定，從而，可以推定類似三角多項(xiàng)式這樣的函數(shù)的付氏級數(shù)系數(shù)Cn能由它的樣本

7、值 來確定。亦即可由y(t)的樣本求出Y()的樣本，從而近似求得Y()。從數(shù)學(xué)上講，這就是Y()的數(shù)值計(jì)算問題。,離散付氏級數(shù)的數(shù)學(xué)解釋,數(shù)值計(jì)算的基本定理(The Basal Theorem of Numerical Computation) 對于x(t)的付氏變換：,離散付氏級數(shù)的數(shù)學(xué)解釋,的計(jì)算基于如下定理： 若T是任意常數(shù)，N是任意整數(shù)，而且有： 則對任何m有： 式中： 由信號理論易知其合理性：時域取樣導(dǎo)致頻域周期化；頻域取樣對應(yīng)時域周期化。,離散付氏級數(shù)的數(shù)學(xué)解釋,因?yàn)橛蠺=NT1，1=N0，所以無論時域或頻域在一個周期均為N個樣值，因此，在一個周期內(nèi)，一組由定理等式定義的N個方程確

8、定了 與 之間的關(guān)系?？梢杂蒒個 樣本值通過求解方程組，求出 的樣本值。 一般而言， 不能唯一確定X(n0)，但若X()滿足：X()=0，當(dāng)|和12，=/T；則有下式成立： 上條件說明x(t)是帶限信號，而且滿足取樣定理。,第三章 付里葉分析,若x(t)不是帶限的，但只要1足夠大，使得當(dāng)|1/2時的X()可以忽略不計(jì)，則當(dāng)n1/20=N/2時， 近似等于X(n0)。但存在一定的混疊誤差： X(n0)- 。 離散付氏變換(Discrete Fourier Transform) DFT引入背景(The Inductive Background of DFT) 再次研討信號時頻域關(guān)系（見下圖）可以發(fā)

9、現(xiàn)在四種信號時頻關(guān)系中，只有第四類信號時頻域均是離散的，能進(jìn)行計(jì)算機(jī)（數(shù)字）處理。第二類信號時域是離散的，但其頻域卻是連續(xù)的，不能直接應(yīng)用數(shù)字信號處理技術(shù)，為了能,信號時頻關(guān)系示意圖,離散付氏變換,夠處理這類信號，故人為引入離散付立葉變換。 分析離散非周期序列（有限長序列）頻譜可知：其頻譜是周期的，只需研究一個周期；頻譜是連續(xù)的，需要對其進(jìn)行離散化，應(yīng)用頻域采樣定理可以在不丟失信息的條件下，將其離散化。進(jìn)行上述處理后即可得到有限長序列的DFT，如上圖所示。 離散付氏變換定義(Definition of DFT) 對一個N點(diǎn)的有限長序列x(n)，由序列的付氏變換定義，有：,離散付氏變換,對正變換

10、，取頻譜的一個周期（設(shè)取主值周期），按頻域采樣定理，在一個周期內(nèi)取N點(diǎn)離散化，令 有： 對反變換，因?yàn)?，故有：,離散付氏變換,DFT定義(Definition of DFT) ： 一N點(diǎn)的有限長序列x(n)，對它的頻譜在一個周期內(nèi)進(jìn)行N點(diǎn)等間隔取樣，則得其的頻域序列，兩者的關(guān)系稱為離散付氏變換(Discrete Fourier Transform,DFT)，即： 式中， 稱為旋轉(zhuǎn)因子。,離散付氏變換,DFT的物理意義(The Physical Meaning of DFT) DFT與Z變換的關(guān)系：容易證明，有限長序列x(n)的DFT是其在單位圓上Z變換（序列的付氏變換）的N點(diǎn)等間隔采樣。 由

11、序列的付氏變換的物理意義容易推得DFT的物理意義：N點(diǎn)有限長序列x(n)的(頻域序列)DFTX(k)為x(n)的頻譜在一個周期里的N點(diǎn)等間隔取樣。只要取樣滿足一定的規(guī)律（頻域取樣定理），即可無失真地反映X(ej)，進(jìn)而可恢復(fù)信號x(n)。,離散付氏變換,DFT的隱含周期性(The Connotative Periodicity of DFT) 由信號時頻關(guān)系的內(nèi)在本質(zhì)聯(lián)系知，對DFT來說，時、頻域均是離散的，故其時、頻域均是周期序列，即時域?qū)?yīng)的是由主值序列x(n)以N為周期進(jìn)行周期性延拓后得到的周期序列 ；頻域?qū)?yīng)的是由主值序列X(k)以N為周期進(jìn)行周期性延拓后得到的周期序列 。 由于在處理

12、時僅需主值序列（或者說一個周期的序列），所以在DFT定義中，時頻域均限制在主值序列范圍內(nèi)，即：0nN-1；0kN-1。,離散付氏變換,例3-12：考察一個離散系統(tǒng)：離散付氏變換分析器，其差分方程為y(n)- y(n-1)=x(n)。 解：易得系統(tǒng)的系統(tǒng)函數(shù)為： 所以其單位脈沖響應(yīng)為： 若輸入為0nN-1的N點(diǎn)有限長序列x(n)，由于x(n)和h(n)均為因果序列，由卷積公式易得：,離散付氏變換,當(dāng)n=N時，因?yàn)橛衳(N)0，所以有： 即當(dāng)系統(tǒng)輸入x(n)時，N時刻系統(tǒng)的輸出等于其對應(yīng)的DFT變換X(k)值，改變系統(tǒng)常數(shù) ；即可求得對應(yīng)的DFT： 。 DFT的基本性質(zhì)(The Basal Pro

13、perties of DFT) 線性性(Linearity) 滿足齊次性和疊加原理。設(shè)x1(n)和x2(n)是長度分別為N1和N2的有限長序列，若a、b為任意常數(shù)，且：,離散付氏變換,取N=maxN1，N2，設(shè)X1(k)和X2(k)分別為x1(n)和x2(n)的N點(diǎn)DFT，則N點(diǎn)序列y(n)的DFT為： 循環(huán)移位性質(zhì)(The Property of Circular Shift) 序列的循環(huán)移位(Circular Shift of Sequence) N點(diǎn)有限長序列x(n)的循環(huán)移位定義為： 式中：x()N表示對x()中序號進(jìn)行模N取余運(yùn)算。 為0N-1的窗口序列。,離散付氏變換,循環(huán)移位的幾

14、何意義和過程可如下圖所示。m0，左移；m0，右移。循環(huán)移位概念也可用圓移位解釋，所以有時又稱為“圓位移”。下面（如圖）用一個N=8，左移3位的圓位移的幾何過程進(jìn)一步說明循環(huán)移位。 時域循環(huán)移位定理(Time-Domain Circular Shift Theorem) 設(shè)x(n)是長為N的有限長序列，y(n)為循環(huán)位移m位后的序列，其DFT為：,循環(huán)移位幾何意義示意圖,用圓位移形象說明循環(huán)位移,離散付氏變換,頻域循環(huán)移位定理(Frequency- Domain Circular Shift Theorem) 若 則 循環(huán)卷積定理(Circular Convolution Theorem) 循環(huán)

15、卷積(Circular Convolution) 設(shè)有兩有限長序列x1(n)和x2(n)，長度分別為N1和N2，取N=maxN1，N2（較短的一個通過補(bǔ)零，達(dá)到N長），則兩者的循環(huán)卷積定義為：,離散付氏變換,或者： 記作： 循環(huán)卷積中x(n)、x1(n)、x2(n)均等長，為N點(diǎn)。 從時域直接計(jì)算兩序列的循環(huán)卷積通常有三種方法： 利用公式直接計(jì)算； 同心圓法； 波形作圖法。 同心圓法和波形作圖法計(jì)算示意見下圖。,循環(huán)卷積計(jì)算圖示,x2(1),x2(0),x2(N-1),x1(N-1),x1(0),x1(1),x2(0),x2(1),x2(N-1),x1(N-1),x1(0),x1(1),x1(

16、n),x2(n),x(n),離散付氏變換,時域卷積定理(Time-Domain Circular Convolution Theorem) 設(shè)x1(n)和x2(n)的N點(diǎn)DFT分別為： 若 則有： 利用卷積定理可將循環(huán)卷積變換到頻域利用乘法運(yùn)算實(shí)現(xiàn)，通過DFT的快速計(jì)算方法可以大大降低運(yùn)算量。,離散付氏變換,頻域卷積定理(Frequency-Domain Circular Convolution Theorem) 與時域?qū)ΨQ，也存在頻域卷積定理： 若 則：,離散付氏變換,復(fù)共軛序列的DFT(DFT of a Complex Conjugation Sequence) 設(shè) 為x(n)的復(fù)共軛序列

17、，而且有：則: ， 0kN-1 且 X(N)=X(0) 共軛對稱性(Conjugation Symmetry) 關(guān)于圓對稱：關(guān)于圓周的中軸線對稱。寫成表達(dá)式如下： 設(shè)xep(n)為有限長共軛對稱序列， xop(n)為有限長共軛反對稱序列；有：,共軛對稱示意,離散付氏變換,對N為偶數(shù)，將上式中n換成N/2n，有： 下圖給出了一個N=8的序列對稱示意。 序列的共軛對稱性(Conjugation Symmetry of Sequences) 任意序列都可寫成其共軛對稱分量與共軛反對稱分量之和； 利用序列與復(fù)共軛序列DFT間的關(guān)系，可導(dǎo)出序列DFT的對稱特性。,復(fù)序列共軛對稱示意圖,離散付氏變換,如果

18、序列x(n)的DFT為X(k)，則x(n)的實(shí)部和純虛部的DFT分別為X(k)的共軛對稱分量和共軛反對稱分量。即，如果：x(n)=xr(n)+jxi(n)；X(k)DFTx(n)Xep(k)Xop(k)，則： DFTxr(n)=Xep(k) ； DFTjxi(n)=Xop(k) 如果序列x(n)的DFT為X(k)，則x(n)的共軛對稱分量和共軛反對稱分量的DFT分別為X(k)的實(shí)部和純虛部。即，如果：x(n)=xep(n)+xop(n)；X(k)DFTx(n)XR(k)jXI(k)，則： DFTxep(n)=ReX(k)=XR(k) DFTxop(n)=jImX(k)=jXI(k) 由序列DF

19、T的共軛關(guān)系，可以推出各類序列DFT的對稱關(guān)系，它們可總結(jié)如下表所示。,序列共軛對稱性總結(jié)及示例,離散付氏變換,1、若x(n)為實(shí)函數(shù)，則X(k)是共軛偶對稱的；x(n)為共軛偶對稱的，則X(k)是實(shí)函數(shù)，從而有： 實(shí)、偶實(shí)、偶 2、若x(n)為共軛奇對稱的，則X(k)是虛函數(shù)； x(n)為實(shí)函數(shù)，則X(k)是共軛偶對稱的，即其虛部為奇函數(shù)；從而有： 實(shí)、奇虛、奇 3、因?yàn)閄(k)=DFTjxiep(n)jDFTxiep(n)，由“1”得DFTxiep(n)是實(shí)偶函數(shù)， 即X(k)為虛偶函數(shù)，從而有： 虛、偶虛、偶 4、因?yàn)閄(k)DFTjxiop(n)jDFTxiop(n)，由“2”得DFT

20、xiop(n)是虛奇函數(shù)，即X(k)為實(shí)奇函數(shù)，從而有： 虛、奇實(shí)、奇,第三章 付里葉分析,利用序列DFT的對稱關(guān)系可以減少DFT的運(yùn)算量，一般而言，只需計(jì)算大約一半點(diǎn)數(shù)的DFT，另一半可由對稱性求得。序列對稱性是DFT和DFS快速算法（FFT)的重要基礎(chǔ)。 頻率域采樣(Frequency Sampling) 由時域采樣定理知：在時域只要滿足采樣定理（即時域采樣點(diǎn)足夠多）即可用采樣序列無失真地恢復(fù)原始信號（用采樣序列代表原始連續(xù)信號）。由時頻域的對稱性原理推斷，在頻域也應(yīng)存在類似的采樣定理。即滿足何種條件可以對頻域連續(xù)函數(shù)采樣，使得采樣序列可以無失真地恢復(fù)原始頻域函數(shù)。,頻率域采樣,頻域采樣定

21、理(Frequency Sampling Theorem) ： 對M點(diǎn)有限長序列x(n)，若X(k)為x(n)頻域函數(shù)的采樣序列，只有當(dāng)采樣點(diǎn)數(shù)NM時，才有： 即可由頻域采樣序列X(k)恢復(fù)原始頻域連續(xù)函數(shù)，進(jìn)而可恢復(fù)原始時域序列x(n)。 若采樣點(diǎn)數(shù)NM，時域?qū)l(fā)生混疊現(xiàn)象（失真），不能無失真地恢復(fù)原始信號； 有限長序列DFT是建立在頻域采樣定理基礎(chǔ)上的，由此可以解釋為何DFT用N點(diǎn)對頻譜等間隔采樣； 由頻域采樣定理可以推斷無限長序列的DFT不存在（無意義），因?yàn)榇藭r無論頻域采樣點(diǎn)數(shù)選取多大，時域都將發(fā)生混疊。,頻率域采樣,X(z)的內(nèi)插公式及內(nèi)插函數(shù)(Interpolation Funct

22、ion and Interpolation Formula of X(z) 滿足頻域采樣定理后，x(n)的DFT（X(k)）可以無失真地恢復(fù)（表示）x(n)，所以它也應(yīng)能表示它的Z變換X(z)。用X(k)表示X(z)的表達(dá)形式稱為X(z)的內(nèi)插公式；在內(nèi)插公式中描述采樣點(diǎn)間軌跡關(guān)系的函數(shù)稱為內(nèi)插函數(shù)。 利用IDFT表達(dá)式和有限項(xiàng)級數(shù)求和公式容易推導(dǎo)得到X(z)的內(nèi)插公式為： 式中： 為內(nèi)插函數(shù)。,頻率域采樣,利用序列z變換與付氏變換的關(guān)系，由X(z)的內(nèi)插公式容易求得 的內(nèi)插公式和內(nèi)插函數(shù)為： 利用尤拉公式和 ，對內(nèi)插函數(shù)進(jìn)行恒等變換：,頻率域采樣,所以， 的內(nèi)插公式和內(nèi)插函數(shù)又可寫作：,第三

23、章 付里葉分析,此表達(dá)方式將在數(shù)字信號處理介紹的頻率采樣FIR濾波器設(shè)計(jì)中得到應(yīng)用。 快速付氏變換(Fast Fourier Transform) 引言(Introduction) DFT是數(shù)字（離散）信號中的一種重要變換，但從DFT定義可以容易得到直接計(jì)算一個N點(diǎn)的DFT需要：N2次復(fù)數(shù)乘法；N(N-1)次復(fù)數(shù)加法。即其運(yùn)算量隨著N按平方增加，當(dāng)N較大時，其計(jì)算量非常大，直接用DFT進(jìn)行實(shí)時計(jì)算或譜分析是不切實(shí)際的。,快速付氏變換,1965年庫利(J.W.Cooley)和圖基(J.W.Tukey)發(fā)現(xiàn)DFT的快速算法后，DFT才得到實(shí)際的應(yīng)用。 自1965年后，DFT的快速計(jì)算算法的研究得到

24、空前的發(fā)展，除了Cooley-Tukey算法；Sande-Tukey算法外，還有許多其它算法，如：Winograd算法；余弦變換快速算法；Walsh變換；數(shù)論變換等。 基2FFT算法(The Algorithm of Base 2 FFT) FFT的基本思想(The Basal Thought of FFT) 長為N的序列x(n)的DFT定義：,快速付氏變換,式中， 為旋轉(zhuǎn)因子，具有如下特性： 周期性： 對稱性： FFT的基本思想(The Basal Thought of FFT) ： 利用 的周期性和對稱性，可使DFT運(yùn)算中的某些項(xiàng)合并； 因?yàn)镈FT的運(yùn)算量與N2成正比，若將DFT運(yùn)算盡可能

25、地分解成小N點(diǎn)的DFT的組合，這樣可以降低運(yùn)算量。,快速付氏變換,基2時域抽取FFT(Cooley-Tukey算法，DIT-FFT) 基2FFT ：通過補(bǔ)零使N滿足：N=2M，M為自然數(shù); 時域抽取原理(Time-Domain Decimation Theory) 按n的奇偶將x(n)分解為兩個N/2點(diǎn)的子序列： 則x(n)的DFT可寫作：,快速付氏變換,再由 的周期性和對稱性可求的DFT的后一半： 由周期性： 得：,快速付氏變換,和 再由對稱性： 從而有： 這樣，一個N點(diǎn)的DFT被分解成了兩個N/2點(diǎn)的DFT線性組合： 將DFT分解M次，最后為2點(diǎn)DFT，完成FFT分解。,快速付氏變換,蝶形

26、運(yùn)算表示(The Denotation of Butterfly Computation) 上式定義的運(yùn)算稱為蝶形運(yùn)算(Butterfly Computation)，它可由下圖形象表示，利用蝶形運(yùn)算符號可將FFT運(yùn)算用流圖描述。,一個蝶形運(yùn)算由一次復(fù)乘法；兩次復(fù)加法實(shí)現(xiàn)。向上加；向下減。,快速付氏變換,N=8的Cooley-Tukey法示例 一個N點(diǎn)基2FFT算法可以通過分解M次，每次用N/2個蝶形運(yùn)算表示。 例3-13：N=8的時域抽取FFT通過3次抽取實(shí)現(xiàn)。后面三個圖分別給出了8點(diǎn)時域抽取FFT的一、二、三次分解過程。由分解完成的8點(diǎn)時域FFT流圖可以看出流圖由M=3級構(gòu)成，每一級由N/2

27、個蝶形組成，每級蝶形的旋轉(zhuǎn)因子均有其規(guī)律。,8 點(diǎn)DFT的第一次時域抽取分解圖,8 點(diǎn)DFT的第二次時域抽取分解圖,N點(diǎn)DIT-FFT運(yùn)算流圖（N=8）,快速付氏變換,Cooley-Tukey算法的規(guī)律及特點(diǎn)(Rules and Properties of Cooley-Tukey Algorithm) 規(guī)律： 流圖結(jié)構(gòu)(The Structure of Flow-Graph) N=2M點(diǎn)基2FFT算法流圖結(jié)構(gòu)共有M級，每級有N/2個蝶形； 輸入序列的倒序(The Reverse order of Input Sequence) 按M位二進(jìn)制“碼位倒置”規(guī)律擾亂輸入序列的角標(biāo)順序。 例3-14：設(shè)N=8，M=3，有：,快速付氏變換,蝶距(The Space of Butterfly Input) 定義：蝶形輸入兩信號點(diǎn)間的節(jié)點(diǎn)數(shù)稱為蝶距。 式中：N為點(diǎn)數(shù)；M為級數(shù)；l為級號。 旋轉(zhuǎn)因子 各級蝶形有 組 ；每組有 個 ，而且組中 的冪m按差 由0遞增。 由這些規(guī)律可以很容易地畫出N=2M點(diǎn)的基2FF