《门爱东老师DSP讲义第3章2》由会员分享，可在线阅读，更多相关《门爱东老师DSP讲义第3章2（150页珍藏版）》请在金锄头文库上搜索。
1、 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTnFFT: Fast Fourier Transformn1965 年年，James W. Cooley 和和 John W. Tukey 在在计计算算数数学学（Mathematics of Computation）上上发发表表了了“ 一一种种用用机机器器计计算算复复序序列列傅傅立立叶叶级级数数的的算算法法（An algorithm for
2、the machine calculation of complex Fourier series）” 论文。论文。n自自此此之之后后，新新的的算算法法不不断断涌涌现现。一一种种是是对对N等等于于 2 的的整整数数次次幂幂的的算算法法，如如基基 2 算算法法，基基 4 算算法法。另另一一种种是是N不不等等于于 2 的的整整数数次次幂幂的的算算法法，例例如如 Winagrad 算法，素因子算法。算法，素因子算法。3.4 FFT （快速离散傅里叶变换）（快速离散傅里叶变换）Dr. James W. CooleyWorked at IBM Watson Research Center in York
3、town Heights, N.Y.After his retirement from IBM in 1991, he joined the Electrical Engineering Department at the University of Rhode Island. John W. Tukey (1915 2000)1 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.4 FF
4、T：直接计算直接计算 DFT 的运算量分析的运算量分析nN 点有限长序列点有限长序列 x(n) 的的 DFT 变换对的定义为：变换对的定义为： 其中其中假设假设 x(n) 是复序列，是复序列， 同时同时 X(k) 一般也是复数。一般也是复数。2 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT复数乘法复数乘法复数加法复数加法每一个每一个X(k)NN 1N 个个X(k)(N 点点 DFT)N
5、2N (N 1)实数乘法实数乘法实数加法实数加法一次复乘一次复乘42一次复加一次复加2每一个每一个 X (k)4N2N+2 (N 1)=2 (2N 1)N个个X (k) (N点点DFT)4N 22N (2N 1)3.4 FFT：直接计算直接计算 DFT 的运算量分析的运算量分析复乘的加复乘的加法次数法次数复加的加复加的加法次数法次数3 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTn如如
6、N=512、1024 和和 8192 时，时，DFT 的乘法运算的乘法运算 N2 = 5122 = 218 = 262144（26万次）万次） N2 = 10242 = 220 = 1048576（105万次）万次） N2 = 81922 = 226 = 67108864（6千千7百万次）百万次）对对于于大大 N，在在实实际际中中是是不不能能接接受受的的，无无法法“实实时时”应应用用 DFT。一般地，在计算机中，一次加法比一次乘法所需时间要短一般地，在计算机中，一次加法比一次乘法所需时间要短;在在DSP中中，由由于于乘乘法法用用特特殊殊的的硬硬件件电电路路专专门门完完成成，因因此此乘乘法法和加
7、法所需机器周期相同。和加法所需机器周期相同。Cooley 与与 Turkey 提提出出的的 FFT 算算法法，大大大大减减少少了了计计算算次次数数。如如 N =512 时时，FFT 的的乘乘法法次次数数约约为为 2000 次次，提提高高了了约约 128 倍倍，而而且且简简化化随随 N 的的增增加加而而巨巨增增，因因而而，用数值方法计算频谱得到实际应用。用数值方法计算频谱得到实际应用。3.4 FFT：直接计算直接计算 DFT 的运算量分析的运算量分析4 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing
8、, Men Aidong, Multimedia Telecommunication Centre, BUPT3.4 FFT：WNkn 的性质的性质5 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTn以以 4 点点 DFT 为例：为例： 直直接接计计算算需需要要：42 = 16 次次复复数数乘乘。而而按按周周期期性性及及对对称称性性，可以将可以将 DFT 表示为：表示为：只需要只需要 1
9、次复数乘次复数乘3.4 FFT：WNkn 的性质的性质信号流图信号流图？x(0)x(2)x(1)x(3)-1-1-1-1W41X(0)X(1)X(2)X(3)6 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTnFFT 算法分类算法分类:时间时间抽选法抽选法 DIT: Decimation-In-Time频率频率抽选法抽选法 DIF: Decimation-In-Frequency3.4 F
10、FT：基本思想基本思想n基本思路基本思路：虽虽然然存存在在不不同同的的 FFT 方方法法，但但其其核核心心思思想想大大致致相相同同，即即通通过过迭迭代代，反反复复利利用用低低点点数数的的 DFT 完完成成高高点点数数的的 DFT 计计算算，以以此此达达到到降降低低运算量的目的。运算量的目的。迭迭代代：利利用用 WNkn 的的周周期期性性、特特殊殊点点和和对对称称性性，合合并并 DFT 计计算算中中很多重复的计算，达到降低运算量的目的。很多重复的计算，达到降低运算量的目的。低低点点数数：将将傅傅氏氏变变换换 DFT 分分解解成成相相继继小小的的DFT计计算算，即即 N 变变小小，而计算量与而计算
11、量与 N2 成正比。成正比。7 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTn算法原理算法原理 设序列点数设序列点数 N = 2M，M 为整数。若不满足，则补零。为整数。若不满足，则补零。 将序列将序列 x(n) 按按 n 的奇偶分成两组：的奇偶分成两组：N 为为 2 的整数幂的的整数幂的 FFT 算法称基算法称基-2 FFT算法。算法。即一组由偶数序号组成，另一组由奇数序号组成。即一组
12、由偶数序号组成，另一组由奇数序号组成。3.4.1 FFT：基基2时间抽选法时间抽选法-算法原理算法原理注意其长度为注意其长度为 N/2 N/2 8 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.4.1 FFT：基基2时间抽选法时间抽选法-算法原理算法原理9 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Pro
13、cessing, Men Aidong, Multimedia Telecommunication Centre, BUPT偶数取样点偶数取样点DFT为：为： 3.4.1 FFT：基基2时间抽选法时间抽选法-算法原理算法原理奇数取样点奇数取样点DFT为：为： k 的的整整个个范范围围为为 0(N-1)，而而X1(k)、X2(k) 是是由由 N/2 个个样样点点形形成成的的 DFT，x(2r) 和和 x(2r1）的长度为）的长度为 N/2； 由由这这两两个个偶偶数数和和奇奇数数 N/2 个个时时域域样样值值可可以以计计算算出出前前 N/2 个个 DFT 系系数数，也可以计算出后也可以计算出后 N
14、/2 个个 DFT 系数。系数。 问问题题：这这前前后后 N/2 个个 DFT 有有无无关关系系？k 在在 N/2 (N-1) 时时， X1(k)、X2(k)、WN 情况如何？情况如何？10 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.4.1 FFT：基基2时间抽选法时间抽选法-算法原理算法原理观察观察则则11 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体
15、中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT因因此此：整整个个 X(k) 的的计算算，可可以以分分解解为前前、后后半半部部分分的的运运算。而算。而只要求出前一半只要求出前一半，就可以由上式求出整个序列。，就可以由上式求出整个序列。3.4.1 FFT：基基2时间抽选法时间抽选法-算法原理算法原理同理同理而而因此因此12 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processin
16、g, Men Aidong, Multimedia Telecommunication Centre, BUPT上式表示为信号流程图：上式表示为信号流程图：此信号流程图也称为此信号流程图也称为蝶形蝶形流程图流程图3.4.1 FFT：基基2时间抽选法时间抽选法-算法原理算法原理偶数点的偶数点的 DFT奇数点的奇数点的 DFTMorpho Butterfly大闪蝶大闪蝶( 南美洲南美洲)13 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecom
17、munication Centre, BUPT以以N=8为例，其信号流程图：为例，其信号流程图：3.4.1 FFT：基基2时间抽选法时间抽选法-算法原理算法原理偶偶数数序序列列奇奇数数序序列列14 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTN / 2 仍为偶数，进一步分解：仍为偶数，进一步分解：N / 2 N / 43.4.1 FFT：基基2时间抽选法时间抽选法-算法原理算法原理15
18、北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.4.1 FFT：基基2时间抽选法时间抽选法-算法原理算法原理同理同理16 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT以以N=8为例
19、，其信号流程图为为例，其信号流程图为3.4.1 FFT：基基2时间抽选法时间抽选法-算法原理算法原理N/2 点点DFTN/2 点点DFT17 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT由于由于 N=2M，这样逐级分解，直到，这样逐级分解，直到 2 点点 DFT当当 N = 8时时，即即分分解解到到 X3(k)，X4(k)，X5(k)，X6(k)，k = 0, 13.4.1 FFT：基基
20、2时间抽选法时间抽选法-算法原理算法原理18 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT每每一次分解一次分解都是按都是按时间域时间域输入输入序列的奇偶性序列的奇偶性次序，分解为次序，分解为两个半长两个半长的的子序列子序列，所以称为，所以称为按时间抽取法按时间抽取法。仍以仍以N=8为例：为例：3.4.1 FFT：基基2时间抽选法时间抽选法-算法原理算法原理注注：复复数数乘乘法法5次次，原
21、原来来 64次次；复复数数加加法法为为 24次次，原原来来56次。次。m=0级级m=1级级m=2级级19 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT 2m 点点 DFT 的基的基 2 时间抽选计算过程时间抽选计算过程 n可见：可见：为什么引入为什么引入FFT？出发点：出发点：考虑考虑 W 因子的特点和性质因子的特点和性质，简化算法。，简化算法。DIT-FFT算法：时间域输入信号算法：时
22、间域输入信号逐级分解逐级分解为奇偶序列。为奇偶序列。3.4.1 FFT：基基2时间抽选法时间抽选法-算法原理算法原理上式中上式中位序位序调整调整第第 0 级级蝶形复合蝶形复合第第 1 级级蝶形复合蝶形复合第第m-1级级蝶形复合蝶形复合x(n)X(k)20 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT例例3.25 使使用用基基 2 时时间间抽抽选选法法 FFT 流流图图，计计算算下下列列数
23、数据据的的 8点点 DFT：x=4,-3,2,0,-1,-2,3,13.4.1 FFT：基基2时间抽选法时间抽选法-算法原理算法原理4-320-1-23142-13-30-214-123-3-2 01355-1-5-1 1-1355j-5-1 1j85+j-25-j-4-1+j-6-1-j85+j-25-j-4j26jj245+j+ j2-2+6j5-j+ j2125+j- j2-2-6j5-j- j221 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimed
24、ia Telecommunication Centre, BUPTn蝶形运算蝶形运算在在FFT信信号号流流图图中中每每一一级级里里节节点点都都是是成成对对存存在在的的，计计算算时时总总是是下下节节点点的的值值乘乘以以 WNr，然然后后与与上上节节点点的的值值相相加加减减，形形成成下下一一列列两两个个节点值。节点值。这种计算的基本关系是：这种计算的基本关系是： 式中式中 p, q 是上下节点的序号。（从是上下节点的序号。（从 0 开始，开始，p,q=0,1,.N/2） 每一级中每对节点称为对偶节点，每一级中每对节点称为对偶节点，对偶节点的间距为：对偶节点的间距为：注意：只有下节点乘以加权因子注意
25、：只有下节点乘以加权因子 WNr 3.4.1 FFT：基基2时间抽选法时间抽选法-蝶形运算蝶形运算22 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTn同址计算（同位特性）同址计算（同位特性）3.4.1 FFT：基基2时间抽选法时间抽选法-同址计算同址计算1) 不同级数的节点序号不变不同级数的节点序号不变 从从蝶蝶形形运运算算可可以以看看出出第第 m 列列的的 xm(p), xm(q) 经
26、经蝶蝶形形运运算算后后，在在第第(m+1) 列列中中的的节节点点序序号号不不变变，即即 xm+1(p) 中中的的 p 与与 xm+1(q) 中中的的 q 仍仍分分别别是是 xm(p), xm(q) 中中的的 p 和和 q 值。值。23 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT2) 蝶形运算是自成独立单元蝶形运算是自成独立单元蝶蝶形形运运算算自自成成独独立立单单元元，即即xm+1(p)
27、、xm+1(q) 只只与与 xm(p)、xm(q) 有有关关，而而与与其其他他节节点点的的值值无无关关，同同时时 xm(p)、xm(q) 也也不不参参与与另另外外的的蝶蝶形形运运算算。因因此此，就就可可把把计计算算结结果果xm+1(p) ,xm+1(q)放放入入计计算算前前 xm(p)、xm(q) 的的存存储储单单元元中中，而而不不用用再再建新的存储单元建新的存储单元 同址计算同址计算。同同址址计计算算所所需需存存储储量量仅仅等等于于给给定定数数据据所所需需的的存存储储量量，这这可可大大大大节省存储单元。节省存储单元。3.4.1 FFT：基基2时间抽选法时间抽选法-同址计算同址计算24 北北京
28、京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTn输入倒序重排输入倒序重排N 点点 DFT 分分解解为为两两个个 N/2 点点 DFT输输入入序序列列按按奇奇偶偶分分组组再再分分解解再再奇奇偶偶重重排排直直到到 2 点点DFT。 即即 FFT 输输出出自自然然序序列列 输输入入序序列列 x(n) 倒倒序序重重排排。3.4.1 FFT：基基2时间抽选法时间抽选法-倒序重排倒序重排010011n0n1
29、n225 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT说明：说明：首先把首先把 x(n) 中的中的 n 表示为二进制。表示为二进制。假定假定N=8，则，则 x(n) x(n2n1n0) ni = 0, 1 FFT 的的时时间间抽抽选选法法按按 n 的的奇奇偶偶分分离离而而形形成成倒倒置置重重排排的的原原理理如如上图所示。上图所示。由由此此可可以以看看出出，时时间间抽抽选选法法 FFT 的
30、的输输入入倒倒序序重重排排，输输出出结结果果为自然顺序。为自然顺序。实际操作实际操作输输入入序序列列重重排排实实际际上上就就是是完完成成二二进进制制前前后后位位序序的的相相互交换：互交换：3.4.1 FFT：基基2时间抽选法时间抽选法-倒序重排倒序重排26 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT当当 N = 2M 时时，共共有有 M=log2N 级级蝶蝶形形；每每级级 N/2 个个
31、蝶蝶形形；每每个蝶形有个蝶形有 1 次复数乘法，次复数乘法，2 次复数加法。次复数加法。复数乘法：复数乘法：复数加法：复数加法：比较比较 DFT/FFT 3.4.1 FFT：基基2时间抽选法时间抽选法-运算量运算量27 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTnFFT 算法算法上上面面讨讨论论的的 FFT 算算法法假假定定 N 为为 2 的的整整数数次次幂幂，即即 N = 2M，是是
32、基基2 FFT 算法算法。当当 N=Rv 时时，这这样样的的算算法法叫叫做做基基R FFT算算法法，而而当当 N=R1v1R2v2R3v3时，叫做时，叫做混合基算法混合基算法。当当 N 是是一一个个高高度度合合数数时时，可可得得到到最最有有效效的的算算法法。最最受受欢欢迎迎也也最最易易编程的算法是编程的算法是基基2 FFT 算法算法。对对于于不不能能分分解解的的质质数数，或或者者当当 N 不不是是 2 的的整整数数次次幂幂时时，可可以以在在信号的末尾补信号的末尾补0，使其成为高度合数或，使其成为高度合数或 2 的整数次幂。的整数次幂。nMatlab FFT 实现实现Matlab 提供了内建的提
33、供了内建的 X = fft(x, N) 函数来计算矢量函数来计算矢量 x 的的 DFT。fft 函函数数是是机机器器码码写写成成的的，而而不不是是以以 Matlab 指指令令写写成成的的，即即不不存存在在 .m 文件，因此它的执行速度很快。文件，因此它的执行速度很快。采用混合算法。采用混合算法。若若 N 为为 2 的幂，则得到高速的基的幂，则得到高速的基 2 FFT 算法；算法；若若 N 不是不是 2 的幂，则将的幂，则将 N分解成质数，得到较慢的混合基分解成质数，得到较慢的混合基 FFT；若若 N 为质数，则为质数，则 fft 函数采用原始函数采用原始 DFT 算法。算法。3.4.1 FFT
34、：基基2时间抽选法时间抽选法-Matlab 实现实现28 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT如如果果输输入入序序列列 x 的的长长度度小小于于 N，则则在在其其填填零零使使其其成成为为 N 点点序序列列，如如果果省省略略变变量量 N，则则 DFT 的的长长度度即即为为 x 的的长长度度。如如果果 x 为为一一个个矩阵，则计算矩阵，则计算 x 中每列的中每列的 N 点点 DFT。
35、IDFT 由由 ifft 函数完成，它的特征与函数完成，它的特征与 fft 函数相同。函数相同。3.4.1 FFT：基基2时间抽选法时间抽选法-Matlab 实现实现n例例 3.26 研研究究当当 1n2048 时时，fft 函函数数的的执执行行时时间间，这这将展示不同的将展示不同的 N的情形下，划分组合的策略。的情形下，划分组合的策略。解解：atlab 提提供供了了两两个个函函数数来来确确定定执执行行时时间间。clock 函函数数读读取取瞬瞬时时时时钟钟，etime(t1,t2) 函函数数计计算算时时刻刻 t1、t2 之之间间所所经经历历的的时时间间。为为了了确确定定执执行行时时间间，产产生
36、生长长度度为为 1 至至 2048 的的随随机机矢矢量量，计计算算它它们们的的 FFT，将将计计算算时时间间存存在在一一个个数数组组里。最后画出执行时间相对于里。最后画出执行时间相对于 N 的图。的图。 29 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT%ComputationalComplexityofFFTusingMATLABNmax=2048;fft_time=zeros(1,N
37、max);forn=1:1:Nmaxx=rand(1,n);%Uniformlydistributedrandomnumbers.t=clock;fft(x);fft_time(n)=etime(clock,t);花花费费的的时间时间endn=1:1:Nmax;top=max(fft_time);plot(n,fft_time,.);axis(0,2500,0,top);xlabel(N);ylabel(TimeinSec.);title(FFTexecutiontimes)text(2100,top,o(N*N)text(2100,top*3/4,o(N*N*3/4)text(2100,to
38、p/2,o(N*N/2)text(2100,top/3,o(N*N/3)text(2100,top/4,o(N*N/4)text(2100,min(fft_time),o(N*logN) 3.4.1 FFT：基基2时间抽选法时间抽选法-Matlab 实现实现30 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTn从从图图中中可可以以看看到到，图图中中曲曲线线分分成成几几组组，表表示示了了N
39、的的不同组合情况。不同组合情况。n当当 N 高高度度可可合合时时，划划分分-组组合合策策略略是是很很有有效效的的。例例如如 N = 2048 时时，执执行行时时间间约约为为 0 秒秒，N = 2047 时时为为 0.05 秒秒，N = 2029 时时为为 0.22 秒。秒。n在在实实际际中中必必须须谨谨慎慎使使用用高高度度合合数数，除除特特定定需需求求外外，实实际际中中的的一一般般选选择择是是 N N = = 2 2M M。当当信信号号的的取取样样点点数数不不是是 2 的的整整数数次次幂幂时时，可可以以在在信信号号的的末末尾尾补补0（Zero padding），外外加加的的 0 不不会会影影响
40、响信信号号的的 DTFT 或或 DFT 特特性性。当当也也要要注注意意，填填0后后可可能能带带来来的的“真真实实频频率率”模模糊糊问问题题，见见前前面面的例题。的例题。3.4.1 FFT：基基2时间抽选法时间抽选法-Matlab 实现实现31 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTnDFT 定义表示为矩阵形式为：定义表示为矩阵形式为：3.4.2 FFT：基基2时间抽选法时间抽选法-
41、矩阵表示矩阵表示32 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTn令：令：n矩阵矩阵 WN 为：为：nDFT 矩阵简单地表示为：矩阵简单地表示为：特性特性3.4.2 FFT：基基2时间抽选法时间抽选法-矩阵表示矩阵表示33 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aido
42、ng, Multimedia Telecommunication Centre, BUPTnFFT 基基 2 时间抽选法信号流图（时间抽选法信号流图（N=8）-1W8218点点24点点42点点x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)-1-1-1-1-1-1-1-1-1-1-1W80W80W82W80W81W82W83C(0)C(1)D(0)D(1)E(0)E(1)F(0)F(1)A(0)A(1)A(2)A(3)B(0)B(1)B(2)B(3)m
43、 = 0 级m = 1级m = 2 级倒置重排3.4.2 FFT：基基2时间抽选法时间抽选法-矩阵表示矩阵表示34 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTnFFT 矩阵形式表示为：矩阵形式表示为：1) 输入矢量输入矢量 x 与与 P8 相乘，则相乘，则只是输入的倒置重排只是输入的倒置重排，没有乘法操作。，没有乘法操作。3.4.2 FFT：基基2时间抽选法时间抽选法-矩阵表示矩阵表示
44、35 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT2) 第第 0 级运算：级运算：2 点点 DFT3.4.2 FFT：基基2时间抽选法时间抽选法-矩阵表示矩阵表示36 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunicat
45、ion Centre, BUPT3) 第第 1 级运算：级运算：4 点点 DFT3.4.2 FFT：基基2时间抽选法时间抽选法-矩阵表示矩阵表示37 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT4) 第第 2 级运算：级运算：8 点点 DFT3.4.2 FFT：基基2时间抽选法时间抽选法-矩阵表示矩阵表示38 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心
46、心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTnFFT算法看成是算法看成是 DFT 矩阵矩阵W8 的分解：的分解： 这这个个因因式式分分解解对对应应于于快快速速算算法法，因因为为矩矩阵阵F8(8)， F8(4) ， F8(2) 和和 P8 的的大大部部分分元元素素为为 0，是是稀稀疏疏矩矩阵阵。因因此此上上述述每每个个矩矩阵阵的的乘乘法法运运算算最最多多只只需需要要 8 次复乘运算，而次复乘运算，而 P8 只是置换操作，没有乘法操作。只是置换操作，没有乘法操作。n不
47、同的不同的 FFT 算法对应于将算法对应于将 DFT 矩阵矩阵 WN 分解成不同的稀疏矩阵。分解成不同的稀疏矩阵。 3.4.2 FFT：基基2时间抽选法时间抽选法-矩阵表示矩阵表示39 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTn输入倒位序，输出自然序输入倒位序，输出自然序n输入自然序，输出倒位序输入自然序，输出倒位序n输入输出均自然序输入输出均自然序n各级具有相同几何形状各级具有相同
48、几何形状输入倒位序，输出自然序输入倒位序，输出自然序输入自然序，输出倒位序输入自然序，输出倒位序3.4.2 FFT：基基2时间抽选法时间抽选法-其它形式的流图其它形式的流图40 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT 3.4.2 FFT：基基2时间抽选法时间抽选法-其它形式的流图其它形式的流图41 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门
49、爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.4.2 FFT：基基2时间抽选法时间抽选法-其它形式的流图其它形式的流图42 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.4.2 FFT：基基2时间抽选法时间抽选法-其它形式的流图其它形式的流图43 北北京京邮邮
50、电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.4.2 FFT：基基2时间抽选法时间抽选法-其它形式的流图其它形式的流图44 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.4.2 FFT：基
51、基2时间抽选法时间抽选法-其它形式的流图其它形式的流图45 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTn算法原理：算法原理：根据时间根据时间-频率的对偶性频率的对偶性时时间间抽抽选选法法：是是把把输输入入 x(n) 按按奇奇偶偶分分解解成成两两个个子子序序列列，即即 N 点点x(n) 序序列列 N/2 点点子子序序列列，而而输输出出 X(k) 是是按按自然顺序排列的。自然顺序排列的。频
52、频率率抽抽选选法法：是是把把输输入入 x(n) 按按照照前前后后对对半半分分开开，而而不不是是奇奇偶偶数数分分开开，而而输输出出 X(k) 逐逐项项分分解解成成偶偶数数点点子子序序列和奇数点子序列。列和奇数点子序列。nDFT 变换表达式为：变换表达式为：3.4.3 FFT：基基2频率抽选法频率抽选法 (DIF-FFT)如果将输入如果将输入 x(n) 按前后等分，即将求和分成两部分，范围分别为：按前后等分，即将求和分成两部分，范围分别为：46 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men
53、 Aidong, Multimedia Telecommunication Centre, BUPT3.4.3 FFT：基基2频率抽选法频率抽选法 算法原理算法原理47 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT 按按 k 的奇偶将的奇偶将X(k)分成两部分：分成两部分：3.4.3 FFT：基基2频率抽选法频率抽选法 算法原理算法原理48 北北京京邮邮电电大大学学信信息息与与通通信信工
54、工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT令令:则则 X(2r) 和和 X(2r+1) 分分别别是是 x1(n) 和和 x2(n) 的的 N/2 点点 DFT，记为记为 X1(k) 和和 X2(k)。3.4.3 FFT：基基2频率抽选法频率抽选法 算法原理算法原理49 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aido
55、ng, Multimedia Telecommunication Centre, BUPTx1(0)x1(1)-1x1(2)x1(3)-1x2(0)x2(1)-1x2(2)x2(3)-1N/2点点DFTN/2点点DFTx(0)x(7)x(1)x(2)x(3)x(4)x(5)x(6)X1(0)=X(0)X2(0)=X(1)X1(1)=X(2)X1(2)=X(4)X1(3)=X(6)X2(1)=X(3)X2(2)=X(5)X2(3)=X(7)3.4.3 FFT：基基2频率抽选法频率抽选法 算法原理算法原理50 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱
56、东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTnFFT 基基 2 频率抽选法信号流图（频率抽选法信号流图（N=8）n逐级分解，直到逐级分解，直到 2 点点 DFT3.4.3 FFT：基基2频率抽选法频率抽选法 算法原理算法原理51 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, B
57、UPTn基本蝶形运算不同基本蝶形运算不同DIT: 先复乘后加减，先复乘后加减，W 因子在上下节点都有体现因子在上下节点都有体现DIF: 先减后复乘，先减后复乘，W因子仅体现在下节点因子仅体现在下节点3.4.3 FFT：基基2时间和频率抽选法的异同时间和频率抽选法的异同52 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTn运算量相同运算量相同n同址计算同址计算3.4.3 FFT：基基2时间和
58、频率抽选法的异同时间和频率抽选法的异同nDIF 输出输出重排，重排，DIT 输入输入重排重排53 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTnDIT 和和 DIF 的基本蝶形互为的基本蝶形互为信号流图转置信号流图转置DITDIF3.4.3 FFT：基基2时间和频率抽选法的异同时间和频率抽选法的异同54 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门
59、爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTnDITDIF FFT 算法互为转置（转置定理）算法互为转置（转置定理）-118点点24点点42点点X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)-1-1-1-1-1-1-1-1-1W80W82W80W81W82W83C(0)C(1)D(0)D(1)E(0)E(1)F(0)F(1)A
60、(0)A(1)A(2)A(3)B(0)B(1)B(2)B(3)m = 0 级m = 1级m = 2 级倒置重排-1-1W80W823.4.3 FFT：基基2时间和频率抽选法的异同时间和频率抽选法的异同55 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTn前前面面讲讲的的都都是是基基 2 的的 FFT 算算法法，除除此此之之外外，还还有有基基 4 的的，基基 8 的的快快速速算算法法。原原理
61、理和和基基 2 的的类类似似，分分解解为为 4 个个交交错错的的集集合合。相相比比基基 2 的的，可可以以进进一一步步节节约约复复数数乘乘的的次次数数，但但是是基基 8 的的和和基基 4 的的差差别别不远。不远。n算法原理省略，自学。算法原理省略，自学。3.4.4 FFT：基基 4 时间抽选法时间抽选法56 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTnDFT 和和 IDFT 的定义：的
62、定义：3.4.5 FFT：IDFT 快速算法快速算法 (IFFT)nDFT 和和 IDFT 的的区别区别： 因子因子 W 的指数相差一个负号；的指数相差一个负号； 相差一个因子相差一个因子 1/N。 FFT 算算法法中中的的分分组组方方式式、排排序序方方式式以以及及蝶蝶形形运运算算结结构构都都可可用用于于IFFT 算算法法的的设设计计，而而这这就就是是可可依依据据现现有有的的 FFT 算算法法直直接接得得出出 IFFT 算法算法的原因。的原因。 57 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing
63、, Men Aidong, Multimedia Telecommunication Centre, BUPTnFFT 和和 IFFT 基本蝶形运算之间的关系基本蝶形运算之间的关系设有序列设有序列 x(n)，其，其 DFT 为为 X(k)，则，则 IDFT 为为: 在在 FFT 的的时间抽抽选法中法中: 3.4.5 FFT：IDFT 快速算法快速算法 (IFFT)对于于 IFFT 算法，算法，输入是入是 X(k) 和和 X(k+N/2)，输出是出是 X1(k) 和和 X2(k)。解上式可以得到解上式可以得到 X1(K)、X2(K) ：X(k)X(k+N/2)X1(k)X2(k)-158 北北京
64、京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTn8 点点 DIT-IFFT 算法算法-1x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)-1-1-1-1-1-1-1-1-10.5W8-00.5W8-20.5W8-00.5W8-10.5W8-20.5W8-
65、3-1-10.5W8-00.5W8-20.50.50.50.50.50.50.50.50.50.50.50.5说明：说明：1）分组过程是按时间序列分组过程是按时间序列 x(n) 的奇偶性在时域上展开的，故的奇偶性在时域上展开的，故称此法为时间抽选算法称此法为时间抽选算法 DIT-IFFT；2）1/N 的分解，的分解，N=2m 。3.4.5 FFT：IDFT 快速算法快速算法 (IFFT)59 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telec
66、ommunication Centre, BUPTn8 点点 DIF-IFFT 算法算法 3.4.5 FFT：IDFT 快速算法快速算法 (IFFT)60 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTn用用 FFT 程序求程序求 IFFT 的方法的方法直接法：利用直接法：利用 DIT、DIF 的的 FFT 程序，改变参量程序，改变参量 把把 X(k) 作为输入序列，而输出序列就是作为输入
67、序列，而输出序列就是 x(n)； 把因子把因子 WNkn 改为改为 WN-kn ； 输入序列的每一个元素除以输入序列的每一个元素除以 N。3.4.5 FFT：IDFT 快速算法快速算法 (IFFT)61 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT流程如下：流程如下： 共轭法共轭法共轭共轭FFT共轭共轭乘乘 1/N3.4.5 FFT：IDFT 快速算法快速算法 (IFFT)62 北北京京
68、邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT主题概述主题概述1 -绪论绪论2 -离散时间系统和离散时间信号的变换离散时间系统和离散时间信号的变换3 -离散傅里叶变换及其快速计算方法离散傅里叶变换及其快速计算方法 3.1 问题的提出问题的提出 3.2 DFS（离散傅里叶级数）（离散傅里叶级数） 3.3 DFT（有限离散傅里叶变换）（有限离散傅里叶变换） 3.4 FFT（快速离散傅里叶变换）（快速离
69、散傅里叶变换） 3.5 CZT及其快速算法及其快速算法 3.6 其它变换其它变换 3.7 本章小结本章小结4 IIR 数字滤波器设计和实现数字滤波器设计和实现5 FIR 数字滤波器设计和实现数字滤波器设计和实现6 数字信号处理中的有限字长效应数字信号处理中的有限字长效应63 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTDFT 不适用于：不适用于：nDFT 是是均均匀匀分分布布在在 Z 平
70、平面面单单位位圆圆上上 N 点点处处的的频频谱谱，如如果我们果我们取样点不均匀取样点不均匀时，则很麻烦。时，则很麻烦。n只只研研究究信信号号的的某某一一频频段段，要要求求对对该该频频段段取取样样密密集集，提提高高分辨率分辨率(如窄带信号的频谱分析）；如窄带信号的频谱分析）；n研究研究非单位圆上非单位圆上的取样值（如频谱峰值探测）；的取样值（如频谱峰值探测）；n需要准确计算需要准确计算 N点点 DFT，且，且 N 为大的素数为大的素数；n当当 x(n) 是是短短时时间间序序列列时时，则则得得到到的的频频率率分分辨辨率率 2pi/N 是是很很低低的的。提提高高频频谱谱密密度度的的办办法法：用用补补
71、零零的的方方法法增增加加点点数数，但但 DFT 的点数又大大增加，使计算工作量增大。的点数又大大增加，使计算工作量增大。CZT 算算法法：对对 z 变变换换采采用用螺螺旋旋线线取取样样，chirp-z 变变换换(线线性性调频调频 z 变换，变换，Chirp z-transform)3.5 线性调频线性调频 z 变换变换 CZT 及其快速算法及其快速算法64 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centr
72、e, BUPTnCZT 的定义的定义 设设 x(n) 为已知时间序列，其为已知时间序列，其 Z 变换的形式为：变换的形式为： 式中复变量式中复变量 z 为：为： 这里这里 s 为拉普拉斯变量，为拉普拉斯变量， 是个实数是个实数 3.5.1 CZT：定义定义65 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT 按按照照上上式式计计算算 Zx(n) 必必然然是是从从 z 的的实实轴轴开开始始，
73、为为得得到到任任意意起起始始点点和和以以螺旋线规律变化螺旋线规律变化的的 z 值，做如下假设：值，做如下假设： 其其中中，A、W 为为任任意意复复数数，0 为 A 的的起起始始角角（第第1个个取取样点点（k=0） ），A0为 A 起起始始半半径径，0 为在在 Z 平平面面中中相相邻的的 zk （即即 zk 和和 zk+1 ）之之间的的夹角角，W0 为任意正数任意正数值。 M为要分析的点数，不一定定于为要分析的点数，不一定定于 N。3.5.1 CZT：定义定义66 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Proc
74、essing, Men Aidong, Multimedia Telecommunication Centre, BUPTnCZT 表达式表达式3.5.1 CZT：定义定义1）取取样点点沿沿螺螺旋旋线按按角角度度间隔隔0 分分布布，0 0 时，取取样轨迹迹逆逆时针旋旋转；0 1，随随着着 k 的的增增加加，向向内内盘旋旋，朝朝向向原原点点；W01，随随着着k 的增加，向外的增加，向外盘旋；旋；3)若若 W0=1， 一一 段段 圆 弧弧 ， 若若 同同 时 A0=1，则为单位位圆一一部部分分，此此时 CZTx(n) = DFTx(n) （M=N）。67 北北京京邮邮电电大大学学信信息息与与通通信
75、信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT例例3.27 A = 0.8*exp(j*pi/6); 起始半径起始半径 0.8，起始角，起始角 pi/6 W = 0.985*exp(-j*pi*0.05); %W01，内旋；取样间隔，内旋；取样间隔 0.05piM = 91; 计算点数计算点数z2 = A*(W.(-(0:M-1);Zplane( ,z2.)-1-0.500.51-1-0.8-0.6-0.4-0.200.20.40
76、.60.81Real PartImaginary Part3.5.1 CZT：定义定义69 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTnCZT 表示为线性卷积形式：表示为线性卷积形式：利用布鲁斯坦利用布鲁斯坦 (Bluestein) 提出的等式提出的等式 把在把在 CZTx(n) 中的中的 Wnk 因子展开，得：因子展开，得：3.5.2 CZT：快速算法快速算法n计计算算量量：直直接接
77、计计算算 M 点点的的 CZT，需需要要 MN 次次复复数数乘乘法法，M(N-1) 次次复复数加法，需要快速算法。数加法，需要快速算法。把上述运算转换为把上述运算转换为线性卷积形式线性卷积形式，从而可以采用，从而可以采用 FFT 算法，提高运算法，提高运算速度。算速度。70 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.5.2 CZT：快速算法快速算法令令则则式中式中71 北北京京邮邮
78、电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.5.2 CZT：快速算法快速算法h(n)x(n)g(n)X(zk)序列：序列：可可以以想想像像为为频频率率随随时时间间（n）线线性性增增长长的的复复指指数数序序列列，在在雷雷达达中中这这类类信信号号，称称为为线线性性调调频频信信号号（chirp Signal)，因因此此，这这里里 z 变变换换称称为为线性调频线性调频 z 变换。变换。该信号的瞬时频率该
79、信号的瞬时频率 i=2t 正比于时间正比于时间 t，因此，该信号的频率随时间线性增长。，因此，该信号的频率随时间线性增长。类比：类比：72 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTn取值范围取值范围n：0N-1，k：0M-1因因果果序序列列 g(n) 的的长长度度为为 N，而而序序列列 h(n) 的的长长度度为为 N+M-1，并并位位于于区区间间内内-(N-1)(M-1)，所所以以卷
80、卷积积后后的的序序列列 y(n) 的的长长度度为为 2N+M-2，且且位位于于区区间间内内 (N-1)（NM2）。）。实际上只要得到区间实际上只要得到区间 0(M-1）内的线性卷积结果就能够完成）内的线性卷积结果就能够完成 CZT 的计算。的计算。3.5.2 CZT：快速算法快速算法73 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT用用循循环环卷卷积积代代替替线线性性卷卷积积且且不不产产
81、生生混混迭迭失失真真的的条条件件是是：循循环环卷卷积积的的点点数数（周周期期）应应大大于于或或等等于于 2NM2，但但 CZT 只只需需要要前前 0(M1) 值值，对对以以后后的的其其它它值值是是否否混混迭迭并并不不关关心心。因因此此，可可将将循循环环卷卷积积的的点点数数缩缩减减到到最最小小为为 N+M-1。为为了了基基 2 FFT 运运算算，取取 L= N+M-1，L=2m 。3.5.2 CZT：快速算法快速算法74 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Mu
82、ltimedia Telecommunication Centre, BUPTng(n)、h(n) 序列的构造序列的构造为为了了进进行行循循环环卷卷积积，把把 h(n) 以以周周期期 L 进进行行周周期期拓拓展展，再再取取主主值值序列，从而得到圆周卷积的一个序列。序列，从而得到圆周卷积的一个序列。从从 n=M 开始补开始补 L（NM1）个零或任意值，补到）个零或任意值，补到 n=L-N 处。处。从从 n=LN1 到到 L1，取，取 h(n) 的周期拓展序列的周期拓展序列 h(L-n)。进行循环卷积的另一个序列进行循环卷积的另一个序列 g(n) 只需要补零到只需要补零到 L 即可。即可。3.5.
83、2 CZT：快速算法快速算法75 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.5.2 CZT：快速算法快速算法h(n) 的构造：的构造：76 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre,
84、 BUPTnCZT 快速算法快速算法 下下面面说说明明上上述述计计算算方方案案的的具具体体实实现现，既既然然 X(zk) 可可用用线线性性卷卷积积表表示示，我我们们就就可可以以用用 DFT 来来计计算算线线性性卷卷积积，只只不不过过 DFT 换成换成 FFT，从而得到，从而得到 CZT 的快速算法。的快速算法。3.5.2 CZT：快速算法快速算法L 点点 DFTH(k)h(n) 构造构造长度度 MN-1长度度 Ng(n) 补零补零L 点点 DFTG(k)G(k)H(k)L=N+M-1L 点点 IDFTy(k)77 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心
85、门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.5.2 CZT：快速算法快速算法78 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTn CZT (Chirp z-transform) 变换的变换的 Matlab 句法为：句法为： y = czt(x,m,w,a)
86、 y = czt(x)CZT 是是 x 信信号号沿沿着着 w 和和 a 定定义义的的螺螺旋旋线线进进行行的的 z 变变换换。m 是是说说明明了了变变换换的的长长度度，w 是是 z 平平面面上上感感兴兴趣趣的的那那部部分分螺螺旋旋线线上上取取样样点点之之间间的的比比值值，a 是是螺螺旋旋线线上上的的复复数数起起始始点点。Z 平平面面上上的的螺螺旋旋线线， 或或 “线性调频脉冲线性调频脉冲” 定义为：定义为： z = a*(w.-(0:m-1)如果如果 x 是矩阵，是矩阵，czt(x,m,w,a) 是是 x 的列变换。的列变换。y = czt(x) 使用下列缺省值：使用下列缺省值： m = len
87、gth(x) w = exp(j*2*pi/m) a = 1 对对于于这这些些缺缺省省值值，czt 返返回回 x 信信号号在在单单位位园园上上 m 份份等等间间隔隔的的 z 变变换换，也也就就是是 x 的的离离散散傅傅立立叶叶变变换换，或或者者 fft(x)。空空矩矩阵阵 说说明明了了这些参数的缺省值。这些参数的缺省值。3.5.3 CZT：Matlab 实现实现79 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication
88、Centre, BUPT例例3.28 用用 czt 放大一个滤波器频率响应的窄带部分（放大一个滤波器频率响应的窄带部分（100150Hz）。）。n首先设计一个滤波器：首先设计一个滤波器： % 30th order LPF filter, cut-off frequency Wn=125/500,use boxcar window h = fir1(30,125/500,boxcar(31); n建立频率和建立频率和 CZT 初始化参数：初始化参数： Fs = 1000; f1 = 100; f2 = 150; % in Hertz m = 1024; 取样点数取样点数 w = exp(-j*2
89、*pi*(f2-f1)/(m*Fs); % 取样点间隔取样点间隔 a = exp(j*2*pi*f1/Fs); 取样点起始位置取样点起始位置n计算滤波器的计算滤波器的 DFT 和和 CZT 变换：变换： y = fft(h,1000); z = czt(h,m,w,a);n得到频率响应和比较结构：得到频率响应和比较结构： fy = (0:length(y)-1)*1000/length(y); fz = (0:length(z)-1)*(f2-f1)/length(z) + f1; plot(fy(1:500),abs(y(1:500); axis(1 500 0 1.2); plot(fz,
90、abs(z); axis(f1 f2 0 1.2)3.5.3 CZT：Matlab 实现实现80 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT主题概述主题概述1 -绪论绪论2 -离散时间系统和离散时间信号的变换离散时间系统和离散时间信号的变换3 -离散傅里叶变换及其快速计算方法离散傅里叶变换及其快速计算方法 3.1 问题的提出问题的提出 3.2 DFS（离散傅里叶级数）（离散傅里叶级数）
91、 3.3 DFT（有限离散傅里叶变换）（有限离散傅里叶变换） 3.4 FFT（快速离散傅里叶变换）（快速离散傅里叶变换） 3.5 CZT及其快速算法及其快速算法 3.6 其它变换其它变换 3.7 本章小结本章小结4 IIR 数字滤波器设计和实现数字滤波器设计和实现5 FIR 数字滤波器设计和实现数字滤波器设计和实现6 数字信号处理中的有限字长效应数字信号处理中的有限字长效应81 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunic
92、ation Centre, BUPTn二维二维 DFT / FFTnDFT 的局限性和克服方法的局限性和克服方法测不准原理测不准原理三个局限性三个局限性短时傅立叶变换短时傅立叶变换 STFT时频联合分析时频联合分析滤波器组滤波器组小波变换小波变换框架框架 (Frame)n其它离散变换其它离散变换KLT 变换变换Walsh 变换变换Hadamard变换变换离散余弦变换离散余弦变换3.6 其它变换其它变换82 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedi
93、a Telecommunication Centre, BUPTnDFT/FFT 计计算算不不仅仅仅仅局局限限于于语语音音和和音音乐乐等等一一维维信信号号，二二维维信信号号的的频频谱谱特特性性也也很很重重要要。2D DFT 是是 1D DFT 的的自自然然延伸。延伸。n2D DFT 定义如下：定义如下：n2D DFT 的的可可分分离离性性：指指首首先先沿沿着着图图像像（二二维维信信号号）的的每每一一行行计计算算一一维维变变换换，然然后后沿沿着着这这一一中中间间结结果果的的每每一一列列再再计计算算一一维维变变换换，以以此此计算二维计算二维 2D-DFT变换，得到最后的结果。变换，得到最后的结果。
94、3.6.1 其它变换：其它变换：2D DFT/FFT83 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT对于每个对于每个x值，当值，当 v=0,1,N-1时，该式时，该式为完整的一维傅里叶变换。为完整的一维傅里叶变换。其中其中1D N-DFTyv1D M-DFTxu3.6.1 其它变换：其它变换：2D DFT/FFT84 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒
95、体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTn直直接接根根据据前前面面的的公公式式，计计算算 N 点点一一维维傅傅里里叶叶变变换换需需要要 N2 次次复复数数乘乘法，法，N(N-1) N2 次复数加法运算。次复数加法运算。n快速傅里叶变换只需要约快速傅里叶变换只需要约 Nlog2N 次运算。次运算。例例如如 N=1024，直直接接傅傅里里叶叶变变换换需需要要大大约约 106 次次操操作作，快快速速傅傅里叶变换只需要里叶变换只需要 104 次操作。次操作。
96、n2D-FFT 计算量计算量3.6.1 其它变换：其它变换：2D DFT/FFT85 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性：局限性： Heisenberg 测不准原理测不准原理n不定原理（不定原理（Heisenberg Heisenberg 测不准原理，测不准原理，Heisenberg-Gabor Heisenberg-Gabor 不定原理不定原理）：）
97、： 给定信号给定信号 x(t)，若，若 ，则：，则：当且仅当当且仅当 x(t) 为高斯信号，即为高斯信号，即 时等号成立，式中：时等号成立，式中： 显然，这是方差的标准定义。显然，这是方差的标准定义。通常定义通常定义 2t、2分别是信分别是信号的时宽和带宽。号的时宽和带宽。定义定义t 为信号的时宽带宽积为信号的时宽带宽积。86 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTn测测不不准准原
98、原理理是是信信号号处处理理中中的的一一个个重重要要的的基基本本定定理理，不不可可能能违背；违背；n测测不不准准原原理理给给出出了了信信号号时时宽宽-带带宽宽之之间间的的制制约约关关系系：对对于于给定的信号，其时带与带宽的乘积为一个常数给定的信号，其时带与带宽的乘积为一个常数。当当信信号号的的时时宽宽减减少少时时，其其带带宽宽将将相相应应增增加加，当当时时宽宽减减到到无无穷穷小小时时，带宽将变成无穷大，如时域的带宽将变成无穷大，如时域的函数；函数；反反之之亦亦然然，如如频频域域处处的的 函函数数，时时域域为为 ejt =cost + jsint ,其其在时域的持续时间是在时域的持续时间是 -+
99、。这这就就是是说说，信信号号的的时时宽宽与与带带宽宽不不可可能能同同时时趋趋于于无无限限小小，这这一一基基本本关系即是我们将要讨论的关系即是我们将要讨论的时间分辨率和频率分辨率的制约关系时间分辨率和频率分辨率的制约关系。在在这这一一基基本本关关系系的的制制约约下下，人人们们在在竭竭力力探探索索既既能能得得到到好好的的时时间间分分辨辨率率（或或窄窄的的时时宽宽）又又能能得得到到好好的的频频率率分分辨辨率率（或或窄窄的的带带宽宽）的的信号分析方法。信号分析方法。若若信信号号 x(t) 的的持持续续时时间间是是有有限限的的，我我们们称称其其为为是是“紧紧支支撑撑”（Compact Support）的
100、的，其其时时间间的的持持续续区区间间（如如 t=t1t2），称称为为“支支撑撑范范围围”；对对频频率率信信号号，也使用类似的称呼。也使用类似的称呼。3.6.2 DFT 局限性：局限性： Heisenberg 测不准原理测不准原理87 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性局限性n1807年年，傅傅立立叶叶在在论论文文On the Propagation o
101、f Heat in Solid Bodies中中提提出出了了周周期期信信号号傅傅立立叶叶级级数数的的概概念念，1822年年，傅傅立立叶叶又又在在著著作作Thorie analytique de la chaleur in 1822中中提提出出了了非非周周期期信信号号分分解解的的概概念念，即即傅傅立叶变换。立叶变换。n傅傅立立叶叶变变换换不不但但是是重重要要的的数数学学分分支支，也也是是信信号号分分析析与与信信号号处理的重要工具。处理的重要工具。n在在傅傅立立叶叶变变换换应应用用中中，人人们们早早就就发发现现了了其其不不足足Gabor，Theory of Communication, IEEE,
102、 1946，体现在三个方面：，体现在三个方面：傅立叶变换在傅立叶变换在时间和频率定位时间和频率定位功能上的局限性；功能上的局限性；傅立叶变换对于傅立叶变换对于非平稳信号非平稳信号的局限性；的局限性；傅立叶变换在傅立叶变换在分辨率上的局限性分辨率上的局限性88 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTn时时间间和和频频率率的的定定位位：某某一一个个特特定定时时间间 t0 所所对对应应的
103、的频频率率是是多少，或对某一个特定的频率多少，或对某一个特定的频率 0所对应的时间是多少。所对应的时间是多少。 n有限长序列的离散付氏变换对定义为有限长序列的离散付氏变换对定义为3.6.2 DFT 局限性：局限性：时间和频率的定位时间和频率的定位对对给给定定的的某某一一频频率率k0，为为求求该该频频率率处处的的傅傅氏氏变变换换 X(k0)，DFTx(n) 中中的的求求和和范范围围 n 需需要要从从 0 到到 N-1，即即需需要要 x(n) 整整个个时时域域的的“知识知识”。反反之之，如如果果我我们们要要求求出出某某一一时时刻刻 n0T 处处的的值值 x(n)，由由 IDFTX(k) 式式，我我
104、们们仍仍需需要要对对 X(k) 从从 0 到到 N-1 求求和和，同同样样也也需需要要 X(k) 整整个个频域的频域的“知识知识”。实实际际上上，傅傅氏氏变变换换 X(k) 是是信信号号 x(n) 在在整整个个求求和和(积积分分)区区间间的的时时间间范范围围内内所所具具有有的的频频率率特特征征的的平平均均表表示示。反反之之，也也是是如如此此，因因此此，傅立叶变换不具有时间和频率的傅立叶变换不具有时间和频率的“定位定位”功能。功能。 89 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men A
105、idong, Multimedia Telecommunication Centre, BUPTn例例1：设信号：设信号 x(n) 由三个不同频率的正弦所组成由三个不同频率的正弦所组成: -101Xa(n)Signal in time|X(ejw)|Linear scaleEnergy spectral density00.10.20.30.4xa(n) 时频分布的二维表示时频分布的二维表示50100150200250300350Time sFrequency 501001502002503003500xa(n)时频分布的三维表示时频分布的三维表示 3.6.2 DFT 局限性：局限性：时间和频
106、率的定位时间和频率的定位90 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTn例例2： DTMF（Dual Tone Multifrequency）双音多频信号）双音多频信号每当按下每当按下一个按键一个按键时，产生高、低频率的时，产生高、低频率的两个音频信号两个音频信号；高、低频音的一个组合表示一个特定的数字高、低频音的一个组合表示一个特定的数字 09、#、* 和和 AD。1209Hz13
107、36Hz1477Hz1633Hz697Hz941Hz852Hz770Hz0 1 2 3 4 5 6 7 8 9 * # a b c d 整个号码的频谱，只有整个号码的频谱，只有 8 个频率个频率3.6.2 DFT 局限性：局限性：时间和频率的定位时间和频率的定位91 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性：局限性：非平稳信号非平稳信号n非平稳的定义：非平稳
108、的定义：两类说法，出发点不同，无大碍。两类说法，出发点不同，无大碍。非平稳随机信号非平稳随机信号在在平平稳稳和和非非平平稳稳随随机机信信号号定定义义中中，前前者者是是指指随随机机信信号号的的一一阶阶和和二二阶阶统统计计特特性性（均均值值、方方差差）不不随随时时间间变变换换，自自相相关关函函数数与与观观察察的的时时间间起点无关。起点无关。若若信信号号是是平平稳稳的的，则则满满足足维维纳纳-辛辛钦钦关关系系，即即功功率率谱谱密密度度与与自自相相关关函函数互为傅立叶变换：数互为傅立叶变换：非平稳信号非平稳信号频率随时间变化的信号，称为时变信号，或非平稳信号频率随时间变化的信号，称为时变信号，或非平稳
109、信号频率不随时间变化的时不变信号，称为平稳信号频率不随时间变化的时不变信号，称为平稳信号注注意意与与随随机机信信号号中中平平稳稳/非非平平稳稳定定义义的的区区别别，说说一一个个信信号号是是平平稳稳信信号号，要指明是频率不随时间变化，还是平稳随机信号。要指明是频率不随时间变化，还是平稳随机信号。若信号是非平稳的，则不满足上述关系。若信号是非平稳的，则不满足上述关系。92 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication
110、 Centre, BUPTn例例3：一个线性频率调制信号（雷达中的：一个线性频率调制信号（雷达中的 Chirp）为：）为：该该信信号号的的瞬瞬时时频频率率 i=2t 正正比比于于时时间间 t，因因此此该该信信号号的的频频率率是是时时变的。变的。傅立叶变换对时变信号的局限性：傅立叶变换对时变信号的局限性：时域波形看，随着时间的增长，信号的振荡（频率）愈来愈快。时域波形看，随着时间的增长，信号的振荡（频率）愈来愈快。但从频域波形看不出该信号的频率随时间线性增长的特点。但从频域波形看不出该信号的频率随时间线性增长的特点。IF 曲线也是信号能量曲线也是信号能量的主要集中处。的主要集中处。Chirp 信
111、号的能量主要集中信号的能量主要集中在时间在时间-频率平面的斜频率平面的斜线上。线上。 -0.500.51X(n)Signal in time|X(ejw)|Linear scaleEnergy spectral density2040608010012000.10.20.30.4WV, lin. scale, contour, Threshold=5%Time sFrequency x(n)时频分布时频分布x(n)时频分布三维表示时频分布三维表示从时频分布能够明从时频分布能够明确体现出频率与时确体现出频率与时间的正比关系间的正比关系3.6.2 DFT 局限性：局限性：时间和频率的定位时间和频率
112、的定位93 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性：局限性：时间和频率分辨率时间和频率分辨率n分辨率分辨率 (Resolution) 是信号处理的基本概念：是信号处理的基本概念：它包含了信号的时域和频域两个方面；它包含了信号的时域和频域两个方面；它是指对信号所能辨别的时域或频域的最小间隔（又称最小分辨细胞）它是指对信号所能辨别的时域或频域的最小间隔（又称最
113、小分辨细胞）。频频率率分分辨辨率率是是通通过过一一个个频频域域窗窗函函数数观观察察频频谱谱时时所所看看到到的的频频率率的的宽宽度度，时时间间分分辨辨率率是通过一个是通过一个时域窗函数时域窗函数观察信号时所看到的时间的宽度。观察信号时所看到的时间的宽度。显然，窗函数越窄，相应的分辨率就越好。显然，窗函数越窄，相应的分辨率就越好。n分辨能力的好坏取决于：分辨能力的好坏取决于：信号的特点；信号的特点；信号的长度；信号的长度；所用的算法。所用的算法。n追追求求时时间间和和频频率率分分辨辨率率同同时时完完好好，但但由由测测不不准准原原理理可可知知，时时间间和和频频率率分分辨辨率率不不可可能能同同时时达达
114、到到最最好好（即即分分辩辩间间隔隔最最小小）。在在实实际际中中，需需要要根根据据信信号号特特点点和和处理需要，选择不同的时间和频率分辨率。处理需要，选择不同的时间和频率分辨率。对对在在时时域域具具有有瞬瞬变变的的信信号号，希希望望时时域域的的分分辨辨率率要要好好（即即时时域域的的观观察察间间隔隔尽尽量量短短），以以保保证证能能观观察察到到该该瞬瞬变变信信号号发发生生的的时时刻刻及及瞬瞬变变的的形形态态，当当然然，这这时时就就忽忽视视频频率率分分辨率；辨率；反之，对于时域缓变的信号，就没必要强调时域分辨率，而需好的频率分辨率。反之，对于时域缓变的信号，就没必要强调时域分辨率，而需好的频率分辨率。
115、n好的信号分析算法，应能适应信号的特点而自动调节时间和频率分辨率。好的信号分析算法，应能适应信号的特点而自动调节时间和频率分辨率。94 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性：局限性：时间和频率分辨率时间和频率分辨率n理论上，傅立叶变换可以写成如下的内积形式：理论上，傅立叶变换可以写成如下的内积形式： 表示信号和的表示信号和的内积内积若若x,y 是连续的，
116、则内积是连续的，则内积若若x,y 是离散的，则内积是离散的，则内积 n信号信号x(t)的傅立叶变换等效于的傅立叶变换等效于 x(t) 和基函数和基函数 ejt 作内积作内积:基基函函数数 ejt 在在频频域域是是位位于于处处的的函函数数，因因此此，当当用用傅傅立立叶叶变变换换来来分析信号的频域行为时，它具有分析信号的频域行为时，它具有最好的频率分辨率最好的频率分辨率。但但是是，ejt 在在时时域域对对应应的的是是正正弦弦函函数数（ ejt =cost + sint），其其在在时时域域的的持持续续时时间间是是 (-, + )，因因此此，在在时时域域有有着着最最坏坏的的时时间间分辨率分辨率。对傅立
117、叶反变换，情况正好相反。对傅立叶反变换，情况正好相反。95 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性：局限性：时间和频率分辨率时间和频率分辨率n实实际际中中，将将 x(t) 乘乘以以矩矩形形窗窗进进行行截截短短，一一个个宽宽度度为为无无穷穷的的矩矩形形窗窗（即即直直流流信信号号）的的傅傅立立叶叶变变换换为为函函数数，反反之之亦亦然然。当矩形窗为有限宽时，其傅
118、立叶变换为一当矩形窗为有限宽时，其傅立叶变换为一Sinc函数，即函数，即 n矩形窗宽度和其频谱主瓣宽度（矩形窗宽度和其频谱主瓣宽度（-/T, +/T）成反比。）成反比。若若信信号号在在时时域域取取得得越越短短，即即保保持持高高的的时时间间分分辨辨率率，那那么么其其频频谱谱的的主瓣变宽，必然导致频域的频率分辨率下降。主瓣变宽，必然导致频域的频率分辨率下降。这这体体现现了了测测不不准准原原理理的的制制约约关关系系，也也体体现现了了傅傅立立叶叶变变换换中中时时间间和和频率分辨率所固有的矛盾。频率分辨率所固有的矛盾。-TT0Atx(t)X()02AT96 北北京京邮邮电电大大学学信信息息与与通通信信工
119、工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTnDFT 的的局局限限性性成成为为寻寻找找新新的的信信号号分分析析和和处处理理的的源源动力。动力。1932年年，Wigner 提提出出了了时时间间-频频率率联联合合分分布布的的概概念念，并将其用于量子物理；并将其用于量子物理；1946年年，Gabor 提提出出了了短短时时傅傅立立叶叶变变换换和和 Gaber 变变换换概念，从而开始了非平稳信号时频联合分析的研究；概念，从而开始了非平稳信号时
120、频联合分析的研究；20世世纪纪80年年代代，提提出出了了滤滤波波器器组组理理论论，为为信信号号的的子子带带分解提供了有力工具；分解提供了有力工具；20世世纪纪80年年代代后后期期，发发展展起起来来了了小小波波变变换换，它它不不仅仅扩扩展展了了信信号号时时频频联联合合分分析析的的概概念念，而而且且在在信信号号的的分分辨辨率率方面具有对信号特点的适应性。方面具有对信号特点的适应性。为为了了更更一一般般地地讨讨论论信信号号的的分分解解问问题题，人人们们提提出出了了框框架架（Frame）理论。）理论。.3.6.2 DFT 局限性：局限性：克服方法克服方法97 北北京京邮邮电电大大学学信信息息与与通通信
121、信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性克服方法：局限性克服方法：短时傅立叶变换短时傅立叶变换n傅立叶变换中的基函数傅立叶变换中的基函数 ejt 用下列基函数代替：用下列基函数代替： 则短时傅立叶变换则短时傅立叶变换 STFT 或加窗傅立叶变换的定义如下：或加窗傅立叶变换的定义如下：式中式中 g() 是对称的实数窗函数。是对称的实数窗函数。 STFTx(t,) 的的意意义义实实际际上上是是用用 g(
122、) 沿沿着着 t 轴轴滑滑动动，截截取取一一段段一一段段的的信信号号 x() ，然然后后对对其其作作傅傅立立叶叶变变换换，得得到到 （t, ) 平平面面上上二二维函数维函数 STFTx(t,)。 g() 的的作作用用是是保保持持时时域域为为有有限限长长（一一般般称称作作“有有限限支支撑撑或或紧紧支支撑撑”），其宽度越小，则时域分辨率越好。），其宽度越小，则时域分辨率越好。n使用不同的基函数可得到不同的分辨率效果。使用不同的基函数可得到不同的分辨率效果。98 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Process
123、ing, Men Aidong, Multimedia Telecommunication Centre, BUPTn可可以以证证明明，STFT 的的基基函函数数 gt,() 在在时时频频平平面面上上具具有有如如下下的的分分辨辨“细细胞胞”：其其中中心心在在 (t,) 处处，大大小小为为 ，不不管管 t, 取取何何值值（即即移移到到何何处处），该该“细细胞胞”的的面面积积始始终终保保持持不不变变。该该面面积积的的大大小小即即是是 STFT 的时频分辨率。的时频分辨率。 3.6.2 DFT 局限性克服方法：局限性克服方法：短时傅立叶变换短时傅立叶变换t1t221nSTFT 时间和频率分辨率的自适
124、应性时间和频率分辨率的自适应性快快变变信信号号对对应应的的是是高高频频信信号号，快快变变信信号号需需要要好好的的时时间间分分辨辨率率，以以观观察察其其快快变变部部分分（如如尖尖脉脉冲冲等等），即即观观察察的的时时间间宽宽度度要要小小，由由测测不不准准原原理理（时时宽宽带带宽宽积积）知道，该信号频域的分辨率必定要下降。知道，该信号频域的分辨率必定要下降。反反之之，慢慢变变信信号号对对应应低低频频信信号号，可可以以降降低低时时域域的的分分辨辨率率，从从而而在在低低频频处处获获得得好好的频率分辨率。的频率分辨率。希希望望时时频频分分析析算算法法能能自自动动适适应应这这一一要要求求，显显然然 STFT
125、 的的不不随随 t, 变变化化，因因而而 STFT 不不具具备备自自动动调调节节能能力力。后后面面讲讲的的小波变换具备这一能力。小波变换具备这一能力。99 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性克服方法：局限性克服方法：时频联合分析时频联合分析n短短时时傅傅立立叶叶变变换换 STFT 是是最最简简单单、最最直直观观的的时时频频联联合合分分析析，但但 STF
126、Tx(t,) 中中变变量量 t, 仍仍是是单单独独取取值值，它它并并不不是是严严格意义上的时频联合分析。格意义上的时频联合分析。n20世世纪纪中中叶叶以以来来，Wigner、Ville、Gabor 和和 Cohen 等等陆陆续续给给出出了了一一大大类类真真正正将将时时间间 t 和和频频率率 联联合合起起来来的的分分析析方法，并在方法，并在 80 年代得到广泛应用。年代得到广泛应用。nWigner-Ville时时频频分分布布：Wigner在在量量子子力力学学中中提提出出了了Wigner分分布布，1948年年 Ville 将将它它引引入入信信号号处处理理领领域域，得得到到了了著著名名的的 Wign
127、er-Ville 时时频分布：频分布：由由于于 x(t) 在在积积分分中中出出现现了了两两次次，所所以以又又称称该该式式为为双双线线性性时时频频分分布布，其其结结果果 Wx(t,)是是 t, 的的二二维维函函数数，它它有有着着一一系系列列好好的的性性质质，因因此是得到广泛应用的一种信号时频分析方法。此是得到广泛应用的一种信号时频分析方法。100 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUP
128、T3.6.2 DFT 局限性克服方法：局限性克服方法：时频联合分析时频联合分析nGabor展展开开：1946 年年 Gabor 提提出出了了信信号号时时频频展展开开的的思思想想，用时间和频率两个坐标同时表示一个信号，即用时间和频率两个坐标同时表示一个信号，即Gabor展开：展开：式式中中 g(t) 是是窗窗函函数数，Cm,n 是是展展开开系系数数，m 代代表表时时域域序序号号，n 代代表表频域序号。频域序号。nCohen 分布：分布：1966 年年Cohen 提出了如下的时频分布提出了如下的时频分布: 式中式中 g(,) 是处在是处在 (,) 平面的权函数平面的权函数;可可以以证证明明，若若g
129、(,) = 1，则则 Cohen 分分布布即即变变成成 Wigner-Ville 分分布布，给定不同的权函数，我们可得到不同的时频分布。给定不同的权函数，我们可得到不同的时频分布。在在80年年代代前前后后提提出出的的时时频频分分布布有有十十多多种种，统统称称为为 Cohen 类类时时频频分分布，简称布，简称 Cohen 类类， 101 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.
130、2 DFT 局限性克服方法：局限性克服方法：时频联合分析时频联合分析n对对给给定定的的信信号号 x(t)，人人们们希希望望能能找找到到一一个个二二维维函函数数 Wx(t,)，它应具有如下基本特性：，它应具有如下基本特性：它它是是人人们们最最关关心心的的两两个个物物理理量量时时间间 t 和和频频率率 的的联联合合分布函数；分布函数；它可反映它可反映 x(t) 的能量随时间的能量随时间 t 和频率和频率 变化的形态；变化的形态；既具有好的时间分辨率，同时又具有好的频率分辨率。既具有好的时间分辨率，同时又具有好的频率分辨率。 102 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒
131、媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性克服方法：局限性克服方法：滤波器组滤波器组n等带宽的等带宽的 M 通道滤波器组通道滤波器组(信号的子带分解信号的子带分解)：H0(z)MH1(z)MHM-1(z)Mn信信号号的的多多分分辨辨率率分分析析：信信号号按按二二进进制制分分解解，产产生生了了不不均均匀匀的的频频带带分分割割，从而得到不同的时间和频率分辨率。从而得到不同的时间和频率分辨率。(非均匀树状滤波器组）非均匀树状滤波器
132、组）a3(n)d3(n)d1(n)d2(n)x(n)a1(n)H1(z)2H0(z)2H1(z)2H0(z)2H0(z)2H1(z)2a2(n)|X(j)|X(j)|103 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性克服方法：局限性克服方法：小波变换定义小波变换定义n在在80年年代代后后期期及及90年年代代初初期期所所发发展展起起来来的的小小波波变变换换理理论
133、论已已形形成成了了信信号号分分析析和和信信号号处处理理的的又又一一强强大大的的工工具具。其其实实，小小波分析可看作信号时频分析的又一种形式。波分析可看作信号时频分析的又一种形式。 n对对于于给给定定信信号号 x(t)，希希望望找找到到一一个个基基本本函函数数(t)，并并通通过过(t) 的伸缩与位移构成一族函数的伸缩与位移构成一族函数 a,b(t)：式式中中, a 是是尺尺度度因因子子，b 是是位位移移， a、b 均均为为常常数数，且且 a0。(t) 又又称称为为基本小波或母小波；基本小波或母小波；a,b(t) 称为小波基函数或小波基。称为小波基函数或小波基。n小波变换定义为信号小波变换定义为信
134、号 x(t) 与小波基与小波基a,b(t) 的内积，即：的内积，即：104 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性克服方法：局限性克服方法：小波变换定义小波变换定义n小小波波变变换换对对信信号号的的“尺尺度度位位移移”联联合合分分析析，也也是是时时频频分分布的一种：布的一种：尺尺度度：尺尺度度因因子子 a 的的作作用用是是把把母母小小波波(t) 作作伸伸缩
135、缩。由由傅傅立立叶叶变变换换的的性性质质可可知知，若若(t)的的傅傅立立叶叶变变换换是是(j)，则则(t/a) 的的傅傅立立叶叶变换是变换是 a(ja)。若若a1，则则(t/a) 表表示示将将(t) 在在时时间间轴轴上上展展宽宽，而而将将 (j) 在在频频率率轴上压缩轴上压缩;若若a0，a=1 ,(c) b 不变，不变，a=2, (d)分析范围。分析范围。(a)(b)(c)(d)n式式中中的的 因因子子是是为为了了保保证证在在不不同同的的尺尺度度 a 时时，小小波波基基 a,b(t) 始终能和母小波始终能和母小波(t) 有着相同的能量。即：有着相同的能量。即： 106 北北京京邮邮电电大大学学
136、信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性克服方法：局限性克服方法：小波变换特点小波变换特点n时间和频率定位功能时间和频率定位功能小小波波基基a,b(t) 和和小小波波变变换换 WTx(a,b) 在在时时域域中中是是有有限限支支撑撑的的，具具有有时间定位时间定位功能；功能；a,b() 和和 X() 在在频频域域中中也也是是有有限限支支撑撑的的，从从而而具具有有频频率率定定位位功能；功
137、能；n小波变换符合时宽带宽积约束小波变换符合时宽带宽积约束若若母母小小波波(t) 的的时时间间中中心心是是 t0，时时宽宽是是t，则则(t/a)的的时时间间中中心心变变为为 at0，时宽变成，时宽变成 a t ；若若母母小小波波(t) 的的频频谱谱() 的的频频率率中中心心是是0，带带宽宽是是， 则则(t/a) 的频谱的频谱 a(a) 的频率中心变为的频率中心变为0 /a，带宽变成，带宽变成/a。(t/a) 的的时时宽宽带带宽宽积积仍仍是是 t，与与尺尺度度 a 无无关关。这这一一方方面面说说明明小小波波变变换换 WTx(a,b) 的的时时频频关关系系也也受受测测不不准准原原理理制制约约，但但
138、另另一一方方面也揭示了小波变换的一个重要性质，即恒面也揭示了小波变换的一个重要性质，即恒 Q 性质。性质。 nQ 值（品质因数）定义：值（品质因数）定义：带宽带宽/ /中心频率中心频率107 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性克服方法：局限性克服方法：小波变换特点小波变换特点n小波变换的恒小波变换的恒 Q 性质性质母小波母小波(t) 的的 Q 值：值：
139、(t/a) 的的 Q 值保持不变：值保持不变：不不论论 a 为为何何值值 (a0)， (t/a) 始始终终和和(t) 具具有有相相同同的的品品质质因因数数 Q。恒恒 Q 性性质质是是小小波波变变换换的的一一个个重重要要性性质质，也也是是区区别别于于其其它它类类型型变变换且被广泛应用的一个重要原因。换且被广泛应用的一个重要原因。下图说明了下图说明了()和和(a)的带宽及中心频率随的带宽及中心频率随 a 变化的情况。变化的情况。 a=1 a=2 a=1/2108 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Proces
140、sing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性克服方法：局限性克服方法：小波变换特点小波变换特点n小波变换的时频区间小波变换的时频区间由由上上页页图图，当当 a 变变小小时时，对对 x(t) 的的时时域域观观察察范范围围变变窄窄，但但对对 X() 的的频频率率观观察察范范围围变变宽宽，且且观观察察的的中中心心频频率率向向高高频频处处移移动动。反反之之，当当 a 变变大大时时，对对 x(t) 的的时时域域观观察察范范围围变变宽宽，频频域域观观察察范范围围变变窄窄，且且分分析析的的中中心心频频率率向向
141、低频处移动。低频处移动。 在在不不同同尺尺度度下下小小波波变变换换所所分分析析的的时时宽宽、带带宽宽、时时间间中中心心和和频频率率中中心心的的关关系，如图：系，如图：n由由于于恒恒 Q 性性质质，因因此此在在不不同同尺尺度度下下，小小波波变变换换的的三三个个时时、频频分分析析区区间间（即即三三个个矩矩形形）的的面面积积保保持持不不变变，但但提提供供了了一一个个在在时时、频频平平面面上上长长度可调的分析窗口。度可调的分析窗口。n该该分分析析窗窗口口在在高高频频端端的的频频率率分分辨辨率率不不好好（矩矩形形窗窗的的频频率率边边变变长长），但但时时域域的的分分辨辨率率变变好好（矩矩形形的的时时间间边
142、边变变短短）；反反之之，在在低低频频端端频频率率分分辨辨率率变变好好，而而时时域域分分辨辨率率变变差差。但但在在不不同同的的 a 值值下下，分分析析窗窗的的面面积保持不变，也即时频分辨率可以随分析任务的需要作出调整。积保持不变，也即时频分辨率可以随分析任务的需要作出调整。109 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性克服方法：局限性克服方法：小波变换特点小
143、波变换特点n小波变换对信号的自适应性小波变换对信号的自适应性小波变换可以自动满足客观实际信号的需要小波变换可以自动满足客观实际信号的需要信信号号中中的的高高频频成成份份往往往往对对应应时时域域中中的的快快变变成成份份，如如陡陡峭峭的的前前沿沿、后后沿沿、尖尖脉脉冲冲等等。对对这这一一类类信信号号分分析析时时则则要要求求时时域域分分辨辨率率要要好好以以适适应应快快变变成成份份间间隔隔短短的的需需要要，对对频频域域的的分分辨辨率率则则可可以以放放宽宽，当当然然，时时、频分析窗也应处在高频端的位置。频分析窗也应处在高频端的位置。与与此此相相反反，低低频频信信号号往往往往是是信信号号中中的的慢慢变变成
144、成份份，对对这这类类信信号号分分析析时时一一般般希希望望频频率率的的分分辨辨率率要要好好，而而时时间间的的分分辨辨率率可可以以放放宽宽，同同时时分分析析的中心频率也应移到低频处。的中心频率也应移到低频处。当当用用较较小小的的 a 对对信信号号作作高高频频分分析析时时，实实际际上上是是用用高高频频小小波波对对信信号号作作时时间间上上的的细细致致观观察察，当当用用较较大大的的 a 对对信信号号作作低低频频分分析析时时，实实际际上上是是用用低低频频小小波波对对信信号号作作时时间间上上概概貌貌观观察察。小小波波变变换换的的这这一一特特点点即既符合对信号作实际分析时的规律，也符合人们的视觉特点。即既符合
145、对信号作实际分析时的规律，也符合人们的视觉特点。n综综上上所所述述，由由于于小小波波变变换换具具有有恒恒 Q 性性质质及及自自动动调调节节对对信信号号分分析析的的时时宽宽-带带宽宽等等一一系系列列突突出出优优点点，因因此此被被人人们们称称为为信号分析的信号分析的“数学显微镜数学显微镜”。 110 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性克服方法：局限性克服方
146、法：小波变换的容许条件小波变换的容许条件n小波变换的容许条件（小波变换存在的条件）：小波变换的容许条件（小波变换存在的条件）： 并并不不是是时时域域的的任任一一函函数数 (t)L2(R) 都都可可以以充充当当小小波波，其其可可以以作作为为小小波波的的必要条件是其傅里叶变换必要条件是其傅里叶变换 满足上述容许条件；满足上述容许条件；必必有有 ，否否则则 c 必必趋趋于于无无穷穷（分分母母=0）。这这等等效效于于小小波波函函数数(t) 是带通函数；是带通函数；由由于于 ，因因此此必必有有 ，(t) 的的取取值值必必然然是是有有正正有有负负，也即它是振荡的。也即它是振荡的。 n上上述述三三条条描描绘
147、绘了了小小波波函函数数的的大大致致特特征征，即即是是一一带带通通函函数数，它它的的时时域域波波形形应应是是振振荡荡的的。此此外外，从从时时频频定定位位的的角角度度，希希望望是是有有限限支支撑撑的的，因因此它应是此它应是快速衰减的快速衰减的。n小波（小波（wavelet）：时域有限长，且是振荡的一类函数。）：时域有限长，且是振荡的一类函数。111 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUP
148、T3.6.2 DFT 局限性克服方法：局限性克服方法：小波变换分类小波变换分类n小波变换是小波变换是80年代后期发展起来的应用数学分支年代后期发展起来的应用数学分支小小波波理理论论：法法国国数数学学家家 Meyer .Y、地地质质物物理理学学家家 Morlet .J 和和理理论论物理学家物理学家 Grossman .A 对小波理论作出了突出的贡献。对小波理论作出了突出的贡献。小小波波工工程程应应用用：法法国国学学者者 Daubechies .I 和和 Mallat .S 在在将将小小波波理理论论引引入入工工程程应应用用，特特别别是是信信号号处处理理领领域域起起到到了了重重要要的的作作用用。人人
149、们们称称这这些人为些人为“法国学派法国学派”。n小波变换的分类：小波变换的分类：第第一一类类是是所所谓谓的的“经经典典小小波波”，在在 MATLAB 中中把把它它们们称称作作“原原始始（Crude）小波）小波”。这是一批在小波发展历史上比较有名的小波；。这是一批在小波发展历史上比较有名的小波；第二类是第二类是 Daubecheis 构造的构造的正交小波正交小波；第三类是由第三类是由 Cohen、Daubechies 构造的构造的双正交小波双正交小波。112 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Process
150、ing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性克服方法：局限性克服方法：经典小波经典小波nHaar 小小波波：源源自自于于数数学学家家 Haar 于于1910年年提提出出的的Haar正正交函数集，其定义是：交函数集，其定义是： nHaar 小波有很多优点：小波有很多优点： Haar小波在时域是紧支撑的；小波在时域是紧支撑的；Haar小波属正交小波小波属正交小波 ；Haar波波是是对对称称的的，是是目目前前唯唯一一一一个个既既具具有对称性又是有限支撑的正交小波；有对称性又是有限支撑的正交小波；Haar
151、小波仅取小波仅取+1和和-1，计算简单。，计算简单。Haar小小波波是是不不连连续续小小波波，使使其其在在实实际际的的信号分析与处理中受到了一定限制；信号分析与处理中受到了一定限制； Haar小小波波有有上上述述优优点点，在在教教科科书书与与论论文文中常被用作范例来讨论。中常被用作范例来讨论。113 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性克服方法：局限性克
152、服方法：经典小波经典小波nMorlet 小波小波 :Morlet小波是一个具有高斯包络的单频率复正弦函数。小波是一个具有高斯包络的单频率复正弦函数。考考虑虑到到待待分分析析的的信信号号一一般般是是实实信信号号，所所以以在在 MATLAB中中将将它它改改造为左式，造为左式，并取并取 0=5。该该小小波波不不是是紧紧支支撑撑的的，t 理理论论上上可可取取 (-, +)。但但是是当当0=5，或取更大的值时，或取更大的值时， (t) 和和() 在时域和频域都具有很好的集中。在时域和频域都具有很好的集中。Matlab改造改造Morlet小波时域波形小波时域波形 Morlet小波的频谱小波的频谱 nMor
153、let 小波的特点小波的特点 : 不是正交的；不是正交的；也不是双正交的；也不是双正交的；是对称的；是对称的；可用于连续小波变换；可用于连续小波变换；是是应应用用较较为为广广泛泛的的一一种种小小波。波。114 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性克服方法：局限性克服方法：经典小波经典小波nMexican hat 小波小波 (墨西哥草帽小波，又称墨西哥草帽
154、小波，又称 Marr 小波小波 ) :式中式中该该小小波波是是由由一一高高斯斯函函数数的的二二阶阶导导数数得得到到的的，它它沿沿着着中中心心轴轴旋旋转转一一周所得到的三维图形犹如一顶墨西哥草帽，故由此而得名。周所得到的三维图形犹如一顶墨西哥草帽，故由此而得名。墨西哥草帽小波时域波形墨西哥草帽小波时域波形 频谱频谱 n墨西哥草帽小波的特点墨西哥草帽小波的特点 : 不是紧支撑的；不是紧支撑的；不是正交的；不是正交的；不是双正交的；不是双正交的；是对称的；是对称的；可用于连续小波变换；可用于连续小波变换；由由于于该该小小波波在在=0处处有有二二阶阶零零点点，因因此此它它满满足足容容许许条条件件，且且
155、该该小小波波比比较较接接近近人人眼眼视视觉觉的的空空间间响响应应特特征征，可可用用于于计计算算机机视视觉觉中中的图像边缘检测。的图像边缘检测。115 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性克服方法：局限性克服方法：经典小波经典小波nGaussian 小小波波：它它是是由由一一基基本本高高斯斯函函数数对对时时间间求求导导而而得得到的，定义为：到的，定义为：式
156、中定标常数式中定标常数 c 是保证是保证 高斯小波高斯小波(k=4) 时域波形时域波形 频谱频谱n高斯小波的特点高斯小波的特点 : 不是紧支撑的；不是紧支撑的；不是正交的；不是正交的；不是双正交的；不是双正交的；当当 k 取取偶偶数数时时， (t) 偶偶对对称称，当当 k 取取奇奇数数时时， (t) 反对称。反对称。 116 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT
157、 局限性克服方法：局限性克服方法：正交小波正交小波n目前提出的正交小波大致可分为四种：目前提出的正交小波大致可分为四种：Daubechies 小波小波对称小波对称小波Coiflets 小波小波Meyer 小波小波n正交小波的基本概念正交小波的基本概念这这些些正正交交小小波波和和前前面面所所讨讨论论的的“经经典典小小波波”不不同同，它它们们一一般般不不能能由由一一个个简简洁洁的的表表达达式式给给出出母母小小波波(t)，而而是是通通过过一一个个叫叫做做“尺尺度度函函数数 (t)（Scalling function）(又又称称为为父小波父小波)” 的加权组合来产生的。尺度函数是小波变换的又一个重要概
158、念。的加权组合来产生的。尺度函数是小波变换的又一个重要概念。尺尺度度函函数数(t) 作作尺尺度度伸伸缩缩和和位位移移产产生生 j,k(t), j,kZ，它它是是 Vj 中中的的正正交交归归一一基基；母母小小波波(t)作作尺尺度度伸伸缩缩和和位位移移产产生生 j,k(t), j,kZ，它它属属于于 Wj 中中的的正正交交归归一一基基，即即小小波波基基。 Vj 是是有有限限能能量量信信号号空空间间 L2(R) 中中的的一一系系列列闭闭合合子子空空间间，Wj 空空间间是是 Vj 空间的正交补空间，空间的正交补空间，VjWj。所谓正交小波就是指由所谓正交小波就是指由(t) 生成的空间生成的空间Wj 中
159、的正交归一基中的正交归一基j,k(t), j,kZ。尺尺度度函函数数(t)、母母小小波波(t)分分别别和和一一个个低低通通滤滤波波器器 H0(z) 及及高高通通(带带通通)滤滤波波器器 H1(z) 相关连，相关连，H0(z) 和和 H1(z) 可构成一个两通道的分析滤波器组。可构成一个两通道的分析滤波器组。这这些些内内容容构构成成了了小小波波变变换换的的多多分分辨辨率率分分析析的的理理论论基基础础。因因此此，在在讨讨论论正正交交小小波波时时，同同时时涉涉及及到到尺尺度度函函数数(t)、分分析析滤滤波波器器组组 H0(z)、H1(z)及及综综合合滤滤波波器器组组G0(z)和和 G1(z)。MAT
160、LAB 中中的的 Wavelet Toolbox 中中有有相相关关的的函函数数来来产产生生各各类类正正交交小小波波及及其其相相应应的的滤波器。滤波器。117 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性克服方法：局限性克服方法：正交小波正交小波n Daubechies 小小波波简简称称 db小小波波，它它是是由由法法国国女女学学者者 Dauechies Ingr
161、id 于于90年年代代初初提提出出并并构构造造的的。Daubechies对对小小波波变变换换的的理理论论做做出出了了突突出出的的贡贡献献，特特别别是是在在尺尺度度取取2的的整整数数次次幂幂时时的的小小波波理理论论及及正正交交小小波波的的构构造造方方面面进进行行了了深深入入的的研研究究，其其代代表表作作Ten Lectures on Wavelet（小波十讲）深受欢迎。（小波十讲）深受欢迎。n dbN 中中的的 N 表表示示 db 小小波波的的阶阶次次，在在 Matlab6.5 中中， N=245。当当N=1时，时，db1 就是就是 Haar 小波。故小波。故Haar小波应归于小波应归于“正交小
162、波正交小波”类。类。nDaubechies 小波的特点小波的特点 : 是正交小波；是正交小波；是双正交小波；是双正交小波；是是紧紧支支撑撑的的。(t)的的支支撑撑范范围围为为 t=0(2N-1)，(t) 的的支支撑撑范范围围为为 (1-N)N；母母小小波波 (t) 具具有有 N 阶阶消消失失矩矩，() 在在=0 处具有处具有 N 阶零点；阶零点；db小小波波是是非非对对称称的的，其其相相应应的的滤滤波波器器组组属属共共轭轭正正交交镜镜像像滤滤波波器器组组（CQMFB）。）。N=4 时时 db小波小波 118 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱
163、爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性克服方法：局限性克服方法：正交小波正交小波n对对称称小小波波简简记记为为 symN，N=2,3,45，它它是是db小小波波的的改改进进，也也是是由由 Daubechies 提提出出并并构构造造的的。它它除除了了有有 db 小小波波的的特特点点外外，主主要要是是(t) 接接近近对对称称。因因此此，所所用用的的滤滤波波器器可可接接近近于线性相位。于线性相位。N=4 时的对称小波时的对称小波119 北北京京邮
164、邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性克服方法：局限性克服方法：正交小波正交小波nCoiflets小波简记为小波简记为coifN，N=1,2,5。在在db小小波波中中，Daubechies小小波波仅仅考考虑虑了了使使小小波波函函数数(t)具具有有消消失失矩矩 (N阶阶 )， 而而 没没 考考 虑虑 尺尺 度度 函函 数数 (t)。 Coifman于于 1989年年
165、向向Daubechies 提提出出建建议议，希希望望能能构构造造出出使使(t) 也也具具有有高高阶阶消消失失矩矩的的正正交交紧紧支支撑撑小小波波。Daubechies 接接受受了了这这一一建建议议，构构造造出出了了这这一一类类小波，并以小波，并以 Coifman 的名字命名。的名字命名。N=4 时的时的 Coiflets小波小波 nCoiflets 小波的特点小波的特点 : 是正交的；是正交的；是双正交的；是双正交的；也是接近对称的；也是接近对称的；是紧支撑的，支撑范围为是紧支撑的，支撑范围为6N-1；(t) 的消失矩是的消失矩是 2N;(t)的消失矩是的消失矩是2N-1。 若若 (t) 展成
166、一个高的展成一个高的 N 阶多多项式（如泰勒式（如泰勒级数），如果数），如果 (t) 具有具有 p 阶消失矩，那么小波消失矩，那么小波变换只反映了只反映了阶次大于次大于 p 的多的多项式部分，它式部分，它们对应高高频端，端，这样有利于突出信号的高有利于突出信号的高频成分和突成分和突变点。从点。从这个角度出个角度出发，希，希望有尽量高的消失矩。望有尽量高的消失矩。消失矩越高，消失矩越高，(w) 在在 w=0 处越平滑地越平滑地为零，也越具有好的零，也越具有好的带通特性。通特性。 在在实际应用中，不管是数据用中，不管是数据压缩、去噪，、去噪，还是突出奇异点，都是突出奇异点，都希望小波希望小波变换后
167、的能量集中在少数系数上后的能量集中在少数系数上，也就是大部分小波系数也就是大部分小波系数为零或尽量的小，零或尽量的小，这取决于：取决于：1）信号）信号 x(t) 自身的特点；自身的特点；2） (t) 的支撑范的支撑范围；3） (t) 是否具有高消失矩是否具有高消失矩。 120 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性克服方法：局限性克服方法：正交小波正交小波
168、nMeyer小小波波简简记记为为meyr，它它是是由由Meyer于于1986年年提提出出的的。该该小小波波无无时时域域表表达达式式，它它是是由由一一对对共共轭轭正正交交镜镜像像滤滤波波器器组组的频谱来定义的。的频谱来定义的。nMeyer 小波的特点小波的特点 : 是正交；是正交；是双正交的；是双正交的；但但不不是是有有限限支支撑撑的的，其其有有效效的的支支撑撑范范围围在在8，8之间。之间。该该小小波波是是对对称称的的，且且有有着着非常好的规则性。非常好的规则性。Meyer小波小波 121 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digita
169、l Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性克服方法：局限性克服方法：双正交小波双正交小波n正正交交小小波波条条件件下下的的， (t)和和(t) 都都不不具具有有线线性性相相位位(Haar小小波波除除外外)。为为此此，Daubechies 和和 Cohen 提提出出并并构构造造了了双双正正交交小小波波，其其目目的的是是在在放放宽宽小小波波正正交交性性的的条条件件下下得得到到线线性性相相位的小波及相应的滤波器组位的小波及相应的滤波器组 h0(n)、h1(n)和和g0(
170、n)、g1(n)。n设设 是希尔伯特空间中的一组向量，若是希尔伯特空间中的一组向量，若 是一组两两相互正交的的向量，则是一组两两相互正交的的向量，则 是正交的。是正交的。n设在设在 H 空间中另有一组向量空间中另有一组向量 ，这一组向量和，这一组向量和 满足如下关系：满足如下关系：则则称称为为双双正正交交 (biorthogonality) 关关系系。特特别别指指出出的的是是，双双正正交交指指的的是是两两组组向向量量之之间间各各对对应应矢矢量量之之间间具具有有正正交交性性。但但每每一一组组向向量量内的矢量之间并不一定具有正交关系。内的矢量之间并不一定具有正交关系。 122 北北京京邮邮电电大大
171、学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性克服方法：局限性克服方法：双正交小波双正交小波n双双正正交交滤滤波波器器组组简简称称 biorNr,Nd，其其中中 Nr 是是低低通通重重建建滤滤波波器器的的阶阶次次，Nd 是是低低通通分分解解滤滤波波器器的的阶阶次次。在在MATLAB中，中，Nr 和和 Nd 的可能组合是：的可能组合是：n双正交小波的特点双正交小波的特点 : 自然不是正
172、交的；自然不是正交的；是双正交的；是双正交的；是紧支撑的；是紧支撑的；主主要要的的是是对对称称的的，因因此此具具有有线线性相位；性相位；分解小波分解小波(t)的消失矩为的消失矩为Nr-1。n由由于于 bior2.2 和和 bior4.4 双双正正交交小小波波的的重重建建和和分分解解滤滤波波器器长长度度的的特特点点，在在文文献献上上它们分别它们分别称为称为 db5.3 和和 db9.7 小波小波。n 在图像处理和图像压缩中得到广泛应用在图像处理和图像压缩中得到广泛应用nh(n)h(n)0-1,1-2,2-3,3-4,4 0.788485616406370.41809227322204-0.040
173、68941760920-0.064538882629760 0.852698679008890.37740285561283-0.11602440441844-0.023849465019560.03782845554969 重建滤波器重建滤波器H(z)分解滤波器分解滤波器H(z)123 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性克服方法：局限性克服方法：双正
174、交小波双正交小波Bior4.4 (db9.7) 小波的分解和重建父小波和母小波小波的分解和重建父小波和母小波Bior2.2 (db5.3) 小波的分解和重建父小波和母小波小波的分解和重建父小波和母小波024600.511.5bior2.2 phi-R0246-1012bior2.2 psi-R124 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性克服方法：局限性克
175、服方法：框架理论框架理论n信信号号变变换换或或分分解解的的基基本本思思路路是是将将信信号号 x(n) 和和一一组组函函数数 n, nZ 做做内积，得到一组标量内积，得到一组标量 an，即信号离散表示的系数。，即信号离散表示的系数。n由由于于正正交交基基具具有有很很多多优优点点，所所以以正正交交基基在在信信号号处处理理中中得得到到最最为为广广泛泛的的应用，例如：应用，例如：DFT、DCT 等。但好的正交基不易寻找。等。但好的正交基不易寻找。n在在时时频频分分析析中中，用用于于信信号号分分解解的的一一组组二二维维函函数数 m,n, m,nZ如如何何构构成成一一组组基基？如如何何构构成成一一组组正正
176、交交基基？如如果果不不能能构构成成一一组组基基？或或者者是是说说 m,n, m,nZ 可可能能是是线线性性无无关关的的（“基基”）、正正交交的的（“正正交交基基”）、或或线线性性相相关关的的（“框框架架”），那那么么在在这这些些情情况况下下，如如何何保保证证信信号分解的完备性，以及信号重建的稳定性？号分解的完备性，以及信号重建的稳定性？对信号分解或合成时，对信号分解或合成时，“基函数基函数”的选择非常关键！的选择非常关键！把正交分解推广到了更为一般信号的分解情况，即框架把正交分解推广到了更为一般信号的分解情况，即框架(Frame);1952年年 Duffin 和和 Schaeffer 在研究由
177、不规则取样重建带限信号时提出的。在研究由不规则取样重建带限信号时提出的。框框架架理理论论在在研研究究信信号号离离散散表表示示的的完完备备性性、稳稳定定性性和和冗冗余余性性方方面面是是非非常常有有用的。用的。125 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性克服方法：局限性克服方法：框架理论框架理论nFrame 的的定定义义：设设 n 是是 Hilbert 空空
178、间间 H 中中的的一一组组向向量量，对对任任一一信信号号 xH，如果存在常数，如果存在常数 A0 和和 B，并使下式成立：，并使下式成立：则称则称 n 构成空间构成空间 H 中的一个框架，式中中的一个框架，式中 A、B 是框架上下界。是框架上下界。n解释：解释： 定义中的中间部分是标量，所以取绝对值，而左边和右边的定义中的中间部分是标量，所以取绝对值，而左边和右边的 x 是向量，所以取范数；是向量，所以取范数； 框架指的是框架指的是 Hilbert 空间中的一组向量，即定义中的空间中的一组向量，即定义中的 ； 范范数数 |x|2 代代表表了了信信号号 x 的的能能量量，它它是是有有限限的的，
179、代代表表了了 x 在在变变换换域域中中的的能能量量，也也即即分分解解系系数数的的能能量量。要要保保证证分分解解系系数数稳稳定定地地重重建建出出 x，那那么么分分解解系系数数的的能能量量必必须须是是有有限限的的，另另一一方方面面，除除非非 x 是是全全零零信信号号，否否则则其其分分解解系系数数不不会会为为全全零零，因因此此，要要求求框框架界满足架界满足 0AB； 正正交交变变换换保保证证变变换换前前后后信信号号的的能能量量不不变变（即即 Parseval 定定理理），且且只只有有正正交交变变换换才才满满足足 Parserval 定定理理。因因此此，若若 为为一一正正交交基基，那那么么必必有有 A
180、=B=1，但但框框架架仅仅要要求求 0AB，可可见见 不不一一定定是是正正交交基基，它它可可能能是是线线性性独独立立的的，也也可可能能是是线线性性相相关的。关的。 若有两个信号若有两个信号 x1 和和 x2，其分解系数分别为：，其分解系数分别为： 则则126 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.2 DFT 局限性克服方法：局限性克服方法：框架理论框架理论n由上可知，框架界
181、由上可知，框架界 A 和和 B 在框架理论中起着重要作用，取值如下：在框架理论中起着重要作用，取值如下：若若 构成一个框架，则框架界一定满足构成一个框架，则框架界一定满足 0AB1，因此，因此 A可作为冗余度的测量，可作为冗余度的测量，A越大，冗余越大；越大，冗余越大；若若 各分量之间的是线性独立的，则各分量之间的是线性独立的，则 A 1B；在在非非紧紧框框架架时时，有有 B/A 1。若若 B/A 越越大大，重重建建误误差差也也越越大大，同同时时对对偶偶框框架架 和和 相差也越大；相差也越大；n问题：问题：对对于于给给定定的的一一组组向向量量或或函函数数 ，如如何何判判断断它它是是否否构构成成
182、一一个个框框架架？即即如如何计算框架界何计算框架界 A 和和 B ？当当 A 和和 B 相差较大时，如何求出对偶框架，以便实现对信号的重建？相差较大时，如何求出对偶框架，以便实现对信号的重建？ 总总之之，框框架架是是 Hilbert 空空间间中中的的一一组组向向量量（函函数数），它它用用于于信信号号的的分分解解和和重重建建，如如果果保保证证了了框框架架界界 0AB，那那么么由由这这一一组组框框架架对对信信号号的的分分解解是是完完备备的的，并并且且由由分分解解系系数对信号的重建也是稳定的。当然，这时分解系数可能会存在信息的冗余。数对信号的重建也是稳定的。当然，这时分解系数可能会存在信息的冗余。框
183、架理论框架理论127 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTn多多 尺尺 度度 几几 何何 分分 析析 （ Multiscale Geometric Analysis，MGA）脊波变换脊波变换（Ridgelet Transform, Candes and Donoho 于于1998年提出）年提出）单单尺尺度度脊脊波波变变换换（Monoscale Ridgelet Transform
184、, Candes and Donoho 于于 1999 年提出）年提出）Curvelet 变换变换（Candes and Donoho 于于 1999 年提出）年提出）Bandelet 变换（变换（Pennec and Mallat 于于2000年提出）年提出）Contourlet 变换（变换（Do and Vetterli 于于 2002年提出）年提出）3.6.2 DFT 局限性克服方法：局限性克服方法：发展发展RadonDomain2DFourierDomainRidgeletDomain1D Fourier Transform1D WaveletTransform128 北北京京邮邮电电
185、大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.3 其它离散变换其它离散变换nDFT 和和 IDFT 定义如下：定义如下： n用矩阵用矩阵 CN 代替代替 WN，则上述定义变成：，则上述定义变成： 其其中中上上标标 T 表表示示转转置置矩矩阵阵，为为常常数数。对对矩矩阵阵 CN ，可可能能有有 CN1 =CN*T， 上上式式 表表示示了了信信号号处处理理中中常常用用的的几几个个离散变换。离散变换。1
186、29 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTn离散变换的种类离散变换的种类K-L变换变换 KLT离散傅立叶变换离散傅立叶变换 DFT离散正弦变换离散正弦变换 DST离散余弦变换离散余弦变换 DCT哈达玛变换哈达玛变换 Hadamard Walsh 变换变换Haar 变换变换Slant 变换变换小波变换小波变换 Wavelet3.6.3 其它离散变换其它离散变换130 北北京京邮邮电
187、电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.3 其它离散变换：其它离散变换：K-LK-L变换（变换（KLTKLT） Karhunen -Love (卡胡南卡胡南-列夫列夫) 变换变换nKLT 变换产生去相关的变换系数变换产生去相关的变换系数nKLT 基基函函数数是是输输入入信信号号协协方方差差矩矩阵阵的的特特征征向向量量，因因此此，它是以统计特性为基础的，也称为特征向量变换它是以统计特性为基础
188、的，也称为特征向量变换。n最最优优的的正正交交变变换换：特特征征向向量量矩矩阵阵向向量量指指向向数数据据变变化化最最大大的方向，能够达到最优的能量集中。的方向，能够达到最优的能量集中。n缺点：计算过程复杂，变换速度慢。缺点：计算过程复杂，变换速度慢。KLT 依赖信号统计特性，而不可能实时计算视频的统计特性；依赖信号统计特性，而不可能实时计算视频的统计特性；KLT 对图象块是不可分离；对图象块是不可分离；变换矩阵不能分解为稀疏矩阵变换矩阵不能分解为稀疏矩阵。131 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Proc
189、essing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.3 其它离散变换：其它离散变换：离散沃尔什变换离散沃尔什变换(DWT)其中其中 N=2n ，指数之和是以指数之和是以 2 为模的算术运算为模的算术运算；bk(z) 为为 z 二二进进制制表表达达式式的的第第 k 位位 (从从右右向向左左)，例例如如： 若若n=3 且且 z=6 (二进制为二进制为110)，则，则 b0(z)=0; b1(6)=1; b2(6)=1。nDWT 变换变换n2D DWT变换：变换：132 北北京京邮邮电电大大学学信信息息与与通通信信工工程程
190、学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.3 其它离散变换：其它离散变换：哈达码变换哈达码变换n考虑一维哈达码变换考虑一维哈达码变换 H二维哈达码变换可以分解为一维哈达码变换二维哈达码变换可以分解为一维哈达码变换哈达码变换矩阵的元素值只有哈达码变换矩阵的元素值只有 1；H 是实对称正交矩阵：是实对称正交矩阵：n一一维维 Hn (N=2n) 基基矩矩阵阵可可以以通通过过 H1 递递归归产产生生(Harmuth，1970；Ellio
191、tt & Rao，1982)133 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.3 其它离散变换：其它离散变换：哈达码变换哈达码变换n二维哈达码变换对二维哈达码变换对 f(x,y)H(u,v)bk(z) 为为 z 二二进进制制表表达达式式的的第第k位位 (从从右右到到左左)，表表达达式式的的指指数数之之和和是是以以 2 为模的算术运算；为模的算术运算；二二维维哈哈达达码码变变换换
192、的的基基函函数数是是独独立立且且对对称称的的，可可以以分分解解为为一一维维哈哈达达码码变换进行计算；变换进行计算；哈哈达达码码变变换换和和沃沃尔尔什什变变换换在在图图象象处处理理中中经经常常混混合合使使用用，称称为为沃沃尔尔什什哈达码变换哈达码变换(WHT)；134 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.3 其它离散变换：其它离散变换：哈达码沃尔什变换哈达码沃尔什变换（WH
193、T）nWHT的基函数的基函数其中其中135 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.3 其它离散变换：其它离散变换：哈达码沃尔什变换快速算法哈达码沃尔什变换快速算法nWHT 变换有快速算法。变换有快速算法。n矩阵矩阵 H8可表示为可表示为 (Jain，1989)：Hadamard变换算法的加法次数为变换算法的加法次数为 Nlog2N，没有乘法。，没有乘法。136 北北京京邮邮
194、电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTn与与其其它它变变换换不不同同 ，它它不不是是基基于于正正弦弦函函数数的的。它它的的变变换换矩矩阵元素值为阵元素值为 1 或或 1。n由由于于矩矩阵阵中中的的元元素素值值为为 1或或1，因因此此，Hadamard 变变换换没没有有乘乘法法运运算算，硬硬件件实实现现简简单单。所所以以，虽虽然然 Hadamard 变变换换的的压压缩缩性性能能不不如如 DCT，
195、但但是是过过去去 Hadamard 变变换换也也应应用用于于数数字字图图像像处处理理。现现在在由由于于DCT专专用用硬硬件件的的应应用用，Hadamard 变变换换在在数数字字图图像像处处理理中中已已经经很很少少使使用用，但但在在 H.264 标准又得到应用标准又得到应用 。n并并且且Hadamard变变换换的的也也应应用用于于移移动动通通信信码码分分多多址址 (CDMA) 技技术术中中，用用于于同同步步通通信信系系统统信信道道编编码码 (Stuber，1996)。3.6.3 其它离散变换：其它离散变换：哈达码沃尔什变换哈达码沃尔什变换（WHT）137 北北京京邮邮电电大大学学信信息息与与通通
196、信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.3 其它离散变换：其它离散变换：离散余弦变换离散余弦变换(DCT)n一维一维 DCT 变换的基函数变换的基函数n一维一维 DCT 正反变换表达式正反变换表达式其中其中138 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telec
197、ommunication Centre, BUPT3.6.3 其它离散变换：其它离散变换：离散余弦变换离散余弦变换(DCT)n二维二维 DCT 变换的基函数变换的基函数n二维二维 DCT 正反变换表达式正反变换表达式其中其中139 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.3 其它离散变换：其它离散变换：DCT 系数的幅度分布系数的幅度分布n下下图图是是从从自自然然图图象象（M
198、auersberger) 得得到到的的 88 DCT 系系数数幅幅度度的的直方图。直方图。n直流直流 DC 系数是典型的均匀分布系数是典型的均匀分布n交流交流 AC 系数的分布类似于系数的分布类似于 Laplacian pdf140 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.3 其它离散变换：其它离散变换：DCT 快速算法快速算法n直直接接进进行行 DCT 计计算算：每每个个系
199、系数数需需要要 64 次次乘乘法法、63 次次加加法法，88 DCT 将需要将需要 1024 次乘法，次乘法，896 次加法。次加法。nDCT 有有快快速速算算法法：2D-DCT 的的行行列列运运算算，每每一一次次运运算算变变为为 1D-DCT 运运算算，1D-DCT 采采用用 fast DCT。一一般般的的 1D-DCT 的的快快速速算算法法使使运运算算量量降降低为低为Nlog2N数量级的实数乘法。数量级的实数乘法。1st dimension转置2st dimension系数ROM矩阵表NN矩阵表NNBTBUC CC C行行列列B=CUVT=VBTVT141 北北京京邮邮电电大大学学信信息息
200、与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.3 其它离散变换：其它离散变换：DCT 快速算法快速算法nDCT 常用算法是中国人陈文雄常用算法是中国人陈文雄 (1977) 提出的提出的Chen W.H.,et.,”A fast computational algorithm for the discrete cosine transform”, IEEE transactions on Communication
201、s,COM-25,1004-1009.N8 时的算法如图cx 对应于 cosx，sx 对应于sinx。142 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.3 其它离散变换：其它离散变换：DCT 快速算法快速算法nDCT矩阵因式分解为稀疏矩阵矩阵因式分解为稀疏矩阵（Chen et.al.,1977）（对应上述流图）（对应上述流图）将将码码位位倒倒置置序序列列转转变变成成顺顺序序序序
202、列列的的输输出向量出向量143 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.3 其它离散变换：其它离散变换：DCT 快速算法快速算法nArai，Agui and Nakajima 算法的快速算法的快速 8-DCT 信号流图信号流图 （此算法需要（此算法需要 13次乘法，次乘法，29次加法）次加法） 144 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中
203、中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPT3.6.3 其它离散变换：其它离散变换：DCT 快速算法快速算法nDCT 矩阵因式分解为稀疏矩阵矩阵因式分解为稀疏矩阵（Arai,Agui and Nakajima; 1988）145 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Ce
204、ntre, BUPT3.6.3 其它离散变换：其它离散变换： DCT 快速算法快速算法nLoeffler, Ligtenberg and Moschytz 快速快速 DCT 算法算法C. Loeffler, A. Ligtenberg and G. Moschytz, Practical Fast 1-D DCT Algorithms with 11 Multiplications, Proc. Intl. Conf. on Acoustics, Speech, and Signal Processing 1989, pp. 988-991此算法需要此算法需要 11 次乘法和次乘法和 29 次
205、加法。次加法。146 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTn44 44 整数变换演变过程：整数变换演变过程： 3.6.3 其它离散变换：其它离散变换：从从 DCT 变换到整数变换变换到整数变换147 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multi
206、media Telecommunication Centre, BUPTn最后最后 44 44 整数变换的表达式为：整数变换的表达式为：n可可以以看看出出，由由于于矩矩阵阵 H 只只有有 1与与 2，只只需需加加法法和和左左移移即可完成变换，所以即可完成变换，所以 H.264 的整数变换是无乘法的。的整数变换是无乘法的。 3.6.3 其它离散变换：其它离散变换：从从 DCT 变换到整数变换变换到整数变换n基核矩阵基核矩阵 H 为：为：148 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men
207、 Aidong, Multimedia Telecommunication Centre, BUPT实验二：数字信号的实验二：数字信号的 FFT 分析（分析（6学时）学时） 数数字字信信号号处处理理的的一一个个重重要要分分支支就就是是信信号号分分析析，而而信信号号分分析析的的基基本本工工具具是是离离散散傅傅立立叶叶变变换换。利利用用傅傅立立叶叶变变换换和和级级数数所所形形成成的的频频谱谱分分析析技技术术作作为为处处理理连连续续信信号号的的重重要要工工具具已已经经应应用用得得很很久久了了,1956年年库库力力（Cooley）和和图图基基（Tukey）所所发发展展的的近近似似频频谱谱的的快快速速算
208、算法法为为频频谱谱分分析析的的数数字字信信号号的的谱谱分分析析铺平了道路。因此，铺平了道路。因此，DFT（FFT）得到广泛应用。本次实验设计了两个内容：）得到广泛应用。本次实验设计了两个内容：(1) 离散信号的频谱分析离散信号的频谱分析 假设信号假设信号 x(n) 由下述信号组成：由下述信号组成： 这这个个信信号号有有两两根根主主谱谱线线 0.3pi 和和 0.302pi 靠靠的的非非常常近近，而而另另一一根根谱谱线线 0.45pi 的的幅幅度度很很小小，请选择合适的长度请选择合适的长度 N 和窗函数，用和窗函数，用 DFT 分析其频谱，得到清楚的三根谱线。分析其频谱，得到清楚的三根谱线。(2
209、) DTMF 信号频谱分析信号频谱分析 用用计计算算机机声声卡卡采采用用一一段段通通信信系系统统中中电电话话双双音音多多频频（DTMF）拨拨号号数数字字 09的的数数据据，采采用用快快速速傅傅立立叶变换（叶变换（FFT）分析这）分析这10个号码个号码DTMF拨号时的频谱。拨号时的频谱。 (3) 目的目的 通过本次实验，应该掌握：通过本次实验，应该掌握：(a) 用傅立叶变换进行信号分析时基本参数的选择。用傅立叶变换进行信号分析时基本参数的选择。 (b) 经经过过离离散散时时间间傅傅立立叶叶变变换换（DTFT）和和有有限限长长度度离离散散傅傅立立叶叶变变换换（DFT） 后后信信号号频频谱谱上上的的
210、区区别别，前前者者 DTFT 时间域是离散信号，频率域还是连续的，而时间域是离散信号，频率域还是连续的，而 DFT 在两个域中都是离散的。在两个域中都是离散的。(c) 离散傅立叶变换的基本原理、特性，以及经典的快速算法（基离散傅立叶变换的基本原理、特性，以及经典的快速算法（基2时间抽选法），体会快速算法的效率。时间抽选法），体会快速算法的效率。(d) 获获得得一一个个高高密密度度频频谱谱和和高高分分辨辨率率频频谱谱的的概概念念和和方方法法，建建立立频频率率分分辨辨率率和和时时间间分分辨辨率率的的概概念念，为为将将来来进进一一步步进进行时频分析（例如小波）的学习和研究打下基础。行时频分析（例如小
211、波）的学习和研究打下基础。(e) 建建立立 DFT 从从整整体体上上可可看看成成是是由由窄窄带带相相邻邻滤滤波波器器组组成成的的滤滤波波器器组组的的概概念念，此此概概念念的的一一个个典典型型应应用用是是数数字字音音频频压缩中的分析滤波器，例如压缩中的分析滤波器，例如 DVD AC3 和和MPEG Audio。上机实验作业 2149 北北京京邮邮电电大大学学信信息息与与通通信信工工程程学学院院多多媒媒体体中中心心门门爱爱东东 Digital Signal Processing, Men Aidong, Multimedia Telecommunication Centre, BUPTn理解傅里叶
212、变换的几种形式理解傅里叶变换的几种形式n掌握掌握 DFSDFS及性质，掌握周期卷积过程及性质，掌握周期卷积过程n掌握掌握 DFTDFT及性质，掌握循环卷积、线性卷积及两者之间及性质，掌握循环卷积、线性卷积及两者之间的关系的关系n掌握线性卷积的掌握线性卷积的 DFT DFT 算法及分段卷积方法算法及分段卷积方法n掌握按时间抽选的基掌握按时间抽选的基-2 FFT -2 FFT 算法的算法原理、运算流算法的算法原理、运算流图和算法特点及图和算法特点及IFFT IFFT 算法算法n掌握按频率抽选的基掌握按频率抽选的基-2 FFT -2 FFT 算法的算法原理、运算流算法的算法原理、运算流图和算法特点及图和算法特点及IFFT IFFT 算法算法n理解频谱分析过程理解频谱分析过程n了解了解 CZT CZT 算法算法n了解其它变换了解其它变换本章小结本章小结150
