ch3-1-2離散傅里葉級數(shù).ppt

1,第03章 離散傅里葉變換及其快速算法,伍凱寧 87544817-8263,華中科技大學(xué)電信系,2,內(nèi)容提要,離散傅里葉變換 (Discrete Fourier Transform，DFT)是時間函數(shù)是離散的，而且頻譜函數(shù)也是離散的變換。 討論周期序列的傅里葉級數(shù)及其性質(zhì)。 討論有限長序列的離散傅里葉變換及其性質(zhì)，其中包括循環(huán)卷積的重要概念。 利用循環(huán)卷積計算線性卷積。 討論頻率取樣理論。 重點討論FFT的時間抽選算法。 介紹變換點數(shù)為合數(shù)時的FFT算法。 介紹快速傅里葉變換算法的應(yīng)用。,華中科技大學(xué)電信系,3,一.DFT是重要的變換 1.分析有限長序列的有用工具。 2.在信號處理的理論上有重要意義。 3.在運算方法上起核心作用，譜分析、 卷積、相關(guān)都可以通過DFT在計算機 上實現(xiàn)。,引言,華中科技大學(xué)電信系,4,二.傅氏變換的幾種可能形式 (1).連續(xù)時間、連續(xù)頻率的傅氏變換-FT,對于非周期的連續(xù)時間信號,華中科技大學(xué)電信系,5,對稱性: 時域連續(xù)，則頻域非周期。 反之亦然。,華中科技大學(xué)電信系,6,(2).連續(xù)時間、離散頻率傅里葉變換-FS,對于周期為Tp的連續(xù)時間信號,華中科技大學(xué)電信系,7,*時域周期為Tp, 頻域譜線間隔為2/Tp,華中科技大學(xué)電信系,8,(3).離散時間、連續(xù)頻率的傅氏變換-DTFT,對于非周期的序列,抽樣間隔T,華中科技大學(xué)電信系,9,共同的缺點：這三種變換總有一個域不是離散的，計算機不能直接計算；,希望的變換：不僅時間離散，頻率也離散DFT。,華中科技大學(xué)電信系,10,華中科技大學(xué)電信系,11,3.1 離散傅里葉級數(shù)及其性質(zhì),3. 1. 1 離散傅里葉級數(shù)(DFS)定義（周期序列）,一個周期為N的周期序列,可表示為：,但是可以用離散傅里葉級數(shù)，即用復(fù)指數(shù)的加權(quán)和表示,用傅里葉級數(shù)表示，其基波頻率為2p/N：,用復(fù)指數(shù)表示基波：,第k次諧波為：,所以，第k次諧波也是周期為N的序列。,不滿足,，ZT不存在。,華中科技大學(xué)電信系,12,因此，對于離散傅里葉級數(shù)，只取下標從0到N-1的N個諧波分量就足以表示原來的信號。這樣可把離散傅里葉級數(shù)表示為,式中，乘以系數(shù)1/N是為了下面計算的方便；,為k次諧波的系數(shù)。,將上式兩邊同乘以,并從n=0到N-1求和，得到：,華中科技大學(xué)電信系,13,由復(fù)指數(shù)序列的正交性：,所以，,得到周期序列的離散傅里葉級數(shù)表達式：,華中科技大學(xué)電信系,14,令,則得到周期序列的離散傅里葉級數(shù)(DFS)變換對,n和k均為離散變量。如果將n當作時間變量，k當作頻率變量，則第一式表示的是時域到頻域的變換，稱為DFS的正變換。第二式表示的是頻域到時域的變換，稱為DFS的反變換。,由于,故 是周期為N的離散周期信號。,周期序列的信息可以用它在一個周期中的N個值來代表。,華中科技大學(xué)電信系,15,DFS總結(jié):,和,2.,是離散和周期性的，且周期均為N；,5. DFS、IDFS具有唯一性.,3.離散周期序列既可用 ,也可用 表示；,1.周期性時間信號的頻譜是離散的，離散時間信號的頻譜是周期性的；周期性離散時間信號的頻譜為周期性離散的；,4. n為離散時間變量，理解為nT；k是離散頻率變量，理解為 kDw;,華中科技大學(xué)電信系,16,3.1.2 離散傅里葉級數(shù)的性質(zhì),1. 線性,設(shè)周期序列 和 的周期都為N，且,若,則有,2周期序列的移位,設(shè),則,華中科技大學(xué)電信系,17,證明,證明：,* 和 都是以N為周期的周期函數(shù)。,華中科技大學(xué)電信系,18,3周期卷積,設(shè),和,都是周期為N的周期序列，它們的,DFS系數(shù)分別為,令,則,上式表示的是兩個周期序列的卷積，稱為周期卷積。,兩個周期為N的序列的卷積的離散傅里葉級數(shù)(DFS)等于它們各自DFS的乘積。,華中科技大學(xué)電信系,19,周期卷積的計算：,周期卷積中的序列 和 對m都是周期為N的周期序列，它們的乘積對m也是以N為周期的，周期卷積僅在一個周期內(nèi)求和。,相乘和相加運算僅在m=0到N-1的區(qū)間內(nèi)進行。計算出n=0到N-1(一個周期)的結(jié)果后，再將其進行周期延拓，就得到周期卷積 。詳見周期卷積的過程。,周期卷積滿足交換律,兩個周期序列的乘積 的DFS為：,華中科技大學(xué)電信系,20,返回,華中科技大學(xué)電信系,21,周期卷積小結(jié):,周期卷積的操作步驟與非周期序列的線性卷積相同，不同的是周期卷積僅在一個周期內(nèi)求和； 周期卷積中,對m是周期性的，周期為N；,的周期為N；,周期卷積滿足交換律。,華中科技大學(xué)電信系,22,3.2 離散傅里葉變換及其性質(zhì),3.2.1 離散傅里葉變換(DFT) 有限長序列的傅里葉變換稱為離散傅里葉變換，簡寫為DFT。 DFT可以按3個步驟由 DFS推導(dǎo)出來： 將有限長序列延拓成周期序列； 求周期序列的DFS； 從DFS中取出一個周期便得到有限長序列的DFT。,將x(n)延拓成周期為N的周期序列 :,華中科技大學(xué)電信系,23,顯然有,的第一個周期，即n=0到N-1的序列稱為主值序列，n=0,到N-1的范圍稱為主值區(qū)間。,上述兩式可分別表示為,其中RN(n)是矩形序列。符號(n)N表示n對模N的余數(shù)，即,這里k是商。,都表示周期序列,華中科技大學(xué)電信系,24,例如： (1) (2),華中科技大學(xué)電信系,25,同理，可以認為周期序列 的DFS系數(shù) 是有限長序列X(k)周期延拓的結(jié)果，而 X(k)是 的主值序列。即,華中科技大學(xué)電信系,26,由此便可以得出有限長序列的離散傅里葉變換(DFT)的表示式為:,由此可見，有限長序列x(n)的DFT即X(k)仍是有限長序列。,華中科技大學(xué)電信系,27,在一般情況下，X(k)是一個復(fù)量，可表示為,或,式中,例3. 1 求有限長序列,的DFT，其中a=0.8，N=8。,華中科技大學(xué)電信系,28,解：,因此得,X(0)=4.16114 X(1)=0.71063-j0.92558 X(2)=0.50746-j0.40597 X(3)=0.47017-j0.16987,X(4)=0.46235 X(5)= 0.47017+j0.16987 X(6)= 0.50746+j0.40597 X(7)= 0.71063+j0.92558,華中科技大學(xué)電信系,29,例 已知,求X(k)的9點的IDFT.,解：,華中科技大學(xué)電信系,30,將x(n)的Z變換,與x(n)的DFT,進行對比，可以看出,式中，,表示z平面單位圓上輻角為,(k=0,1,N-1)的N個等間隔點。,Z變換在這些點上的取樣值就是X(k)。,DFT與ZT的關(guān)系,華中科技大學(xué)電信系,31,DFT與DTFT的關(guān)系,有限長序列x(n)的DFT系數(shù)X(k)可看作其DTFT在一個周期(2p)內(nèi)等間距取樣的樣本值，取樣間隔為Dw=2p/N，即,DFT與DTFT的關(guān)系示意圖,華中科技大學(xué)電信系,32,DTFT與ZT的關(guān)系,單位圓(z=ej)上的Z變換，即傅里葉變換X(ej)。,華中科技大學(xué)電信系,33,序列x(n)的DFT就是其ZT在單位圓上的等角距取樣。,序列x(n)的DFT就是其DTFT在頻率取樣點的取值。,序列x(n)的DTFT就是其在單位圓上的ZT。,華中科技大學(xué)電信系,34,例 已知復(fù)序列 x(n)=xr(n)+jxi(n)，其中xr(n),xi(n)是實序列。序列x(n)的ZTX(z)的單位圓的下半部(pw2p)為0。求x(n)的DFTX(k)后一半的值，請說明理由。,解：,因為,華中科技大學(xué)電信系,35,例 已知序列,求其4點DFT，8點DFT，16點DFT？并畫出,|X(k)|k的曲線圖。,解：x(n)的FT為：,華中科技大學(xué)電信系,36,x(n)的4點DFT為：,1,華中科技大學(xué)電信系,37,x(n)的8點DFT為：,1,華中科技大學(xué)電信系,38,x(n)的16點DFT為：,1,華中科技大學(xué)電信系,39,4,8,12,16點：,8點：,4點：,華中科技大學(xué)電信系,40,華中科技大學(xué)電信系,41,對比：,離散時間信號的FT-DTFT： 時域離散，頻域連續(xù) 離散的有限長信號的DFT： 時域離散，頻域離散,華中科技大學(xué)電信系,42,離散傅里葉變換(DFT)總結(jié),序列x(n)在時域是離散、有限長的(長度為N)，它的離散傅里葉變換X(k)也是離散、有限長的(長度也為N)。所以， x(n)和X(k)均可用計算機實現(xiàn)。 n為時域變量(nT)，k為頻域變量(kDw)。 DFT與DFS沒有本質(zhì)區(qū)別，DFT實際上是DFS的主值，DFT也隱含有周期性。 離散傅里葉變換(DFT)具有唯一性。 DFT的物理意義：序列x(n)的Z變換在單位圓上的等角距取樣。,華中科技大學(xué)電信系,43,N/2點的DFT:,N/4點的DFT:,華中科技大學(xué)電信系,44,旋轉(zhuǎn)因子 的性質(zhì),對稱性：,周期性：,換底：,k/2,N/2為整數(shù),幾個特殊值：,華中科技大學(xué)電信系,45,例. 令X(k)表示N點序列x(n)的N點DFT，X(k)本身也是一個N點序列，如果計算X(k)的DFT得到一個序列x1(n)，試用x(n)求x1(n)。,解：,華中科技大學(xué)電信系,46,華中科技大學(xué)電信系,47,3.2.2 離散傅里葉變換的性質(zhì),DFT隱含著周期性，因此在討論DFT的性質(zhì)時，常與DFS的概念聯(lián)系起來，并把有限長序列看作周期序列的一個周期來處理。 設(shè)x1(n)和x2(n)的長度都為N，且它們對應(yīng)的DFT分別為X1(k)和X2(k)。,1線性,設(shè)x3(n)=ax1(n)+bx2(n)，a和b都為常數(shù)，則,若它們長度不等，取長度最大者，將短的序列通過補零加長。 此性質(zhì)可以直接由DFT的定義進行證明。,華中科技大學(xué)電信系,48,對于長為N的復(fù)序列x(n)，,證明：,（1）因為X(k)隱含周期性，所以,（2）對于實序列，,2對稱性,華中科技大學(xué)電信系,49,這意味著,或,實序列的DFT系數(shù)X(k)的模是偶對稱序列，輻角是奇對稱序列,對于實序列的DFT，可以只計算一半：,華中科技大學(xué)電信系,50,3序列的循環(huán)移位,一個長度為N的序列x(n)的循環(huán)移位定義為,循環(huán)移位分3步計算：,(1)將x(n)延拓成周期為N的周期序列 ； (2)將 移位得 或x(n+m)N； (3)對x(n+m)N取主值得x(n+m)NRN(n)。 這個過程如下圖所示。,華中科技大學(xué)電信系,51,從圖中兩虛線之間的主值序列的移位情況可以看出，當主值序列左移m個樣本時，從右邊會同時移進m個樣本，而且好像是剛向左邊移出的那些樣本又從右邊循環(huán)移了進來。因此取名“循環(huán)移位”。 顯然，循環(huán)移位不同于線性移位。,華中科技大學(xué)電信系,52,將序列右移：,華中科技大學(xué)電信系,53,序列循環(huán)移位后的DFT為,證明：由周期序列的移位性質(zhì)得,x(n+m)NRN(n)是 的主值序列,的DFS的主值，即,根據(jù)時域和頻域的對偶關(guān)系，可以得出,若,則,它的DFT就是,華中科技大學(xué)電信系,54,例.已知,求出該信號的DFT ， X(k)=DFTx(n)，變換區(qū)間長度為8。,（提示：注意x(n)的區(qū)間不符合DFT要求的區(qū)間）,解:,其中,華中科技大學(xué)電信系,55,華中科技大學(xué)電信系,56,幾種變換的時移性質(zhì)匯總：,華中科技大學(xué)電信系,57,4循環(huán)卷積,設(shè)Y(k)=Xl(k)X2(k)，則,或,由上式表示的卷積稱為循環(huán)卷積，常記為,(式3.36),華中科技大學(xué)電信系,58,證明：,利用DFT的隱含周期性，將Y(k)周期延拓計算后再取主值. m取值的0N-1范圍是主值區(qū)間，故 因此,華中科技大學(xué)電信系,59,循環(huán)卷積的計算是對序列按循環(huán)移位后求對應(yīng)項的乘積之和，實際上就是周期卷積取主值。,華中科技大學(xué)電信系,60,循環(huán)卷積的計算過程： x1(n)的N個值按順時針方向均勻分布在內(nèi)圓周上，x2(n)的N個值按反時針方向均勻分布在外圓周上，把內(nèi)外圓周上對應(yīng)的數(shù)值兩兩相乘，然后把乘積相加就得到y(tǒng)(0)。若將外圓周順時針方向轉(zhuǎn)動一格(如圖3.6(b)所示)，將內(nèi)外圓周上對應(yīng)的數(shù)值兩兩相乘并把乘積相加，便得到y(tǒng)(1)。依次類推，可以得出y(n)的其它值。 循環(huán)卷積也叫做圓卷積或圓周卷積。,下圖表示的是序列x1(n)和x2(n)的4點(即N=4)循環(huán)卷積的計算過程。圖中，x1(n)=(n)+(n-1)+(n-2)，x2(n)=(n)+1.5(n-1)+2(n-2)+2.5(n-3)。,華中科技大學(xué)電信系,61,華中科技大學(xué)電信系,62,考慮到DFT關(guān)系的對偶性，可以證明，長為N的兩序列之積的DFT等于它們的DFT的循環(huán)卷積除以N，即,這一計算過程分4步: （相當于求周期卷積的主值） (1)周期延拓和折疊 (2)移位和取主值 (3)相乘 (4)相加 注意：若x1(n)和x2(n)的長度不一致，可以根據(jù)需要添零延拓。,華中科技大學(xué)電信系,63,華中科技大學(xué)電信系,64,循環(huán)卷積小結(jié): 循環(huán)卷積的過程與周期卷