第2章 离散傅里叶变换和快速算法.ppt

1、第2章 离散傅里叶变换和快速算法,2.1 离散傅里叶变换 2.2 利用DFT做连续信号的频谱分析 2.3 快速傅里叶变换 2.4 关于FFT应用中的问题,2.1 离散傅里叶变换,序列的傅里叶变换可以用来分析连续时间信号的频谱，但是，它不能让计算机用来计算信号的频谱。为什么呢？ 真正的傅里叶变换有4种： CTFS给连续周期信号用， CTFT给连续非周期信号用， DTFS给离散周期信号用， DTFT给离散非周期信号用。,2.1.1 离散傅里叶级数,离散傅里叶级数的定义： 它们的物理意义是什么呢？,离散傅里叶级数是用在周期序列的，其x(n)和X(k)都是离散值，都具有周期性。 怎么知道它们有周期性呢

2、？ 离散傅里叶级数的定义是怎么来的？,离散傅里叶级数的定义是这么来的：,DFS的性质： 线性性质、序列移位性质、共轭对称性质等都和DTFT的相同。 共轭对称的定义是f(t)=f*(-t)， 共轭反对称的定义是f(t)=-f*(-t)。,共轭对称性的说明： 若复数序列x(n)的共轭序列是x*(n)，则它的离散傅里叶级数的系数 怎么证明它呢？,进一步可以得到实数序列的DFS是共轭对称的，即 怎么证明它呢？,周期序列也有卷积运算，其的卷积范围是一个时序周期， 不过要注意的是：参加卷积的两个周期序列的周期必须相等。 周期序列也有卷积定理，即,请注意DFS和DTFT的性质不同之处： （1）DFS的频率变

3、量是离散的，DTFT的频率变量是连续的； （2）DFS的卷积范围是有限的，DTFT的卷积范围是无限的。 这种区别意味着什么？从数字信号处理的角度来看。,2.1.2 离散傅里变换,离散傅里叶级数是用在周期序列的，而大部分的序列是非周期的，实际应用中，我们处理信号时是分段处理的。怎么办？ 人为地将周期信号的主值区间的序列看作是一个非周期信号，看作是被分析的信号的一部分。 这种做法就是离散傅里叶变换的精神。离散傅里叶变换是离散傅里叶级数的特例。,离散傅里叶变换的定义： WN是什么？它的物理意义是什么？有什么用？,离散傅里叶变换和离散傅里叶级数的区别在DFT的： （1）取值范围，n和k均在0N-1；

4、（2）书写方法，RN(n)和RN(k); （3）计算方法，先把序列当作周期序列计算，然后再限制周期序列的范围。,例1（书上第51页） 求x=1+j2, 2+j2, j, 1+j的离散傅里叶变换。 解：方法一，按定义来计算。 方法二，按矩阵来计算。设x和X都是列向量。 方法一和方法二有什么关系？,方法三，按MATLAB来计算。 如果x和X都是列向量的话，则 X=WN*x， 其中WN=exp(-j2/Nkn)，这时k和n都是行向量。 请注意(4+j6)和(4.000+6.000i)的区别。,对于有限长序列的离散傅里叶变换，其性质和离散傅里叶级数的相同，只是注意取主值的限制就可以了。 例如： （1）

5、线性性质，注意它们的长度。 （2）移位性质，注意它们的移位。 （3）循环卷积，注意它们的主值范围。,例2（书上第54页）设x5(n)=x5(n)=R5(n)。求两个序列的5点长循环卷积和10点长循环卷积y(n)。 解： （1）5点的循环卷积： 方法一，按循环卷积的定义计算；可以心算吗？ 方法二，按循环卷积定理计算。可以心算吗？,（2）10点的循环卷积： 方法一，按循环卷积的定义计算；可以心算吗？ 方法二，按循环卷积定理计算。可以心算吗？,循环卷积的长度N和线性卷积的长度(N1+N2-1)有什么关系？ 为什么要提这个问题？,因为长度为N1的序列x1(n)和长度为N2的序列x2(n)的线性卷积 而

6、长度为N1的序列x1(n)和长度为N2的序列x2(n)的N点长循环卷积（NN1和N2）,yL(n)和yC(n) 的关系 说明了什么？ 这个关系N(N1+N2-1)有什么用？,四种傅里叶变换的频率关系（物理意义）： （1）当作周期函数的成分的正弦波是 ， （2）当作非周期函数的成分的正弦波是 ， （3）当作周期序列的成分的正弦波是 ， （4）当作非周期序列的成分的正弦波是 。,周期函数的谐波频率与周期序列的谐波频率是否对等呢？ 由于离散傅里叶级数的定义是： 所以，只有当周期函数x(t)的周期T0=NT时，周期函数x(t)和周期序列x(n)的谐波角频率才有对等的关系。,傅里叶变换在信号压缩中的应用

7、： 假设在时间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 利用DFT做连续信号的频谱分析,离散傅里叶变换可以用来分析连续时间信号的频谱，其原理如下： 这种方法存在如下问题： 混叠，泄漏，栅栏效应，分辨率，周期效应。 根据例6（书上63页）说明上面5个问题。,

8、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,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.3 快速傅里叶变换,快速傅里叶变换是一种快速计算DFT的方法，是相对于直接按照DFT的定义进行计算的方法而言的。 有代表性的快速算法有两个： （1）基

9、2时域抽取法快速傅里叶变换， （2）基2频域抽取法快速傅里叶变换。,按定义对N点DFT进行计算时，需要的复数乘法次数是 ？ ，需要的复数加法次数是 ？ 。 据N点长DFT的基本运算量公式：N2，请大家想一想，减少DFT运算量的基本原理是怎样的呢？,减少DFT运算量的基本原理是缩短被计算的DFT的长度。 如何缩短呢？大家想一想，是不是有多种方法？,2.3.1 按时间抽取的FFT,这种方法的基本做法是：将序列分成两半，按序号的偶数和奇数进行分解，使一个N点DFT变成两个N/2点DFT。 时域抽取法FFT的序列长度必须是： N=2M， 以保证序列的分解能够反复地进行到1点长的序列。,基本的分解方法由

10、两步组成： （1）按奇偶时序分解N点序列成为N/2点序列， （2）整顿DFT表达式，使之成为真正的N/2点DFT。,第1次分解DFT后的复数计算量： （1）乘法的计算量是 次？ （2）加法的计算量是 次？ 需要多少次分解才能将N点DFT变成1点DFT？ 这时的复数乘法的计算量是 次？复数加法的计算量是多少 次？,怎样看用分解的方法简化整个DFT过程的计算量？ （1）反复运用分解的基本方程， （2）将分解的基本方程简化为蝶形图，用蝶形图分析和设计快速运算。 蝶形图有流图的方式和交叉线的方式。,例题1：请画出N=8时DIT-radix2-FFT的流图。 解：分解时的序列顺序符号的表达方式很重要，按

11、二进制的形式排列有特殊的好处。 它能使最后1点长的序列的排列方式，有一个很有规律的做法。,DIT-radix2-FFT的规律： （1）蝶形运算分解DFT， （2）蝶形运算是原位运算， （3）蝶形的类型是按分解的次数成倍地增加， （4）输入序列的序号倒序排列。,2.3.2 按频率抽取的FFT,这种方法的基本做法是：将序列分成两半，按时序的前后两半进行分解，使一个N点DFT变成两个N/2点DFT。 频域抽取法FFT的序列长度必须是： N=2M， 以保证序列的分解能够反复地进行到1点长的序列。,基本的分解方法由两步组成： （1）分解N点序列成为N/2点序列，,（2）按频谱序号偶数和奇数整顿DFT表达

12、式，使之成为真正的N/2点DFT。 对于偶数序号的频谱， 对于奇数序号的频谱，,令相加和相减的短序列（注意下标的含义）为 它们分别对应偶数频序和奇数频序的频谱；,基本的DIF-FFT的分解公式能用蝶形符号来表示吗？,例题2：请画出N=8时的DIF-radix2-FFT的蝶形运算图。 解：分解时间序列时，频序按二进制的形式排列有特殊的好处。 它能使最后1点长的频谱序列的排列方式，有一个很有规律的做法。,DIF-radix2-FFT的规律： （1）蝶形运算分解DFT， （2）蝶形运算是原位运算， （3）蝶形的类型是按分解的次数成倍地减少， （4）输出频谱序列的频序是倒序排列。,2.3.3 N为组合

13、数的FFT和基4FFT,N为组合数PQ的FFT的基本做法是：先将序列分成Q点长的P段小序列，然后将Q点长的小序列变成真正意义的Q点DFT。 基4FFT是对N=4M的序列进行分解，每个被分解的序列都被分解成4个等长的小序列。,2.3.4 DFT的应用,DFT可以用来建立建筑物摆动的模型：,2.4 关于FFT应用中的几个问题,快速傅里叶变换是计算离散傅里叶变换的节省时间和节省存储器的方法。它有两个有代表性的算法，对N点DFT进行计算时，需要的复数乘法次数是 ？ ，需要的复数加法次数是 ？ 。,2.4.1 用FFT计算IDFT,快速计算IDFT的快速方法有几种？ （1）重新编程； （2）用FFT的程

14、序，变换旋转因子的符号； （3）用FFT的程序，取共轭的共轭。,2.4.2 实数序列的FFT,快速计算实数序列的DFT的方法有几种？ （1）重新编程； （2）用FFT的程序，一举两得的方法，一次变换两个实数序列； （3）用FFT的程序，事半功倍的方法，将实数序列变成两段。,一举两得的方法是用两个实数序列x(n)和y(n)组成一个复数序列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。,事半功倍的

15、方法是将一个实数序列分成两段，当作一个复数序列的实部和虚部： 有几种做法？,2.4.3 线性卷积的FFT算法,线性卷积的快速算法就是用循环卷积代替线性卷积，然后用快速傅里叶变换对循环卷积进行计算。其基本步骤是： （1）延长线性卷积的两个序列的长度N1和N2，用补零的方法延长到L ，L N1+N2-1； （2）对两个序列作L点FFT，并根据卷积定理求它们的频谱乘积； （3）用FFT求该频谱的L点时间序列。,线性卷积的FFT算法快在哪里呢？ 例题3：当两个序列的长度N1=N2=1024时，请比较直接线性卷积的运算量和用FFT算法的运算量。 解： （1）直接线性卷积的乘法次数是 ， 加法次数是 。

16、（2）FFT算法的乘法次数是 ， 加法次数是 。,（1）直接线性卷积的运算量： 运算总数为4190209次。 （2）用FFT算法的运算量： 运算总数为350208次。 （1）的总量比（2）的总量多11倍。,2.4.4 用FFT计算相关函数,相关是指两个信号的相似程度，它的定义是： 相关函数的用途是比较两个信号的相对相似程度，或者是比较信号自己的相对相似程度。什么意思呢？,相关函数与卷积函数相比，卷积函数是 根据两者的关系，可以用FFT来解决相关函数的问题。,例9 用相关函数测量液体流动的速度，如微血管、管道、河流等。（书上90页） N=18;n=0:N; x=sin(0.3*n);%泡泡信号

17、subplot(4,1,1);stem(n,x,.);axis(0,25,-1,1);xlabel(k);ylabel(x(k); y=zeros(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;%

18、相关函数信号 subplot(414);stem(n,rxy,.);xlabel(n);ylabel(r_xy(n); axis(-25,25,-14,14);,将DFT的成分理念用到二维图像的成分分析上，有离散余弦变化。 例如（pout,tire等）： I= imread(circles.tif); subplot(221);imshow(I); J = dct2(I); subplot(223);imshow(log(abs(J), colorbar,书上习题2.26的解答： a=0.8;N=10;n=0:N-1;x1=a.(-n);x2=ones(1,N); figure(1); sub

19、plot(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);xlabel(n);ylabel(x_2(n-2);legen

20、d(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);legend(补0扩展); subplot(3,2,2);stem(m,x3

21、(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,3);stem(m,r2(mod(m,20)+1),.k);xlabel(m)

22、;ylabel(r_2(m);legend(循环卷积的方法);,试验一解答： 第1题的目的是了解用DFT分析信号频谱时的泄漏和混叠失真的含义。书上第61页。 泄漏含义由傅里叶变换的定义来理解， 持续时间有限的信号f(t)的正变换可积分，其频谱F()的频带无限宽；频带有限的频谱F()的逆变换可积分，其信号f(t)的持续时间无限长。,第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题的目的是了解频谱峰值的频率位置和实际频率的关系。书上第59页。 N=100;n=0:N-1; a=0.1;f=0.0625; x=exp(-a*n).*