第5章有限長(zhǎng)離散變換

1、第第5 5章章 有限長(zhǎng)離散變換有限長(zhǎng)離散變換n正交變換正交變換nDFTDFT定義定義nDTFTDTFT與與DFTDFT的關(guān)系的關(guān)系nDFTDFT的性質(zhì)的性質(zhì)nDFTDFT的快速算法：的快速算法：FFTFFT基序列基序列n定義定義5.1 5.1 正交變換正交變換n特性：能量保持特性：能量保持1*0 , NnX kx nk n分析式分析式綜合式綜合式01kN101 , Nkx nX kk nN1*01,1 , , 0,Nnlkk nl nlkN112200 NNnkx nX k時(shí)域周期延拓時(shí)域周期延拓頻率采樣頻率采樣離散時(shí)間離散時(shí)間傅立葉變換傅立葉變換DTFT離散離散傅立葉變換傅立葉變換DFT5.

2、2 5.2 離散傅里葉變換離散傅里葉變換 12/2/0Njjkn Nk NnX kX ex n ennjjenxeX)(DTFTDFT正正變變換換01kNN點(diǎn)有限長(zhǎng)序列點(diǎn)有限長(zhǎng)序列 deeXnxnjj21IDTFT 12/01,01Njkn Nkx nX k enNNIDFT反反變變換換離散傅立葉變換離散傅立葉變換 Discrete Fourier Transform DFT 定義定義 10DFT 01NknNnX kx nWkN 101IDFT01NknNkx nX k WnNN2/jNNWe10102)(1)(1)(NknkNNkNknjWkXNekXNnxotherwiserNlkNee

3、eWNlkjlkjNnnklNjNnnlkN011/2210210IDFT證明證明證明證明: 11111000001100111NNNNNk l nlnknlnNNNNnnknkNNk l nNknx nWX k WWX k WNNX kWX lN jkX kX k eDFT幅度譜幅度譜 k X kDFT相位譜相位譜2/jNNWe性質(zhì)性質(zhì)222knjkn NNnrN nNNNNWeWWWW01NNNnN nNNWWWW 1021022102NnnNkjNnnjnNkjNnnNNkjkXenxeenxenxNkX證明：證明：DFT的周期性的周期性 X kNX kN為為xn的長(zhǎng)度的長(zhǎng)度10 ,)(

4、)(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 例例1： 2NDFTcos 2/,01 01x nrn NnNrN例 ：求長(zhǎng)度為 的序列的： 2/2/1122jrn Njrn NrnrnNNx neeWW 1100/21/220NNr k Nr k NNNnnNkrX kWWNkNrotherw

5、ise正頻率正頻率負(fù)頻率負(fù)頻率Xk的的DFT頻譜頻譜16N 3r 5.3 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 MjenX kX exn eX e 2/ kj

6、k Mx nX eMN 估計(jì)估計(jì)N點(diǎn)序列點(diǎn)序列 01 011ex nnNx nNnM 補(bǔ)零補(bǔ)零M大小對(duì)大小對(duì)Xk的影響的影響? cos 2/,3,16(1) 16x nrn NrN例：序列求其點(diǎn)DFT;(2) 將(1)中的序列以補(bǔ)零方式加長(zhǎng)到256，求其256點(diǎn)DFT (1) cos 3/4x nn解:(1)(2)增大增大M可以提高信號(hào)可以提高信號(hào)DFT的頻率分辨率的頻率分辨率頻域取樣中兩相鄰點(diǎn)之間的頻率間隔頻域取樣中兩相鄰點(diǎn)之間的頻率間隔N大小對(duì)信號(hào)周期估計(jì)的影響大小對(duì)信號(hào)周期估計(jì)的影響? 60 cos(2 () ) (64256x nn例：序列周期為）N=128和和N=129時(shí)的時(shí)的DFT

7、頻譜頻譜N為周期的整數(shù)倍為周期的整數(shù)倍頻譜的頻譜的尖峰尖峰為正弦的頻率為正弦的頻率N不是周期的整數(shù)倍不是周期的整數(shù)倍出現(xiàn)出現(xiàn)模糊模糊單頻模擬信號(hào)單頻模擬信號(hào)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)DTFTIDFTIDTFTDFT ()() kjjx nX eX eY Ky n 頻域采樣yn與與xn的關(guān)系？的關(guān)系？DTFTDFT 頻域采樣頻域采樣離散離散連續(xù)連續(xù) 2/2jjk NklkNlNY kX eX ex l W 1100101011101110NN

8、knklknNNNkklNk n lNlknNk n lNky nY k Wx l W WNNx lWNx nmNnNrnmMWotherwiseN 01x nNy nx nnN當(dāng)長(zhǎng)度小于或等于 時(shí)， 0 12 3 4 5x n， ， ， ， ，例例：jX e對(duì)對(duì) 進(jìn)行進(jìn)行8點(diǎn)均勻抽樣點(diǎn)均勻抽樣 2/8)k( (2/4k（） ?y n 其逆變換其逆變換若做若做4點(diǎn)抽樣點(diǎn)抽樣 ?y n 其逆變換其逆變換 01ny nx nmNnN 888070 1 2 3 4 5 0 0y nx nx nx nny n點(diǎn)抽樣： 444054 6 2 3 4 6y nx nx nx nny n點(diǎn)抽樣：， ， ，

9、， ，混疊混疊頻域采樣率不夠，時(shí)域信號(hào)會(huì)發(fā)生混疊頻域采樣率不夠，時(shí)域信號(hào)會(huì)發(fā)生混疊序列的循環(huán)移位序列的循環(huán)移位0000010modNnx nnnnNxnnx Nnnnnmmn（）56nx26nx x n61xn64xn5.4 圓周卷積圓周卷積移位移位與與循環(huán)移位循環(huán)移位0N-10N-1循環(huán)移循環(huán)移2位位周期延拓周期延拓移移2 2位位()NNxnxNn循環(huán)移位的周期循環(huán)移位的周期循環(huán)移位的時(shí)反循環(huán)移位的時(shí)反()NNxnmxnNmn性質(zhì)性質(zhì)圓周卷積圓周卷積 10NLmyng m h nm g nh nN設(shè)、為 點(diǎn)長(zhǎng)的序列21LN回顧：回顧：N N點(diǎn)序列的點(diǎn)序列的線性卷積線性卷積y yL Lnn的長(zhǎng)

10、度？的長(zhǎng)度？ 10N NCNmyng nh ng m hn mN N點(diǎn)序列的圓周卷積點(diǎn)序列的圓周卷積y yC Cnn的長(zhǎng)度？的長(zhǎng)度？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) 圓周卷積圓周卷積 = 線性卷積線性卷積5.5 有限長(zhǎng)序列的分類有限長(zhǎng)序列的分類共軛對(duì)稱：共軛對(duì)稱：* x nx -n* x n-x -n共軛反對(duì)稱：共軛反對(duì)稱： cscax nxnxn任意復(fù)序列可分解為共軛對(duì)稱和共軛反對(duì)稱部分任意復(fù)序列可分解為共軛對(duì)稱和

11、共軛反對(duì)稱部分共軛對(duì)稱部分共軛對(duì)稱部分共軛反對(duì)稱部分共軛反對(duì)稱部分 2caxnx nx -n/ 2csxnx nx -n/特例：實(shí)序列特例：實(shí)序列偶對(duì)稱：偶對(duì)稱： x nx -n x n-x -n奇對(duì)稱：奇對(duì)稱： eox nx nx n任意實(shí)序列可分解為偶對(duì)稱和奇對(duì)稱部分任意實(shí)序列可分解為偶對(duì)稱和奇對(duì)稱部分 2ox nx nx -n/ 2ex nx nx -n/偶對(duì)稱部分偶對(duì)稱部分奇對(duì)稱部分奇對(duì)稱部分圓周共軛對(duì)稱：圓周共軛對(duì)稱：* 01Nx nxnx N -nnN* 01Nx nxnx N -nnN 圓周共軛反對(duì)稱：圓周共軛反對(duì)稱： pcspcax nxn xnN點(diǎn)序列可分解為圓周共軛對(duì)稱和圓

12、周共軛反對(duì)稱部分點(diǎn)序列可分解為圓周共軛對(duì)稱和圓周共軛反對(duì)稱部分* 2pcsxnx nx N -n/* 2 pcaxnx nx N -n/圓周共軛對(duì)稱圓周共軛對(duì)稱部分部分圓周共軛反對(duì)圓周共軛反對(duì)稱部分稱部分幾何對(duì)稱：幾何對(duì)稱： 101x nx NnnN 101x nx NnnN 幾何反對(duì)稱：幾何反對(duì)稱：對(duì)稱中心：對(duì)稱中心：(N-1)/25.6 DFT的對(duì)稱關(guān)系的對(duì)稱關(guān)系復(fù)序列復(fù)序列DFT的對(duì)稱關(guān)系的對(duì)稱關(guān)系序列序列DFT頻譜頻譜* x n* NXk* Nxn* Xk共軛、共軛、時(shí)反時(shí)反 Re x n*1 2pcsNNXkXkXkIm jx n*1 2pcaNNXkXkXk實(shí)部、實(shí)部、虛部虛部 p

13、csxnRe X k pcaxnIm jX k圓對(duì)稱、圓對(duì)稱、反對(duì)稱反對(duì)稱實(shí)序列實(shí)序列DFT的對(duì)稱關(guān)系的對(duì)稱關(guān)系Re Re NX kXk* NX kXkIm ImNX kXk | | | |NX kXkarg arg NX kXk DFT頻譜頻譜對(duì)稱關(guān)系對(duì)稱關(guān)系 pexnRe X k poxnIm jX k偶對(duì)稱、偶對(duì)稱、奇對(duì)稱奇對(duì)稱序列序列DFT頻譜頻譜| | | |NX kXkarg arg NX kXk 為何實(shí)序列有這樣的對(duì)稱關(guān)系？為何實(shí)序列有這樣的對(duì)稱關(guān)系？xn=cos(0.1n)的的DFT頻譜頻譜例：例：xn=cos(0.1n)的的DFT頻譜頻譜Re Re NX kXkIm ImNX

14、 kXk 5.7 DFT定理定理 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 nGkk頻移頻移調(diào)幅廣播調(diào)幅廣播DFT對(duì)偶：對(duì)偶： NG nNgk g nG kDFTN點(diǎn)圓周卷積點(diǎn)圓周卷積10 ( )( )NNmg m h nmG k H k ()()jjg nh nG eH eDTFT卷積卷積調(diào)制調(diào)制(加窗加窗)101 NNmg n

15、h nG m HkmNdeHeGnhngjj)()(21)(DFTDTFT帕斯瓦爾公式帕斯瓦爾公式1122001NNnkx nXkN*1 ()()2jjng n h nG eH edDFTDTFTNnNnkHkGNnhng0*0*1兩個(gè)實(shí)序列兩個(gè)實(shí)序列DFT的計(jì)算的計(jì)算5.9 實(shí)序列實(shí)序列DFT的計(jì)算的計(jì)算 x ng njh n令 *1212NNG kX kXkH kX kXkjDFT的對(duì)稱性的對(duì)稱性基本思想：利用基本思想：利用DFT的對(duì)稱性的對(duì)稱性2N點(diǎn)實(shí)序列點(diǎn)實(shí)序列DFT的計(jì)算的計(jì)算2N點(diǎn)實(shí)序列點(diǎn)實(shí)序列vn 2111212222000112002221021NNNnknknkNNNnnnN

16、NnknkkNNNnnkNNNv nv n Wvn WvnWg n Wh n W WGkWHkkN， 2g nvn 21h nvn偶數(shù)點(diǎn)偶數(shù)點(diǎn)奇數(shù)點(diǎn)奇數(shù)點(diǎn)GK和和Hk可用前一方法可用前一方法兩個(gè)有限長(zhǎng)序列的線性卷積兩個(gè)有限長(zhǎng)序列的線性卷積5.10 用用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 nm

17、G k H k循環(huán)前綴循環(huán)前綴 10Lly nh nx nh l x nlXN-M+1, XN-1X0, , XN-M, XN-M+1, XN-1循環(huán)前綴循環(huán)前綴線性卷積線性卷積 10NeNly nh nx nhl xnl圓周卷積圓周卷積12MnNM01nN 01y ny nnN 01 eY kX knNHk用途：構(gòu)造用途：構(gòu)造 線性卷積線性卷積=圓周卷積圓周卷積 簡(jiǎn)化信號(hào)估計(jì)簡(jiǎn)化信號(hào)估計(jì)有限長(zhǎng)序列與無(wú)限長(zhǎng)序列的線性卷積有限長(zhǎng)序列與無(wú)限長(zhǎng)序列的線性卷積 10Mlh lMx ny nh l x nlh nx n設(shè)為點(diǎn)有限長(zhǎng)序列，為無(wú)限長(zhǎng)序列求：基本思想：無(wú)限長(zhǎng)卷積基本思想：無(wú)限長(zhǎng)卷積有限長(zhǎng)卷積之

18、和有限長(zhǎng)卷積之和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ì)算量5.115.11 短時(shí)短時(shí)( (加窗加窗) )傅立葉變換傅立葉變換基音周期不同基音周期不同10()( )( )Njj mnnmXew m x m e加窗加窗語(yǔ)譜圖語(yǔ)譜圖 三維短時(shí)功率譜三維短時(shí)功率譜聲音聲音

19、九色鹿九色鹿tf短時(shí)短時(shí)DFT顏色顏色表示表示幅度幅度語(yǔ)語(yǔ)譜譜圖圖tftf短時(shí)短時(shí)DFT清音清音頻譜能量分頻譜能量分布在整個(gè)頻率段布在整個(gè)頻率段內(nèi)、無(wú)明顯衰減內(nèi)、無(wú)明顯衰減濁音濁音頻譜能量頻譜能量集中在低頻率集中在低頻率區(qū)、衰減較快區(qū)、衰減較快基于基于語(yǔ)譜圖語(yǔ)譜圖的清濁音分析的清濁音分析靜音靜音頻譜頻譜能量能量很小很小jiuselu頻率頻率與與樂(lè)譜樂(lè)譜樂(lè)音樂(lè)音：發(fā)音物體有規(guī)律地振動(dòng)而產(chǎn)生的具有固定：發(fā)音物體有規(guī)律地振動(dòng)而產(chǎn)生的具有固定音高的音音高的音 A ., 441 ,.B ., 495 ,. C ., 556 ,. D ., 589 ,.E ., 661 ,.F ., 742 ,.G .,

20、 833 ,.音符音符頻率頻率表表(Hz)中音中音頻率頻率組合組合表示表示五線譜五線譜簡(jiǎn)譜簡(jiǎn)譜五線譜五線譜與與短時(shí)傅立葉分析短時(shí)傅立葉分析f0頻頻率率時(shí)間時(shí)間21100 ,01knNNjnkNNnnX kx n ex nWkN211001 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ù)加法快速傅立葉變換快速傅立葉變換FFT(第第11章章)l 1965年，年，J.W.Cooley 和和 J.W.Tukey 首次提出了首次提出了DFT運(yùn)算的一種快速算法運(yùn)算的一種快速算法l此后相繼出

21、現(xiàn)了各種用于計(jì)算機(jī)平臺(tái)的改進(jìn)此后相繼出現(xiàn)了各種用于計(jì)算機(jī)平臺(tái)的改進(jìn)FFT 算法算法lFFT使使DFT的運(yùn)算時(shí)間可縮短一、二個(gè)數(shù)量級(jí)，使的運(yùn)算時(shí)間可縮短一、二個(gè)數(shù)量級(jí)，使DFT的運(yùn)算可以應(yīng)用到實(shí)際中的運(yùn)算可以應(yīng)用到實(shí)際中按時(shí)間抽取法按時(shí)間抽取法10 NnkNnX kx nWDFT11200 12NNNnnnknkNNNnnNX kx nW Wx nW21NnnjnNWe 頻域分為前后兩半頻域分為前后兩半1/2 1/2 12(21)000 2 21NNNnkrkrkNNNnrrX kx nWx r Wx rW1/2 1/2 12(21)000 12 212NNNnnkrkrkNNNnrrNX kx

22、 nWx r Wx rW偶數(shù)點(diǎn)奇數(shù)點(diǎn)/2 1/2 121/200 2 2 NNrkrkNNrrX kx r Wx r W/2 1/2 1(21)2/200 2121NNrkkrkNNNrrX kx rWWx rWN/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)2點(diǎn)點(diǎn)2點(diǎn)點(diǎn)log2N2點(diǎn)點(diǎn)DFT002201220010110101XxWxWxxX

23、xWxWxx0 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)X1(0)X1(1)DFT4點(diǎn)NX4(0)X4(1)x4(0) x1(1) x(2)x

24、4(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 1x(1)X(4)x(5)X(5) 10NWx(3)X(6)x(7)X(7) 10NW0

25、NW2NW 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偶部奇部比特逆序比特逆序例：例：N=8輸入順序輸入順序01234567二進(jìn)制碼二進(jìn)制碼000001010011100101110111碼位倒讀碼位倒讀000100010110001101

26、011111輸出順序輸出順序04261537時(shí)間抽取法流程時(shí)間抽取法流程比特比特逆序逆序 x n蝶形蝶形運(yùn)算運(yùn)算 X k2、原位運(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 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)