1、第5章 有限長離散變換正交變換DFT定義DTFT與DFT的關系DFT的性質DFT的快速算法：FFT基序列定義5.1 正交變換特性：能量保持分析式綜合式時域周期延拓頻率采樣離散時間傅立葉變換DTFT離散傅立葉變換DFT5.2 離散傅里葉變換DTFTDFT正變換N點有限長序列IDTFTIDFT反變換離散傅立葉變換 Discrete Fourier Transform DFT 定義IDFT證明證明:DFT幅度譜DFT相位譜性質定義周期性快速算法直流圓周時反證明：DFT的周期性N為xn的長度DFT的運算量DFTIDFTN2N*(N-1)DFT、IDFT復數乘法DFT、IDFT復數加法例1：正頻率負頻率

2、Xk的DFT頻譜5.3 DTFT與DFT的關系離散連續插值插值公式DFT用于DTFT的數值估算 估計N點序列補零M大小對Xk的影響? 解:(1)(2)增大M可以提高信號DFT的頻率分辨率N大小對信號周期估計的影響? N=128和N=129時的DFT頻譜N為周期的整數倍頻譜的尖峰為正弦的頻率N不是周期的整數倍出現模糊單頻模擬信號DFT寬頻DFT頻譜原因？ 129點128點時域上看周期延拓周期延拓波形的突變產生多種頻率分量頻域上看128點129點yn與xn的關系？ 頻域采樣離散連續例：對 進行8點均勻抽樣 其逆變換若做4點抽樣其逆變換混疊頻域采樣率不夠，時域信號會發生混疊序列的循環移位5.4 圓周

3、卷積移位與循環移位0N-10N-1循環移2位周期延拓移2位循環移位的周期循環移位的時反性質圓周卷積回顧：N點序列的線性卷積yLn的長度？N點序列的圓周卷積yCn的長度？LM+N-10N-10M-1L0N-1LM+N-10M-1L0M-1xn0N-1hn線性卷積與圓周卷積的關系線性卷積圓周卷積00M+N-1yn0L=M+N-1點 圓周卷積 = 線性卷積5.5 有限長序列的分類共軛對稱：共軛反對稱：任意復序列可分解為共軛對稱和共軛反對稱部分共軛對稱部分共軛反對稱部分特例：實序列偶對稱：奇對稱：任意實序列可分解為偶對稱和奇對稱部分偶對稱部分奇對稱部分圓周共軛對稱：圓周共軛反對稱：N點序列可分解為圓周

4、共軛對稱和圓周共軛反對稱部分圓周共軛對稱部分圓周共軛對稱部分幾何對稱：幾何反對稱：對稱中心：(N-1)/25.6 DFT的對稱關系復序列DFT的對稱關系序列DFT頻譜共軛、時反實部、虛部圓對稱、反對稱實序列DFT的對稱關系DFT頻譜對稱關系 偶對稱、奇對稱序列DFT頻譜xn=cos(0.1n)的DFT頻譜例：xn=cos(0.1n)的DFT頻譜5.7 DFT定理已知線性：循環時移時移DTFTDFT幅度(功率)譜不變，僅影響相位譜循環頻移頻移DFT對偶：DFTN點圓周卷積DTFT卷積調制(加窗)DFTDTFT帕斯瓦爾公式DFTDTFT兩個實序列DFT的計算5.9 實序列DFT的計算DFT的對稱性

5、基本思想：利用DFT的對稱性2N點實序列DFT的計算2N點實序列vn偶數點奇數點GK和Hk可用前一方法兩個有限長序列的線性卷積5.10 用DFT計算線性卷積補零補零基本思想：線性卷積圓周卷積 DFT計算循環前綴XN-M+1, XN-1X0, , XN-M, XN-M+1, XN-1循環前綴線性卷積圓周卷積用途：只需計算線性卷積的部分值有限長序列與無限長序列的線性卷積基本思想：無限長卷積有限長卷積之和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線性卷

6、積與hn 做L=N3 圓計算量 線計算量N=128 圓計算量 = 8% 線計算量5.11 短時(加窗)傅立葉變換基音周期不同加窗語譜圖 三維短時功率譜聲音 九色鹿tf短時DFT顏色表示幅度語譜圖tftf短時DFT清音頻譜能量分布在整個頻率段內、無明顯衰減濁音頻譜能量集中在低頻率區、衰減較快基于語譜圖的清濁音分析靜音頻譜能量很小jiuselu頻率與樂譜樂音：發音物體有規律地振動而產生的具有固定音高的音 A ., 441 ,.B ., 495 ,. C ., 556 ,. D ., 589 ,.E ., 661 ,.F ., 742 ,.G ., 833 ,.音符頻率表(Hz)中音頻率組合表示五線

7、譜簡譜五線譜與短時傅立葉分析f0頻率時間DFT的運算量DFTIDFTN2N*(N-1)DFT、IDFT復數乘法DFT、IDFT復數加法快速傅立葉變換FFT(第11章) 1965年，J.W.Cooley 和 J.W.Tukey 首次提出了DFT運算的一種快速算法此后相繼出現了各種用于計算機平臺的改進FFT 算法FFT使DFT的運算時間可縮短一、二個數量級，使DFT的運算可以應用到實際中按時間抽取法DFT頻域分為前后兩半偶數點奇數點N/2點DFT時間抽取法蝶形運算一次乘法，兩次加法偶部奇部N點DFT分解N點N/2點N/2點N/4點N/4點N/4點N/4點2點2點2點2點log2N2點DFT例：偶部

8、奇部可繼續分解N=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碼位倒讀000100010110001101011111輸出順序04261537時間抽取法流程比特逆序蝶形運算2、原位運算：頻率抽取法前半部后半部按k的奇偶將Xk分為兩部分 N/2點DFT偶序奇序頻率抽取法蝶形運算按頻率抽取的FFT（N=8）信號流圖頻率抽取法中的比特逆序例：N=8二進制0 000 010 100 111 001 011 101 11二進制00 001 010 011 000 101 110 111 1前半部后半部原序01234567蝶形運算02461357頻率抽取法流程蝶形運算比特逆序IFFT算法IDFTDFTIFFT取共軛可用FFT計算取共軛運算量分析： 乘法 加法 DFT N2 N(N+1) FFT (N/2)log2N Nlog2N 改善比 2N/log2N (N+1)/log2N例： DFT FFT 乘法 加法 乘法 加法