課件第4章變換

1、第四章第四章 傅立葉變換傅立葉變換離散時(shí)間傅里葉變換離散時(shí)間傅里葉變換DTFTDTFT離散傅立葉變換離散傅立葉變換DFTDFT傅立葉傅立葉 1768-1830(Fourier, Jean Baptiste Joseph) 法國數(shù)學(xué)家、物理學(xué)家法國數(shù)學(xué)家、物理學(xué)家最早使用定積分符號最早使用定積分符號改進(jìn)符號法則、根數(shù)判別方法改進(jìn)符號法則、根數(shù)判別方法傅立葉級數(shù)創(chuàng)始人傅立葉級數(shù)創(chuàng)始人 1807 熱的傳播熱的傳播推導(dǎo)熱傳導(dǎo)方程中發(fā)現(xiàn)解函數(shù)可推導(dǎo)熱傳導(dǎo)方程中發(fā)現(xiàn)解函數(shù)可以由三角函數(shù)級數(shù)構(gòu)成的級數(shù)形以由三角函數(shù)級數(shù)構(gòu)成的級數(shù)形式表示式表示 1822 熱的分析理論熱的分析理論傅立葉級數(shù)、分析等理論傅立葉級

2、數(shù)、分析等理論傅立葉分析方法的歷史傅立葉分析方法的歷史l古巴比倫人古巴比倫人 l “三角函數(shù)和三角函數(shù)和” 描述周期性過程、預(yù)測天體描述周期性過程、預(yù)測天體運(yùn)動(dòng)運(yùn)動(dòng)l 1748年年 歐拉歐拉l 振動(dòng)弦的形狀是振蕩模的線性組合振動(dòng)弦的形狀是振蕩模的線性組合l1753年年 D伯努利伯努利l 弦的實(shí)際運(yùn)動(dòng)可用標(biāo)準(zhǔn)振蕩模的線性組合來表弦的實(shí)際運(yùn)動(dòng)可用標(biāo)準(zhǔn)振蕩模的線性組合來表示示l1759年年 拉格朗日拉格朗日l 不能用三角級數(shù)來表示具有間斷點(diǎn)的函數(shù)不能用三角級數(shù)來表示具有間斷點(diǎn)的函數(shù)l l 1822年年 傅立葉傅立葉l “熱的分析理論熱的分析理論” 中提出并證明周期函數(shù)的正弦級中提出并證明周期函數(shù)的正

3、弦級數(shù)展開原理，奠定了傅立葉級數(shù)的理論基礎(chǔ)數(shù)展開原理，奠定了傅立葉級數(shù)的理論基礎(chǔ)l 1829年年 P.L狄里赫利狄里赫利l 周期信號傅立葉級數(shù)表示的若干精確條件周期信號傅立葉級數(shù)表示的若干精確條件l 19-20世紀(jì)世紀(jì)l 兩種傅立葉分析方法兩種傅立葉分析方法-連續(xù)與離散連續(xù)與離散l 1965年年 Cooley & Tukey (IBM)l 發(fā)明發(fā)明FFT 算法算法引例引例時(shí)域時(shí)域和弦和弦 中音中音CEG頻域頻域如何分解出如何分解出CEG分量？分量？傅立葉變換的導(dǎo)出傅立葉變換的導(dǎo)出濾波濾波相乘相乘中音中音C每個(gè)頻率分量？每個(gè)頻率分量？頻域頻域?yàn)V波器濾波器時(shí)域時(shí)域卷積卷積頻率頻率為為 分量

4、分量幅度幅度頻率頻率通帶通帶變窄變窄( )j th tex(t)x(t)( )h t( )( )*j txtx te濾波器濾波器頻域頻域頻率頻率幅度幅度時(shí)域時(shí)域單位沖擊單位沖擊響應(yīng)響應(yīng)與與 t無關(guān)無關(guān)常數(shù)常數(shù)( )( )*( )*(cossin) j txtx tex ttjt()( )( )cos()sin()( )cos()sin()( ) jtxtxtjtdxtjt dx t ed = =( )( ) jj txtxede()( )j tX jx t edt x(t)x(t)( )j th te四種常用的傅立葉變換四種常用的傅立葉變換時(shí)域時(shí)域頻域頻域離散離散連續(xù)連續(xù)離散時(shí)間傅立葉變換離散

5、時(shí)間傅立葉變換連續(xù)連續(xù)連續(xù)連續(xù)連續(xù)時(shí)間傅立葉變換連續(xù)時(shí)間傅立葉變換 離散離散離散離散 離散傅立葉變離散傅立葉變換換連續(xù)連續(xù)離散離散連續(xù)時(shí)間傅立葉級數(shù)連續(xù)時(shí)間傅立葉級數(shù)連續(xù)時(shí)間傅立葉變換連續(xù)時(shí)間傅立葉變換(FT) x(t)X(j) 正變換正變換 反變換反變換()( )j tX jx t edt 正變換正變換 分解分解 ( (提取提取) )1( )()2j tx tX jed反變換反變換 合成合成 ( (還原還原) )( )( ) j tXjx t edtx t dt 條件條件 有限個(gè)不連續(xù)點(diǎn)有限個(gè)不連續(xù)點(diǎn) 絕對可積絕對可積非周期連續(xù)時(shí)間信號非周期連續(xù)時(shí)間信號非周期連續(xù)頻率函數(shù)非周期連續(xù)頻率函數(shù)常

6、見信號頻譜常見信號頻譜連續(xù)時(shí)間傅立葉級數(shù)連續(xù)時(shí)間傅立葉級數(shù)(FS)周期周期022fT ()( )j tX jx t edt 正變換正變換 000()( )TjktkX jkx t edta1( )()2j tx tX jed反變換反變換001( )()jktx tX jkeT收斂性收斂性抽樣定理抽樣定理周期連續(xù)時(shí)間信號周期連續(xù)時(shí)間信號非周期離散頻譜函數(shù)非周期離散頻譜函數(shù)常見信號頻譜常見信號頻譜離散時(shí)間傅里葉變換離散時(shí)間傅里葉變換(DTFT)T ()( )j tX jx t edt 正變換正變換 ()( )jj nnX ex n e1( )()2j tx tX jed反變換反變換201( )()

7、2jj tx nX eed非周期離散信號非周期離散信號周期連續(xù)頻率函數(shù)周期連續(xù)頻率函數(shù)常見信號頻譜常見信號頻譜 ()()jjjX eX ee ()()jjX eX e ：傅立葉頻譜：幅度函數(shù) 或 幅度譜：相位函數(shù) 或 相位譜例：例：00DTFTj nIDTFTnne 0022DTFTjnIDTFTkek DTFT頻譜頻譜 的性質(zhì)：的性質(zhì)：)(jeX 222cossintanjjrejjimjjjreimjimjreXeX eXeX eX eXeXeXeXe 1. 模與幅角模與幅角 2. 對于實(shí)序列對于實(shí)序列() jj nnX ex n e() cos()()jjrerenXex nnXe為 的

8、偶函數(shù)() sin()()jjimimnXex nnXe 為 的奇函數(shù)222jjjreimX eXeXe tanjimjreXeXe ()jX e為 的偶函數(shù)( ) 為 的奇函數(shù)3jX e、為周期2 的連續(xù)函數(shù)(2)(2)() ()jj nnjk nnjkX ex n ex n eX e證明：證明：DTFT的收斂條件（的收斂條件（convergence) ()jx nX e絕對可和收斂 jj nnnX ex n ex n () jj nnX ex n e無窮項(xiàng)求和無窮項(xiàng)求和() jX ex n收斂絕對可和?例：低通濾波器例：低通濾波器(p105，例，例3.8) jDTFTnkDTFTnjkjD

9、TFTkDTFTDTFTenukekenuknDTFT 11122211221100，對：常用周期沖激串周期沖激串 periodic impulse train DTFT的性質(zhì)的性質(zhì)() jG eg n ()jh nH e 1. 線性 g nh n)(jjG eH e 2. 時(shí)間反轉(zhuǎn)時(shí)間反轉(zhuǎn) ()jG egn()jj nnY egn e證明：證明： j mmg m em=-njG e3. 時(shí)移時(shí)移00()j njeG eg nn證明證明0()jj nnY eg nn e0() jm nmg m e0j njeG em=n-n0幅度幅度(功率功率)譜不變譜不變僅影響相位譜僅影響相位譜0101()

10、()jjjjd V ed eV epp e0101 1 1d v nd v npnpn .v n利用傅立葉變換性質(zhì)，不解差分方程求序列解：解：0101()jjjpp eV edd e傅立葉反變換傅立葉反變換vn4. 頻移頻移00() ()jnjg nG ee 證明：證明：0() jnjj nnY eeg n e0() jnng n e 0()jG e 調(diào)頻廣播、頻率調(diào)制調(diào)頻廣播、頻率調(diào)制5. 頻域微分頻域微分() jdG en g njd j njj nnndg n edG ejng n edd 證明：證明：6. 卷積卷積 ()()jjg nh nG eH e證明：證明：() jj nnkY

11、eg k h nke () jn kj kkng kh nk ee j kj mkmg k eh m ejjG eH em=n-kdeHeGnhngjj)()(21)(7.調(diào)制定理調(diào)制定理(也稱為加窗定理也稱為加窗定理)() jj nnY eg n h n e1 ()2j njj nnh n eG eed()1() 2jjnnG eh n ed ()1()()2jjG eH ed 證明證明高頻高頻例：幅度調(diào)制例：幅度調(diào)制 x n0cosn y n0 cosy nx nn0011()()222jjY eX ed 001()()2jjX eX e 低頻低頻0-幅度幅度頻率頻率幅度幅度0-oo頻率頻

12、率低通低通濾波濾波 y n r n x n0cosn解調(diào)解調(diào)20001 cos(1cos2) 211 cos2 22r nx nnn x nx nnx n低頻低頻高頻高頻例：加窗例：加窗 x n w n y n y nx n w n()1()()2jjjY eX eW ed 無限長序列無限長序列窗函數(shù)窗函數(shù)加窗后頻譜產(chǎn)生失真加窗后頻譜產(chǎn)生失真測不準(zhǔn)原理：時(shí)域分辨率測不準(zhǔn)原理：時(shí)域分辨率*頻域分辨率頻域分辨率常數(shù)常數(shù)加窗實(shí)例加窗實(shí)例 x n w n y n頻譜頻譜頻譜頻譜加窗后頻譜產(chǎn)生失真加窗后頻譜產(chǎn)生失真正正弦弦序序列列 8. 帕斯瓦爾公式帕斯瓦爾公式 *1 ()()2jjng n h nG

13、eHed*1()()2jjG eHed*1() 2jj nnHeg n ed* ng n h n證明：證明：*1 ()2jj nng nHeed時(shí)域的能量等于頻域的能量時(shí)域的能量等于頻域的能量2()jX e 稱為能量譜密度特例：特例： g nh nx n221( )()2jnEx nX ed*1 ()()2jjng n h nG eHedLTI離散時(shí)間系統(tǒng)的頻率響應(yīng)離散時(shí)間系統(tǒng)的頻率響應(yīng)傅立葉變換：信號傅立葉變換：信號不同頻率正弦信號的線性組合不同頻率正弦信號的線性組合xnhnyn ()()()kjjjy nh k x nkY eH eX eLTI系統(tǒng)對單頻信號的響應(yīng)系統(tǒng)對單頻信號的響應(yīng) 任何

14、復(fù)雜信號的響應(yīng)任何復(fù)雜信號的響應(yīng)()() ()jjj njnY eH eh n eX e jj kkH eh k ejH e argjH e 頻率響應(yīng)：頻率響應(yīng)：幅度響應(yīng)：幅度響應(yīng)：相位響應(yīng)：相位響應(yīng)：實(shí)沖激響應(yīng)實(shí)沖激響應(yīng))()(jjeHeH)()(是奇函數(shù)是偶函數(shù)，)()(jimjreeHeH幅度響應(yīng)和相位響應(yīng)周期為幅度響應(yīng)和相位響應(yīng)周期為2相位響應(yīng)是奇函數(shù)相位響應(yīng)是奇函數(shù) 幅度響應(yīng)是偶函數(shù)幅度響應(yīng)是偶函數(shù)()() ()jjj njnY eH eh n eX e2111:() ():()()FIRIIRNjj nn NMj kjkjkNjj kkkH eh n ep eY eH eX ed

15、e1/,01 0,otherwiseMnMh n例：例：求滑動(dòng)平均濾波器求滑動(dòng)平均濾波器 頻率響應(yīng)？頻率響應(yīng)？2/)1(0010)2/sin()2/sin(11111111)(MjjjMjMnnjMnnjnnjMnnjjeMMeeMeeMeeMeMeH解解:為什么是折線為什么是折線M的變化有何影響的變化有何影響例：輸入信號例：輸入信號通過通過3階階FIR高通濾波器高通濾波器)4 . 0cos()1 . 0cos(nnnnx 1456335.13276195. 6nxnxnxny觀察輸出信號幅度和相位的變化觀察輸出信號幅度和相位的變化Matlab仿真圖形仿真圖形 y n比較絳紅與藍(lán)色線比較絳紅與

16、藍(lán)色線,有何區(qū)別？有何區(qū)別？cos(0.4 )n x ncos(0.1 )n相位：相位：產(chǎn)生產(chǎn)生 延時(shí)延時(shí))(arg)(0jeH幅度：幅度：濾除濾除cos(0.1n)頻率分量頻率分量()()()jjjY eH eX e相延遲相延遲(phase delay)和群延遲和群延遲(group delay)(cos(| )(|)(cos(| )(|0000000neHAneHAnyjj ( )p nnAnxo),cos(不同頻率的正弦分量不同頻率的正弦分量 + 系統(tǒng)相延遲系統(tǒng)相延遲 = 相位失真相位失真xnhnyn相延時(shí)相延時(shí) ( )gdd 群延遲：濾波器平均延遲的一個(gè)度量，群延遲：濾波器平均延遲的一個(gè)

17、度量， 是相位在一個(gè)窄帶信號上的近似延遲是相位在一個(gè)窄帶信號上的近似延遲群延時(shí)群延時(shí)pg ( )gdd 群延時(shí)群延時(shí)xnhnyn)(| )(| )()(jjjjeeHeXeY)(nyeYj)()()(jjjeeYeYba)(jbeanyny線性相位線性相位00()j njeG eg nn滑動(dòng)平均濾波器的群延時(shí)？意義？滑動(dòng)平均濾波器的群延時(shí)？意義？(1)/21sin(/2)()sin(/2)jj MMH eeM 12gM群延遲：群延時(shí)為常量，與頻率無關(guān)（線性相位）群延時(shí)為常量，與頻率無關(guān)（線性相位）1/,01 0,otherwiseMnMh n離散傅里葉變換離散傅里葉變換時(shí)域周期延拓時(shí)域周期延拓

18、頻率采樣頻率采樣離散時(shí)間傅立葉變換離散時(shí)間傅立葉變換DTFT離散傅立葉變換離散傅立葉變換DFT 12/2/0Njjkn Nk NnX kX ex n ennjjenxeX)(DTFTDFT正正變變換換01kNN點(diǎn)有限長序列點(diǎn)有限長序列 deeXnxnjj21IDTFT 12/01,01Njkn Nkx nX k enNNIDFT反反變變換換離散傅立葉變換離散傅立葉變換 Discrete Fourier Transform DFT 定義定義 10DFT 01NknNnX kx nWkN 101IDFT01NknNkx nX k WnNN2/jNNWe jkX kX k eDFT幅度譜幅度譜 k

19、X kDFT相位譜相位譜2/jNNWe性質(zhì)性質(zhì)222knjkn NNnrN nNNNNWeWWWW01NNNnN nNNWWWW10102)(1)(1)(NknkNNkNknjWkXNekXNnxotherwiserNlkNeeeWNlkjlkjNnnklNjNnnlkN011/2210210IDFT證明證明證明證明: 11111000001100111NNNNNk l nlnknlnNNNNnnknkNNk l nNknx nWX k WWX k WNNX kWX lN 1021022102NnnNkjNnnjnNkjNnnNNkjkXenxeenxenxNkX證明：證明：DFT的周期性的周

20、期性 X kNX kN為為xn的長度的長度10 ,)()(10102NkWnxenxkXNnnkNNnNknj10102)()(1)(NknkNNkNknjWkXekXNnxDFT的運(yùn)算量的運(yùn)算量DFTIDFTN2N*(N-1)DFT、IDFT復(fù)數(shù)乘法復(fù)數(shù)乘法DFT、IDFT復(fù)數(shù)加法復(fù)數(shù)加法 2101010DFTkmjDFTkmNNnx nX kotherwisenmx nX kWeotherwise 例：例： 2NDFTcos 2/,01 01x nrn NnNrN例 ：求長度為 的序列的： 2/2/1122jrn Njrn NrnrnNNx neeWW 1100/21/220NNr k N

21、r k NNNnnNkrX kWWNkNrotherwise正頻率正頻率負(fù)頻率負(fù)頻率Xk的的DFT頻譜頻譜16N 3r DTFT與與DFT的關(guān)系的關(guān)系DFTDTFT 1011112/000011Njj nnNNNNknj nj njkn NnnkknX ex n eX k WeX keeNN 離散離散連續(xù)連續(xù)212/1 /22/2/02sin1221sin2jNkNjk NNjk N njk NnNkeeeNkeN 插值插值 12/1 /202sin122sin2Njk NNjkNkX eX keNkNN 插值公式插值公式DFT用于用于DTFT的數(shù)值估算的數(shù)值估算 12/0 kMjMNjkn

22、MjenX kX exn eX e 2/ kjk Mx nX eMN 估計(jì)估計(jì)N點(diǎn)序列點(diǎn)序列 01 011ex nnNx nNnM 補(bǔ)零補(bǔ)零M大小對大小對Xk的影響的影響? cos 2/,3,16(1) 16x nrn NrN例：序列求其點(diǎn)DFT;(2) 將(1)中的序列以補(bǔ)零方式加長到256，求其256點(diǎn)DFT (1) cos 3/4x nn解:(1)(2)增大增大M可以提高信號可以提高信號DFT的頻率分辨率的頻率分辨率N大小對信號周期估計(jì)的影響大小對信號周期估計(jì)的影響? 60 cos(2 () ) (64256x nn例：序列周期為）N=128和和N=129時(shí)的時(shí)的DFT頻譜頻譜N為周期的

23、整數(shù)倍為周期的整數(shù)倍頻譜的尖峰為正弦的頻率頻譜的尖峰為正弦的頻率N不是周期的整數(shù)倍不是周期的整數(shù)倍出現(xiàn)模糊出現(xiàn)模糊單頻模擬信號單頻模擬信號DFT寬頻寬頻DFT頻譜頻譜原因？原因？ 129點(diǎn)點(diǎn)128點(diǎn)點(diǎn)時(shí)域上看時(shí)域上看周期延拓周期延拓波形的突變產(chǎn)生多種頻率分量波形的突變產(chǎn)生多種頻率分量頻域上看頻域上看128點(diǎn)點(diǎn)129點(diǎn)點(diǎn)序列的循環(huán)移位序列的循環(huán)移位0000010modNnx nnnnNxnnx Nnnnnmmn（）56nx26nx x n61xn64xnDFT的性質(zhì)的性質(zhì) : 有限長序列的運(yùn)算有限長序列的運(yùn)算移位與循環(huán)移位移位與循環(huán)移位0N-10N-1循環(huán)移循環(huán)移2位位周期延拓周期延拓移移2 2

24、位位()NNxnxNn循環(huán)移位的周期循環(huán)移位的周期循環(huán)移位的時(shí)反循環(huán)移位的時(shí)反()NNxnmxnNmn性質(zhì)性質(zhì)證明證明有限長序列的分類有限長序列的分類共軛對稱：共軛對稱：* x nx -n* x n-x -n共軛反對稱：共軛反對稱： cscax nxnxn任意復(fù)序列可分解為共軛對稱和共軛反對稱部分任意復(fù)序列可分解為共軛對稱和共軛反對稱部分共軛對稱部分共軛對稱部分共軛反對稱部分共軛反對稱部分 2caxnx nx -n/ 2csxnx nx -n/特例：實(shí)序列特例：實(shí)序列偶對稱：偶對稱： x nx -n x n-x -n奇對稱：奇對稱： eox nx nx n任意實(shí)序列可分解為偶對稱和奇對稱部分任

25、意實(shí)序列可分解為偶對稱和奇對稱部分 2ox nx nx -n/ 2ex nx nx -n/偶對稱部分偶對稱部分奇對稱部分奇對稱部分圓周共軛對稱：圓周共軛對稱：* 01Nx nxnx N -nnN* 01Nx nxnx N -nnN 圓周共軛反對稱：圓周共軛反對稱： pcspcax nxn xnN點(diǎn)序列可分解為圓周共軛對稱和圓周共軛反對稱部分點(diǎn)序列可分解為圓周共軛對稱和圓周共軛反對稱部分* 2pcsxnx nx N -n/* 2 pcaxnx nx N -n/圓周共軛對稱圓周共軛對稱部分部分圓周共軛對稱圓周共軛對稱部分部分幾何對稱：幾何對稱： 101x nx NnnN 101x nx NnnN

26、幾何反對稱：幾何反對稱：DFT的對稱關(guān)系的對稱關(guān)系復(fù)序列復(fù)序列DFT的對稱關(guān)系的對稱關(guān)系序列序列DFT頻譜頻譜* x n* NXk* Nxn* Xk共軛、共軛、時(shí)反時(shí)反 Re x n*1 2pcsNNXkXkXkIm jx n*1 2pcaNNXkXkXk實(shí)部、實(shí)部、虛部虛部 pcsxnRe X k pcaxnIm jX k圓對稱、圓對稱、反對稱反對稱實(shí)序列實(shí)序列DFT的對稱關(guān)系的對稱關(guān)系Re Re NX kXk* NX kXkIm ImNX kXk | | | |NX kXkarg arg NX kXk DFT頻譜頻譜對稱關(guān)系對稱關(guān)系 pexnRe X k poxnIm jX k偶對稱、偶對

27、稱、奇對稱奇對稱序列序列DFT頻譜頻譜DFT的性質(zhì)的性質(zhì) g nG kh nH k已知已知線性：線性： g nh n kG kH循環(huán)時(shí)移循環(huán)時(shí)移00( )knNNg nnWG k時(shí)移時(shí)移00()j njeG eg nnDTFTDFT幅度幅度(功率功率)譜不變，僅影響相位譜譜不變，僅影響相位譜00() ()jnjg nG ee 循環(huán)頻移循環(huán)頻移00 k nNNWg nG kk頻移頻移調(diào)幅廣播調(diào)幅廣播DFT對偶：對偶： NG nNgk g nG kDFTN點(diǎn)圓周卷積點(diǎn)圓周卷積10 ( )( )NNmg m h nmG k H k ()()jjg nh nG eH eDTFT卷積卷積圓周卷積圓周卷積

28、 10NLmyng m h nm g nh nN設(shè)、為 點(diǎn)長的序列21LN回顧：回顧：N N點(diǎn)序列的線性卷積點(diǎn)序列的線性卷積yLnyLn的長度？的長度？ 10N NCNmyng nh ng m hnmN N點(diǎn)序列的圓周卷積點(diǎn)序列的圓周卷積yCnyCn的長度？的長度？LNLM+N-10 N-10M-1L0 N-1LM+N-10M-1L0M-1xn0 N-1hn線性卷積與圓周卷積的關(guān)系線性卷積與圓周卷積的關(guān)系線性卷積線性卷積圓周卷積圓周卷積00M+N-1yn0L=M+N-1點(diǎn)點(diǎn) 圓周卷積圓周卷積 = 線性卷積線性卷積調(diào)制調(diào)制(加窗加窗)101 NNmg n h nG m HkmNdeHeGnhng

29、jj)()(21)(DFTDTFT帕斯瓦爾公式帕斯瓦爾公式1122001 NNnkx nX kN*1 ()()2jjng n h nG eHedDFTDTFTNnNnkHkGNnhng0*0*1兩個(gè)實(shí)序列兩個(gè)實(shí)序列DFT的計(jì)算的計(jì)算實(shí)序列實(shí)序列DFT的計(jì)算的計(jì)算 x ng njh n令 *1212NNG kX kXkH kX kXkjDFT的對稱性的對稱性基本思想：利用基本思想：利用DFT的對稱性的對稱性2N點(diǎn)實(shí)序列點(diǎn)實(shí)序列DFT的計(jì)算的計(jì)算2N點(diǎn)實(shí)序列點(diǎn)實(shí)序列vn 2111212222000112002221021NNNnknknkNNNnnnNNnknkkNNNnnkNNNv nv n W

30、vn WvnWg n Wh n W WGkWHkkN， 2g nvn 21h nvn偶數(shù)點(diǎn)偶數(shù)點(diǎn)奇數(shù)點(diǎn)奇數(shù)點(diǎn)兩個(gè)有限長序列的線性卷積兩個(gè)有限長序列的線性卷積用用DFT計(jì)算線性卷積計(jì)算線性卷積1LMN LCeeyng nh nyngnL h n LCeeyng nh nyngnL h n Ng n點(diǎn)序列補(bǔ)零補(bǔ)零 0101eg nnNgnNnL Mh n點(diǎn)序列 0101eh nnMh nMnL補(bǔ)零補(bǔ)零基本思想：線性卷積基本思想：線性卷積圓周卷積圓周卷積 DFT計(jì)算計(jì)算10 ( )( )NNmg m h nmG k H k有限長序列與無限長序列的線性卷積有限長序列與無限長序列的線性卷積 10Mlh

31、lMx ny nh l x nlh nx n設(shè)為點(diǎn)有限長序列，為無限長序列求：基本思想：無限長卷積基本思想：無限長卷積有限長卷積之和有限長卷積之和0M-1 0 xnhn1. 重疊相加法重疊相加法N-1線線性性卷卷積積0與與hn 做做L=M+N-1 點(diǎn)圓周卷積點(diǎn)圓周卷積N-12N-1重疊相加重疊相加0yn2個(gè)個(gè) (M+N-1)點(diǎn)點(diǎn) DFT0M-1 0 xnhn2. 重疊保留法重疊保留法N-1線線性性卷卷積積與與hn 做做L=N3 圓計(jì)算量圓計(jì)算量 線計(jì)算量線計(jì)算量N=128 圓計(jì)算量圓計(jì)算量 = 8% 線計(jì)算量線計(jì)算量短時(shí)分析短時(shí)分析 短時(shí)短時(shí)( (加窗加窗) )傅立葉變換傅立葉變換基音周期不同

32、基音周期不同10()( )( )Njj mnnmXew m x m e加窗加窗語譜圖語譜圖 三維短時(shí)功率譜三維短時(shí)功率譜聲音聲音 九色鹿九色鹿tf短時(shí)短時(shí)DFT顏色表示幅度顏色表示幅度語語譜譜圖圖tftf短時(shí)短時(shí)DFT清音頻譜能量分清音頻譜能量分布在整個(gè)頻率段布在整個(gè)頻率段內(nèi)、無明顯衰減內(nèi)、無明顯衰減濁音頻譜能量濁音頻譜能量集中在低頻率集中在低頻率區(qū)、衰減較快區(qū)、衰減較快基于語譜圖的清濁音分析基于語譜圖的清濁音分析靜音靜音頻譜頻譜能量能量很小很小jiuselu頻率與樂譜頻率與樂譜樂音：發(fā)音物體有規(guī)律地振動(dòng)而產(chǎn)生的具有固定樂音：發(fā)音物體有規(guī)律地振動(dòng)而產(chǎn)生的具有固定音高的音音高的音 A ., 44

33、1 ,.B ., 495 ,. C ., 556 ,. D ., 589 ,.E ., 661 ,.F ., 742 ,.G ., 833 ,.音符頻率表音符頻率表(Hz)(Hz)中音中音頻率組合頻率組合表示表示五線譜五線譜簡譜簡譜五線譜與短時(shí)傅立葉分析五線譜與短時(shí)傅立葉分析f0頻頻率率時(shí)間時(shí)間21100 ,01knNNjnkNNnnX kx n ex n WkN211001 knNNjnkNNkkx nX k eX k WNDFT的運(yùn)算量的運(yùn)算量DFTIDFTN2N*(N-1)DFT、IDFT復(fù)數(shù)乘法復(fù)數(shù)乘法DFT、IDFT復(fù)數(shù)加法復(fù)數(shù)加法快速傅立葉變換快速傅立葉變換FFTl 1965年，年

34、，J.W.Cooley 和和 J.W.Tukey 首次提出了首次提出了DFT運(yùn)算的一種快速算法運(yùn)算的一種快速算法l此后相繼出現(xiàn)了各種用于計(jì)算機(jī)平臺的改進(jìn)此后相繼出現(xiàn)了各種用于計(jì)算機(jī)平臺的改進(jìn)FFT 算法算法lFFT使使DFT的運(yùn)算時(shí)間可縮短一、二個(gè)數(shù)量級，使的運(yùn)算時(shí)間可縮短一、二個(gè)數(shù)量級，使DFT的運(yùn)算可以應(yīng)用到實(shí)際中的運(yùn)算可以應(yīng)用到實(shí)際中按時(shí)間抽取法按時(shí)間抽取法10 NnkNnX kx n WDFT11200 12NNNnnnknkNNNnnNX kx n W Wx n W21NnnjnNWe 1/2 1/2 12(21)000 2 21NNNnkrkrkNNNnrrX kx n Wxr W

35、xrW1/2 1/2 12(21)000 12 212NNNnnkrkrkNNNnrrNX kx n Wxr WxrW偶數(shù)點(diǎn)奇數(shù)點(diǎn)/2 1/2 121/200 2 2 NNrkrkNNrrX kxr Wxr W/2 1/2 1(21)2/200 2121NNrkkrkNNNrrX kxrWWxrWN/2點(diǎn)點(diǎn)DFT1212 2kNkNX kX kW XkNX kX kW Xk時(shí)間抽取法蝶形運(yùn)算時(shí)間抽取法蝶形運(yùn)算一次乘法，兩次加法一次乘法，兩次加法偶部2NX k 1 X k2 Xk X k1kNW奇部N點(diǎn)點(diǎn)DFT分解分解N點(diǎn)點(diǎn)N/2點(diǎn)點(diǎn)N/2點(diǎn)點(diǎn)N/4點(diǎn)點(diǎn)N/4點(diǎn)點(diǎn)N/4點(diǎn)點(diǎn)N/4點(diǎn)點(diǎn)2點(diǎn)點(diǎn)2點(diǎn)點(diǎn)

36、2點(diǎn)點(diǎn)2點(diǎn)點(diǎn)log2N2點(diǎn)點(diǎn)DFT002201220010110101XxWxWxxXxWxWxx0 x1x0X1X1X1(0)X1(1)x1(0) x(0)X(0)X(1)X1(2)X1(3)110NWDFT2點(diǎn)Nx1(1) x(2)x1(2) x(4)x1(3) x(6)X(2)X(3)X2(0)X2(1)x2(0) x(1)X(4)X(5)X2(2)X2(3)DFT2點(diǎn)Nx2(1) x(3)x2(2) x(5)x2(3) x(7)X(6)X(7)1NW2NW3NW11例：例：偶部奇部可繼續(xù)分解DFT4點(diǎn)NX3(0)X3(1)x3(0) x1(0) x(0)x3(1) x1(2) x(4)

37、X1(0)X1(1)DFT4點(diǎn)NX4(0)X4(1)x4(0) x1(1) x(2)x4(1) x1(3) x(6)X1(2)X1(3)110NW2NWX(0)X(1)X(2)X(3)DFT4點(diǎn)NX5(0)X5(1)x5(0) x2(0) x(1)x5(1) x2(2) x(5)X2(0)X2(1)DFT4點(diǎn)NX6(0)X6(1)x6(0) x2(1) x(3)x6(1) x2(3) x(7)X2(2)X2(3)11X(4)X(5)X(6)X(7)0NW1NW2NW3NW11110NW2NWx(0)X(0)x(4)X(1) 10NWx(2)X(2)x(6)X(3) 10NW0NW2NW 1 1

38、x(1)X(4)x(5)X(5) 10NWx(3)X(6)x(7)X(7) 10NW0NW2NW 1 10NW1NW2NW3NW 1 1 1 1N=8 按時(shí)間抽取的按時(shí)間抽取的FFT運(yùn)算流圖運(yùn)算流圖時(shí)間抽取時(shí)間抽取FFT的特點(diǎn)：的特點(diǎn)：1、奇偶抽取與比特逆序、奇偶抽取與比特逆序例：例：N=8二進(jìn)制二進(jìn)制0 000 010 100 111 001 011 101 11二進(jìn)制二進(jìn)制00 001 010 011 000 101 110 111 1原序原序01234567奇偶抽取奇偶抽取02461357偶部奇部時(shí)間抽取法流程時(shí)間抽取法流程比特比特逆序逆序 x n蝶形蝶形運(yùn)算運(yùn)算 X k比特逆序比特逆序

39、例：例：N=8輸入順序輸入順序01234567二進(jìn)制碼二進(jìn)制碼000001010011100101110111碼位倒讀碼位倒讀000100010110001101011111輸出順序輸出順序042615372、原位運(yùn)算：、原位運(yùn)算：x(0)X(0)x(4)X(1) 10NWx(2)X(2)x(6)X(3) 10NW0NW2NW 1 1x(1)X(4)x(5)X(5) 10NWx(3)X(6)x(7)X(7) 10NW0NW2NW 1 10NW1NW2NW3NW 1 1 1 1頻率抽取法頻率抽取法1112002( )( )( )( )NNNnknknkNNNNnnnX kx n Wx n Wx

40、n W前半部后半部12/20( )2NNknkNNnNx nx nWW120( )( 1)2NknkNnNx nx nW 按按k的奇偶將的奇偶將Xk分為兩部分分為兩部分 N/2點(diǎn)點(diǎn)DFT122012/20(2 )( )2 ( )2NnkNnNnrNnNXrx nx nWNx nx nW偶序偶序12(21)012/20(21)( )2 ( )2NnrNnNnnrNNnNXrx nx nWNx nx nWW奇序奇序12( )( )2( )( )2nNNx nx nx nNx nx nx nW頻率抽取法蝶形運(yùn)算頻率抽取法蝶形運(yùn)算( )x n()2Nx n1( )x n12( )x nkNW110NW

41、2NWx(0)x(1)x(2)x(3)11x(4)x(5)x(6)x(7)0NW1NW2NW3NWX(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)0NW2NW111111110NW0NW0NW0NW按頻率抽取的按頻率抽取的FFT（N=8）信號流圖）信號流圖頻率抽取法中的比特逆序頻率抽取法中的比特逆序例：例：N=8二進(jìn)制二進(jìn)制0 000 010 100 111 001 011 101 11二進(jìn)制二進(jìn)制00 001 010 011 000 101 110 111 1前半部后半部原序原序01234567蝶形運(yùn)算蝶形運(yùn)算02461357頻率抽取法流程頻率抽取法流程蝶形蝶形運(yùn)算運(yùn)算 x

42、n比特比特逆序逆序 X k101 NnkNkx nX k WNIFFT算法算法10( )( )NnkNkX kx n WIDFTDFT10( )( )NnkNkX kx n WIFFT101( )( )NnkNkx nX k WN101( )( )NnkNkxnXk WN取共軛取共軛可用FFT計(jì)算101( )( )NnkNkx nXk WN取共軛取共軛運(yùn)算量分析：運(yùn)算量分析： 乘法乘法 加法加法 DFT N2 N(N+1) FFT (N/2)log2N Nlog2N 改善比改善比 2N/log2N (N+1)/log2N例：例： DFT FFT 乘法乘法 加法加法 乘法乘法 加法加法 128

43、16384 256 65536 65792 1024 2048 516 2.7*105 2.7*105 2304 4608 1024 1.0*106 1.0*106 5120 10240乘法、加法、浮點(diǎn)、定點(diǎn)乘法、加法、浮點(diǎn)、定點(diǎn)小結(jié)小結(jié)nDTFTnDFTnFFT頻譜分辨率頻譜分辨率 Fs/128 Hz？為何不準(zhǔn)確？為何不準(zhǔn)確應(yīng)用：頻率估計(jì)應(yīng)用：頻率估計(jì)128點(diǎn)點(diǎn)DFT200 Hz單頻信號單頻信號1000 Hz采樣采樣64點(diǎn)點(diǎn) 估計(jì)出頻率估計(jì)出頻率26* Fs/128 =203.125Hz1.譜峰檢測法譜峰檢測法譜峰檢測法頻率估計(jì)為何不精確？譜峰檢測法頻率估計(jì)為何不精確？FFT點(diǎn)數(shù)有限點(diǎn)數(shù)有限 頻譜分辨率不夠頻譜分辨率不夠？能否提高估計(jì)精度？能否提高估計(jì)精度(不增加不增加FFT點(diǎn)數(shù)點(diǎn)數(shù))(t)exp()iiifAjt頻率估計(jì)方法頻率估計(jì)方法2：導(dǎo)數(shù)法：導(dǎo)數(shù)法( )( )()( )nniiiftjf t時(shí)域求導(dǎo)時(shí)域求導(dǎo) ( )222n2-|( )|()( )| ( )|nniiiiiftdtjf tdtf tdt 平方積分平方積分2( )202220|( )|( )|niniiftdf td 00002222|( )|2|( )|knkinkkkF kNF k離散離散Parseval定理定理主瓣能量主瓣能量傅立葉變換性質(zhì)傅立葉變換性質(zhì)100點(diǎn)點(diǎn)DFT導(dǎo)數(shù)法估計(jì)導(dǎo)數(shù)