《測(cè)試信號(hào)處理技術(shù)第四章》由會(huì)員分享，可在線閱讀，更多相關(guān)《測(cè)試信號(hào)處理技術(shù)第四章（89頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、 離散時(shí)間信號(hào)分析內(nèi)容提要 序列的傅里葉變換（DTFT） 拉氏變換、傅氏變換與z變換之間的關(guān)系 離散傅里葉級(jí)數(shù)（DFS） 離散傅里葉變換（DFT） 快速傅里葉變換（FFT） 快速傅里葉變換的應(yīng)用 離散時(shí)間傅里葉變換DTFT與連續(xù)時(shí)間傅里葉變換的關(guān)系性質(zhì)離散傅里葉變換DFT定義性質(zhì)離散傅里葉變換的快速算法FFT原理流程應(yīng)用 實(shí)際信號(hào)的特點(diǎn)：時(shí)域：連續(xù)時(shí)間信號(hào); 持續(xù)時(shí)間較長(zhǎng)頻域：頻譜是連續(xù)的數(shù)字處理設(shè)備（計(jì)算機(jī)）的特點(diǎn)：存儲(chǔ)空間有限- 只能存儲(chǔ)有限多的數(shù)據(jù)離散的時(shí)間點(diǎn)有限長(zhǎng)的時(shí)間范圍表示空間有限- 只能表示有限多的數(shù)值 取值在一定精度內(nèi)取值在一定范圍內(nèi) 在時(shí)域如何對(duì)信號(hào)進(jìn)行離散化？要求保證信號(hào)的
2、信息不受損！信息不受損= 可以恢復(fù)原信號(hào)理論問(wèn)題已在第二章解決乘以沖激串信號(hào)，進(jìn)行時(shí)域抽樣要求抽樣過(guò)程滿足抽樣定理信號(hào)頻帶有限，抽樣頻率是信號(hào)最高頻率的兩倍矛盾1已基本解決 如何用抽樣信號(hào)的頻譜來(lái)恢復(fù)原信號(hào)的頻譜？抽樣信號(hào)頻譜與原信號(hào)頻譜是什么關(guān)系？理論上如何恢復(fù)？工程實(shí)踐上如何實(shí)現(xiàn)？ 抽樣信號(hào)的頻譜如何計(jì)算？得到抽樣信號(hào)后，如何計(jì)算其頻譜？輸入：抽樣信號(hào)（序列）輸出：抽樣信號(hào)的頻譜在工程上，計(jì)算機(jī)接受的輸入是一系列數(shù)值 信號(hào)被截短時(shí)，頻譜發(fā)生什么變化？有時(shí)信號(hào)持續(xù)時(shí)間超出處理能力時(shí)域信號(hào)需要被截?cái)嘟財(cái)鄷?huì)不會(huì)影響對(duì)信號(hào)的分析？截?cái)鄬?duì)信號(hào)的頻譜有何影響？ 有限長(zhǎng)離散信號(hào)頻譜的存儲(chǔ)與計(jì)算頻譜是連續(xù)
3、周期的1. 只能存儲(chǔ)有限長(zhǎng)的頻譜一個(gè)周期即可2. 只能存儲(chǔ)有限多的頻譜離散頻率點(diǎn)處的頻譜值離散頻率點(diǎn)譜值的計(jì)算法一：先有連續(xù)譜，后有離散譜值（頻域采樣）法二：直接用時(shí)間抽樣值計(jì)算離散譜值（公式）？ 如何由頻譜恢復(fù)抽樣信號(hào)？離散頻譜值是有限的恢復(fù)抽樣信號(hào)的計(jì)算公式如何編程實(shí)現(xiàn)（如何進(jìn)行快速計(jì)算）？按定義實(shí)現(xiàn)- 計(jì)算量太大由離散信號(hào)計(jì)算離散頻譜由離散頻譜恢復(fù)離散信號(hào) 從工程需要出發(fā)，理解信號(hào)頻譜分析的實(shí)際問(wèn)題。即在實(shí)踐中領(lǐng)悟處理原理的意義從解決問(wèn)題出發(fā)，理解各種信號(hào)處理方法的目的。即在矛盾中思考工程實(shí)現(xiàn)的背景在解決的問(wèn)題過(guò)程中感受知識(shí)的力量、體會(huì)學(xué)習(xí)的快樂(lè) 1.定義x (n)的z變換為如果X (z
4、)在單位圓上是收斂的，則把在單位圓上的z變換定義為序列的傅里葉變換，表示為(4.1) 相對(duì)應(yīng)序列的傅里葉反變換，由z反變換的圍線積分公式若把積分圍線C取在單位圓上，則有（4.2） 2物理意義把序列的傅里葉變換稱作非周期序列的頻譜，為什么把序列的傅里葉變換和序列的頻譜聯(lián)系在一起?可以與連續(xù)信號(hào)的傅里葉變換進(jìn)行對(duì)比進(jìn)行分析.已知連續(xù)信號(hào)的傅里葉變換為 F ()有頻譜密度的意義，是頻譜的概念，在式（4.1）中，X (ej)是序列的傅里葉變換，與F ()在連續(xù)信號(hào)傅里葉變換的表達(dá)式中一樣起著相同的作用，所以看作是序列的頻譜。f (t) 和x (n)的兩個(gè)表達(dá)式都具有疊加重構(gòu)（綜合）時(shí)域信號(hào)即傅里葉反變
5、換的作用，因此把式（4.2）稱為序列的傅里葉反變換。 將式（4.1）和（4.2）重寫(xiě)并表示為(4.3)(4.4) 3特點(diǎn)由式(4.3)知，序列頻譜X (ej) 是ejn的函數(shù)，而ejn 是以2為周期的函數(shù)，并且由于序列在時(shí)域上是非周期的，因而，序列的頻譜是周期的連續(xù)頻譜。同時(shí)X (ej)是 的復(fù)函數(shù)，可進(jìn)一步表示為(4.5)( ) ( ) ( ) ( ) ( ) wwwjww jjjjj eXjeXeeXeX ImRe += 其幅度譜如圖4.1所示圖4.1 序列及其幅譜圖 序列傅立葉變換存在的條件由于序列的傅里葉變換是單位圓上的z變換，序列的z變換在單位圓上必須收斂是序列傅里葉變換存在的條件，
6、即上式表明，序列傅里葉變換存在的條件是：序列必須絕對(duì)可和。(充分條件)( ) =n nx 例4.1 求出下列序列的傅里葉變換。x2(n) = (n+3) - (n-4)解: ( ) ( ) ( ) = = =+= +=+=+= =+= = = = = = = = ww wwww wwwwww wwwwwwwww wwwwwww www 21sin 27sin11 11111111 43 3212121 27272737 3434 3 3203031303130 3 3jjjj jjjjjj jjjjjjjjj n jn njn njn njn njn njn nj n njn njj eeee
7、 eeeeee eeeeeeeee eeeeeee eenneX 目的:找出連續(xù)信號(hào)與離散信號(hào)各種變換的關(guān)系變換關(guān)系的紐帶:沖激抽樣信號(hào) 溝通連續(xù)和離散信號(hào)的橋梁 1.沖激抽樣信號(hào)的拉氏變換Xs(s)與連續(xù)信號(hào)的拉氏變換Xa(s)之間關(guān)系：拉氏變換的指數(shù)形式為周期為T的周期沖激信號(hào)傅氏級(jí)數(shù)的表達(dá)式(周期延拓)為見(jiàn)例2.12的證明 為采樣角頻率，則沖激抽樣信號(hào)可表示為可導(dǎo)出沖激抽樣信號(hào)拉氏變換的另一種形式 由此，可得到?jīng)_激抽樣信號(hào)的拉氏變換有指數(shù)級(jí)數(shù)與周期延拓表示的兩種等價(jià)表達(dá)式。即() ( )( )= = W= =m san snTas jmsXT enTxsX1 (4.14 ) 2沖激抽樣信
8、號(hào)的拉氏變換Xs(s)與抽樣序列的z變換X(z)之間關(guān)系z(mì)與s變量之間的映射關(guān)系z(mì)=esT，若離散時(shí)間信號(hào)為抽樣序列，即x (nT)=x(n)，并引入z=esT時(shí)，得到序列z變換為上式表示，z變換可以看成沖激抽樣信號(hào)的拉氏變換由s平面映射到z平面的變換。 3沖激抽樣信號(hào)的拉氏變換Xs(s)與其傅氏變換Xs(j)之間的關(guān)系為由s=+j，若=0，而且拉氏變換收斂域包含虛軸時(shí)，則虛軸上的拉氏變換即為其傅氏變換，或者說(shuō)，沖激抽樣信號(hào)的傅里葉變換是其在虛軸上的拉氏變換。 4沖激抽樣信號(hào)的傅氏變換Xs(j)與連續(xù)時(shí)間信號(hào)的傅氏變換Xa(j)之間：沖激抽樣信號(hào)傅氏變換的指數(shù)級(jí)數(shù)的形式，以及連續(xù)時(shí)間信號(hào)的傅里
9、葉變換Xa(j)的周期延拓形式，對(duì)沖激抽樣信號(hào)而言是等價(jià)的，表示為 5激抽樣信號(hào)傅氏變換的指數(shù)形式與序列的傅里葉變換表達(dá)式：兩相比較，若序列為抽樣序列，有：x(n) = xa(nT)，而且數(shù)字角頻率與模擬角頻率，滿足 = T，則相應(yīng)頻率點(diǎn)上的頻譜值相等。 6序列z變換X(z)與序列傅里葉變換X(ej)之間：序列的傅里葉變換X(ej)為X(z)在單位圓上的特例。 把上述分析的結(jié)論，用圖來(lái)形象地描繪如下：( ) () ( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) = W= W= =W= = = = =W=WW =W n jnjTn Tnjasm sa ezjs n
10、nez nTxnxn sTnasm sa enxeXenTxjXjmjXT znxzXenTxsXjmsXT jsTa www w11此圖非常清晰地表明了：沖激抽樣信號(hào)是溝通離散信號(hào)與連續(xù)信號(hào)各種變換的橋梁。 4.3.1 傅里葉變換在時(shí)域和頻域中的對(duì)稱規(guī)律一連續(xù)非周期信號(hào)，由前述，其傅里葉變換（頻譜）Xa()是非周期的連續(xù)譜，時(shí)域上的非周期對(duì)應(yīng)頻域上的連續(xù)，或頻域上的連續(xù)對(duì)應(yīng)時(shí)域上的非周期，由此可以得到時(shí)、頻域的第一個(gè)對(duì)稱規(guī)律：時(shí)域上的非周期將產(chǎn)生頻譜的連續(xù)，或者說(shuō)，頻域的連續(xù)導(dǎo)致時(shí)域的非周期總之一個(gè)域中函數(shù)的連續(xù)對(duì)應(yīng)另一個(gè)域的非周期。如下圖4.4（a）所示 圖4.4 信號(hào)在時(shí)、頻域中的對(duì)稱規(guī)
11、律 如圖4.4（b），一周期信號(hào)xp(t)，其頻譜是離散譜Xpk1)。可以從另一個(gè)角度來(lái)理解：Xp(k)正是對(duì)圖4.4（a）中的頻譜Xa()以采樣頻率1進(jìn)行抽樣，即頻域被離散化，則在時(shí)域上產(chǎn)生單周期信號(hào)xa(t)的周期延拓，延拓周期為T1=21，形成周期延拓波形xp(t).時(shí)、頻域的第二個(gè)對(duì)稱規(guī)律：時(shí)域上的周期化將產(chǎn)生頻譜的離散化，或者說(shuō)，頻域的離散化導(dǎo)致時(shí)域的周期化，總之，一個(gè)域的離散化對(duì)應(yīng)另一個(gè)域的周期化。 各種信號(hào)傅里葉變換在時(shí)域、頻域上對(duì)稱性的一規(guī)律可概括歸納為：1 在某一個(gè)域（時(shí)域或頻域）中是連續(xù)的，相應(yīng)地在另一個(gè)域（頻域或時(shí)域）中肯定是非周期性的。2 在某一個(gè)域（時(shí)域或頻域）中是離
12、散的，相應(yīng)地在另一個(gè)域（頻域或時(shí)域）中肯定是周期性的。上述規(guī)律是由傅里葉變換的對(duì)稱性（對(duì)偶性）所決定的。 4.3.2 離散傅里葉級(jí)數(shù)DFS對(duì)于連續(xù)周期函數(shù)x p (t)，有對(duì)x p (t)進(jìn)行抽樣，變成了離散時(shí)間周期信號(hào)x ps (nT) 或x p (n)（以抽樣序列x p (n)為例），周期序列在時(shí)域可用復(fù)指數(shù)序列形式的傅里葉級(jí)數(shù)來(lái)表示，將t = nT、 代入上式中，得( ) ( )kXkX pp =W1 從而有記作由于復(fù)指數(shù)序列的周期性，顯然有( ) ( )nn krNk = + 由上述分析可知：周期離散信號(hào)在時(shí)、頻域上均為周期序列，根據(jù)周期信號(hào)的特點(diǎn)，當(dāng)k變化一個(gè)N的整數(shù)倍時(shí)，得到的是完
13、全一樣的序列，所以，一個(gè)周期序列可以表示成一個(gè)有限項(xiàng)（N項(xiàng)）指數(shù)序列分量的疊加（即用任一個(gè)周期的序列情況，可以描述、代表所有其他周期序列的情況），則 習(xí)慣上表示為上式就是離散傅里葉級(jí)數(shù)（DFS）的定義式，是反變換的概念。根據(jù)反變換的表達(dá)式來(lái)導(dǎo)出正變換Xp(k)的解析表達(dá)式( ) ( )= 10 21 Nk knNjpp ekXNnx p( ) ( ) = = 10 2Nn knNjpp enxkX p 傅里葉級(jí)數(shù)的正變換以符號(hào)DFS 表示，離散傅里葉級(jí)數(shù)的反變換，符號(hào)IDFS 表示，寫(xiě)成為表達(dá)簡(jiǎn)潔,引入符號(hào)( ) ( ) ( )( ) ( ) ( ) = = = 10 210 21 Nk kn
14、Njppp Nn knNjppp ekXNkXIDFSnx enxnxDFSkX ppNjN eW p2= DFT要解決兩個(gè)問(wèn)題：一是離散與量化，二是快速運(yùn)算。 一.DFT是重要的變換1.分析有限長(zhǎng)序列的有用工具。2.在信號(hào)處理的理論上有重要意義。3.在運(yùn)算方法上起核心作用，譜分析、卷積、相關(guān)都可以通DFT在計(jì)算機(jī)上實(shí)現(xiàn)。 4.4.1 離散傅里葉變換DFT定義式 對(duì)于一個(gè)周期為N的周期序列xp(n)，把它的第一個(gè)周期的有限長(zhǎng)序列定義為這一周期序列的主值序列，用x(n)表示( ) ( ) = += rp rNnxnx 周期序列X p (k)、x p (n)換成主值序列X (k)、x (n)，這樣
15、就得到了兩個(gè)有限長(zhǎng)序列的變換對(duì)，并表示為式（4.35）稱為離散傅里葉正變換，以符號(hào)DFT 表示，式（4.36）是離散傅里葉反變換，以符號(hào)IDFT 表示( ) ( ) ( )( ) ( ) ( ) )36.4(10,1 )35.4(10,1010 = = = = NnWkXNkXIDFTnx NkWnxnxDFTkX Nk knNNn knN DFT ， IDFT 可簡(jiǎn)寫(xiě)為:式中，X (k)與x (n)分別為N 行的列矩陣，而Wnk 與W-nk分別為N N 的對(duì)稱方陣。例4.2 用矩陣形式求矩形序列x(n)=R4(n)的DFT，再由所得X(k)經(jīng)IDFT求x(n)，驗(yàn)證所求結(jié)果的正確性。 4.4
16、.2 離散傅里葉變換DFT與序列傅里葉變換的關(guān)系設(shè)一有限長(zhǎng)序列x (n)長(zhǎng)度為N點(diǎn)，其z變換為因序列為有限長(zhǎng)，滿足絕對(duì)可和的條件，其z變換的收斂域?yàn)檎麄€(gè)z平面，必定包含單位圓，則序列的傅里葉變換為 現(xiàn)以 為間隔，把單位圓（表示為ej）均勻等分為N個(gè)點(diǎn)，則在第k個(gè)等分點(diǎn)由上式可以得出：有限長(zhǎng)序列的DFT就是序列在單位圓上的z變換（即序列傅里葉變換）在單位圓上以為間隔 的抽樣值，參見(jiàn)下圖。Npw 21 = Npw 2 1 = DFT與 序 列 傅 里 葉 變 換 對(duì) 比 1線性特性若: X(k) = DFTx(n) ,Y(k) = DFTy(n) 則DFTax(n)+by(n) = aX(k) +
17、 bY(k)式中，a、b為任意常數(shù)。如果兩個(gè)序列的長(zhǎng)度不相等，以最長(zhǎng)的序列為基準(zhǔn)，對(duì)短序列要補(bǔ)零，使序列長(zhǎng)度相等，才能進(jìn)行線性相加，經(jīng)過(guò)補(bǔ)零的序列頻譜會(huì)變密，但不影響問(wèn)題的性質(zhì)。 2 .時(shí)移特性（1）圓周移位圓周移位也叫循環(huán)移位，簡(jiǎn)稱圓移位。它是序列的這樣一種移位：將一有限長(zhǎng)序列x (n)，進(jìn)行周期延拓，周期為N，構(gòu)成周期序列x p (n) ，然后對(duì)周期序列x p (n)作m位移位處理得移位序列x p(n-m)，再取其主值序列（x p(n-m)與一矩形序列RN (n)相乘），得x p (n-m)R N (n)，就是所謂的圓周移位序列。 2.圓周位移的含義由于我們?nèi)≈髦敌蛄?，即只觀察n=0到N-
18、1這一主值區(qū)間，當(dāng)某一抽樣從此區(qū)間一端移出時(shí)，與它相同值的抽樣又從此區(qū)間的另一端進(jìn)來(lái)。如果把x(n)排列一個(gè)N等分的圓周上，序列的移位就相當(dāng)于x(n)在圓上旋轉(zhuǎn)，故稱作圓周移位。當(dāng)圍著圓周觀察幾圈時(shí)，看到就是周期序列: x(n) 。 （2）時(shí)移定理所謂時(shí)移定理是指：若DFT x (n) = X (k)則DFT xp(n-m)RN(n) =時(shí)移定理表明：序列在時(shí)域上圓周移位，頻域上將產(chǎn)生附加相移。( )kXWmkN 3 頻 移 特 性若 DFT x (n) = X (k)則并上 述 特 性 表 明 ： 若 序 列 在 時(shí) 域 上 乘 以 復(fù) 指 數(shù)序 列 ， 則 在 頻 域 上 ， X (k)將
19、 圓周 移 位 l 位 ， 這 可 以 看 作 調(diào) 制 信 號(hào) 的 頻 譜 搬 移 ，因 而 又 稱 “ 調(diào) 制 定 理 ” 。( ) ( ) ( )kRlkXWnxDFT NplnN =( ) ( ) ( ) lnNNp WnxkRlkXIDFT = lnNjlnN eW p2= 4. 5 離散傅里葉變換的性質(zhì)4圓周卷積特性（1）時(shí)域圓周卷積若對(duì)N點(diǎn)的序列有X (k) DFT x (n) , H (k) DFT h (n) , Y (k) DFT y (n) ，Y (k) = X (k) H (k) 則 若x (m)保持不移位，則 正是圓周 移位，故稱 為圓周卷積。即( ) ( ) ( )
20、( ) ( ) = = 10Nm Np nRmnhmxkYIDFTny ( ) ( )nRmnh Np ( ) ( ) ( )= 10Nm Np nRmnhmx( ) ( ) ( ) ( ) ( ) ( ) = = 10Nm Np nRmnhmxnhnxny （2）頻域圓卷積若： y (n) = x (n) h (n)則：( ) ( ) ( ) ( ) ( ) = = 101 Nl Np kRlkHlXNnyDFTkY DFT變換的性質(zhì)( ) ( ) ( ) ( ) ( ) ( )( ) = = 1111 NmNm mnymxmnymxkYkXIDFT 反 褶 循 環(huán) 移 位 相 乘 相 加也
21、 是 一 種 卷 積 ! 為 了 突 出 新 “ 卷 積 ” 與 “ 舊 ” 卷 積 的 不 同 , 同時(shí) 也 為 了 突 出 它 們 之 間 的 相 同 , 稱 過(guò) 去 傳 統(tǒng) 的 卷 積 為 線 卷 積 ,而 稱 此 “ 新 卷 積 ” 為 序 列 的 圓 周 卷 積 ， 簡(jiǎn) 稱 圓 卷 積 。( ) ( ) ( ) ( )= = 10Nm mnymxnynx頻 域 卷 積 ( ) ( ) ( ) ( )kYkXNnynxDFT = 1 編 程 實(shí) 現(xiàn) 容 易 4. 5 離散傅里葉變換的性質(zhì)5奇偶性（1）實(shí)數(shù)序列設(shè)x (n)為實(shí)序列，X (k) DFT x (n) ，則可知：X (k)的實(shí)
22、部為k的偶函數(shù)，X (k)的虛部是k的奇函數(shù)。( ) ( )( ) ( )( ) ( ) kjXkX nkNnxjnkNnx enxkX IR NnNn Nn nkNj+= = = = = 1010 10 2 2sin2cos pp p 4. 5 離散傅里葉變換的性質(zhì)X (k)的幅度和相位分別為設(shè)x (n)是實(shí)序列，其DFT可寫(xiě)成( ) ( ) ( )( ) ( )( )kX kXkX kXkXkX RIIRarctanarg 22= +=( ) ( ) ( )( ) ( ) ( )( ) ( )53.4 101010 kNX WnNxWnx Wnx nxDFTkX Nn nNkNNn nkN
23、Nn nkN= = = = = = 4. 5 離散傅里葉變換的性質(zhì)從而有由上述式子表明：實(shí)數(shù)序列x (n)的離散傅里葉變換X (k)，在0至N的范圍內(nèi)，對(duì)于N/2點(diǎn)，| X (k) | 呈半周期偶對(duì)稱分布，arg X (k) 呈半周期奇對(duì)稱分布。但由于長(zhǎng)度為N的X (k)有值區(qū)間是0 （N-1），而在式（4.53）中增加了第N點(diǎn)的數(shù)值，因此所謂的對(duì)稱性并不是很嚴(yán)格。( ) ( ) ( )( ) ( ) ( ) ( )( )55.454.4argargarg = = kNXkNXkX kNXkNXkX 4. 5 離散傅里葉變換的性質(zhì)（2）復(fù)數(shù)序列對(duì)于共軛復(fù)數(shù)序列。若有限長(zhǎng)序列x * (n)是x
24、(n)的共軛復(fù)數(shù)序列，并設(shè)( ) ( ) ( )( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( ) = += = += nxnxnx nxnxnx njxnxnx njxnxnx IR IR IR2121 4. 5 離散傅里葉變換的性質(zhì)則利用式（4.57）、（4.58）可以計(jì)算出一個(gè)N點(diǎn)復(fù)序列DFT的同時(shí)，計(jì)算出兩個(gè)N點(diǎn)實(shí)序列的DFT。( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( )59.458.421 57.421kXkXkX kNXkXkxDFTkX kNXkXkxDFTkX IR II RR += = += 4.
25、 5 離散傅里葉變換的性質(zhì)6 帕斯瓦爾定理若X (k) DFT x (n) 則上式左端代表離散信號(hào)在時(shí)域中的能量，右端是代表在頻域中的能量，表明變換過(guò)程中能量是守恒的。( ) ( ) = = 10 210 2 1 NkNn kXNnx 計(jì)算DFT的快速算法- FFT( ) ( ) ( )1,1,0,10 -=-= NkWnxnxDFT Nn nkN L計(jì) 算 DFT的 計(jì) 算 量 ：每 算 一 個(gè) X(k)， 需 要 N次 復(fù) 數(shù) 乘 法 ， N-1次加 法 。 因 此 ， N點(diǎn) DFT需 要 N*N次 復(fù) 數(shù) 乘法 ， N(N-1)次 復(fù) 數(shù) 加 法 。直 接 計(jì) 算 DFT的 復(fù) 雜 度
26、為 O(N2)盡 管 預(yù) 先 算 好 并 保 存 旋 轉(zhuǎn) 因 子 W Nk 可 以 節(jié) 省 部分 運(yùn) 算 ， 但 按 定 義 求 DFT的 運(yùn) 算 量 仍 然 很 大 。 4.6 快速傅里葉變換（FFT）4.6.1 DFT直接運(yùn)算的問(wèn)題和改進(jìn)思路1DFT直接運(yùn)算的工作量直接對(duì)DFT進(jìn)行計(jì)算的基本問(wèn)題是運(yùn)算量大，很難實(shí)現(xiàn)信號(hào)的實(shí)時(shí)處理，如某序列x(n)，N 4， ，則序列x (n)的DFT為 NjN eW p2=( )( )( )( ) ( )( )( )( )= 32103210 9630 6420 3210 0000 xxxxWWWW WWWW WWWW WWWWXXXX 4.6 快速傅里葉
27、變換（FFT）若要求X (k)的N = 4個(gè)值，復(fù)數(shù)乘的次數(shù)： N2 = 42 =16，復(fù)數(shù)加的次數(shù)： N (N-1) 12，這樣簡(jiǎn)單的DFT計(jì)算，其計(jì)算量已經(jīng)不小。如果N = 210 = 1024，則復(fù)數(shù)乘的次數(shù)： N2 =1,048,576，復(fù)數(shù)加次數(shù)： N2 =1,048,576，難以實(shí)現(xiàn)信號(hào)的實(shí)時(shí)處理，若N大大增加，運(yùn)算量也會(huì)隨之大大增加，實(shí)時(shí)處理幾乎就變得不可能了，因此必須改進(jìn)DFT的算法。 4.6 快速傅里葉變換（FFT）2改進(jìn)思路DFT的定義式為（1） 的周期性（2） 的對(duì)稱性( ) ( ) ( )= 10Nn nkNWnxnxDFTkXnkNW ( ) ( ) ( )nmNk
28、NklNnNkNnNnkN WWWW + =nkNW 1222 = NNjNN eW p nkNNNnkNNnkN WWWW = + 22 將上述（1）、（2）中的結(jié)果，代入矩陣W，可以簡(jiǎn)化為（）矩陣W中，許多元素是相等的，可明顯減少計(jì)算量。（）由于運(yùn)算量正比于N 2 ，因此可以把大點(diǎn)數(shù)（大N）DFT的計(jì)算化為小點(diǎn)數(shù)（如N/2），又可進(jìn)一步地把DFT計(jì)算量大幅度減下來(lái)。綜合應(yīng)用上述的改進(jìn)思路，實(shí)現(xiàn)傅里葉變換的快速計(jì)算的算法，就是快速傅里葉變換，F(xiàn)FT（Fast Fourier Transform）。 = 1010 0000 1010 00009630 6420 3210 0000 WWWW W
29、WWW WWWW WWWWWWWW WWWW WWWW WWWW 特別說(shuō)明：FFT是DFT的快速算法，不是新的變換方法。其算法基礎(chǔ)是：W的兩個(gè)性質(zhì)。1. W具有周期性2. W具有對(duì)稱性( )nmNkNnkN WW += nkNNnkN WW = + 2 經(jīng) 過(guò) 周 期 性 與 對(duì) 稱 性 簡(jiǎn) 化 之 后 ,容易 發(fā) 現(xiàn) DFT運(yùn) 算 中 存 在 著 不 必 要的 重 復(fù) 計(jì) 算 ,避 免 這 種 重 復(fù) ,是 簡(jiǎn)化 運(yùn) 算 的 關(guān) 鍵 .N點(diǎn) DFT運(yùn) 算 可 以 分 解 為 兩 組 N/2點(diǎn) DFT運(yùn) 算 ， 然 后 再 取 和 。DFT的復(fù)雜度與點(diǎn)數(shù)N有關(guān)！ 4.6.2 基2按時(shí)間抽取的F
30、FT算法（時(shí)析型）1算法原理“基2”序列x (n)，設(shè)：N = 2 M （M為整數(shù)），如果N不是2的冪次，應(yīng)在序列后面補(bǔ)零到2 M ，這是“基2”的意思。隨后按照n的奇偶性以及時(shí)間的先后抽取序列值，把序列分成奇數(shù)序號(hào)與偶數(shù)序號(hào)兩組序列之和（大點(diǎn)數(shù)化為小點(diǎn)數(shù)），這也就是所謂的“按時(shí)間抽取”的基本含意。 ( ) ( ) ( )( )( ) ( )( )( ) ( )( ) ( )( ) ( ) 12,2,1,0122 122 122 12 0 212 0 2 12 0 212 0 2 nn = += += += += = = Nrrxrz rxry WrxWWrx WrxWWrx WnxWnxkX
31、 Nr rkNkNNr rkN Nr rkNkNNr rkN nkNnkN L奇 數(shù)偶 數(shù) 注 意 Y(k)與 Z(k)的 周 期 是 N/2 ! ( )( )kZkNZ kYkNY = + = +22 kNkNNNkNN WWWW = + 22于 是 ， N點(diǎn) X(k)可 用 N/2點(diǎn) 的 Y(k)和 Z(k)來(lái) 計(jì) 算 ：( ) ( ) ( )( ) ( ) 12,1,0 222 2= + += + += +Nk kZWkY kNZWkNYkNX kZWkYkX kN kNNkNL ( ) ( ) ( )kZWkYkX kN+= ( ) ( )kZWkYkNX kN= +28點(diǎn) DFT 4
32、點(diǎn) DFT（ 先 按 奇 偶 序 分 組 ， 再 求 4點(diǎn) DFT） 就 地 置 換 無(wú) 需 緩 存 一 個(gè) 蝶 形 單 元 只 需 一 次 復(fù) 數(shù)乘 法 和 兩 次 復(fù) 數(shù) 加 法 全 部 計(jì) 算 分 解 為 M級(jí) ， 或 稱 為 M次 迭 代 。 輸 入 序 列 x(n)按 碼 位 倒 讀 順 序 排 列 ， 輸 出 序 列 X(k)按 自 然 順 序 排 列 。 每 級(jí) 都 包 含 N/2個(gè) 蝶 形 單 元 。 每 級(jí) 的 若 干 蝶 形 單 元 組 成 “ 群 ” 。 第 1級(jí) 群 數(shù)為 N/2， 第 2級(jí) 群 數(shù) 為 N/4， 第 i級(jí) 群 數(shù) 為 N/2i，最 后 一 級(jí) 的 群
33、數(shù) 為 1。 每 個(gè) 蝶 形 單 元 都 包 含 乘 Wnk與 -Wnk的 運(yùn)算 （ 可 簡(jiǎn) 化 為 乘 Wnk與 加 、 減 法 各 一 次 ） 。 同 一 級(jí) 中 ， 各 個(gè) 群 的 W分 布 規(guī) 律 完 全 相 同 碼 位 倒 讀輸 入 序 列 x(n)的 排 列 次 序 不 符 合 自 然 順 序 。 此 現(xiàn)象 是 由 于 按 n的 奇 偶 分 組 進(jìn) 行 DFT運(yùn) 算 而 造 成 的 ，這 種 排 列 方 式 稱 為 “ 碼 位 倒 讀 ” 的 順 序 。所 謂 “ 倒 讀 ” ， 是 指 按 二 進(jìn) 制 表 示 的 數(shù)字 首 尾 位 置 顛 倒 ， 重 新 按 十 進(jìn) 制 讀 數(shù) 。 自然順序二進(jìn)制順序碼位倒置碼位倒讀順序0 000 000 01 001 100 42 010 010 23 011 110 64 100 001 15 101 101 56 110 011 37 111 111 7碼 位 倒 讀 示 例 （ N=8）
測(cè)試信號(hào)處理技術(shù)第四章
