第5章有限长离散变换

1、第第5 5章章 有限长离散变换有限长离散变换n正交变换正交变换nDFTDFT定义定义nDTFTDTFT与与DFTDFT的关系的关系nDFTDFT的性质的性质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性质性质222knjkn NNnrN nNNNNWeWWWW01NNNnN nNNWWWW 1021022102NnnNkjNnnjnNkjNnnNNkjkXenxeenxenxNkX证明：证明：DFT的周期性的周期性 X kNX kN为为xn的长度的长度10 ,)(

4、)(10102NkWnxenxkXNnnkNNnNknj10102)()(1)(NknkNNkNknjWkXekXNnxDFT的运算量的运算量DFTIDFTN2N*(N-1)DFT、IDFT复数乘法复数乘法DFT、IDFT复数加法复数加法 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 离散离散连续连续212/1 /22/2/02sin1221sin2jNkNjk NNjk N njk NnNkeeeNkeN 插值插值 12/1 /202sin122sin2Njk NNjkNkX eX keNkNN 插值公式插值公式DFT用于用于DTFT的数值估算的数值估算 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为周期的整数倍为周期的整数倍频谱的频谱的尖峰尖峰为正弦的频率为正弦的频率N不是周期的整数倍不是周期的整数倍出现出现模糊模糊单频模拟信号单频模拟信号DFT宽频宽频DFT频谱频谱原因？原因？ 129点点128点点时域上看时域上看周期延拓周期延拓波形的突变产生多种频率分量波形的突变产生多种频率分量频域上看频域上看128点点129点点DTFTIDFTIDTFTDFT ()() kjjx nX eX eY Ky n 频域采样yn与与xn的关系？的关系？DTFTDFT 频域采样频域采样离散离散连续连续 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、， ，混叠混叠频域采样率不够，时域信号会发生混叠频域采样率不够，时域信号会发生混叠序列的循环移位序列的循环移位0000010modNnx nnnnNxnnx Nnnnnmmn（）56nx26nx x n61xn64xn5.4 圆周卷积圆周卷积移位移位与与循环移位循环移位0N-10N-1循环移循环移2位位周期延拓周期延拓移移2 2位位()NNxnxNn循环移位的周期循环移位的周期循环移位的时反循环移位的时反()NNxnmxnNmn性质性质圆周卷积圆周卷积 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循环时移循环时移00( )knNNg nnWG k时移时移00()j njeG eg nnDTFTDFT幅度幅度(功率功率)谱不变，仅影响相位谱谱不变，仅影响相位谱00() ()jnjg nG ee 循环频移循环频移00 k nNNWg nGkk频移频移调幅广播调幅广播DFT对偶：对偶： NG nNgk g nG kDFTN点圆周卷积点圆周卷积10 ( )( )NNmg m h nmG k H k ()()jjg nh nG eH eDTFT卷积卷积调制调制(加窗加窗)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偶数点偶数点奇数点奇数点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循环前缀循环前缀 10Lly nh nx nh l x nlXN-M+1, XN-1X0, , XN-M, XN-M+1, XN-1循环前缀循环前缀线性卷积线性卷积 10NeNly nh nx nhl xnl圆周卷积圆周卷积12MnNM01nN 01y ny nnN 01 eY kX knNHk用途：构造用途：构造 线性卷积线性卷积=圆周卷积圆周卷积 简化信号估计简化信号估计有限长序列与无限长序列的线性卷积有限长序列与无限长序列的线性卷积 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清音清音频谱能量分频谱能量分布在整个频率段布在整个频率段内、无明显衰减内、无明显衰减浊音浊音频谱能量频谱能量集中在低频率集中在低频率区、衰减较快区、衰减较快基于基于语谱图语谱图的清浊音分析的清浊音分析静音静音频谱频谱能量能量很小很小jiuselu频率频率与与乐谱乐谱乐音乐音：发音物体有规律地振动而产生的具有固定：发音物体有规律地振动而产生的具有固定音高的音音高的音 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复数乘法复数乘法DFT、IDFT复数加法复数加法快速傅立叶变换快速傅立叶变换FFT(第第11章章)l 1965年，年，J.W.Cooley 和和 J.W.Tukey 首次提出了首次提出了DFT运算的一种快速算法运算的一种快速算法l此后相继出

21、现了各种用于计算机平台的改进此后相继出现了各种用于计算机平台的改进FFT 算法算法lFFT使使DFT的运算时间可缩短一、二个数量级，使的运算时间可缩短一、二个数量级，使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偶数点奇数点/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例：例：偶部奇部可继续分解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)