ch離散傅里葉級(jí)數(shù)PPT課件

1、1第第03章章 離散傅里葉離散傅里葉變換及其快速算法變換及其快速算法伍凱寧伍凱寧 87544817-8263第1頁(yè)/共66頁(yè)2內(nèi)容提要 離散傅里葉變換 (Discrete Fourier Transform，DFT)是時(shí)間函數(shù)是離散的，而且頻譜函數(shù)也是離散的變換。 討論周期序列的傅里葉級(jí)數(shù)及其性質(zhì)。 討論有限長(zhǎng)序列的離散傅里葉變換及其性質(zhì)，其中包括循環(huán)卷積的重要概念。 利用循環(huán)卷積計(jì)算線(xiàn)性卷積。 討論頻率取樣理論。 重點(diǎn)討論FFT的時(shí)間抽選算法。 介紹變換點(diǎn)數(shù)為合數(shù)時(shí)的FFT算法。 介紹快速傅里葉變換算法的應(yīng)用。第2頁(yè)/共66頁(yè)3一.DFT是重要的變換 1.分析有限長(zhǎng)序列的有用工具。 2.在信

2、號(hào)處理的理論上有重要意義。 3.在運(yùn)算方法上起核心作用，譜分析、 卷積、相關(guān)都可以通過(guò)DFT在計(jì)算機(jī) 上實(shí)現(xiàn)。引言第3頁(yè)/共66頁(yè)4(1).連續(xù)時(shí)間、連續(xù)頻率的傅氏變換-FT0t)(tx0)( jX對(duì)于非周期的連續(xù)時(shí)間信號(hào)第4頁(yè)/共66頁(yè)5時(shí)域信號(hào)頻域信號(hào)連續(xù)的非周期的非周期的連續(xù)的對(duì)稱(chēng)性: 時(shí)域連續(xù)，則頻域非周期。 反之亦然。第5頁(yè)/共66頁(yè)6(2).連續(xù)時(shí)間、離散頻率傅里葉變換-FS0t-0對(duì)于周期為T(mén)p的連續(xù)時(shí)間信號(hào)第6頁(yè)/共66頁(yè)7時(shí)域信號(hào)頻域信號(hào)連續(xù)的周期的非周期的離散的*時(shí)域周期為T(mén)p, 頻域譜線(xiàn)間隔為2/Tp第7頁(yè)/共66頁(yè)8 (3).離散時(shí)間、連續(xù)頻率的傅氏變換-DTFT 對(duì)于

3、非周期的序列0Ts2-抽樣間隔Tx(nT)-T0T2Ttx(nT)T-T0T2Tt第8頁(yè)/共66頁(yè)9時(shí)域信號(hào)頻域信號(hào)離散的非周期的周期的連續(xù)的共同的缺點(diǎn)：這三種變換總有一個(gè)域不是離散的，計(jì)算機(jī)不能直接計(jì)算； 希望的變換：不僅時(shí)間離散，頻率也離散DFT。 第9頁(yè)/共66頁(yè)10第10頁(yè)/共66頁(yè)113.1 離散傅里葉級(jí)數(shù)及其性質(zhì)3. 1. 1 離散傅里葉級(jí)數(shù)(DFS)定義（周期序列） 一個(gè)周期為N的周期序列可表示為： 但是可以用離散傅里葉級(jí)數(shù)，即用復(fù)指數(shù)的加權(quán)和表示用傅里葉級(jí)數(shù)表示，其基波頻率為2/N：用復(fù)指數(shù)表示基波：第k次諧波為：所以，第k次諧波也是周期為N的序列。21jnNee2jnkNke

4、e22()jn k NjnkNNk Nkeeee( )nnx n r 不滿(mǎn)足，ZT不存在。第11頁(yè)/共66頁(yè)12因此，對(duì)于離散傅里葉級(jí)數(shù)，只取下標(biāo)從0到N-1的N個(gè)諧波分量就足以表示原來(lái)的信號(hào)。這樣可把離散傅里葉級(jí)數(shù)表示為 式中，乘以系數(shù)1/N是為了下面計(jì)算的方便； 為k次諧波的系數(shù)。將上式兩邊同乘以并從n=0到N-1求和，得到：第12頁(yè)/共66頁(yè)13由復(fù)指數(shù)序列的正交性：所以，得到周期序列的離散傅里葉級(jí)數(shù)表達(dá)式：2221()()0()101NNNNjk r njk r Nnjk rNkreekre 第13頁(yè)/共66頁(yè)14令則得到周期序列的離散傅里葉級(jí)數(shù)(DFS)變換對(duì)n和k均為離散變量。如果

5、將n當(dāng)作時(shí)間變量，k當(dāng)作頻率變量，則第一式表示的是時(shí)域到頻域的變換，稱(chēng)為DFS的正變換。第二式表示的是頻域到時(shí)域的變換，稱(chēng)為DFS的反變換。由于故 是周期為N的離散周期信號(hào)。周期序列的信息可以用它在一個(gè)周期中的N個(gè)值來(lái)代表。第14頁(yè)/共66頁(yè)15DFS總結(jié):( )X k和2.是離散和周期性的，且周期均為N； 5. DFS、IDFS具有唯一性. 3.離散周期序列既可用 ,也可用 表示； ( )X k1.周期性時(shí)間信號(hào)的頻譜是離散的，離散時(shí)間信號(hào)的頻譜是周期性的；周期性離散時(shí)間信號(hào)的頻譜為周期性離散的； 4. n為離散時(shí)間變量，理解為nT；k是離散頻率變量，理解為 kDw; 第15頁(yè)/共66頁(yè)16

6、3.1.2 離散傅里葉級(jí)數(shù)的性質(zhì)1. 線(xiàn)性設(shè)周期序列 和 的周期都為N，且若則有2周期序列的移位 設(shè)則第16頁(yè)/共66頁(yè)17證明證明：* 和 都是以N為周期的周期函數(shù)。10()Nk n mmkNNnx nm WW%1( )NmktmkNNtmx t W W %( )X k,第17頁(yè)/共66頁(yè)183周期卷積設(shè)和都是周期為N的周期序列，它們的DFS系數(shù)分別為令則上式表示的是兩個(gè)周期序列的卷積，稱(chēng)為周期卷積。兩個(gè)周期為N的序列的卷積的離散傅里葉級(jí)數(shù)(DFS)等于它們各自DFS的乘積。第18頁(yè)/共66頁(yè)19周期卷積的計(jì)算：周期卷積中的序列 和 對(duì)m都是周期為N的周期序列，它們的乘積對(duì)m也是以N為周期的

7、，周期卷積僅在一個(gè)周期內(nèi)求和。 相乘和相加運(yùn)算僅在m=0到N-1的區(qū)間內(nèi)進(jìn)行。計(jì)算出n=0到N-1(一個(gè)周期)的結(jié)果后，再將其進(jìn)行周期延拓，就得到周期卷積 。詳見(jiàn)周期卷積的過(guò)程。 周期卷積滿(mǎn)足交換律兩個(gè)周期序列的乘積 的DFS為：第19頁(yè)/共66頁(yè)20返回133第20頁(yè)/共66頁(yè)21周期卷積小結(jié):)(),(21mnxmx)(ny周期卷積的操作步驟與非周期序列的線(xiàn)性卷積相同，不同的是周期卷積僅在一個(gè)周期內(nèi)求和；周期卷積中對(duì)m是周期性的，周期為N；的周期為N；周期卷積滿(mǎn)足交換律。第21頁(yè)/共66頁(yè)223.2 離散傅里葉變換及其性質(zhì)3.2.1 離散傅里葉變換(DFT) 有限長(zhǎng)序列的傅里葉變換稱(chēng)為離散

8、傅里葉變換，簡(jiǎn)寫(xiě)為DFT。DFT可以按3個(gè)步驟由 DFS推導(dǎo)出來(lái)：將有限長(zhǎng)序列延拓成周期序列；求周期序列的DFS；從DFS中取出一個(gè)周期便得到有限長(zhǎng)序列的DFT。將x(n)延拓成周期為N的周期序列 :第22頁(yè)/共66頁(yè)23顯然有的第一個(gè)周期，即n=0到N-1的序列稱(chēng)為主值序列，n=0到N-1的范圍稱(chēng)為主值區(qū)間。上述兩式可分別表示為 其中RN(n)是矩形序列。符號(hào)(n)N表示n對(duì)模N的余數(shù)，即 這里k是商。 都表示周期序列第23頁(yè)/共66頁(yè)24例如：(1)(2)第24頁(yè)/共66頁(yè)25同理，可以認(rèn)為周期序列 的DFS系數(shù) 是有限長(zhǎng)序列X(k)周期延拓的結(jié)果，而 X(k)是 的主值序列。即 1010

9、10( )( )( )( )( )( )( )01( )0NknNnNknNNNnNknNnX kx n WX kRkx n WRnx n WkNX k%其他第25頁(yè)/共66頁(yè)26由此便可以得出有限長(zhǎng)序列的離散傅里葉變換(DFT)的表示式為:由此可見(jiàn)，有限長(zhǎng)序列x(n)的DFT即X(k)仍是有限長(zhǎng)序列。第26頁(yè)/共66頁(yè)27在一般情況下，X(k)是一個(gè)復(fù)量，可表示為或式中例3. 1 求有限長(zhǎng)序列的DFT，其中a=0.8，N=8。 第27頁(yè)/共66頁(yè)28解：因此得 X(0)=4.16114 X(1)=0.71063-j0.92558 X(2)=0.50746-j0.40597 X(3)=0.47

10、017-j0.16987 第28頁(yè)/共66頁(yè)29例 已知50( )218kX kk求X(k)的9點(diǎn)的IDFT.88990011( )( )329912 ( )0,1,.,83knknkkx nX k WWnn89090,=01,.,8knknWn其中解： 第29頁(yè)/共66頁(yè)30將x(n)的Z變換與x(n)的DFT進(jìn)行對(duì)比，可以看出式中，表示z平面單位圓上輻角為(k=0,1,N-1)的N個(gè)等間隔點(diǎn)。Z變換在這些點(diǎn)上的取樣值就是X(k)。DFT與與ZT的關(guān)系的關(guān)系第30頁(yè)/共66頁(yè)312/2/( )()()jk Njk NX kX eX ewwDFT與與DTFT的關(guān)系的關(guān)系有限長(zhǎng)序列x(n)的DF

11、T系數(shù)X(k)可看作其DTFT在一個(gè)周期(2)內(nèi)等間距取樣的樣本值，取樣間隔為Dw=2/N，即DFT與與DTFT的關(guān)系示意圖的關(guān)系示意圖210( )( )NjknNnX kx n e10()( )Njj nnX ex n eww第31頁(yè)/共66頁(yè)32DTFT與與ZT的關(guān)系的關(guān)系單位圓(z=ej)上的Z變換，即傅里葉變換X(ej)。()( )jjz eX eX zww10()( )Njj nnX ex n eww10( )( )NnnX zx n z第32頁(yè)/共66頁(yè)332( )()jk NX kX eww2( )( )( )kjkNNz Wz eX kX zX z()( )jjz eX eX

12、zww序列x(n)的DFT就是其ZT在單位圓上的等角距取樣。序列x(n)的DFT就是其DTFT在頻率取樣點(diǎn)的取值。序列x(n)的DTFT就是其在單位圓上的ZT。第33頁(yè)/共66頁(yè)34例 已知復(fù)序列 x(n)=xr(n)+jxi(n)，其中xr(n),xi(n)是實(shí)序列。序列x(n)的ZTX(z)的單位圓的下半部(w2)為0。求x(n)的DFTX(k)后一半的值，請(qǐng)說(shuō)明理由。解： 1,.,12,2, 0)(NNNkkX2( )( )( )kjkNNz Wz eX kX zX z因?yàn)?第34頁(yè)/共66頁(yè)35例 已知序列103( )0nx nothers求其4點(diǎn)DFT，8點(diǎn)DFT，16點(diǎn)DFT？并畫(huà)

13、出|X(k)|k的曲線(xiàn)圖。 4322222221()( )1()sin(2 )()sin()2jjj njnjjjjjjjeX ex n eeeeeeeeewwwwwwwwwwwww解：x(n)的FT為：第35頁(yè)/共66頁(yè)36x(n)的4點(diǎn)DFT為：3424sin()( )()sin()4jkjkkX kX eekww1第36頁(yè)/共66頁(yè)37x(n)的8點(diǎn)DFT為：3828sin()2( )()sin()8jkjkkX kX eekww1第37頁(yè)/共66頁(yè)38x(n)的16點(diǎn)DFT為：316216sin()4( )()sin()16jkjkkX kX eekww1第38頁(yè)/共66頁(yè)394812

14、16點(diǎn)：8點(diǎn)：4點(diǎn)：第39頁(yè)/共66頁(yè)40第40頁(yè)/共66頁(yè)41對(duì)比：離散時(shí)間信號(hào)的FT-DTFT： 時(shí)域離散，頻域連續(xù)離散的有限長(zhǎng)信號(hào)的DFT： 時(shí)域離散，頻域離散第41頁(yè)/共66頁(yè)42離散傅里葉變換離散傅里葉變換(DFT)總結(jié)總結(jié)序列序列x(n)在時(shí)域是離散、有限長(zhǎng)的在時(shí)域是離散、有限長(zhǎng)的(長(zhǎng)度為長(zhǎng)度為N)，它它的離散傅里葉變換的離散傅里葉變換X(k)也是離散、有限長(zhǎng)的也是離散、有限長(zhǎng)的(長(zhǎng)度長(zhǎng)度也為也為N)。所以，所以， x(n)和和X(k)均可用計(jì)算機(jī)實(shí)現(xiàn)。均可用計(jì)算機(jī)實(shí)現(xiàn)。n為時(shí)域變量為時(shí)域變量(nT)，k為頻域變量為頻域變量(kDwDw)。DFT與與DFS沒(méi)有本質(zhì)區(qū)別，沒(méi)有本質(zhì)區(qū)別

15、，DFT實(shí)際上是實(shí)際上是DFS的的主值，主值，DFT也隱含有周期性。也隱含有周期性。離散傅里葉變換離散傅里葉變換(DFT)具有唯一性。具有唯一性。DFT的物理意義：序列的物理意義：序列x(n)的的Z變換在單位圓上的變換在單位圓上的等角距取樣。等角距取樣。第42頁(yè)/共66頁(yè)43N/2點(diǎn)的DFT: 1202( )( )0,1,2,.,12NknNnNX kx n Wk1404( )( )0,1,2,.,14NknNnNX kx n WkN/4點(diǎn)的DFT: 第43頁(yè)/共66頁(yè)44旋轉(zhuǎn)因子旋轉(zhuǎn)因子 的性質(zhì)的性質(zhì) NjNeW2對(duì)稱(chēng)性： kNNkNWW)*(周期性： kNmNkNWW換底： 22kmkkN

16、mNNWWW,k/2,N/2為整數(shù) 幾個(gè)特殊值： 1kNNW21NNW 4NNWj 34NNWj第44頁(yè)/共66頁(yè)45例. 令X(k)表示N點(diǎn)序列x(n)的N點(diǎn)DFT，X(k)本身也是一個(gè)N點(diǎn)序列，如果計(jì)算X(k)的DFT得到一個(gè)序列x1(n)，試用x(n)求x1(n)。解：111100 011 00( )( )( )( )NNNknknknNNNkknNNk n nNnkx nX k Wx n WWx nW 第45頁(yè)/共66頁(yè)46111 00( )( )NNk n nNnkx nx nW()( )( )NlNNNxnNl RnNxnRn 10,0Nk n nNkNnnNl lZW其他第46頁(yè)

17、/共66頁(yè)473.2.2 離散傅里葉變換的性質(zhì) DFT隱含著周期性，因此在討論DFT的性質(zhì)時(shí)，常與DFS的概念聯(lián)系起來(lái)，并把有限長(zhǎng)序列看作周期序列的一個(gè)周期來(lái)處理。設(shè)x1(n)和x2(n)的長(zhǎng)度都為N，且它們對(duì)應(yīng)的DFT分別為X1(k)和X2(k)。1線(xiàn)性 設(shè)x3(n)=ax1(n)+bx2(n)，a和b都為常數(shù)，則 若它們長(zhǎng)度不等，取長(zhǎng)度最大者，將短的序列通過(guò)補(bǔ)零加長(zhǎng)。 此性質(zhì)可以直接由DFT的定義進(jìn)行證明。第47頁(yè)/共66頁(yè)48對(duì)于長(zhǎng)為N的復(fù)序列x(n)，*( )()DFT x nXNk*10)(*)()(NnnkNNWnxkNX10)(*)(NnnkNNWnx10*)(NnknNWnx)

18、(*nxDFT證明：（1）因?yàn)閄(k)隱含周期性，所以*()( )DFT xNnXk（2）對(duì)于實(shí)序列，* ( )( )()DFT x nX kXNk2對(duì)稱(chēng)性 第48頁(yè)/共66頁(yè)49這意味著或( )0,.,2 1()( )X kkNX NkXk實(shí)序列的DFT系數(shù)X(k)的模是偶對(duì)稱(chēng)序列，輻角是奇對(duì)稱(chēng)序列*()( )XNkX k對(duì)于實(shí)序列的DFT，可以只計(jì)算一半：第49頁(yè)/共66頁(yè)503序列的循環(huán)移位 一個(gè)長(zhǎng)度為N的序列x(n)的循環(huán)移位定義為 循環(huán)移位分3步計(jì)算：(1)將x(n)延拓成周期為N的周期序列 ； (2)將 移位得 或x(n+m)N；(3)對(duì)x(n+m)N取主值得x(n+m)NRN(n

19、)。這個(gè)過(guò)程如下圖所示。第50頁(yè)/共66頁(yè)51 從圖中兩虛線(xiàn)之間的主值序列的移位情況可以看出，當(dāng)主值序列左移m個(gè)樣本時(shí)，從右邊會(huì)同時(shí)移進(jìn)m個(gè)樣本，而且好像是剛向左邊移出的那些樣本又從右邊循環(huán)移了進(jìn)來(lái)。因此取名“循環(huán)移位”。 顯然，循環(huán)移位不同于線(xiàn)性移位。 第51頁(yè)/共66頁(yè)52將序列右移：第52頁(yè)/共66頁(yè)53序列循環(huán)移位后的DFT為 證明：由周期序列的移位性質(zhì)得x(n+m)NRN(n)是 的主值序列的DFS的主值，即根據(jù)時(shí)域和頻域的對(duì)偶關(guān)系，可以得出若則它的DFT就是第53頁(yè)/共66頁(yè)54othersnnx, 03| , 1)(求出該信號(hào)的DFT ， X(k)=DFTx(n)，變換區(qū)間長(zhǎng)度為

20、8。（提示：注意x(n)的區(qū)間不符合DFT要求的區(qū)間） 1( )(3)x nx n)(nx0n)(nx6 61othersnnx, 06 , 5 , 4 , 3 , 2 , 1 , 0, 1)(1解:,其中)()()3()(138881kXWnRnxDFTkXk1(3)( )x nx n第54頁(yè)/共66頁(yè)55kjkjnknnkneeWWnxkX4476087081111)()(733443481441( )( )11jkjkj kjkkjkjkeeeX kWX keee第55頁(yè)/共66頁(yè)56幾種變換的時(shí)移性質(zhì)匯總： 0)()(0tjFTejXttx0)()(0stLTesXttxmZTzzXm

21、nx)()(kmNDFTWkXmnx)()(第56頁(yè)/共66頁(yè)574循環(huán)卷積 設(shè)Y(k)=Xl(k)X2(k)，則或由上式表示的卷積稱(chēng)為循環(huán)卷積，常記為)( )()(1021nRmnxmxNNm(式3.36)第57頁(yè)/共66頁(yè)58證明：證明： 利用利用DFT的隱含周期性，將的隱含周期性，將Y(k)周期延拓計(jì)算后再取周期延拓計(jì)算后再取主值主值.m取值的取值的0N-1范圍是主值區(qū)間，故范圍是主值區(qū)間，故因此因此第58頁(yè)/共66頁(yè)59循環(huán)卷積的計(jì)算是對(duì)序列按循環(huán)移位后求對(duì)應(yīng)項(xiàng)的乘積之和，實(shí)際上就是周期卷積取主值。第59頁(yè)/共66頁(yè)60循環(huán)卷積的計(jì)算過(guò)程： x1(n)的N個(gè)值按順時(shí)針?lè)较蚓鶆蚍植荚趦?nèi)圓周上，x2(n)的N個(gè)值按反時(shí)針?lè)较蚓鶆蚍植荚谕鈭A周上，把內(nèi)外圓周上對(duì)應(yīng)