第七講 DFT——FFT

1、 第1章 離散時(shí)間信號(hào)、系統(tǒng)和z變換 第2章 DFT及其快速算法 第3章數(shù)字濾波器設(shè)計(jì) 第4章 離散隨機(jī)信號(hào)的處理目 錄第2章 DFT及其快速算法 2-1 周期序列 2-2 離散傅立葉級(jí)數(shù) 2-3 離散傅立葉變換 2-4 頻率采樣理論 2-5 快速傅立葉變換 2-6 離散傅立葉反變換（IDFT) 的運(yùn)算意義：頻域內(nèi)離散化-快速算法（FFT）-易于計(jì)算機(jī)實(shí)現(xiàn)2-1 2-1 周期序列周期序列為整數(shù)，應(yīng)滿足對(duì)于所有的周期序列一個(gè)周期為mmNnxnxnx)()(n),(N定義：主值區(qū)間、主值序列為主值序列個(gè)樣本為主值區(qū)間，義個(gè)樣本值是獨(dú)立的，定，有周期序列)(N) 1(0N)(nxNnx1N0)(nx

2、n主值區(qū)間主值序列)(nx)()()(nRnxnxN周期序列)(nxrrNnxnx)()(間的余數(shù)?。ǎ? 1, 0)/()()()(NNnnnxnxNN若n=mN+n1 ，稱n與n1同余。周期延拓 例：設(shè)x(n)如圖所示，求，即N=44)(nx0312)(nxn4)(nxn03123123121 23 5 4 3 2 1 0 1 2 3 4 5 6 nNn)(Nnx)( 0 3 2 1 0 3 2 1 0 3 2 1 3 0 1 2 3 01 231 200312)(nxn4)(nxn03123123121 2 3混疊失真n03123121 2 3)n(R)n(x)n(x)n(x)n(x,M

3、)n( xNNNNN長(zhǎng)度為設(shè))n( x)n(xMNN時(shí)，2)n(x1NnNM)n( x1NMn0)n( x)n(x2NMNN時(shí)，1M 補(bǔ)充 ： 傅里葉變換的四種基本形式1連續(xù)時(shí)間與連續(xù)頻率 連續(xù)傅里葉變換)(txat0f)( fXa0f2dfefXtxftjaa2)(21)(dtetxfXftjaa2)()(2離散時(shí)間與連續(xù)頻率 序列傅里葉變換 )(nTxan0)(nxTt1( )()2jj nx nX eednnjjenxeX)()()(jeX0TT/22周期性4離散時(shí)間與離散頻率 離散傅里葉級(jí)數(shù)0)(nxntf0)(kX時(shí)域、頻域都是周期性的3連續(xù)時(shí)間與離散頻率 傅里葉級(jí)數(shù))(txpt01

4、Tf0)(1kfX)(1kXktkfjpekfXtx121)()(dtetxTkfXTtkfjp110211)(1)(周期性第一個(gè)域離散函數(shù)第二個(gè)域周期函數(shù)連續(xù)函數(shù)非周期函數(shù)且易證： 一個(gè)域中的周期函數(shù)的周期 離散間隔另一個(gè)域中離散函數(shù)的)2( 12-2. 離散傅里葉級(jí)數(shù)（離散傅里葉級(jí)數(shù)（DFS） 1從序列傅里葉變換導(dǎo)出 DFS )(jeX為 的連續(xù)的周期的函數(shù)，周期為2 。對(duì) )(jeX離散化，離散間隔 N2，即令 kNjeXkX2)()(整數(shù)k頻域的離散化 時(shí)域的周期化 將導(dǎo)致離散間隔 N2周期點(diǎn)數(shù) 122NNNkNjeXkX2)()(210( )Njk nNnx n e ( )DFS x

5、 n在 deeXnxnjj)(21)(的表達(dá)式， )()(kXeXjkN2Nd210Nk)()(nxnx21012( )( )2NjknNkx nX k eN2101( )NjknNkX k eN( )IDFS X kDFS 變換對(duì) 10 ( )( )( )NnkNnDFS x nx n WX k101( )( )( )NnkNkIDFS X kX k Wx nN1. 線性2. 移位)()()()(nxWlkXIDFSkXWmnxDFSnlNmkNknjknNNeW22-1 2-1 周期序列周期序列性質(zhì)：)()(NnkNnNkNknNWWW周期性：共軛奇對(duì)稱共軛偶對(duì)稱)()()()(*nxnx

6、nxnx)()(*nNkNnkNNknNknNWWWW）（對(duì)稱性：nrrNnNWNkknN其他為整數(shù)正交性：,010是一個(gè)周期復(fù)序列因子：knjknNNeWDFT23周期序列的周期卷積 兩個(gè)周期為N 的周期序列進(jìn)行卷積 12( )( )x nx n（1）周期卷積 102121)()()()(Nmmnxmxnxnx兩個(gè)N 點(diǎn)的周期序列進(jìn)行周期卷積，其結(jié)果仍為周期為N 的周期序列。 12( )()mx m x nm（2）卷積定理 )()()(21nxnxny)()()(21kXkXkYNNNDFSDFS DFSNNN12( )( )( )y nx nxn121( )( )( )Y kX kXkNN

7、NNDFSDFS DFSNNN例DFTn)(1nx211023n)(2nx11023mm)(1mx)(2mxm11023)(2mx 04n)()(21nxnxm1102 3)1 (2mx152 354m11023)4(2mx102121)()()()(Nmmnxmxnxnx周期均為N1 DFT 的定義 用計(jì)算機(jī)進(jìn)行傅里葉變換運(yùn)算時(shí)，要求 （1）時(shí)、頻域均為離散的； （2）時(shí)、頻域的點(diǎn)數(shù)均為有限的。 在離散傅里葉級(jí)數(shù)中，由于其時(shí)域及頻域均為周期序列，在整個(gè)域中都存在非零的序列值。但同時(shí)可注意到，其時(shí)域與頻域之間的映射關(guān)系在一個(gè)周期內(nèi)便可以完全地反映出來。2-3. 離散傅里葉變換（離散傅里葉變換（

8、DFT）)(kX1N主值序列)(nx主值序列)(kX1NDFT變換對(duì)DFS變換對(duì)0)(nxnk0)()(kXnxDFT)()(10kRWnxNNnnkN)()(nxkXIDFT)()(110nRWkXNNNknkNDFT變換對(duì) DFT是一種數(shù)學(xué)上的映射關(guān)系，反映了時(shí)域上的 N點(diǎn)與頻域上的 N 點(diǎn)之間的對(duì)應(yīng)關(guān)系2jNNWe的關(guān)系與問的序列加長(zhǎng)補(bǔ)零為長(zhǎng)度為把點(diǎn)點(diǎn)例：)()(1100)()()()()()(kXkYrNnNNnnxnynyrNnxkXNnxN注意長(zhǎng)度N)rk(X)k(Y2 DFT與 DFS （1） DFT與DFS的關(guān)系 時(shí)域頻域DFTDFSx(n)有限長(zhǎng)序列(N) = )()(nRn

9、xN周期序列 )(nx取主值區(qū)間 X(k)有限長(zhǎng)序列(N) = )()(kRkXN周期序列 )(kX取主值區(qū)間 )(nx周期序列(N) = Nnx)(有限長(zhǎng)序列x(n)的周期延拓)(kX周期序列(N) = NkX)(有限長(zhǎng)序列X(k)的周期延拓2.3.4 DFT與Z變換 （1） DFT與Z變換的關(guān)系 對(duì)于有限長(zhǎng)序列x(n)（0nN1 ） 10)()(NnnznxzX10( )( )( )NnkNNnX kx n WRk顯然， )(zXkNjezzXkX2)()(在Z平面的單位圓上采樣 ？ 4例 用封閉形式表示下列有限長(zhǎng)序列的N點(diǎn)DFTx(n) （a） )1)()(NMnRnxM（b） )()(

10、0nRenxNnj解： （a） )()()(10kRWnRkXNNnnkNM)(10kRWNMnnkN)(11kRWWNkNMkN)(sinsin)1(kRekNMkNNkMNj)(kXk0N2.3.2 DFT的性質(zhì) （1）線性 時(shí)域 )()()(213nbxnaxnx1N2NN,max21NNN NNN頻域 )()()(213kbXkaXkX（2）圓周移位 若 )()()(nRmnxnfNN，稱f(n)為x(n)的 m點(diǎn)圓周移位序列。步驟：）移位 m點(diǎn)； ）取主值序列。 ）將x(n)以N 為周期進(jìn)行周期延拓；0312)(nxnn03123123124)(nx1 23n031212 34)2(

11、 nx)()2(44nRnx根據(jù)同余算法 n(2)Nn (2)( )NNx nRn0 1 2 32 3 0 11 0 3 2若 )()(kXnxDFT則 )()()(kXWnRmnxDFTmkNNN且 )()()(nxWkRlkXIDFTnlNNN(3). 共軛對(duì)稱性 定義其他，定義對(duì)，長(zhǎng)度為互為、1100)()0()()()(NDFT)()(NnnnNxxnRnNxnNxkXnxNN)()()()(NnNxnNxnxnx 取主值右移周期延拓后，反轉(zhuǎn)其他1100)()0()()()(NkNkkNXXnRkNXkNXNNNnN13 共軛對(duì)稱性 復(fù)共軛序列的DFT10*)()(NnnkNWnxnx

12、DFT證明：*10)(NnnkNWnx)(*kX)()(*10)(kNXWnxNnkNnN)0(X)N(X)n(R)kN(X)kN(X)n(xDFTNN*10NkNkN1共軛對(duì)稱與共軛反對(duì)稱61是實(shí)數(shù)時(shí)，為奇序列則稱為共軛反對(duì)稱序列序列滿足是實(shí)數(shù)時(shí)，為偶序列則稱為共軛對(duì)稱序列序列滿足為復(fù)序列，則如果)()(),()(1)()(),()(1)(nxnxnxnxnxnxnxnxnxoe)()(21)()()(21)()()()()(*nxnxnxnxnxnxnxnxnxnxoeoe和一個(gè)共軛反對(duì)稱序列之軛對(duì)稱序列和，總可以表示為一個(gè)共任意一個(gè)序列)()()()(*nxnxnxnxooee 圓周共軛

13、偶（奇）對(duì)稱序列)()()()(*nxnxnxnxooee)()(21)()()()(21)()(*nNxnxnNxnxnNxnxnNxnxopopepep)()(21)()()(21)(*nxnxnxnxnxnxoe)()()(nxnxnxopep)()(nNxnxepep)(arg)(argnNxnxepep)()(21)()()()(21)()(*kNXkXkNXkXkNXkXkNXkXopopepep頻域：)()()(kXkXkXopep)(Re)(RekXkNXoo)(Im)(ImkXkNXoo DFT的共軛特性)kN(X)nN( xDFT)k(X)nN(xDFT*)()()(21)

14、()(21)(kXkNXkXnxnxDFTnxDFTepr)()()(21)()(21)(kXkNXkXnxnxDFTnjxDFTopi)()()(kXkXkXopep)(Re)(kXnxDFTep)(Im)(kXjnxDFTop 共軛對(duì)稱性實(shí)虛部討論 若將有限長(zhǎng)序列認(rèn)為是分布在N等分圓周上，則共軛偶部 和 滿足左半圓上和右半圓上的序列共軛對(duì)稱；而共軛奇部 和 滿足左半圓和右半圓上的序列共軛反對(duì)稱。時(shí)域x(n)頻域X(k)DFTx(n)圓周共軛偶部)(nxepx(n)圓周共軛奇部)(nxopx(n)實(shí)部)(nxrx(n)虛部)(njxiX(k)共軛偶部)(kXepX(k)共軛奇部)(kXopX

15、(k)實(shí)部)(kXrX(k)虛部)(kjXi)(nxe)(kXe)(nxo)(kXo（4）圓周卷積 周期卷積取主值序列 若 則 N)n(y)n(x)n(R)mn(y)mn(y)m(y)n(y)n(y)n(xNNNn 卷積與取主值序列右移反轉(zhuǎn)周期延拓）（）（)k(Y)n(y),k(X)n(x)k(Y)k(X)k(F1N0mNN)n(R)mn(y)m( x)k(FIDFT)n( f圓周卷積 頻域 若 則 N)k(Y)n(y),k(X)n(x)n( y)n( x)n(f1N0lNN)k(R)lk(Y)l (XN1)n( fIDFT)k(F1N0lNN)k(R)lk(X)l (YN1（5）. 帕賽瓦爾定律1