第5章有限長離散變換

1、第第5 5章章 有限長離散變換有限長離散變換n正交變換正交變換nDFTDFT定義定義nDTFTDTFT與與DFTDFT的關系的關系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時域周期延拓時域周期延拓頻率采樣頻率采樣離散時間離散時間傅立葉變換傅立葉變換DTFT離散離散傅立葉變換傅立葉變換DFT5.

2、2 5.2 離散傅里葉變換離散傅里葉變換 12/2/0Njjkn Nk NnX kX ex n ennjjenxeX)(DTFTDFT正正變變換換01kNN點有限長序列點有限長序列 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的長度的長度10 ,)(

4、)(10102NkWnxenxkXNnnkNNnNknj10102)()(1)(NknkNNkNknjWkXekXNnxDFT的運算量的運算量DFTIDFTN2N*(N-1)DFT、IDFT復數(shù)乘法復數(shù)乘法DFT、IDFT復數(shù)加法復數(shù)加法 2101010DFTkmjDFTkmNNnx nX kotherwisenmx nX kWeotherwise 例例1： 2NDFTcos 2/,01 01x nrn NnNrN例 ：求長度為 的序列的： 2/2/1122jrn Njrn NrnrnNNx neeWW 1100/21/220NNr k Nr k NNNnnNkrX kWWNkNrotherw

5、ise正頻率正頻率負頻率負頻率Xk的的DFT頻譜頻譜16N 3r 5.3 DTFT與與DFT的關系的關系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 估計估計N點序列點序列 01 011ex nnNx nNnM 補零補零M大小對大小對Xk的影響的影響? cos 2/,3,16(1) 16x nrn NrN例：序列求其點DFT;(2) 將(1)中的序列以補零方式加長到256，求其256點DFT (1) cos 3/4x nn解:(1)(2)增大增大M可以提高信號可以提高信號DFT的頻率分辨率的頻率分辨率頻域取樣中兩相鄰點之間的頻率間隔頻域取樣中兩相鄰點之間的頻率間隔N大小對信號周期估計的影響大小對信號周期估計的影響? 60 cos(2 () ) (64256x nn例：序列周期為）N=128和和N=129時的時的DFT

7、頻譜頻譜N為周期的整數(shù)倍為周期的整數(shù)倍頻譜的頻譜的尖峰尖峰為正弦的頻率為正弦的頻率N不是周期的整數(shù)倍不是周期的整數(shù)倍出現(xiàn)出現(xiàn)模糊模糊單頻模擬信號單頻模擬信號DFT寬頻寬頻DFT頻譜頻譜原因？原因？ 129點點128點點時域上看時域上看周期延拓周期延拓波形的突變產(chǎn)生多種頻率分量波形的突變產(chǎn)生多種頻率分量頻域上看頻域上看128點點129點點DTFTIDFTIDTFTDFT ()() kjjx nX eX eY Ky n 頻域采樣yn與與xn的關系？的關系？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當長度小于或等于 時， 0 12 3 4 5x n， ， ， ， ，例例：jX e對對 進行進行8點均勻抽樣點均勻抽樣 2/8)k( (2/4k（） ?y n 其逆變換其逆變換若做若做4點抽樣點抽樣 ?y n 其逆變換其逆變換 01ny nx nmNnN 888070 1 2 3 4 5 0 0y nx nx nx nny n點抽樣： 444054 6 2 3 4 6y nx nx nx nny n點抽樣：， ， ，

9、， ，混疊混疊頻域采樣率不夠，時域信號會發(fā)生混疊頻域采樣率不夠，時域信號會發(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)移位的時反循環(huán)移位的時反()NNxnmxnNmn性質(zhì)性質(zhì)圓周卷積圓周卷積 10NLmyng m h nm g nh nN設、為 點長的序列21LN回顧：回顧：N N點序列的點序列的線性卷積線性卷積y yL Lnn的長

10、度？的長度？ 10N NCNmyng nh ng m hn mN N點序列的圓周卷積點序列的圓周卷積y yC Cnn的長度？的長度？LNLM+N-10 N-10M-1L0 N-1LM+N-10M-1L0M-1xn0 N-1hn線性卷積線性卷積與與圓周卷積圓周卷積的關系的關系線性卷積線性卷積圓周卷積圓周卷積00M+N-1yn0L=M+N-1點點 圓周卷積圓周卷積 = 線性卷積線性卷積5.5 有限長序列的分類有限長序列的分類共軛對稱：共軛對稱：* x nx -n* x n-x -n共軛反對稱：共軛反對稱： cscax nxnxn任意復序列可分解為共軛對稱和共軛反對稱部分任意復序列可分解為共軛對稱和

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

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

13、csxnRe X k pcaxnIm jX k圓對稱、圓對稱、反對稱反對稱實序列實序列DFT的對稱關系的對稱關系Re Re NX kXk* NX kXkIm ImNX kXk | | | |NX kXkarg arg NX kXk DFT頻譜頻譜對稱關系對稱關系 pexnRe X k poxnIm jX k偶對稱、偶對稱、奇對稱奇對稱序列序列DFT頻譜頻譜| | | |NX kXkarg arg NX kXk 為何實序列有這樣的對稱關系？為何實序列有這樣的對稱關系？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)時移循環(huán)時移00( )knNNg nnWG k時移時移00()j njeG eg nnDTFTDFT幅度幅度(功率功率)譜不變，僅影響相位譜譜不變，僅影響相位譜00() ()jnjg nG ee 循環(huán)頻移循環(huán)頻移00 k nNNWg nGkk頻移頻移調(diào)幅廣播調(diào)幅廣播DFT對偶：對偶： NG nNgk g nG kDFTN點圓周卷積點圓周卷積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兩個實序列兩個實序列DFT的計算的計算5.9 實序列實序列DFT的計算的計算 x ng njh n令 *1212NNG kX kXkH kX kXkjDFT的對稱性的對稱性基本思想：利用基本思想：利用DFT的對稱性的對稱性2N點實序列點實序列DFT的計算的計算2N點實序列點實序列vn 2111212222000112002221021NNNnknknkNNNnnnN

16、NnknkkNNNnnkNNNv nv n Wvn WvnWg n Wh n W WGkWHkkN， 2g nvn 21h nvn偶數(shù)點偶數(shù)點奇數(shù)點奇數(shù)點GK和和Hk可用前一方法可用前一方法兩個有限長序列的線性卷積兩個有限長序列的線性卷積5.10 用用DFT計算線性卷積計算線性卷積1LMN LCeeyng nh nyngnL h n LCeeyng nh nyngnL h n Ng n點序列補零補零 0101eg nnNgnNnL Mh n點序列 0101eh nnMh nMnL補零補零基本思想：線性卷積基本思想：線性卷積圓周卷積圓周卷積 DFT計算計算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)造 線性卷積線性卷積=圓周卷積圓周卷積 簡化信號估計簡化信號估計有限長序列與無限長序列的線性卷積有限長序列與無限長序列的線性卷積 10Mlh lMx ny nh l x nlh nx n設為點有限長序列，為無限長序列求：基本思想：無限長卷積基本思想：無限長卷積有限長卷積之

18、和有限長卷積之和0M-1 0 xnhn1. 重疊相加法重疊相加法N-1線線性性卷卷積積0與與hn 做做L=M+N-1 點點圓周卷積圓周卷積N-12N-1重疊相加重疊相加0yn2個個 (M+N-1)點點 DFT0M-1 0 xnhn2. 重疊保留法重疊保留法N-1線線性性卷卷積積與與hn 做做L=N3 圓圓計算量計算量 線線計算量計算量N=128 圓圓計算量計算量 = 8% 線線計算量計算量5.115.11 短時短時( (加窗加窗) )傅立葉變換傅立葉變換基音周期不同基音周期不同10()( )( )Njj mnnmXew m x m e加窗加窗語譜圖語譜圖 三維短時功率譜三維短時功率譜聲音聲音

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

20、 833 ,.音符音符頻率頻率表表(Hz)中音中音頻率頻率組合組合表示表示五線譜五線譜簡譜簡譜五線譜五線譜與與短時傅立葉分析短時傅立葉分析f0頻頻率率時間時間21100 ,01knNNjnkNNnnX kx n ex nWkN211001 knNNjnkNNkkx nX k eX k WNDFT的運算量的運算量DFTIDFTN2N*(N-1)DFT、IDFT復數(shù)乘法復數(shù)乘法DFT、IDFT復數(shù)加法復數(shù)加法快速傅立葉變換快速傅立葉變換FFT(第第11章章)l 1965年，年，J.W.Cooley 和和 J.W.Tukey 首次提出了首次提出了DFT運算的一種快速算法運算的一種快速算法l此后相繼出

21、現(xiàn)了各種用于計算機平臺的改進此后相繼出現(xiàn)了各種用于計算機平臺的改進FFT 算法算法lFFT使使DFT的運算時間可縮短一、二個數(shù)量級，使的運算時間可縮短一、二個數(shù)量級，使DFT的運算可以應用到實際中的運算可以應用到實際中按時間抽取法按時間抽取法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ù)點奇數(shù)點/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點點DFT1212 2kNkNX kX kW XkNX kX kW Xk時間抽取法蝶形運算時間抽取法蝶形運算一次乘法，兩次加法一次乘法，兩次加法偶部2NX k 1 X k2 Xk X k1kNW奇部N點點DFT分解分解N點點N/2點點N/2點點N/4點點N/4點點N/4點點N/4點點2點點2點點2點點2點點log2N2點點DFT002201220010110101XxWxWxxX

23、xWxWxx0 x1x0X1X1X1(0)X1(1)x1(0) x(0)X(0)X(1)X1(2)X1(3)110NWDFT2點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點Nx2(1) x(3)x2(2) x(5)x2(3) x(7)X(6)X(7)1NW2NW3NW11例：例：偶部奇部可繼續(xù)分解DFT4點NX3(0)X3(1)x3(0) x1(0) x(0)x3(1) x1(2) x(4)X1(0)X1(1)DFT4點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點NX5(0)X5(1)x5(0) x2(0) x(1)x5(1) x2(2) x(5)X2(0)X2(1)DFT4點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 按時間抽取的按時間抽取的FFT運算流圖運算流圖時間抽取時間抽取FFT的特點：的特點：1、奇偶抽取與比特逆序、奇偶抽取與比特逆序例：例：N=8二進制二進制0 000 010 100 111 001 011 101 11二進制二進制00 001 010 011 000 101 110 111 1原序原序01234567奇偶抽取奇偶抽取02461357偶部奇部比特逆序比特逆序例：例：N=8輸入順序輸入順序01234567二進制碼二進制碼000001010011100101110111碼位倒讀碼位倒讀000100010110001101

26、011111輸出順序輸出順序04261537時間抽取法流程時間抽取法流程比特比特逆序逆序 x n蝶形蝶形運算運算 X k2、原位運算：、原位運算：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點點DFT122012/20(2 )( )2 ( )2NnkNnNnrNnNXrx nx nWNx nx nW偶序偶序12(21)012/20(21)