第三章 離散傅里葉變換(DFT)

1、第三章第三章離散傅里葉變換（離散傅里葉變換（DFT）學習目標學習目標 掌握離散傅里葉變換的定義及性質(zhì)掌握離散傅里葉變換的定義及性質(zhì) 了解頻率域采樣理論了解頻率域采樣理論 了解了解DFT的應用的應用 離散傅里葉變換離散傅里葉變換 Discrete Fourier Transform 是研究是研究有限長序列有限長序列的一種重要工具的一種重要工具 重要作用：使數(shù)字信號處理可以在重要作用：使數(shù)字信號處理可以在頻域頻域采用采用數(shù)數(shù)字運算字運算的方法進行的方法進行 多種快速算法多種快速算法(FFT)3.1 DFT的定義的定義3.1.1 DFT的定義的定義 設設x(n)是一個長度為是一個長度為M的有限長序列

2、，的有限長序列， 則定義則定義x(n)的的N點點DFT為為X(k)的的IDFT為為1, 1 , 0,)()()(10N kWnxnxDFTkXNnknN1, 1 , 0,)(1)()(10N nWkXNkXIDFTnxNkknN變換區(qū)間長度為其中，DFTNeWNjN,27 , 0,)8sin()2sin()()(11)()(, 8DFT84)(),()(8388822244470827084 kkke eeeeeeee eWnxk XNnx nRn xkjkjkjkjkjkjkjkjkjnknjnkn解：點點和的求例注：注：x(x)的離散傅里葉變換結果與變換區(qū)間長度的離散傅里葉變換結果與變換區(qū)

3、間長度N的取值有關。的取值有關。3.1.2 DFT和和Z變換的關系變換的關系 設序列設序列x(n)的長度為的長度為N，其，其Z變換和變換和DFT分別為：分別為：1010( ) ( )( )( ) ( )( )0kN-1NnnNknNnX zZT x nx n zX kDFT x nx n W1.,1 , 0| )()(1,.,1 , 0| )()(22N keXkXN kzXkXkNjezkNj DFT的的物理性質(zhì)物理性質(zhì)： 序列序列x(n)的的N點點DFT是是x(n)的的z變換在變換在單單位圓位圓上的上的N點等間隔點等間隔采樣。采樣。 序列序列x(n)的的N點點DFT是是x(n)的的Four

4、ier變變換在區(qū)間換在區(qū)間0，2的的N點等間隔采樣。點等間隔采樣。圖3.1.1 R4(n)的FT和DFT的幅度特性關系 Fourier變換的幾種可能形式：變換的幾種可能形式： 時間函數(shù)時間函數(shù) 頻率函數(shù)頻率函數(shù) Fourier形式形式1.連續(xù)時間、連續(xù)頻率連續(xù)時間、連續(xù)頻率 傅里葉變換傅里葉變換(FT)2.連續(xù)時間、離散頻率連續(xù)時間、離散頻率 傅里葉級數(shù)傅里葉級數(shù)(DFS)3.離散時間、連續(xù)頻率離散時間、連續(xù)頻率 序列傅里葉變換序列傅里葉變換(DTFT)4.離散時間、離散頻率離散時間、離散頻率 離散傅里葉變換離散傅里葉變換(DFT)1 1、連續(xù)時間、連續(xù)頻率、連續(xù)時間、連續(xù)頻率傅里葉變換傅里葉

5、變換 時域時域連續(xù)連續(xù)造成頻域造成頻域是非周期是非周期的譜的譜 時域的時域的非周期非周期造成頻域是造成頻域是連連續(xù)續(xù)的譜密度函數(shù)。的譜密度函數(shù)。dejXtxdtetxjXtjtj)(21)()()(2、連續(xù)時間、離散頻、連續(xù)時間、離散頻率率傅里葉級數(shù)傅里葉級數(shù) 時域時域連續(xù)連續(xù)函數(shù)造成頻域函數(shù)造成頻域是是非周期非周期的譜的譜 頻域的頻域的離散離散對應時域的對應時域的周期周期函數(shù)函數(shù)ktjkTTtjkejkXtxdtetxTjkX0000)()()(1)(02/2/003、離散時間、連續(xù)頻率、離散時間、連續(xù)頻率序列的傅里葉變換序列的傅里葉變換 時域的時域的離散離散化造成頻域的化造成頻域的周期周期

6、延拓延拓 時域的時域的非周期非周期對應于頻域對應于頻域的的連續(xù)連續(xù)deeXtxenxeXnjjnnjj)(21)()()(4、離散時間、離散頻、離散時間、離散頻率率離散傅里葉離散傅里葉變換變換 一個域的一個域的離散離散造成造成另一個域的另一個域的周期周期延延拓拓102102)(1)()()(NnnkNjNnnkNjekXNnxenxkX四種傅里葉變換形式歸納四種傅里葉變換形式歸納3.1.3 DFT的隱含周期性的隱含周期性 因因WknN的周期性，使的周期性，使X(k)隱含周期性，且周期均隱含周期性，且周期均為為N。 對任意整數(shù)對任意整數(shù)m， 總有總有(),kk mNNNWWk m N均為整數(shù) 1

7、()010()( )( )( )Nk mN nNnNknNnX kmNx n Wx n WX k同理可證同理可證 x(n+mN)=x(n)為周期延拓序列以表示為周期延拓序列以表示的主值區(qū)間是的周期延拓是的關系和則的序列表示為周期為NkX kXkXNnx nxnxnxn xnRnxnxnxnx mNnxnxnxnx nxNNNNm)(,)()()(,)()()()(),()()()()(, )()(:)()(),( 周期周期序列的序列的離散傅里葉級數(shù)離散傅里葉級數(shù)( (DFSDFS) )的正反變的正反變換：換： 有限長序列有限長序列 的的DFT DFT ，正好是周期，正好是周期延拓序列延拓序列

8、的離散傅里葉級數(shù)系數(shù)的離散傅里葉級數(shù)系數(shù) 的主值序列。的主值序列。)()()(,)(1)(1)()()()()()()()(10101010kRkXkXWkXNWkXNnxnRnxnxWnxWnxnxDFSkXNNkknNNkknNNnkNNnnkNNnN，)(nx)(kXNnx)()(kX 用用Matlab計算序列的計算序列的DFT 調(diào)用函數(shù)：調(diào)用函數(shù)：Xk=fft(xn,N) 例子例子3.1.23.2 DFT的基本性質(zhì)的基本性質(zhì)1、線性性質(zhì)、線性性質(zhì) 若若x1(n)和和x2(n)是兩個有限長序列，長度分別為是兩個有限長序列，長度分別為N1和和N2。 y(n)=ax1(n)+bx2(n) 式

9、中式中a、 b為常數(shù)，為常數(shù)， 即即NmaxN1, N2，則則y(n)的的N點點DFT為為 Y(k)=DFTy(n)=aX1(k)+bX2(k), 0kN-1 其中其中X1(k)和和X2(k)分別為分別為x1(n)和和x2(n)的的N點點DFT。 2、循環(huán)移位性質(zhì)、循環(huán)移位性質(zhì)1)、序列的循環(huán)移位、序列的循環(huán)移位 設設x(n)為有限長序列，為有限長序列，長度為長度為N，則，則x(n)的循的循環(huán)移位定義為環(huán)移位定義為 )()()(nRmnxnyNN2)、時域循環(huán)移位定理、時域循環(huán)移位定理 設設x(n) 是長度為是長度為N的有限長序列，的有限長序列，y(n)為為x(n)的循的循環(huán)移位，環(huán)移位， 即

10、即 則則 證明：證明：)()()()()(10),()(),()()()()()(10)(110kXWWixW Wixm n iWmnxmnxDFSNk nxDFTkXkXWnyDFTkYnRmnxnymkNkiNNimkNmikNmNminkNNnkmNNN令其中3)、頻域循環(huán)移位定理、頻域循環(huán)移位定理)()()()()()()()(10)()(nxWDFTlk X nxWkYIDFTn ykRlkXk YNk nxDFTk XnlNnlNNN或則若3、循環(huán)卷積定理、循環(huán)卷積定理1012102121221121212121)()()()()()()()()()()()()()()()()()

11、()(,max,),()(NmNNNmNNnRmnxmxkXIDFTn xnRmnxmxkXIDFTn xkXkXk XnxDFTk XnxDFTk XDFTNnxnxNNNNNnxnx或則如果分別為：點的和長度分別為和有限長序列1) 1)、時域循環(huán)卷積定理、時域循環(huán)卷積定理 結論：結論： 循環(huán)卷積過程中，要求對循環(huán)卷積過程中，要求對x2(m)循環(huán)循環(huán)反轉，反轉，循循環(huán)環(huán)移位移位 兩個兩個N長的序列的循環(huán)卷積長度仍為長的序列的循環(huán)卷積長度仍為N。 顯然與一般的線性卷積不同，顯然與一般的線性卷積不同， 故稱之為故稱之為循環(huán)循環(huán)卷積卷積， 記為記為1221( )( )( )( )( )( )x n

12、IDFT X kx nx nx nx n2)、頻域循環(huán)卷積定理、頻域循環(huán)卷積定理10,)()()()() )()()(1)()(1)()()()()(1)()(1)()()()()(221110121210212121Nk nxDFTkX nxDFTk X kRlkXlXN kXkXNnxDFTk XkRlkXlXN kXkXNnxDFTk Xnxnxn xNlNNNlNN式中或則如果50211021215241)()()()()()()(6),() 1()(),()(mNmmnxmx mnxmxny nxnxnRnnxnRnx解：卷積和。求兩個周期序列的循環(huán)，和周期延拓成周期序列將序列以周期

13、為分別例：已知序列4、復共軛序列的、復共軛序列的DFT)()()0()()(10),()()()()()(*kXnNx DFTXN XkX Nk kNXnx DFTnxDFTk XNnxnx同理：的隱含周期性由于且則的復共軛序列，長度為是設5、DFT 的共軛對稱性的共軛對稱性1)、有限長共軛對稱序列和共軛反對稱序列、有限長共軛對稱序列和共軛反對稱序列有限長共軛對稱序列：有限長共軛對稱序列：有限長共軛反對稱序列：有限長共軛反對稱序列：10),()(10),()(*Nn nNxnxNn nNxnxopopepep120),2()2(120),2()2(*Nn nNxnNxNn nNxnNxopop

14、epep5、DFT的共軛對稱性的共軛對稱性序列的序列的Fourier變換的對稱性質(zhì)中提到：變換的對稱性質(zhì)中提到：)()(21)()()()(21)()()()()(*nxnxnxn xnxnxnxn xnxnxn xooeeoe其中：分量之和：對稱分量和共軛反對稱任意序列可表示成共軛)()(21)()()()(21)()(10),()()(*nNxnxnNxn xnNxnxnNxn xNn nxnxn xopopepepopep同理：2)、DFT的共軛對稱性的共軛對稱性)()()()()()()()()()(21)(Im)()()(21)(Re)()()()(1*kXkXnxDFTk XkXn

15、jx DFTkXnx DFTnxnxnxjn jxnxnxnxn xnjxnxn xopepopiepririr則其中）如果（2)、DFT的共軛對稱性的共軛對稱性)()()()()(Im)()(Re)()()(21)()()(21)(10),()()(2*kjXkXnxDFTk XkXjnx DFTkXnx DFTnNxnxn xnNxnxn xNn nxnxn xIRopepopepopep則其中）如果（ DFT的共軛對稱性：的共軛對稱性： 實數(shù)序列實數(shù)序列DFT的共軛對稱性：的共軛對稱性： 純虛序列純虛序列DFT的共軛對稱性：的共軛對稱性：設設 x ( n ) 是 長 度 為是 長 度 為

16、 N 的 實 序 列 ， 且的 實 序 列 ， 且X(k)=DFTx(n)， 則則(1) X(k)共軛對稱共軛對稱，即，即 X(k)=X*(N-k),0kN-1(2) 如果如果 x(n)=x(N-n)，則，則X(k)實偶對稱實偶對稱， 即即 X(k)=X(N-k)(3) 如果如果x(n)=-x(N-n)，則，則X(k)純虛奇對稱純虛奇對稱， 即即 X(k)=-X(N-k) 對實序列進行對實序列進行DFT，利用上述性質(zhì)，可減，利用上述性質(zhì)，可減少少DFT運算量。運算量。 例：設例：設x1(n)和和x2(n)都是都是N點的實數(shù)序列，點的實數(shù)序列，試用試用N點點DFT運算來計算他們各自的運算來計算他

17、們各自的DFT)()(21)()()(21)()()()()(*2*1kNXkXjk XkNXkXk X kXkXnxDFTk Xopep又)()()()()()()()()()()()()()()(212121212211kjXkX nxjDFTnxDFT njxnxDFTnxDFTk Xnjxnxnx kXnx DFTkXnxDFT則個復序列：解：利用兩序列構成一3.3 頻率域采樣頻率域采樣 時域采樣定理：在滿足來奎斯特定理條件時域采樣定理：在滿足來奎斯特定理條件下，時域抽樣信號可以不失真地還原連續(xù)下，時域抽樣信號可以不失真地還原連續(xù)信號信號 頻域采樣呢？采樣條件？內(nèi)插公式？頻域采樣呢？采

18、樣條件？內(nèi)插公式？ 任意絕對可和的非周期序列任意絕對可和的非周期序列x(n)，其，其z變換變換?)()()(| )()()()()( nxkXWnxzXkX NzXznxzXnkNnWznnkN分析：序列：點等間隔采樣，得周期在單位圓上對 m rrNn mWN rNnx WNmx WWmxN WkXNkXIDFSnxIDFSkXnxNkknmNrmNkknmNNknkNmmkNNknkNNN其他為任意整數(shù)：的為令0,11)(1)()(1)(1)()()()(10)(10)(1010 結論結論1：由頻域采樣序列由頻域采樣序列 還原得到的周期序還原得到的周期序列是原非周期序列列是原非周期序列 的周

19、期延拓序列，的周期延拓序列，其周期為頻域采樣點數(shù)其周期為頻域采樣點數(shù) N。 結論結論2：時域采樣造成頻域周期延拓時域采樣造成頻域周期延拓頻域采樣造成時域周期延拓頻域采樣造成時域周期延拓)(kX)(nx 結論結論3：混疊失真不失真為有限長序列，長度為混疊失真為無限長序列 M N M N Mnxnx,)2,) 1)()( 頻率采樣定理：頻率采樣定理： 若序列長度為若序列長度為M，則只有當頻域采樣點數(shù)：，則只有當頻域采樣點數(shù)： 時，才有時，才有 即可由頻域采樣即可由頻域采樣X(k)不失真地恢復原信號不失真地恢復原信號x(n),否則產(chǎn)生時域混疊現(xiàn)象。否則產(chǎn)生時域混疊現(xiàn)象。MN )()()()()(nx

20、nRkXIDFSnRnxNNn內(nèi)插公式內(nèi)插公式 用頻域采樣用頻域采樣 X(k) 表示表示 X(z) 的內(nèi)插公式的內(nèi)插公式1011011010101010101)(111)(1)(1)(1)()()(),(NkkNNNkkNNNkNNknNnnkNNnnNknkNNnnMnnzWkXNzzWzWkXN zWkXN zWkXN znxznxzXMNNnxM點等間隔采樣，且頻域點有限長序列階極點：零點：則內(nèi)插公式簡化為：內(nèi)插函數(shù)：內(nèi)插公式：) 1(0,1, 1 , 0,)()()(111)(1)(1)(22101101N e zN re zzkXzXzWzNz zWkXNzzXkNjrNjkNkkN

21、NkNkkNN內(nèi)插公式內(nèi)插公式 用頻域采樣用頻域采樣 X(k) 表示表示 X(ejw) 的內(nèi)插公式的內(nèi)插公式10)21(21)1(10)2()()()2sin()2sin(1)()2sin()2(sin1| )()()()(| )()(NkjNjNjNNkjezkjkNkjkezjkNkXeXeNNeekNkNNNzeekXzXeXjj內(nèi)插公式：內(nèi)插函數(shù)：3.4 DFT的應用舉例的應用舉例主要應用：主要應用：1. 用用DFT計算卷積和相關系數(shù)計算卷積和相關系數(shù)2. 用用DFT對連續(xù)信號和序列進行譜分析對連續(xù)信號和序列進行譜分析3.4.1 用用DFT計算線性卷積計算線性卷積10),()()()(

22、10,)()()()()()()()()()(212211102121Lk kXkXnyDFTk YLk nxDFTk XnxDFTk XnRmnxmxnxnxn yLmLL有：則由時域循環(huán)卷積定理且如果 線性卷積和循環(huán)卷積之間的關系？線性卷積和循環(huán)卷積之間的關系？ 循環(huán)卷積與線性卷積相等的條件？循環(huán)卷積與線性卷積相等的條件？ 設設h(n)和和x(n)都是有限長序列，長度分別是都是有限長序列，長度分別是N和和M。它們的線性卷積和循環(huán)卷積分別為。它們的線性卷積和循環(huán)卷積分別為： 其中，其中， LmaxN, M 1010( )( )( )( ) ()( )( )( )( ) ()( )NlmLcL

23、Lmy nh nx nh m x nmy nh nx nh m x nmR n( )(),Lqx nx nqL1010( )( )()( )( ) ()( )NcLmqNLqmy nh mx nmqL R nh m x nmqL R n 對照線性卷積的表達式可以看出線性卷積對照線性卷積的表達式可以看出線性卷積和循環(huán)卷積之間的關系：和循環(huán)卷積之間的關系： 10( ) ()()( )()( )NlmclLqh m x nqLMy nqLy ny nqL R n 線性卷積和循環(huán)卷積相等的條件：線性卷積和循環(huán)卷積相等的條件：1MNL0123451234h(n) x(n)nL 60123451234nL

24、 867h(n) x(n)0123451234nL 1067h(n) x(n)（ d ）（ e ）( f )0123451234nN M1 867h(n) x(n)*nM 5012341x(n)nN 401231h(n)（ a ）（ b ）（ c ）89* * 189 10補L N個零點L點DFT補L M個零點L點DFTL點IDFTy(n)h(n)x(n)若遇到兩個序列長度相差很大的情況，將若遇到兩個序列長度相差很大的情況，將長序列分段計算，采用重疊相加法。長序列分段計算，采用重疊相加法。 設序列設序列h(n)長度為長度為N，x(n)為無限長序列。為無限長序列。將將x(n)均勻分段，每段長度取

25、均勻分段，每段長度取M， 則則0( )( )( )( )()kikMx nx nx nx nRnkMh(n)與x(n)的線性卷積可表示為：000( )( )( )( )( )( )( )( )kkkkkkky nh nx nh nx nh nx ny nM0NMMx1(n)x0(n)x2(n)N M 1N M 1y0(n)y1(n)N M 1y2(n)2MM3M N 10N 1y(n) y0(n) y1(n) y2(n) nnnnnnh(n)3.4.2 用用DFT進行譜分析進行譜分析 信號的頻譜分析：計算信號的傅立葉變換信號的頻譜分析：計算信號的傅立葉變換3.4.2 用用DFT進行譜分析進行譜

26、分析1、用、用DFT對連續(xù)信號進行譜分析對連續(xù)信號進行譜分析 設設連續(xù)信號連續(xù)信號xa(t)持續(xù)時間和持續(xù)時間和Tp，最高頻率，最高頻率為為fh。 xa(t)的傅里葉變換為的傅里葉變換為 對對xa(t)以采樣間隔以采樣間隔T1/2fh(即即fs=1/T2fh)采采樣樣得得a(t)=Xa(nT)。設共采樣。設共采樣N點，并對點，并對Xa(jf)作零階近似作零階近似(t=nT, dt=T)得得2()( )( )jfaaaXifFT x tx t etdt120()()NjfnTanX ifTx nT e Xa(jf)是是f的的連續(xù)周期函數(shù)連續(xù)周期函數(shù)，對，對 X(jf)在區(qū)在區(qū)間間0, fs上等間

27、隔采樣上等間隔采樣N點，采樣間隔為點，采樣間隔為F參數(shù)參數(shù)fs 、 Tp、 N和和F滿足如下關系式：滿足如下關系式： 11spfFNNTFT由于由于NT=Tp， 所以所以 210()()NjknNanX jkFTx nT e 0kN-1 ( )(), ( )()aaXkX jkfx nx nT令 則 21010210( )( ) ( )2( )()( )1( )1( )NjknNanNnNejknNanaXkTx n eT DFT x nx nXa nTFXa k ejknNFNXkNIDFT XkT 頻率響應的混疊失真及參數(shù)的選擇頻率響應的混疊失真及參數(shù)的選擇 譜分析范圍：譜分析范圍：已知信

28、號的最高頻率已知信號的最高頻率fh 頻率分辨率：頻率分辨率：即頻率采樣間隔即頻率采樣間隔F0000/12FfTTNTFffshs頻率抽樣：時域抽樣： 信號最高頻率和頻率分辨率之間的矛盾信號最高頻率和頻率分辨率之間的矛盾.1000000NffTNFTFFNffFfTTNhsshs采樣點數(shù)和頻率分辨率，需增加同時提高信號最高頻率必，要不產(chǎn)生混疊，給定，當，則要提高頻率分辨率，即，即分辨率必給定，當，則要增加信號最高頻率 信號最高頻率信號最高頻率fh的確定的確定 時域變化越快，高頻分量越豐富時域變化越快，高頻分量越豐富002112/tTfTthhh例例 對實信號進行譜分析，要求譜分辨率對實信號進行譜

29、分析，要求譜分辨率F10 Hz，信號最高頻率信號最高頻率fc=2.5 kHz， 試確定最小記錄時試確定最小記錄時間間TPmin，最大的采樣間隔，最大的采樣間隔Tmax，最少的采樣點，最少的采樣點數(shù)數(shù)Nmin。如果。如果fc不變，要求譜分辨率增加一倍，不變，要求譜分辨率增加一倍，最少的采樣點數(shù)和最小的記錄時間是多少最少的采樣點數(shù)和最小的記錄時間是多少? 解：解： 因此因此TPmin=0.1 s，因為，因為fs2fc， 所以所以 110.110PTsF3maxmin110.2 1022250022250050010ccTsffNF為使頻率分辨率提高一倍，為使頻率分辨率提高一倍， F=5 HzF=5 Hz， 要求要求minmin225001000510.25pNTs2、用、用DFT對序列進行譜分析對序列進行譜分析 因為：因為：已知單位圓上的已知單位圓上的Z變換就是序列傅里葉變變換就是序列傅里葉變換，換， 即即X(k)是單位圓上的是單位圓上的N點等間隔采樣點等間隔采樣 所以：序列的所以：序列的FT可以利用可以利用DFT計算。計算。()( )jjz eX eX z 對周期對周期N的周期序列的周期序列 ，其頻譜函數(shù)為，其頻譜函數(shù)為 根據(jù)根據(jù)DFT的隱含周