课件第4章变换

1、第四章第四章 傅立叶变换傅立叶变换离散时间傅里叶变换离散时间傅里叶变换DTFTDTFT离散傅立叶变换离散傅立叶变换DFTDFT傅立叶傅立叶 1768-1830(Fourier, Jean Baptiste Joseph) 法国数学家、物理学家法国数学家、物理学家最早使用定积分符号最早使用定积分符号改进符号法则、根数判别方法改进符号法则、根数判别方法傅立叶级数创始人傅立叶级数创始人 1807 热的传播热的传播推导热传导方程中发现解函数可推导热传导方程中发现解函数可以由三角函数级数构成的级数形以由三角函数级数构成的级数形式表示式表示 1822 热的分析理论热的分析理论傅立叶级数、分析等理论傅立叶级

2、数、分析等理论傅立叶分析方法的历史傅立叶分析方法的历史l古巴比伦人古巴比伦人 l “三角函数和三角函数和” 描述周期性过程、预测天体描述周期性过程、预测天体运动运动l 1748年年 欧拉欧拉l 振动弦的形状是振荡模的线性组合振动弦的形状是振荡模的线性组合l1753年年 D伯努利伯努利l 弦的实际运动可用标准振荡模的线性组合来表弦的实际运动可用标准振荡模的线性组合来表示示l1759年年 拉格朗日拉格朗日l 不能用三角级数来表示具有间断点的函数不能用三角级数来表示具有间断点的函数l l 1822年年 傅立叶傅立叶l “热的分析理论热的分析理论” 中提出并证明周期函数的正弦级中提出并证明周期函数的正

3、弦级数展开原理，奠定了傅立叶级数的理论基础数展开原理，奠定了傅立叶级数的理论基础l 1829年年 P.L狄里赫利狄里赫利l 周期信号傅立叶级数表示的若干精确条件周期信号傅立叶级数表示的若干精确条件l 19-20世纪世纪l 两种傅立叶分析方法两种傅立叶分析方法-连续与离散连续与离散l 1965年年 Cooley & Tukey (IBM)l 发明发明FFT 算法算法引例引例时域时域和弦和弦 中音中音CEG频域频域如何分解出如何分解出CEG分量？分量？傅立叶变换的导出傅立叶变换的导出滤波滤波相乘相乘中音中音C每个频率分量？每个频率分量？频域频域滤波器滤波器时域时域卷积卷积频率频率为为 分量

4、分量幅度幅度频率频率通带通带变窄变窄( )j th tex(t)x(t)( )h t( )( )*j txtx te滤波器滤波器频域频域频率频率幅度幅度时域时域单位冲击单位冲击响应响应与与 t无关无关常数常数( )( )*( )*(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四种常用的傅立叶变换四种常用的傅立叶变换时域时域频域频域离散离散连续连续离散时间傅立叶变换离散

5、时间傅立叶变换连续连续连续连续连续时间傅立叶变换连续时间傅立叶变换 离散离散离散离散 离散傅立叶变离散傅立叶变换换连续连续离散离散连续时间傅立叶级数连续时间傅立叶级数连续时间傅立叶变换连续时间傅立叶变换(FT) x(t)X(j) 正变换正变换 反变换反变换()( )j tX jx t edt 正变换正变换 分解分解 ( (提取提取) )1( )()2j tx tX jed反变换反变换 合成合成 ( (还原还原) )( )( ) j tXjx t edtx t dt 条件条件 有限个不连续点有限个不连续点 绝对可积绝对可积非周期连续时间信号非周期连续时间信号非周期连续频率函数非周期连续频率函数常

6、见信号频谱常见信号频谱连续时间傅立叶级数连续时间傅立叶级数(FS)周期周期022fT ()( )j tX jx t edt 正变换正变换 000()( )TjktkX jkx t edta1( )()2j tx tX jed反变换反变换001( )()jktx tX jkeT收敛性收敛性抽样定理抽样定理周期连续时间信号周期连续时间信号非周期离散频谱函数非周期离散频谱函数常见信号频谱常见信号频谱离散时间傅里叶变换离散时间傅里叶变换(DTFT)T ()( )j tX jx t edt 正变换正变换 ()( )jj nnX ex n e1( )()2j tx tX jed反变换反变换201( )()

7、2jj tx nX eed非周期离散信号非周期离散信号周期连续频率函数周期连续频率函数常见信号频谱常见信号频谱 ()()jjjX eX ee ()()jjX eX e ：傅立叶频谱：幅度函数 或 幅度谱：相位函数 或 相位谱例：例：00DTFTj nIDTFTnne 0022DTFTjnIDTFTkek DTFT频谱频谱 的性质：的性质：)(jeX 222cossintanjjrejjimjjjreimjimjreXeX eXeX eX eXeXeXeXe 1. 模与幅角模与幅角 2. 对于实序列对于实序列() jj nnX ex n e() cos()()jjrerenXex nnXe为 的

8、偶函数() sin()()jjimimnXex nnXe 为 的奇函数222jjjreimX eXeXe tanjimjreXeXe ()jX e为 的偶函数( ) 为 的奇函数3jX e、为周期2 的连续函数(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无穷项求和无穷项求和() jX ex n收敛绝对可和?例：低通滤波器例：低通滤波器(p105，例，例3.8) jDTFTnkDTFTnjkjD

9、TFTkDTFTDTFTenukekenuknDTFT 11122211221100，对：常用周期冲激串周期冲激串 periodic impulse train DTFT的性质的性质() jG eg n ()jh nH e 1. 线性 g nh n)(jjG eH e 2. 时间反转时间反转 ()jG egn()jj nnY egn e证明：证明： j mmg m em=-njG e3. 时移时移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利用傅立叶变换性质，不解差分方程求序列解：解：0101()jjjpp eV edd e傅立叶反变换傅立叶反变换vn4. 频移频移00() ()jnjg nG ee 证明：证明：0() jnjj nnY eeg n e0() jnng n e 0()jG e 调频广播、频率调制调频广播、频率调制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.调制定理调制定理(也称为加窗定理也称为加窗定理)() jj nnY eg n h n e1 ()2j njj nnh n eG eed()1() 2jjnnG eh n ed ()1()()2jjG eH ed 证明证明高频高频例：幅度调制例：幅度调制 x n0cosn y n0 cosy nx nn0011()()222jjY eX ed 001()()2jjX eX e 低频低频0-幅度幅度频率频率幅度幅度0-oo频率频

12、率低通低通滤波滤波 y n r n x n0cosn解调解调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 无限长序列无限长序列窗函数窗函数加窗后频谱产生失真加窗后频谱产生失真测不准原理：时域分辨率测不准原理：时域分辨率*频域分辨率频域分辨率常数常数加窗实例加窗实例 x n w n y 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时域的能量等于频域的能量时域的能量等于频域的能量2()jX e 称为能量谱密度特例：特例： g nh nx n221( )()2jnEx nX ed*1 ()()2jjng n h nG eHedLTI离散时间系统的频率响应离散时间系统的频率响应傅立叶变换：信号傅立叶变换：信号不同频率正弦信号的线性组合不同频率正弦信号的线性组合xnhnyn ()()()kjjjy nh k x nkY eH eX eLTI系统对单频信号的响应系统对单频信号的响应 任何

14、复杂信号的响应任何复杂信号的响应()() ()jjj njnY eH eh n eX e jj kkH eh k ejH e argjH e 频率响应：频率响应：幅度响应：幅度响应：相位响应：相位响应：实冲激响应实冲激响应)()(jjeHeH)()(是奇函数是偶函数，)()(jimjreeHeH幅度响应和相位响应周期为幅度响应和相位响应周期为2相位响应是奇函数相位响应是奇函数 幅度响应是偶函数幅度响应是偶函数()() ()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例：例：求滑动平均滤波器求滑动平均滤波器 频率响应？频率响应？2/)1(0010)2/sin()2/sin(11111111)(MjjjMjMnnjMnnjnnjMnnjjeMMeeMeeMeeMeMeH解解:为什么是折线为什么是折线M的变化有何影响的变化有何影响例：输入信号例：输入信号通过通过3阶阶FIR高通滤波器高通滤波器)4 . 0cos()1 . 0cos(nnnnx 1456335.13276195. 6nxnxnxny观察输出信号幅度和相位的变化观察输出信号幅度和相位的变化Matlab仿真图形仿真图形 y n比较绛红与蓝色线比较绛红与

16、蓝色线,有何区别？有何区别？cos(0.4 )n x ncos(0.1 )n相位：相位：产生产生 延时延时)(arg)(0jeH幅度：幅度：滤除滤除cos(0.1n)频率分量频率分量()()()jjjY eH eX e相延迟相延迟(phase delay)和群延迟和群延迟(group delay)(cos(| )(|)(cos(| )(|0000000neHAneHAnyjj ( )p nnAnxo),cos(不同频率的正弦分量不同频率的正弦分量 + 系统相延迟系统相延迟 = 相位失真相位失真xnhnyn相延时相延时 ( )gdd 群延迟：滤波器平均延迟的一个度量，群延迟：滤波器平均延迟的一个

17、度量， 是相位在一个窄带信号上的近似延迟是相位在一个窄带信号上的近似延迟群延时群延时pg ( )gdd 群延时群延时xnhnyn)(| )(| )()(jjjjeeHeXeY)(nyeYj)()()(jjjeeYeYba)(jbeanyny线性相位线性相位00()j njeG eg nn滑动平均滤波器的群延时？意义？滑动平均滤波器的群延时？意义？(1)/21sin(/2)()sin(/2)jj MMH eeM 12gM群延迟：群延时为常量，与频率无关（线性相位）群延时为常量，与频率无关（线性相位）1/,01 0,otherwiseMnMh n离散傅里叶变换离散傅里叶变换时域周期延拓时域周期延拓

18、频率采样频率采样离散时间傅立叶变换离散时间傅立叶变换DTFT离散傅立叶变换离散傅立叶变换DFT 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/jNNWe jkX kX k eDFT幅度谱幅度谱 k

19、X kDFT相位谱相位谱2/jNNWe性质性质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的运算量的运算量DFTIDFTN2N*(N-1)DFT、IDFT复数乘法复数乘法DFT、IDFT复数加法复数加法 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正频率正频率负频率负频率Xk的的DFT频谱频谱16N 3r 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

22、MjenX kX exn eX e 2/ kjk 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频谱频谱N为周期的

23、整数倍为周期的整数倍频谱的尖峰为正弦的频率频谱的尖峰为正弦的频率N不是周期的整数倍不是周期的整数倍出现模糊出现模糊单频模拟信号单频模拟信号DFT宽频宽频DFT频谱频谱原因？原因？ 129点点128点点时域上看时域上看周期延拓周期延拓波形的突变产生多种频率分量波形的突变产生多种频率分量频域上看频域上看128点点129点点序列的循环移位序列的循环移位0000010modNnx nnnnNxnnx Nnnnnmmn（）56nx26nx x n61xn64xnDFT的性质的性质 : 有限长序列的运算有限长序列的运算移位与循环移位移位与循环移位0N-10N-1循环移循环移2位位周期延拓周期延拓移移2 2

24、位位()NNxnxNn循环移位的周期循环移位的周期循环移位的时反循环移位的时反()NNxnmxnNmn性质性质证明证明有限长序列的分类有限长序列的分类共轭对称：共轭对称：* x nx -n* x n-x -n共轭反对称：共轭反对称： cscax nxnxn任意复序列可分解为共轭对称和共轭反对称部分任意复序列可分解为共轭对称和共轭反对称部分共轭对称部分共轭对称部分共轭反对称部分共轭反对称部分 2caxnx nx -n/ 2csxnx nx -n/特例：实序列特例：实序列偶对称：偶对称： x nx -n x n-x -n奇对称：奇对称： eox nx nx n任意实序列可分解为偶对称和奇对称部分任

25、意实序列可分解为偶对称和奇对称部分 2ox nx nx -n/ 2ex nx nx -n/偶对称部分偶对称部分奇对称部分奇对称部分圆周共轭对称：圆周共轭对称：* 01Nx nxnx N -nnN* 01Nx nxnx N -nnN 圆周共轭反对称：圆周共轭反对称： pcspcax nxn xnN点序列可分解为圆周共轭对称和圆周共轭反对称部分点序列可分解为圆周共轭对称和圆周共轭反对称部分* 2pcsxnx nx N -n/* 2 pcaxnx nx N -n/圆周共轭对称圆周共轭对称部分部分圆周共轭对称圆周共轭对称部分部分几何对称：几何对称： 101x nx NnnN 101x nx NnnN

26、几何反对称：几何反对称：DFT的对称关系的对称关系复序列复序列DFT的对称关系的对称关系序列序列DFT频谱频谱* x n* NXk* Nxn* Xk共轭、共轭、时反时反 Re x n*1 2pcsNNXkXkXkIm jx n*1 2pcaNNXkXkXk实部、实部、虚部虚部 pcsxnRe 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偶对称、偶对

27、称、奇对称奇对称序列序列DFT频谱频谱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 nG kk频移频移调幅广播调幅广播DFT对偶：对偶： NG nNgk g nG kDFTN点圆周卷积点圆周卷积10 ( )( )NNmg m h nmG k H k ()()jjg nh nG eH eDTFT卷积卷积圆周卷积圆周卷积

28、 10NLmyng m h nm g nh nN设、为 点长的序列21LN回顾：回顾：N N点序列的线性卷积点序列的线性卷积yLnyLn的长度？的长度？ 10N NCNmyng nh ng m hnmN N点序列的圆周卷积点序列的圆周卷积yCnyCn的长度？的长度？LNLM+N-10 N-10M-1L0 N-1LM+N-10M-1L0M-1xn0 N-1hn线性卷积与圆周卷积的关系线性卷积与圆周卷积的关系线性卷积线性卷积圆周卷积圆周卷积00M+N-1yn0L=M+N-1点点 圆周卷积圆周卷积 = 线性卷积线性卷积调制调制(加窗加窗)101 NNmg n h nG m HkmNdeHeGnhng

29、jj)()(21)(DFTDTFT帕斯瓦尔公式帕斯瓦尔公式1122001 NNnkx nX kN*1 ()()2jjng n h nG eHedDFTDTFTNnNnkHkGNnhng0*0*1两个实序列两个实序列DFT的计算的计算实序列实序列DFT的计算的计算 x ng njh n令 *1212NNG kX kXkH kX kXkjDFT的对称性的对称性基本思想：利用基本思想：利用DFT的对称性的对称性2N点实序列点实序列DFT的计算的计算2N点实序列点实序列vn 2111212222000112002221021NNNnknknkNNNnnnNNnknkkNNNnnkNNNv nv n W

30、vn WvnWg n Wh n W WGkWHkkN， 2g nvn 21h nvn偶数点偶数点奇数点奇数点两个有限长序列的线性卷积两个有限长序列的线性卷积用用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 nmG k H k有限长序列与无限长序列的线性卷积有限长序列与无限长序列的线性卷积 10Mlh

31、lMx ny nh l x nlh nx n设为点有限长序列，为无限长序列求：基本思想：无限长卷积基本思想：无限长卷积有限长卷积之和有限长卷积之和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% 线计算量线计算量短时分析短时分析 短时短时( (加窗加窗) )傅立叶变换傅立叶变换基音周期不同

32、基音周期不同10()( )( )Njj mnnmXew m x m e加窗加窗语谱图语谱图 三维短时功率谱三维短时功率谱声音声音 九色鹿九色鹿tf短时短时DFT颜色表示幅度颜色表示幅度语语谱谱图图tftf短时短时DFT清音频谱能量分清音频谱能量分布在整个频率段布在整个频率段内、无明显衰减内、无明显衰减浊音频谱能量浊音频谱能量集中在低频率集中在低频率区、衰减较快区、衰减较快基于语谱图的清浊音分析基于语谱图的清浊音分析静音静音频谱频谱能量能量很小很小jiuselu频率与乐谱频率与乐谱乐音：发音物体有规律地振动而产生的具有固定乐音：发音物体有规律地振动而产生的具有固定音高的音音高的音 A ., 44

33、1 ,.B ., 495 ,. C ., 556 ,. D ., 589 ,.E ., 661 ,.F ., 742 ,.G ., 833 ,.音符频率表音符频率表(Hz)(Hz)中音中音频率组合频率组合表示表示五线谱五线谱简谱简谱五线谱与短时傅立叶分析五线谱与短时傅立叶分析f0频频率率时间时间21100 ,01knNNjnkNNnnX kx n ex n WkN211001 knNNjnkNNkkx nX k eX k WNDFT的运算量的运算量DFTIDFTN2N*(N-1)DFT、IDFT复数乘法复数乘法DFT、IDFT复数加法复数加法快速傅立叶变换快速傅立叶变换FFTl 1965年，年

34、，J.W.Cooley 和和 J.W.Tukey 首次提出了首次提出了DFT运算的一种快速算法运算的一种快速算法l此后相继出现了各种用于计算机平台的改进此后相继出现了各种用于计算机平台的改进FFT 算法算法lFFT使使DFT的运算时间可缩短一、二个数量级，使的运算时间可缩短一、二个数量级，使DFT的运算可以应用到实际中的运算可以应用到实际中按时间抽取法按时间抽取法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偶数点奇数点/2 1/2 121/200 2 2 NNrkrkNNrrX kxr Wxr W/2 1/2 1(21)2/200 2121NNrkkrkNNNrrX kxrWWxrWN/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点点

36、2点点2点点log2N2点点DFT002201220010110101XxWxWxxXxWxWxx0 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)

37、X1(0)X1(1)DFT4点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点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 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 按时间抽取的按时间抽取的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偶部奇部时间抽取法流程时间抽取法流程比特比特逆序逆序 x n蝶形蝶形运算运算 X k比特逆序比特逆序

39、例：例：N=8输入顺序输入顺序01234567二进制码二进制码000001010011100101110111码位倒读码位倒读000100010110001101011111输出顺序输出顺序042615372、原位运算：、原位运算：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点点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频率抽取法蝶形运算频率抽取法蝶形运算( )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二进制二进制0 000 010 100 111 001 011 101 11二进制二进制00 001 010 011 000 101 110 111 1前半部后半部原序原序01234567蝶形运算蝶形运算02461357频率抽取法流程频率抽取法流程蝶形蝶形运算运算 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计算101( )( )NnkNkx nXk WN取共轭取共轭运算量分析：运算量分析： 乘法乘法 加法加法 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乘法、加法、浮点、定点乘法、加法、浮点、定点小结小结nDTFTnDFTnFFT频谱分辨率频谱分辨率 Fs/128 Hz？为何不准确？为何不准确应用：频率估计应用：频率估计128点点DFT200 Hz单频信号单频信号1000 Hz采样采样64点点 估计出频率估计出频率26* Fs/128 =203.125Hz1.谱峰检测法谱峰检测法谱峰检测法频率估计为何不精确？谱峰检测法频率估计为何不精确？FFT点数有限点数有限 频谱分辨率不够频谱分辨率不够？能否提高估计精度？能否提高估计精度(不增加不增加FFT点数点数)(t)exp()iiifAjt频率估计方法频率估计方法2：导数法：导数法( )( )()( )nniiiftjf t时域求导时域求导 ( )222n2-|( )|()( )| ( )|nniiiiiftdtjf tdtf tdt 平方积分平方积分2( )202220|( )|( )|niniiftdf td 00002222|( )|2|( )|knkinkkkF kNF k离散离散Parseval定理定理主瓣能量主瓣能量傅立叶变换性质傅立叶变换性质100点点DFT导数法估计导数