《第2章 离散傅里叶变换和快速算法.ppt》由会员分享，可在线阅读，更多相关《第2章 离散傅里叶变换和快速算法.ppt（64页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法 2.1 离散傅里叶变换离散傅里叶变换 2.2 利用利用DFT做连续信号的频谱分析做连续信号的频谱分析 2.3 快速傅里叶变换快速傅里叶变换 2.4 关于关于FFT应用中的问题应用中的问题杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法2.1 离散傅里叶变换离散傅里叶变换序列的傅里叶变换可以用来分析连续时间信号的频谱，序列的傅里叶变换可以用来分析连续时间信号的频谱，但是，它不能让计算机用来计算信号的频谱。但是，它不能让计算机用来计算信号
2、的频谱。为什么为什么呢？呢？真正的傅里叶变换有真正的傅里叶变换有4种：种：CTFS给连续周期信号用，给连续周期信号用，CTFT给连续非周期信号用，给连续非周期信号用，DTFS给离散周期信号用，给离散周期信号用，DTFT给离散非周期信号用。给离散非周期信号用。杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法2.1.1 离散傅里叶级数离散傅里叶级数离散傅里叶级数的定义：离散傅里叶级数的定义：它们的物理意义是什么呢？它们的物理意义是什么呢？杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法离散傅里叶级数是用在周期序列的，其离散傅里叶级数是用在周期序列
3、的，其x(n)和和X(k)都是都是离散值，都具有周期性。离散值，都具有周期性。怎么知道它们有周期性呢？怎么知道它们有周期性呢？离散傅里叶级数的定义是怎么来的？离散傅里叶级数的定义是怎么来的？杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法离散傅里叶级数的定义是这么来的：离散傅里叶级数的定义是这么来的：杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法DFS的性质：的性质：线性性质、序列移位性质、共轭对称性质等都和线性性质、序列移位性质、共轭对称性质等都和DTFT的相的相同。同。共轭对称的定义是共轭对称的定义是f(t)=f*(-t)，共轭反对称的
4、定义是共轭反对称的定义是f(t)=-f*(-t)。杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法共轭对称性的说明：共轭对称性的说明：若复数序列若复数序列x(n)的共轭序列是的共轭序列是x*(n)，则它的离散傅里叶级，则它的离散傅里叶级数的系数数的系数怎么证明它呢？怎么证明它呢？杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法进一步可以得到实数序列的进一步可以得到实数序列的DFS是共轭对称的，即是共轭对称的，即怎么证明它呢？怎么证明它呢？杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法周期序列也有卷积运算，其的卷积范
5、围是一个时序周期，周期序列也有卷积运算，其的卷积范围是一个时序周期，不过要注意的是：参加卷积的两个周期序列的周期必须相不过要注意的是：参加卷积的两个周期序列的周期必须相等。等。周期序列也有卷积定理，即周期序列也有卷积定理，即杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法请注意请注意DFS和和DTFT的性质不同之处：的性质不同之处：（1）DFS的频率变量是离散的，的频率变量是离散的，DTFT的频率变量是连续的频率变量是连续的；的；（2）DFS的卷积范围是有限的，的卷积范围是有限的，DTFT的卷积范围是无限的卷积范围是无限的。的。这种区别意味着什么？从数字信号处理的角度
6、来看。这种区别意味着什么？从数字信号处理的角度来看。杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法2.1.2 离散傅里变换离散傅里变换离散傅里叶级数是用在周期序列的，而大部分的序列是离散傅里叶级数是用在周期序列的，而大部分的序列是非周期的，实际应用中，我们处理信号时是分段处理非周期的，实际应用中，我们处理信号时是分段处理的。怎么办？的。怎么办？人为地人为地将周期信号的主值区间的序列看作是一个非周期将周期信号的主值区间的序列看作是一个非周期信号，看作是被分析的信号的一部分。信号，看作是被分析的信号的一部分。这种做法就是离散傅里叶变换的精神。离散傅里叶变换这种做法就是离
7、散傅里叶变换的精神。离散傅里叶变换是离散傅里叶级数的特例。是离散傅里叶级数的特例。杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法离散傅里叶变换的定义：离散傅里叶变换的定义：WN是什么？它的物理意义是什么？有什么用？是什么？它的物理意义是什么？有什么用？杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法离散傅里叶变换和离散傅里叶级数的区别在离散傅里叶变换和离散傅里叶级数的区别在DFT的：的：（1）取值范围，）取值范围，n和和k均在均在0N-1；（2）书写方法，）书写方法，RN(n)和和RN(k);（3）计算方法，先把序列当作周期序列计算，然后再
8、限制）计算方法，先把序列当作周期序列计算，然后再限制周期序列的范围。周期序列的范围。杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法例例1（书上第（书上第51页）页）求求x=1+j2,2+j2,j,1+j的离散傅里叶变的离散傅里叶变换。换。解：方法一，按定义来计算。解：方法一，按定义来计算。方法二，按矩阵来计算。设方法二，按矩阵来计算。设x和和X都是列向量。都是列向量。方法一和方法二有什么关系？方法一和方法二有什么关系？杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法方法三，按方法三，按MATLAB来计算。来计算。如果如果x和和X都是列向量的
9、话，则都是列向量的话，则X=WN*x，其中其中WN=exp(-j2/Nkn)，这时，这时k和和n都是行向量。都是行向量。请注意请注意(4+j6)和和(4.000+6.000i)的区别。的区别。杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法对于有限长序列的离散傅里叶变换，其性质和离散傅里叶对于有限长序列的离散傅里叶变换，其性质和离散傅里叶级数的相同，只是注意取主值的限制就可以了。级数的相同，只是注意取主值的限制就可以了。例如：例如：（1）线性性质，注意它们的长度。）线性性质，注意它们的长度。（2）移位性质，注意它们的移位。）移位性质，注意它们的移位。（3）循环卷积，注
10、意它们的主值范围。）循环卷积，注意它们的主值范围。杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法例例2（书上第（书上第54页）设页）设x5(n)=x5(n)=R5(n)。求两个序列的。求两个序列的5点长循环卷积和点长循环卷积和10点长循环卷积点长循环卷积y(n)。解：解：（1）5点的循环卷积：点的循环卷积：方法一，按循环卷积的定义计算；方法一，按循环卷积的定义计算；可以心算吗？可以心算吗？方法二，按循环卷积定理计算。方法二，按循环卷积定理计算。可以心算吗？可以心算吗？杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法（2）10点的循环卷积：点
11、的循环卷积：方法一，按循环卷积的定义计算；方法一，按循环卷积的定义计算；可以心算吗？可以心算吗？方法二，按循环卷积定理计算。方法二，按循环卷积定理计算。可以心算吗？可以心算吗？杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法循环卷积的长度循环卷积的长度N和线性卷积的长度和线性卷积的长度(N1+N2-1)有什么关系有什么关系？为什么要提这个问题？为什么要提这个问题？杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法因为长度为因为长度为N1的序列的序列x1(n)和长度为和长度为N2的序列的序列x2(n)的线性卷的线性卷积积而长度为而长度为N1的序列
12、的序列x1(n)和长度为和长度为N2的序列的序列x2(n)的的N点长循点长循环卷积（环卷积（NN1和和N2）杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法yL(n)和和yC(n)的关系的关系说明了什么？说明了什么？这个关系这个关系N(N1+N2-1)有什么用？有什么用？杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法四种傅里叶变换的频率关系（物理意义）：四种傅里叶变换的频率关系（物理意义）：（1）当作周期函数的成分的正弦波是）当作周期函数的成分的正弦波是 ，（2）当作非周期函数的成分的正弦波是）当作非周期函数的成分的正弦波是 ，（3）当作周
13、期序列的成分的正弦波是）当作周期序列的成分的正弦波是 ，（4）当作非周期序列的成分的正弦波是）当作非周期序列的成分的正弦波是 。杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法周期函数的谐波频率与周期序列的谐波频率是否对等呢？周期函数的谐波频率与周期序列的谐波频率是否对等呢？由于离散傅里叶级数的定义是：由于离散傅里叶级数的定义是：所以，只有当周期函数所以，只有当周期函数x(t)的周期的周期T0=NT时，周期函数时，周期函数x(t)和周期序列和周期序列x(n)的谐波角频率才有对等的关系。的谐波角频率才有对等的关系。杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅
14、里叶变换和快速算法傅里叶变换在信号压缩中的应用：傅里叶变换在信号压缩中的应用：假设在时间假设在时间0，2内有一个信号，内有一个信号，如果想压缩它的如果想压缩它的90%数据，请问该用什么方法进行压缩呢？数据，请问该用什么方法进行压缩呢？t=linspace(0,2*pi,28);y=exp(-cos(t).2).*(sin(2*t)+2*cos(4*t)+0.4*sin(t).*sin(50*t);Y=fft(y);m=max(abs(Y)*0.12;X=Y.*abs(Y)m;x=ifft(X);plot(t,x);杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法2.2
15、 利用利用DFT做连续信号的频谱分析做连续信号的频谱分析离散傅里叶变换可以用来分析连续时间信号的频谱，其离散傅里叶变换可以用来分析连续时间信号的频谱，其原理如下：原理如下：这种方法存在如下问题：这种方法存在如下问题：混叠，泄漏，栅栏效应，分辨率，周期效应。混叠，泄漏，栅栏效应，分辨率，周期效应。根据例根据例6（书上（书上63页）说明上面页）说明上面5个问题。个问题。杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法clear;close all;f=10;a=4;T=1/(a*f);t=0:T:3;x=sin(2*pi*f*t);subplot(211);plot(t,
16、x);xlabel(t/s);ylabel(x(t);N=length(t);n=0:N-1;k=n;W=exp(-j*2*pi/N*k*n);X=W*conj(x);subplot(212);stem(k,abs(X),.);xlabel(k);ylabel(X(k);杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法2.3 快速傅里叶变换快速傅里叶变换快速傅里叶变换是一种快速计算快速傅里叶变换是一种快速计算DFT的方法，是相对于的方法，是相对于直接按照直接按照DFT的定义进行计算的方法而言的。的定义进行计算的方法而言的。有代表性的快速算法有两个：有代表性的快速算法有
17、两个：（1）基）基2时域抽取法快速傅里叶变换，时域抽取法快速傅里叶变换，（2）基）基2频域抽取法快速傅里叶变换。频域抽取法快速傅里叶变换。杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法按定义对按定义对N点点DFT进行计算时，需要的复数乘法次数是进行计算时，需要的复数乘法次数是？，需要的复数加法次数是，需要的复数加法次数是？。据据N点长点长DFT的基本运算量公式：的基本运算量公式：N2，请大家想一想，减少，请大家想一想，减少DFT运算量的基本原理是怎样的呢？运算量的基本原理是怎样的呢？杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法减少减少D
18、FT运算量的基本原理是缩短被计算的运算量的基本原理是缩短被计算的DFT的长度。的长度。如何缩短呢？大家想一想，是不是有多种方法？如何缩短呢？大家想一想，是不是有多种方法？杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法2.3.1 按时间抽取的按时间抽取的FFT这种方法的基本做法是：将序列分成两半，按序号的偶这种方法的基本做法是：将序列分成两半，按序号的偶数和奇数进行分解，使一个数和奇数进行分解，使一个N点点DFT变成两个变成两个N/2点点DFT。时时域抽取法域抽取法FFT的序列长度必须是：的序列长度必须是：N=2M，以保证序列的分解能够反复地进行到以保证序列的分解能够
19、反复地进行到1点长的序列。点长的序列。杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法基本的分解方法由两步组成：基本的分解方法由两步组成：（1）按奇偶时序分解）按奇偶时序分解N点序列成为点序列成为N/2点序列，点序列，（2）整顿）整顿DFT表达式，使之成为真正的表达式，使之成为真正的N/2点点DFT。杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法第第1次分解次分解DFT后的复数计算量：后的复数计算量：（1）乘法的计算量是）乘法的计算量是 次？次？（2）加法的计算量是）加法的计算量是 次？次？需要多少次分解才能将需要多少次分解才能将N点点DF
20、T变成变成1点点DFT？这时的复数乘法的计算量是这时的复数乘法的计算量是 次？复数加法的计算量是次？复数加法的计算量是多少多少 次？次？杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法怎样看用分解的方法简化整个怎样看用分解的方法简化整个DFT过程的计算量？过程的计算量？（1）反复运用分解的基本方程，）反复运用分解的基本方程，（2）将分解的基本方程简化为蝶形图，用蝶形图分析和设）将分解的基本方程简化为蝶形图，用蝶形图分析和设计快速运算。计快速运算。蝶形图有流图的方式和交叉线的方式。蝶形图有流图的方式和交叉线的方式。杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅
21、里叶变换和快速算法例题例题1：请画出：请画出N=8时时DIT-radix2-FFT的流图。的流图。解：分解时的序列顺序符号的表达方式很重要，按二进制解：分解时的序列顺序符号的表达方式很重要，按二进制的形式排列有特殊的好处。的形式排列有特殊的好处。它能使最后它能使最后1点长的序列的排列方式，有一个很有规律的做点长的序列的排列方式，有一个很有规律的做法。法。杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法DIT-radix2-FFT的规律：的规律：（1）蝶形运算分解）蝶形运算分解DFT，（2）蝶形运算是原位运算，）蝶形运算是原位运算，（3）蝶形的类型是按分解的次数成倍地增
22、加，）蝶形的类型是按分解的次数成倍地增加，（4）输入序列的序号倒序排列。）输入序列的序号倒序排列。杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法2.3.2 按频率抽取的按频率抽取的FFT这种方法的基本做法是：将序列分成两半，按时序的前这种方法的基本做法是：将序列分成两半，按时序的前后两半进行分解，使一个后两半进行分解，使一个N点点DFT变成两个变成两个N/2点点DFT。频域抽取法频域抽取法FFT的序列长度必须是：的序列长度必须是：N=2M，以保证序列的分解能够反复地进行到以保证序列的分解能够反复地进行到1点长的序列。点长的序列。杨毅明杨毅明 第第2章章 离散傅里叶变
23、换和快速算法离散傅里叶变换和快速算法基本的分解方法由两步组成：基本的分解方法由两步组成：（1）分解）分解N点序列成为点序列成为N/2点序列，点序列，杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法（2）按频谱序号偶数和奇数整顿）按频谱序号偶数和奇数整顿DFT表达式，使之成为真表达式，使之成为真正的正的N/2点点DFT。对于偶数序号的频谱，对于偶数序号的频谱，对于奇数序号的频谱，对于奇数序号的频谱，杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法令相加和相减的短序列（注意下标的含义）为令相加和相减的短序列（注意下标的含义）为它们分别对应偶数频序
24、和奇数频序的频谱；它们分别对应偶数频序和奇数频序的频谱；杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法基本的基本的DIF-FFT的分解公式能用蝶形符号来表示吗？的分解公式能用蝶形符号来表示吗？杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法例题例题2：请画出：请画出N=8时的时的DIF-radix2-FFT的蝶形运算图。的蝶形运算图。解：分解时间序列时，频序按二进制的形式排列有特殊的解：分解时间序列时，频序按二进制的形式排列有特殊的好处。好处。它能使最后它能使最后1点长的频谱序列的排列方式，有一个很有规律点长的频谱序列的排列方式，有一个很有
25、规律的做法。的做法。杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法DIF-radix2-FFT的规律：的规律：（1）蝶形运算分解）蝶形运算分解DFT，（2）蝶形运算是原位运算，）蝶形运算是原位运算，（3）蝶形的类型是按分解的次数成倍地减少，）蝶形的类型是按分解的次数成倍地减少，（4）输出频谱序列的频序是倒序排列。）输出频谱序列的频序是倒序排列。杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法2.3.3 N为组合数的为组合数的FFT和基和基4FFTN为组合数为组合数PQ的的FFT的的基本做法是：先将序列分成基本做法是：先将序列分成Q点点长的长
26、的P段小序列，然后将段小序列，然后将Q点长的小序列变成真正意义点长的小序列变成真正意义的的Q点点DFT。基基4FFT是对是对N=4M的序列进行分解，每个被分解的序列的序列进行分解，每个被分解的序列都被分解成都被分解成4个等长的小序列。个等长的小序列。杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法2.3.4 DFT的应用的应用DFT可以用来建立建筑物摆动的模型：可以用来建立建筑物摆动的模型：杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法2.4 关于关于FFT应用中的几个问题应用中的几个问题快速傅里叶变换是计算离散傅里叶变换的节省时间和节快速
27、傅里叶变换是计算离散傅里叶变换的节省时间和节省存储器的方法。它有两个有代表性的算法，对省存储器的方法。它有两个有代表性的算法，对N点点DFT进行计算时，需要的复数乘法次数是进行计算时，需要的复数乘法次数是？，需，需要的复数加法次数是要的复数加法次数是？。杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法2.4.1 用用FFT计算计算IDFT快速计算快速计算IDFT的快速方法有几种？的快速方法有几种？（1）重新编程；）重新编程；（2）用）用FFT的程序，变换旋转因子的符号；的程序，变换旋转因子的符号；（3）用）用FFT的程序，取共轭的共轭。的程序，取共轭的共轭。杨毅明杨毅
28、明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法2.4.2 实数序列的实数序列的FFT快速计算实数序列的快速计算实数序列的DFT的方法有几种？的方法有几种？（1）重新编程；）重新编程；（2）用）用FFT的程序，一举两得的方法，一次变换两个实的程序，一举两得的方法，一次变换两个实数序列；数序列；（3）用）用FFT的程序，事半功倍的方法，将实数序列变成的程序，事半功倍的方法，将实数序列变成两段。两段。杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法一举两得的方法是用两个实数序列一举两得的方法是用两个实数序列x(n)和和y(n)组成一个复组成一个复数序列数序
29、列g(n)=x(n)+jy(n)，然后对复数序列，然后对复数序列g(n)进行进行FFT，得到频谱，得到频谱G(k)，最后，最后证明证明X(k)要利用要利用realg(n)=g(n)+g*(n)/2和和DFTg*(n)=G*(-k)，证明证明jY(k)要利用要利用imagg(n)=g(n)-g*(n)/2。杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法事半功倍的方法是将一个实数序列分成两段，当作一个事半功倍的方法是将一个实数序列分成两段，当作一个复数序列的实部和虚部：复数序列的实部和虚部：有有几种几种做法？做法？杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅
30、里叶变换和快速算法2.4.3 线性卷积的线性卷积的FFT算法算法线性卷积的快速算法就是用循环卷积代替线性卷积，然线性卷积的快速算法就是用循环卷积代替线性卷积，然后用快速傅里叶变换对循环卷积进行计算。其基本步后用快速傅里叶变换对循环卷积进行计算。其基本步骤是：骤是：（1）延长线性卷积的两个序列的长度）延长线性卷积的两个序列的长度N1和和N2，用补零的，用补零的方法延长到方法延长到L，L N1+N2-1；（2）对两个序列作）对两个序列作L点点FFT，并根据卷积定理求它们的，并根据卷积定理求它们的频谱乘积；频谱乘积；（3）用）用FFT求该频谱的求该频谱的L点时间序列。点时间序列。杨毅明杨毅明 第第2
31、章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法线性卷积的线性卷积的FFT算法快在哪里呢？算法快在哪里呢？例题例题3：当两个序列的长度：当两个序列的长度N1=N2=1024时，请比较直接时，请比较直接线性卷积的运算量和用线性卷积的运算量和用FFT算法的运算量。算法的运算量。解解：（1）直接线性卷积的乘法次数是）直接线性卷积的乘法次数是 ，加法次数是加法次数是 。（2）FFT算法的乘法次数是算法的乘法次数是 ，加法次数是加法次数是 。杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法（1）直接线性卷积的运算量：）直接线性卷积的运算量：运算总数为运算总数为419020
32、9次。次。（2）用）用FFT算法的运算量：算法的运算量：运算总数为运算总数为350208次。次。（1）的总量比（）的总量比（2）的总量多）的总量多11倍。倍。杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法2.4.4 用用FFT计算相关函数计算相关函数相关是指两个信号的相似程度，它的定义是：相关是指两个信号的相似程度，它的定义是：相关函数的用途是比较两个信号的相对相似程度，或者相关函数的用途是比较两个信号的相对相似程度，或者是比较信号自己的相对相似程度。是比较信号自己的相对相似程度。什么意思呢？什么意思呢？杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变
33、换和快速算法相关函数与卷积函数相比，卷积函数是相关函数与卷积函数相比，卷积函数是根据两者的关系，可以用根据两者的关系，可以用FFT来解决相关函数的问题。来解决相关函数的问题。杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法例例9 用相关函数测量液体流动的速度，如微血管、管道、河流等。（书上用相关函数测量液体流动的速度，如微血管、管道、河流等。（书上90页）页）N=18;n=0:N;x=sin(0.3*n);%泡泡信号泡泡信号subplot(4,1,1);stem(n,x,.);axis(0,25,-1,1);xlabel(k);ylabel(x(k);y=zeros(
34、1,5),x;n=0:N+5;%下游泡泡信号下游泡泡信号subplot(4,1,2);stem(n,y,.);axis(0,25,-1,1);xlabel(k);ylabel(y(k);N=length(y);n=0:N-1;s=y+0.5*randn(1,N);%下游信号下游信号subplot(413);stem(n,s,.);axis(0,25,-3,3);xlabel(k);ylabel(s(k);rxy=xcorr(x,y);n=-N+1:N-1;%相关函数信号相关函数信号subplot(414);stem(n,rxy,.);xlabel(n);ylabel(r_xy(n);axis(
35、-25,25,-14,14);杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法将将DFT的成分理念用到二维图像的成分分析上，有离散的成分理念用到二维图像的成分分析上，有离散余弦变化。余弦变化。例如（例如（pout,tire等）：等）：I=imread(circles.tif);subplot(221);imshow(I);J=dct2(I);subplot(223);imshow(log(abs(J),colorbar杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法书上习题书上习题2.26的解答：的解答：a=0.8;N=10;n=0:N-1;
36、x1=a.(-n);x2=ones(1,N);figure(1);subplot(3,2,1);stem(n,x1,k.);xlabel(n);ylabel(x_1(n);axis(0,20,0,8);subplot(3,2,2);stem(n,x2,k.);xlabel(n);ylabel(x_2(n);legend(m=0);axis(0,20,0,1.2);subplot(3,2,3);stem(n-2,x2,.k);xlabel(n);ylabel(x_2(n+2);legend(m=2);axis(-2,18,0,1.2);subplot(3,2,4);stem(n+2),x2,.k
37、);xlabel(n);ylabel(x_2(n-2);legend(m=-2);axis(0,20,0,1.2);r1=xcorr(x1,x2);subplot(3,1,3);stem(-N+1:N-1,fliplr(r1),.k);xlabel(m);ylabel(r_1(m);axis(-20,20,0,40);legend(线性相关的方法线性相关的方法);figure(2);m=-20:20;x3=x1,zeros(1,N);x4=x2,zeros(1,N);subplot(3,2,1);stem(0:2*N-1,x3,k.);xlabel(n);ylabel(x_1(n);legen
38、d(补补0扩展扩展);subplot(3,2,2);stem(m,x3(mod(-m,2*N)+1),k.);xlabel(n);ylabel(x_1(-n);legend(周期化周期化);subplot(3,2,3);stem(0:2*N-1,x4,k.);xlabel(n);ylabel(x_2(n);legend(补补0扩展扩展);subplot(3,2,4);stem(m,x4(mod(-m,2*N)+1),k.);xlabel(n);ylabel(x_2(-n);legend(周期化周期化);r2=real(ifft(conj(fft(x3).*fft(x4);subplot(3,1
39、,3);stem(m,r2(mod(m,20)+1),.k);xlabel(m);ylabel(r_2(m);legend(循环卷积的方法循环卷积的方法);杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法试验一解答：试验一解答：第第1题的目的是了解用题的目的是了解用DFT分析信号频谱时的泄漏和混叠失分析信号频谱时的泄漏和混叠失真的含义。书上第真的含义。书上第61页。页。泄漏含义由傅里叶变换的定义来理解，泄漏含义由傅里叶变换的定义来理解，持续时间有限的信号持续时间有限的信号f(t)的正变换可积分，其频谱的正变换可积分，其频谱F()的频的频带无限宽；频带有限的频谱带无限宽
40、；频带有限的频谱F()的逆变换可积分，其信的逆变换可积分，其信号号f(t)的持续时间无限长。的持续时间无限长。杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法第第1题的程序题的程序N=32;n=0:N-1;p=8;q=2;x=exp(-(n-p).2/q).*n=15;subplot(211),stem(n,x);xlabel(n);ylabel(x(n);X=fft(x,1000);subplot(212);plot(abs(X);xlabel(omega);ylabel(|X(omega)|);杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速
41、算法第第2题的目的是了解频谱峰值的频率位置和实际频率的关系。题的目的是了解频谱峰值的频率位置和实际频率的关系。书上第书上第59页。页。N=100;n=0:N-1;a=0.1;f=0.0625;x=exp(-a*n).*sin(2*pi*f*n).*n=15;subplot(211),stem(n,x,.);xlabel(n);ylabel(x(n);X=fft(x);subplot(212);stem(n/N,abs(X),.);xlabel(f);ylabel(|X(f)|);杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法第第3题的目的是分析两个信号的频谱区别。题
42、的目的是分析两个信号的频谱区别。N=32;n=0:N-1;xc=n.*n=4&n=7;subplot(221),stem(n,xc,.);xlabel(n);ylabel(x_c(n);Xc=fft(xc);subplot(222);stem(n,abs(Xc),.);xlabel(k);ylabel(|X_c(k)|);xd=(4-n).*n=4&n=7;subplot(223),stem(n,xd,.);xlabel(n);ylabel(x_d(n);Xd=fft(xd);subplot(224);stem(n,abs(Xd),.);xlabel(k);ylabel(|X_d(k)|);杨
43、毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法第第4题的目的是观察连续信号的频谱。其题的目的是观察连续信号的频谱。其MATLAB程序是，程序是，N=32;n=0:N-1;f=0.125;df=1/16;x=sin(2*pi*f*n)+cos(2*pi*(f+df)*n);subplot(211),stem(n,x,.);xlabel(n);ylabel(x(n);X=fft(x);subplot(212);stem(n/N,abs(X),.);xlabel(k/N);ylabel(|X(k)|);fc=f+df杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里
44、叶变换和快速算法第第5题的目的是观察语音信号的频谱。其题的目的是观察语音信号的频谱。其MATLAB程序是，程序是，load mtlb.mat;sound(mtlb,Fs)x=mtlb;N=length(x);n=1:N;subplot(211);plot(n/Fs,x);xlabel(t/s);ylabel(x(t);X=fft(x);subplot(212);plot(Fs/N*n,abs(X);xlabel(f/Hz);ylabel(|X(f)|);杨毅明杨毅明 第第2章章 离散傅里叶变换和快速算法离散傅里叶变换和快速算法试验一解答：试验一解答：第第3题的目的是测量人耳区别两个相同声音的最小时间差。题的目的是测量人耳区别两个相同声音的最小时间差。td=N/Fs（秒）（秒）sound(mtlb/max(mtlb),Fs),pause,N=300;x=conv(mtlb,1,zeros(1,N),1);sound(x/max(x),Fs),td=N/Fs