測試信號處理技術(shù)第四章

《測試信號處理技術(shù)第四章》由會員分享，可在線閱讀，更多相關(guān)《測試信號處理技術(shù)第四章（89頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 離散時間信號分析內(nèi)容提要 序列的傅里葉變換（DTFT） 拉氏變換、傅氏變換與z變換之間的關(guān)系 離散傅里葉級數(shù)（DFS） 離散傅里葉變換（DFT） 快速傅里葉變換（FFT） 快速傅里葉變換的應(yīng)用 離散時間傅里葉變換DTFT與連續(xù)時間傅里葉變換的關(guān)系性質(zhì)離散傅里葉變換DFT定義性質(zhì)離散傅里葉變換的快速算法FFT原理流程應(yīng)用 實(shí)際信號的特點(diǎn)：時域：連續(xù)時間信號; 持續(xù)時間較長頻域：頻譜是連續(xù)的數(shù)字處理設(shè)備（計算機(jī)）的特點(diǎn)：存儲空間有限- 只能存儲有限多的數(shù)據(jù)離散的時間點(diǎn)有限長的時間范圍表示空間有限- 只能表示有限多的數(shù)值 取值在一定精度內(nèi)取值在一定范圍內(nèi) 在時域如何對信號進(jìn)行離散化？要求保證信號的

2、信息不受損！信息不受損= 可以恢復(fù)原信號理論問題已在第二章解決乘以沖激串信號，進(jìn)行時域抽樣要求抽樣過程滿足抽樣定理信號頻帶有限，抽樣頻率是信號最高頻率的兩倍矛盾1已基本解決 如何用抽樣信號的頻譜來恢復(fù)原信號的頻譜？抽樣信號頻譜與原信號頻譜是什么關(guān)系？理論上如何恢復(fù)？工程實(shí)踐上如何實(shí)現(xiàn)？ 抽樣信號的頻譜如何計算？得到抽樣信號后，如何計算其頻譜？輸入：抽樣信號（序列）輸出：抽樣信號的頻譜在工程上，計算機(jī)接受的輸入是一系列數(shù)值 信號被截短時，頻譜發(fā)生什么變化？有時信號持續(xù)時間超出處理能力時域信號需要被截斷截斷會不會影響對信號的分析？截斷對信號的頻譜有何影響？ 有限長離散信號頻譜的存儲與計算頻譜是連續(xù)

3、周期的1. 只能存儲有限長的頻譜一個周期即可2. 只能存儲有限多的頻譜離散頻率點(diǎn)處的頻譜值離散頻率點(diǎn)譜值的計算法一：先有連續(xù)譜，后有離散譜值（頻域采樣）法二：直接用時間抽樣值計算離散譜值（公式）？ 如何由頻譜恢復(fù)抽樣信號？離散頻譜值是有限的恢復(fù)抽樣信號的計算公式如何編程實(shí)現(xiàn)（如何進(jìn)行快速計算）？按定義實(shí)現(xiàn)- 計算量太大由離散信號計算離散頻譜由離散頻譜恢復(fù)離散信號 從工程需要出發(fā)，理解信號頻譜分析的實(shí)際問題。即在實(shí)踐中領(lǐng)悟處理原理的意義從解決問題出發(fā)，理解各種信號處理方法的目的。即在矛盾中思考工程實(shí)現(xiàn)的背景在解決的問題過程中感受知識的力量、體會學(xué)習(xí)的快樂 1.定義x (n)的z變換為如果X (z

4、)在單位圓上是收斂的，則把在單位圓上的z變換定義為序列的傅里葉變換，表示為(4.1) 相對應(yīng)序列的傅里葉反變換，由z反變換的圍線積分公式若把積分圍線C取在單位圓上，則有（4.2） 2物理意義把序列的傅里葉變換稱作非周期序列的頻譜，為什么把序列的傅里葉變換和序列的頻譜聯(lián)系在一起?可以與連續(xù)信號的傅里葉變換進(jìn)行對比進(jìn)行分析.已知連續(xù)信號的傅里葉變換為 F ()有頻譜密度的意義，是頻譜的概念，在式（4.1）中，X (ej)是序列的傅里葉變換，與F ()在連續(xù)信號傅里葉變換的表達(dá)式中一樣起著相同的作用，所以看作是序列的頻譜。f (t) 和x (n)的兩個表達(dá)式都具有疊加重構(gòu)（綜合）時域信號即傅里葉反變

5、換的作用，因此把式（4.2）稱為序列的傅里葉反變換。 將式（4.1）和（4.2）重寫并表示為(4.3)(4.4) 3特點(diǎn)由式(4.3)知，序列頻譜X (ej) 是ejn的函數(shù)，而ejn 是以2為周期的函數(shù)，并且由于序列在時域上是非周期的，因而，序列的頻譜是周期的連續(xù)頻譜。同時X (ej)是 的復(fù)函數(shù)，可進(jìn)一步表示為(4.5)( ) ( ) ( ) ( ) ( ) wwwjww jjjjj eXjeXeeXeX ImRe += 其幅度譜如圖4.1所示圖4.1 序列及其幅譜圖 序列傅立葉變換存在的條件由于序列的傅里葉變換是單位圓上的z變換，序列的z變換在單位圓上必須收斂是序列傅里葉變換存在的條件，

6、即上式表明，序列傅里葉變換存在的條件是：序列必須絕對可和。(充分條件)( ) =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ù)信號與離散信號各種變換的關(guān)系變換關(guān)系的紐帶:沖激抽樣信號 溝通連續(xù)和離散信號的橋梁 1.沖激抽樣信號的拉氏變換Xs(s)與連續(xù)信號的拉氏變換Xa(s)之間關(guān)系：拉氏變換的指數(shù)形式為周期為T的周期沖激信號傅氏級數(shù)的表達(dá)式(周期延拓)為見例2.12的證明 為采樣角頻率，則沖激抽樣信號可表示為可導(dǎo)出沖激抽樣信號拉氏變換的另一種形式 由此，可得到?jīng)_激抽樣信號的拉氏變換有指數(shù)級數(shù)與周期延拓表示的兩種等價表達(dá)式。即() ( )( )= = W= =m san snTas jmsXT enTxsX1 (4.14 ) 2沖激抽樣信

8、號的拉氏變換Xs(s)與抽樣序列的z變換X(z)之間關(guān)系z與s變量之間的映射關(guān)系z=esT，若離散時間信號為抽樣序列，即x (nT)=x(n)，并引入z=esT時，得到序列z變換為上式表示，z變換可以看成沖激抽樣信號的拉氏變換由s平面映射到z平面的變換。 3沖激抽樣信號的拉氏變換Xs(s)與其傅氏變換Xs(j)之間的關(guān)系為由s=+j，若=0，而且拉氏變換收斂域包含虛軸時，則虛軸上的拉氏變換即為其傅氏變換，或者說，沖激抽樣信號的傅里葉變換是其在虛軸上的拉氏變換。 4沖激抽樣信號的傅氏變換Xs(j)與連續(xù)時間信號的傅氏變換Xa(j)之間：沖激抽樣信號傅氏變換的指數(shù)級數(shù)的形式，以及連續(xù)時間信號的傅里

9、葉變換Xa(j)的周期延拓形式，對沖激抽樣信號而言是等價的，表示為 5激抽樣信號傅氏變換的指數(shù)形式與序列的傅里葉變換表達(dá)式：兩相比較，若序列為抽樣序列，有：x(n) = xa(nT)，而且數(shù)字角頻率與模擬角頻率，滿足 = T，則相應(yīng)頻率點(diǎn)上的頻譜值相等。 6序列z變換X(z)與序列傅里葉變換X(ej)之間：序列的傅里葉變換X(ej)為X(z)在單位圓上的特例。 把上述分析的結(jié)論，用圖來形象地描繪如下：( ) () ( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) = W= W= =W= = = = =W=WW =W n jnjTn Tnjasm sa ezjs n

10、nez nTxnxn sTnasm sa enxeXenTxjXjmjXT znxzXenTxsXjmsXT jsTa www w11此圖非常清晰地表明了：沖激抽樣信號是溝通離散信號與連續(xù)信號各種變換的橋梁。 4.3.1 傅里葉變換在時域和頻域中的對稱規(guī)律一連續(xù)非周期信號，由前述，其傅里葉變換（頻譜）Xa()是非周期的連續(xù)譜，時域上的非周期對應(yīng)頻域上的連續(xù)，或頻域上的連續(xù)對應(yīng)時域上的非周期，由此可以得到時、頻域的第一個對稱規(guī)律：時域上的非周期將產(chǎn)生頻譜的連續(xù)，或者說，頻域的連續(xù)導(dǎo)致時域的非周期總之一個域中函數(shù)的連續(xù)對應(yīng)另一個域的非周期。如下圖4.4（a）所示 圖4.4 信號在時、頻域中的對稱規(guī)

11、律 如圖4.4（b），一周期信號xp(t)，其頻譜是離散譜Xpk1)?？梢詮牧硪粋€角度來理解：Xp(k)正是對圖4.4（a）中的頻譜Xa()以采樣頻率1進(jìn)行抽樣，即頻域被離散化，則在時域上產(chǎn)生單周期信號xa(t)的周期延拓，延拓周期為T1=21，形成周期延拓波形xp(t).時、頻域的第二個對稱規(guī)律：時域上的周期化將產(chǎn)生頻譜的離散化，或者說，頻域的離散化導(dǎo)致時域的周期化，總之，一個域的離散化對應(yīng)另一個域的周期化。 各種信號傅里葉變換在時域、頻域上對稱性的一規(guī)律可概括歸納為：1 在某一個域（時域或頻域）中是連續(xù)的，相應(yīng)地在另一個域（頻域或時域）中肯定是非周期性的。2 在某一個域（時域或頻域）中是離

12、散的，相應(yīng)地在另一個域（頻域或時域）中肯定是周期性的。上述規(guī)律是由傅里葉變換的對稱性（對偶性）所決定的。 4.3.2 離散傅里葉級數(shù)DFS對于連續(xù)周期函數(shù)x p (t)，有對x p (t)進(jìn)行抽樣，變成了離散時間周期信號x ps (nT) 或x p (n)（以抽樣序列x p (n)為例），周期序列在時域可用復(fù)指數(shù)序列形式的傅里葉級數(shù)來表示，將t = nT、 代入上式中，得( ) ( )kXkX pp =W1 從而有記作由于復(fù)指數(shù)序列的周期性，顯然有( ) ( )nn krNk = + 由上述分析可知：周期離散信號在時、頻域上均為周期序列，根據(jù)周期信號的特點(diǎn)，當(dāng)k變化一個N的整數(shù)倍時，得到的是完

13、全一樣的序列，所以，一個周期序列可以表示成一個有限項(xiàng)（N項(xiàng)）指數(shù)序列分量的疊加（即用任一個周期的序列情況，可以描述、代表所有其他周期序列的情況），則 習(xí)慣上表示為上式就是離散傅里葉級數(shù)（DFS）的定義式，是反變換的概念。根據(jù)反變換的表達(dá)式來導(dǎo)出正變換Xp(k)的解析表達(dá)式( ) ( )= 10 21 Nk knNjpp ekXNnx p( ) ( ) = = 10 2Nn knNjpp enxkX p 傅里葉級數(shù)的正變換以符號DFS 表示，離散傅里葉級數(shù)的反變換，符號IDFS 表示，寫成為表達(dá)簡潔,引入符號( ) ( ) ( )( ) ( ) ( ) = = = 10 210 21 Nk kn

14、Njppp Nn knNjppp ekXNkXIDFSnx enxnxDFSkX ppNjN eW p2= DFT要解決兩個問題：一是離散與量化，二是快速運(yùn)算。 一.DFT是重要的變換1.分析有限長序列的有用工具。2.在信號處理的理論上有重要意義。3.在運(yùn)算方法上起核心作用，譜分析、卷積、相關(guān)都可以通DFT在計算機(jī)上實(shí)現(xiàn)。 4.4.1 離散傅里葉變換DFT定義式 對于一個周期為N的周期序列xp(n)，把它的第一個周期的有限長序列定義為這一周期序列的主值序列，用x(n)表示( ) ( ) = += rp rNnxnx 周期序列X p (k)、x p (n)換成主值序列X (k)、x (n)，這樣

15、就得到了兩個有限長序列的變換對，并表示為式（4.35）稱為離散傅里葉正變換，以符號DFT 表示，式（4.36）是離散傅里葉反變換，以符號IDFT 表示( ) ( ) ( )( ) ( ) ( ) )36.4(10,1 )35.4(10,1010 = = = = NnWkXNkXIDFTnx NkWnxnxDFTkX Nk knNNn knN DFT ， IDFT 可簡寫為:式中，X (k)與x (n)分別為N 行的列矩陣，而Wnk 與W-nk分別為N N 的對稱方陣。例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è)一有限長序列x (n)長度為N點(diǎn)，其z變換為因序列為有限長，滿足絕對可和的條件，其z變換的收斂域?yàn)檎麄€z平面，必定包含單位圓，則序列的傅里葉變換為 現(xiàn)以 為間隔，把單位圓（表示為ej）均勻等分為N個點(diǎn)，則在第k個等分點(diǎn)由上式可以得出：有限長序列的DFT就是序列在單位圓上的z變換（即序列傅里葉變換）在單位圓上以為間隔 的抽樣值，參見下圖。Npw 21 = Npw 2 1 = DFT與 序 列 傅 里 葉 變 換 對 比 1線性特性若: X(k) = DFTx(n) ,Y(k) = DFTy(n) 則DFTax(n)+by(n) = aX(k) +

17、 bY(k)式中，a、b為任意常數(shù)。如果兩個序列的長度不相等，以最長的序列為基準(zhǔn)，對短序列要補(bǔ)零，使序列長度相等，才能進(jìn)行線性相加，經(jīng)過補(bǔ)零的序列頻譜會變密，但不影響問題的性質(zhì)。 2 .時移特性（1）圓周移位圓周移位也叫循環(huán)移位，簡稱圓移位。它是序列的這樣一種移位：將一有限長序列x (n)，進(jìn)行周期延拓，周期為N，構(gòu)成周期序列x p (n) ，然后對周期序列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ū)間一端移出時，與它相同值的抽樣又從此區(qū)間的另一端進(jìn)來。如果把x(n)排列一個N等分的圓周上，序列的移位就相當(dāng)于x(n)在圓上旋轉(zhuǎn)，故稱作圓周移位。當(dāng)圍著圓周觀察幾圈時，看到就是周期序列: x(n) 。 （2）時移定理所謂時移定理是指：若DFT x (n) = X (k)則DFT xp(n-m)RN(n) =時移定理表明：序列在時域上圓周移位，頻域上將產(chǎn)生附加相移。( )kXWmkN 3 頻 移 特 性若 DFT x (n) = X (k)則并上 述 特 性 表 明 ： 若 序 列 在 時 域 上 乘 以 復(fù) 指 數(shù)序 列 ， 則 在 頻 域 上 ， X (k)將

19、 圓周 移 位 l 位 ， 這 可 以 看 作 調(diào) 制 信 號 的 頻 譜 搬 移 ，因 而 又 稱 “ 調(diào) 制 定 理 ” 。( ) ( ) ( )kRlkXWnxDFT NplnN =( ) ( ) ( ) lnNNp WnxkRlkXIDFT = lnNjlnN eW p2= 4. 5 離散傅里葉變換的性質(zhì)4圓周卷積特性（1）時域圓周卷積若對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、 是 一 種 卷 積 ! 為 了 突 出 新 “ 卷 積 ” 與 “ 舊 ” 卷 積 的 不 同 , 同時 也 為 了 突 出 它 們 之 間 的 相 同 , 稱 過 去 傳 統(tǒng) 的 卷 積 為 線 卷 積 ,而 稱 此 “ 新 卷 積 ” 為 序 列 的 圓 周 卷 積 ， 簡 稱 圓 卷 積 。( ) ( ) ( ) ( )= = 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可寫成( ) ( ) ( )( ) ( )( )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)，對于N/2點(diǎn)，| X (k) | 呈半周期偶對稱分布，arg X (k) 呈半周期奇對稱分布。但由于長度為N的X (k)有值區(qū)間是0 （N-1），而在式（4.53）中增加了第N點(diǎn)的數(shù)值，因此所謂的對稱性并不是很嚴(yán)格。( ) ( ) ( )( ) ( ) ( ) ( )( )55.454.4argargarg = = kNXkNXkX kNXkNXkX 4. 5 離散傅里葉變換的性質(zhì)（2）復(fù)數(shù)序列對于共軛復(fù)數(shù)序列。若有限長序列x * (n)是x

24、(n)的共軛復(fù)數(shù)序列，并設(shè)( ) ( ) ( )( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( ) = += = += nxnxnx nxnxnx njxnxnx njxnxnx IR IR IR2121 4. 5 離散傅里葉變換的性質(zhì)則利用式（4.57）、（4.58）可以計算出一個N點(diǎn)復(fù)序列DFT的同時，計算出兩個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) 則上式左端代表離散信號在時域中的能量，右端是代表在頻域中的能量，表明變換過程中能量是守恒的。( ) ( ) = = 10 210 2 1 NkNn kXNnx 計算DFT的快速算法- FFT( ) ( ) ( )1,1,0,10 -=-= NkWnxnxDFT Nn nkN L計 算 DFT的 計 算 量 ：每 算 一 個 X(k)， 需 要 N次 復(fù) 數(shù) 乘 法 ， N-1次加 法 。 因 此 ， N點(diǎn) DFT需 要 N*N次 復(fù) 數(shù) 乘法 ， N(N-1)次 復(fù) 數(shù) 加 法 。直 接 計 算 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)算的問題和改進(jìn)思路1DFT直接運(yùn)算的工作量直接對DFT進(jìn)行計算的基本問題是運(yùn)算量大，很難實(shí)現(xiàn)信號的實(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個值，復(fù)數(shù)乘的次數(shù)： N2 = 42 =16，復(fù)數(shù)加的次數(shù)： N (N-1) 12，這樣簡單的DFT計算，其計算量已經(jīng)不小。如果N = 210 = 1024，則復(fù)數(shù)乘的次數(shù)： N2 =1,048,576，復(fù)數(shù)加次數(shù)： N2 =1,048,576，難以實(shí)現(xiàn)信號的實(shí)時處理，若N大大增加，運(yùn)算量也會隨之大大增加，實(shí)時處理幾乎就變得不可能了，因此必須改進(jìn)DFT的算法。 4.6 快速傅里葉變換（FFT）2改進(jìn)思路DFT的定義式為（1） 的周期性（2） 的對稱性( ) ( ) ( )= 10Nn nkNWnxnxDFTkXnkNW ( ) ( ) ( )nmNk

28、NklNnNkNnNnkN WWWW + =nkNW 1222 = NNjNN eW p nkNNNnkNNnkN WWWW = + 22 將上述（1）、（2）中的結(jié)果，代入矩陣W，可以簡化為（）矩陣W中，許多元素是相等的，可明顯減少計算量。（）由于運(yùn)算量正比于N 2 ，因此可以把大點(diǎn)數(shù)（大N）DFT的計算化為小點(diǎn)數(shù)（如N/2），又可進(jìn)一步地把DFT計算量大幅度減下來。綜合應(yīng)用上述的改進(jìn)思路，實(shí)現(xiàn)傅里葉變換的快速計算的算法，就是快速傅里葉變換，F(xiàn)FT（Fast Fourier Transform）。 = 1010 0000 1010 00009630 6420 3210 0000 WWWW W

29、WWW WWWW WWWWWWWW WWWW WWWW WWWW 特別說明：FFT是DFT的快速算法，不是新的變換方法。其算法基礎(chǔ)是：W的兩個性質(zhì)。1. W具有周期性2. W具有對稱性( )nmNkNnkN WW += nkNNnkN WW = + 2 經(jīng) 過 周 期 性 與 對 稱 性 簡 化 之 后 ,容易 發(fā) 現(xiàn) DFT運(yùn) 算 中 存 在 著 不 必 要的 重 復(fù) 計 算 ,避 免 這 種 重 復(fù) ,是 簡化 運(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按時間抽取的F

30、FT算法（時析型）1算法原理“基2”序列x (n)，設(shè)：N = 2 M （M為整數(shù)），如果N不是2的冪次，應(yīng)在序列后面補(bǔ)零到2 M ，這是“基2”的意思。隨后按照n的奇偶性以及時間的先后抽取序列值，把序列分成奇數(shù)序號與偶數(shù)序號兩組序列之和（大點(diǎn)數(shù)化為小點(diǎn)數(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)來 計 算 ：( ) ( ) ( )( ) ( ) 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） 就 地 置 換 無 需 緩 存 一 個 蝶 形 單 元 只 需 一 次 復(fù) 數(shù)乘 法 和 兩 次 復(fù) 數(shù) 加 法 全 部 計 算 分 解 為 M級 ， 或 稱 為 M次 迭 代 。 輸 入 序 列 x(n)按 碼 位 倒 讀 順 序 排 列 ， 輸 出 序 列 X(k)按 自 然 順 序 排 列 。 每 級 都 包 含 N/2個 蝶 形 單 元 。 每 級 的 若 干 蝶 形 單 元 組 成 “ 群 ” 。 第 1級 群 數(shù)為 N/2， 第 2級 群 數(shù) 為 N/4， 第 i級 群 數(shù) 為 N/2i，最 后 一 級 的 群

33、數(shù) 為 1。 每 個 蝶 形 單 元 都 包 含 乘 Wnk與 -Wnk的 運(yùn)算 （ 可 簡 化 為 乘 Wnk與 加 、 減 法 各 一 次 ） 。 同 一 級 中 ， 各 個 群 的 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）