04 第4章 离散傅里叶变换及其快速算法.pptx

第1页：第4章离散傅里叶变换及其快速算法

第4章离散傅里叶变换及其快速算法：本章课件封面，标注课程名称、任课教师与授课班级信息。

第2页：本章目录

本章目录

• 4.1 傅里叶变换的几种形式
• 4.5 利用DFT对连续信号进行谱分析
• 4.4 离散傅里叶变换的性质
• 4.3 离散傅里叶变换
• 4.2 周期序列的离散傅里叶级数

第3页：本章目录

本章目录

• 4.6 快速傅里叶变换
• 4.8 综合实例
• 4.7 FFT的应用

第4页：本章学习要点

本章学习要点

• 了解周期序列的傅里叶级数及性质，掌握周期卷积过程掌握圆周(循环)卷积、线性卷积及两者之间的关系理解离散傅里叶变换及性质，掌握圆周移位、共轭对称性掌握FFT算法的计算量分析，按时间、频率抽选的基-2FFT算法掌握

第5页：傅里叶变换的几种形式

Fourier变换的几种可能形式时间函数频率函数连续时间、连续频率—傅里叶变换连续时间、离散频率—傅里叶级数离散时间、连续频率—离散时间信号(序列)的傅里叶变换离散时间、离散频率—

第6页：傅里叶变换的几种形式

连续时间、连续频率—傅里叶变换时域连续函数对应频域是非周期的谱，而时域的非周期对应频域是连续的谱密度函数。

第7页：傅里叶变换的几种形式

连续时间、离散频率—傅里叶级数时域连续函数对应频域是非周期的谱，而频域的离散对应时域是周期函数。

第8页：傅里叶变换的几种形式

离散时间、连续频率—序列的傅里叶变换时域的离散化造成频域的周期延拓，而时域的非周期对应于频域的连续。

第9页：傅里叶变换的几种形式

离散时间、离散频率—离散傅里叶变换一个域的离散对应另一个域的周期延拓，因此离散傅里叶变换的时域和频域都是离散的和周期的。

第10页：傅里叶变换的几种形式

四种傅里叶变换形式的归纳频率函数时间函数非周期和连续连续和非周期非周期和离散(Ω0=2π/T0)连续和周期(T0)周期(Ωs=2π/T)和连续离散(T)和非周期周期(Ωs=2π/T)和离散(Ω0=2π/T0)离散(T)和周期(T0)

第11页：周期序列不能进行Z变换

周期序列不能进行Z变换，因为其在n=-到+都周而复始永不衰减，即z平面上没有收敛域。但是，正象连续时间周期信号可用傅氏级数表达，周期序列也可用离散的傅氏级数来表示，也即用周期为N的正弦序列来表示。

第12页：离散傅里叶级数的导出

离散傅里叶级数的导出对于一个周期为N的周期序列，离散傅里叶级数形式为式中N是一个常数，选取它是为了下面的表达式成立的需要，系数对于该离散傅里叶级数表达式的特性不会有重要影响。

第13页：周期序列的离散傅里叶级数

这就是求k等于0至N-1的N个谐波系数的公式，并注意到式(4.14)所给出的序列呈周期性，且周期为N，即由此说明，时域上周期序列的离散傅里叶级数在频域上仍然是一个周期序列，这与离散傅里叶级数只有N个不同的系数的结论是一致的。

这样，式(4.12)同式(4.14)一起可以看作是时域和频域上周期序列的离散傅里叶级数(DFS)表达式。

第14页：为方便起见

为方便起见，定义复数量符号为则式(4.12)与式(4.14)可表示成由式(4.16)知，频域周期序列，是时域周期序列内一个周期z变换的结果，然后将z变换在z平面单位圆上按等间隔角采样得到的。

第15页：周期序列的离散傅里叶级数

令通常将称为的主值区间序列，则的z变换为可知可以看出，当时，是在z平面单位圆上的N个等间隔角点上对z变换的采样，其第一个采样点为，即出现在处，在之外随着k的变化，的值呈周期变化，这些特点如图4.8所示。图4.8z平面单位圆上对采样

第16页：周期序列的离散傅里叶级数

由于单位圆上的z变换即为序列的傅里叶变换，所以周期序列也可以理解为一个周期傅里叶变换的等间隔采样，因为可以看出这相当于以2π/N的频率间隔对傅里叶变换进行采样。

第17页：离散傅里叶级数的性质令和都

离散傅里叶级数的性质令和都是周期为N的周期序列，其各自的DFS分别为1.线性式中，a和b为任意常数，所得到的频域序列也是以N为周期的周期序列。2.序列的移位(时移特性)

第18页：调制特性(频移特性)或4.共轭

23.调制特性(频移特性)或4.共轭对称性5.周期卷积对于两个周期为N的周期序列和，它们的DFS分别为和，若，则可定义和的周期卷积，且，或

第19页：离散傅里叶变换

设x(n)为有限长序列，长度为N，即x(n)只在点上为非零值，其他都为0。由此，可以把x(n)看成周期为N的周期序列的一个周期，即而把看成x(n)的以N为周期的周期延拓，即通常把的第一个周期到定义为的“主值区间”，也可以说x(n)是的主值序列，即主值区间上的序列。

这样式(4-33)可以表示为

第20页：离散傅里叶变换

所以频域的周期序列也可看成是对有限长序列的主值序列，即式(4.16)和式(4.17)的DFS变换对为它们的求和都只限定在的主值区间进行，因而变换关系也适用于主值序列和，于是可得到有限长序列的离散傅里叶变换定义

第21页：式(4.36)和式(4.37)均

式(4.36)和式(4.37)均为线性方程组，是N个x(n)与N个X(k)之间的变换关系，也可以用矩阵方程来表示。设x为由x(n)( )构成的列矩阵，X为由X(k)( )构成的列矩阵，即则有DFT的矩阵方程

第22页：离散傅里叶变换

同样，IDFT的矩阵方程为

第23页：例4.2 求它的N点DFT

例4.2已知序列，求它的N点DFT。

解由DFT的定义式(4.36)得到的如图4.13所示。这是一个很特殊的例子，表明对序列来说，不论对它进行多少点的DFT，所得结果都是一个离散矩形序列。n012kN-10…图4.13序列及其

第24页：例4.4 求复数序列的DFT

例4.4求复数序列的DFT。

解根据式(4.38)可求得

第25页：线性设两个

线性设两个有限长序列为和，则几点说明如下(1)若和皆为点序列，即在范围有值，则也是N点序列；(2)若和的点数不等，设为点( )，而为点( )，则应为点，故DFT必须按N计算。

例如，若，则取，再将补上个零值点后变为点的序列，然后都作点的DFT。

第26页：循环移位

循环移位定义：一个长度为N的有限长序列的循环移位定义为图4.14序列的循环移位(a)有限长序列(b)周期延拓(c)周期序列移位(d)取主值周期

第27页：时域循环移位定理

时域循环移位定理：对于有限长序列，，为它的循环移位，则循环移位后的DFT为这表明，有限长序列的循环移位在离散频域中引入一个和频率成正比的线性相移，而频谱的幅度没有改变。

第28页：频域循环移位定理

频域循环移位定理：对于频域有限长序列，也可进行循环移位，利用频域和时域的对偶关系，不难得到这就是调制特性，说明时域序列的调制等效于频域的循环移位。

第29页：离散傅里叶变换的性质

循环卷积对于有限长序列和( )若，则有两种表示方法，即一般称式(4.44)为和的N点循环卷积，记作，以便与线性卷积相区别。这个卷积可以看作是周期序列和做周期卷积后再取主值序列。

第30页：离散傅里叶变换的性质

线性卷积与循环卷积之间的关系线性卷积的非零区间为，的非零区间为，将两个不等式相加，得到的非零区间为循环卷积设是两序列的L点循环卷积，，这就要把和都看成是L点的序列，所以将和延长成L点的序列，不足的补零。

第31页：离散傅里叶变换的性质

则和的L点循环卷积为结论：(1)和L点的循环卷积是其线性卷积以L为周期进行周期延拓，然后再取主值序列的结果。

第32页：(2)由于

(2)由于有N1+N2-1个非零值，所以延拓的周期L必须满足L ≥ N1+N2-1,此时周期延拓不会发生混叠，而的前(N1+N2-1)个值都为的值，其余的L-(N1+N2-1)个点上的序列值则是补充的零值；否则，当L<N1+N2-1时，周期延拓时必然会有一部分非零值发生混叠。

(3)循环卷积等于线性卷积的必要条件是L ≥ N1+N2-1。

第33页：离散傅里叶变换的性质

本页源文件仅保留章节页眉「离散傅里叶变换的性质」，未提取到正文文字，页面以图示为主。建议对照原课件图片补充本页要点说明。

第34页：共轭对称性

共轭对称性即存在共轭偶对称性，存在共轭奇对称性。

第35页：用及分别表示序列的共轭偶

用及分别表示序列的共轭偶对称分量和共轭奇对称分量，则

第36页：DFT与z变换的关系当时或表明

DFT与z变换的关系当时或表明是z平面单位圆上辅角为的点，也是将z平面单位圆N等分后的第k点，所以，也就是z变换在单位圆上的等间隔采样，如图4.19所示。式(4.61)表明DFT是对DTFT的采样结果，其采样间隔为。

第37页：离散傅里叶变换的性质

本页源文件仅保留章节页眉「离散傅里叶变换的性质」，未提取到正文文字，页面以图示为主。建议对照原课件图片补充本页要点说明。

第38页：DFT形式下的Parseval定理若

DFT形式下的Parseval定理若，则式(4.62)变成即式(4.63)两边都是序列能量的表现形式，这表明一个序列在时域计算的能量与在频域计算的能量是相等的。

第39页：混叠现象防止混叠的唯一办法就

51.混叠现象防止混叠的唯一办法就是保证采样频率足够高。实际应用时，通常取，对于采样频率固定情况，为确保无混叠，可在采样前设置一模拟低通滤波器，滤除高于折叠频率的频率成分，这种滤波器就是抗混叠滤波器。

第40页：截断效应时间无限的信号进行DFT运算过程

52.截断效应时间无限的信号进行DFT运算过程中，必须将其截短成有限长信号，虽然无限信号频带有限，但由于截短导致了分散的扩展谱线现象，称为频谱泄漏或功率泄露。3.栅栏效应由于N点DFT是在频率区间[0 , 2π]上对信号的频谱进行N点等间隔采样，而采样点之间的频谱函数值是未知的，这就如同从N个栅栏缝隙中观看景象一样，只能得到N个缝隙中看到的频谱函数值，因此称这种现象为栅栏效应。

第41页：DFT的分辨率增补零值可以改变

54. DFT的分辨率增补零值可以改变对DTFT的采样密度，但这并不能提高DFT的频率分辨率，因为DFT的频率分辨率通常规定为，这里的N是指信号的有效长度，而不是补零的长度。不同长度的，其DTFT的结果是不同的；而相同长度的尽管补零的长度不同，其DTFT的结果却是相同的，它们的DFT只是反应了对相同的DTFT采用了不同的采样密度。

因此，要提高DFT的分辨率，只有增加信号的截取长度N。

第42页：直接计算DFT的运算量一般情况下

直接计算DFT的运算量一般情况下，、以及都是复数，因此每计算一个值，需要N次复数乘法和N-1次复数加法，而共有N个点(k从0取到N-1)，所以完成整个DFT运算需要N2次复数乘法及N(N-1)次复数加法。实际上复数运算是由实数运算来完成的，1次复数乘法要做4次实数乘法和2次实数加法，1次复数加法要做2次实数加法。

所以，做1次DFT需要做4N2次实数乘法及2N(2N-1)次实数加法。

第43页：改进途径(1)的周期性(2)

改进途径(1)的周期性(2)的对称性(3)的可约性利用这些特性，使DFT运算中有些项可以合并，并可以把长序列的DFT分解为短序列的DFT。

第44页：快速傅里叶变换

按时间抽取的基-2FFT算法设输入序列长度为N=2M(M为正整数，将该序列按时间顺序的奇偶分解为越来越短的子序列，称为基2按时间抽取的FFT算法。也称为Coolkey-Tukey算法。其中基数2----N=2M，M为整数.若不满足这个条件，可以人为地加上若干零值（加零补长）使其达到N=2M。

算法原理

第45页：快速傅里叶变换

设序列点数N = 2M，M为整数。若不满足，则补零。时间抽选FFT算法，分解遵循两条规则：时间上进行奇偶分解；频率上进行前后分解。算法步骤

第46页：快速傅里叶变换

本页源文件仅保留章节页眉「快速傅里叶变换」，未提取到正文文字，页面以图示为主。建议对照原课件图片补充本页要点说明。

第47页：快速傅里叶变换

注

第48页：快速傅里叶变换

蝶形运算

第49页：快速傅里叶变换

(1)N/2点的DFT运算量:复乘次数:复加次数:(2)两个N/2点的DFT运算量:复乘次数:复加次数:(3)N/2个蝶形运算的运算量:复乘次数:复加次数:复乘:复加:总共运算量:*但是,N点DFT的复乘为N2;复加N(N-1);与分解后相比可知,计算工作点差不多减少一半。

第50页：首先可以分解

首先可以分解为两个N/2=4点的DFT.具体方法如下:8点FFT的算法

第51页：快速傅里叶变换

（1）N=8点分解成2个4点的DFT的信号流图X(4)~X(7)同学们自已写

第52页：快速傅里叶变换

(2)N/2(4点)-->N/4(2点)FFT由于N=2L,所以N/2仍为偶数,可以进一步把每个N/2点的序列再按其奇偶部分分解为两个N/4的子序列。

第53页：根据旋转因子的可约性

根据旋转因子的可约性，将系数统一为，则一个N=8点DFT就可分解为四个N/4=2点DFT

第54页：(3)N/4（2点）->2个1点DFT

(3)N/4（2点）->2个1点DFT

第55页：例4.5 计算机的速度为平均每次复数乘

例4.5如果计算机的速度为平均每次复数乘需要5×10-6秒，每次复数加需要10-6秒，用来计算N=1024点DFT，求分别利用DFT和FFT计算各需要多少时间？二者计算量之比值？解直接用DFT的复数乘运算次数为N2次=1024×1024次，复数加法计算次数为N(N-1)= 1024×1023，所以直接计算所需时间为T=5×10-6×10242+10-6×1024×1023≈6.29s。

FFT计算所需时间为DFT运算时间/FFT运算时间=6.29s /35.84ms =175.5倍。

第56页：算法特点1）原位计算m表示第m级迭代

算法特点1）原位计算m表示第m级迭代，k，j表示数据所在的行数

第57页：倒位序规律

倒位序规律

第58页：蝶形运算参数规律第L级蝶形

蝶形运算参数规律第L级蝶形中系数因子为(L=1,2,…,M；J=0,1,2,…, 2L-1-1)，即第L级蝶形运算系数因子类型数为2L-1个。如N=8，共有M=3级。第一级，20=1个蝶形运算系数为，即一种蝶形运算类型。第二级，21=2个蝶形运算系数为，两种蝶形运算类型。

第三级，22 =4个蝶形运算系数为，即四种蝶形运算类型。

第59页：快速傅里叶变换

按频率抽取的基-2FFT算法1、算法原理设序列点数N=2L，L为整数。将X(k)按k的奇偶分组前，先将输入x(n)按n的顺序分成前后两半：时间上前后分，频率上奇偶分。

第60页：N点DFT按k的奇偶分组可分

62.N点DFT按k的奇偶分组可分为两个N/2的DFT当k为偶数,即k=2r时,(-1)k=1；当k为奇数,即k=2r+1时(-1)k=-1。这时X(k)可分为两部分：

第61页：可见,上面两式均

可见,上面两式均为N/2的DFT。

第62页：快速傅里叶变换

63.蝶形运算

第63页：快速傅里叶变换

把一个N点DFT按k的奇偶分解为两个N/2点的DFT。N=8时，上述分解过程如图4.27所示。

第64页：快速傅里叶变换

本页源文件仅保留章节页眉「快速傅里叶变换」，未提取到正文文字，页面以图示为主。建议对照原课件图片补充本页要点说明。

第65页：快速傅里叶变换

本页源文件仅保留章节页眉「快速傅里叶变换」，未提取到正文文字，页面以图示为主。建议对照原课件图片补充本页要点说明。

第66页：快速傅里叶变换

按频率抽取法的运算特点尽管DIF与DIT的蝶形结构不同，但其运算量相同，即有M级运算，每级运算需N/2个蝶形运算来完成，总共需要次复乘，次复加。与时间抽取法不同的是，按频率抽取法的输入是自然序列，而输出是倒位序。

因此运算完毕后，要通过变址计算将倒位序转换成自然序列，然后再输出，转换方法与时间抽取法相同。

第67页：FFT的应用

本页源文件仅保留章节页眉「FFT的应用」，未提取到正文文字，页面以图示为主。建议对照原课件图片补充本页要点说明。

第68页：FFT的应用

用FFT计算IDFT比较两式可知,只要DFT的每个系数换成,最后再乘以常数1/N就可以得到IDFT的快速算法--IFFT。

第69页：FFT的应用

本页源文件仅保留章节页眉「FFT的应用」，未提取到正文文字，页面以图示为主。建议对照原课件图片补充本页要点说明。

第70页：实数序列的FFT

实数序列的FFT如果序列x1(n)是实序列，由于FFT计算的序列一般都是复序列，所以可以把两个相同长度(例如N)的实数序列x1(n)和x2(n)组成一个复数序列，一次求两个实序列的变换，从而节约运算量。

所以

第71页：线性卷积的FFT算法

线性卷积的FFT算法

第72页：FFT的应用

本页源文件仅保留章节页眉「FFT的应用」，未提取到正文文字，页面以图示为主。建议对照原课件图片补充本页要点说明。

第73页：FFT的应用

本页源文件仅保留章节页眉「FFT的应用」，未提取到正文文字，页面以图示为主。建议对照原课件图片补充本页要点说明。

第74页：FFT的应用

本页源文件仅保留章节页眉「FFT的应用」，未提取到正文文字，页面以图示为主。建议对照原课件图片补充本页要点说明。

第75页：用FFT计算相关函数若L点x(n)

用FFT计算相关函数若L点x(n)，M点y(n)，计算线性相关：x(n)及y(n)的卷积公式

第76页：相关和卷积的时域关系

相关和卷积的时域关系

第77页：FFT计算相关

FFT计算相关

第78页：Matlab程序实现

已知一模拟信号xa(t)=e-tu(t)，现以采样频率fs=20Hz进行采样。用DFT分别计算当序列长度L=100和20时，N=200点的幅度频谱样值，并通过作图与理论上的频谱样值进行比较。解原信号xa(t)=e-tu(t)的傅里叶变换为其幅度为用

MATLAB程序实现如下。fs=20;L=100;N=200;n=0:L-1;t1=n/fs;xn1=exp(-t1);xn=[xn1,zeros(1,N-L)];

第79页：Matlab程序实现

Xk1=dft1(xn,N);magXk1=abs(Xk1);k1=(0:length(magXk1)'-)*N/length(magXk1);L=20;N=200;n=0:L-1;t2=n/fs;xn2=exp(-t2);xn=[xn2,zeros(1,N-L)];Xk2=dft1(xn,N);magXk2=abs(Xk2);k2=(0:length(magXk2)'-)*N/length(magXk2);figure(1);stem(t1,xn1); %title('xa(t) t=5s');figure(2);stem(t2,xn2); %title('xa(t) t=1s');figure(3);stem(k1,magXk1);%title('X(k) L=100 N=200');figure(4);stem(k2,magXk2);%title('X(k) L=20 N=200');figure(5);Omeger=0:0.1:20*pi;Xa=1./(1+Omeger.^2);stem(Omeger/pi,Xa);%title('|Xa(j\omega)|');

第80页：综合实例

以上程序运行结果如图4.38和图4.39所示。

第81页：综合实例

本页源文件仅保留章节页眉「综合实例」，未提取到正文文字，页面以图示为主。建议对照原课件图片补充本页要点说明。