《离散傅里叶变换》PPT课件.ppt

测试信号分析与处理课程 第四章 离散傅里叶变换及其 快速算法 数字谱分析是数字信号处理的基本内容，通过对信号的频谱 分析，掌握信号特征，以便对信号作进一步处理，达到提 取有用信息的目的。包括序列的傅立叶变换、离散傅立叶 级数、离散傅立叶变换和快速傅立叶变换 第一节 序列的傅里叶变换 第二节 离散傅里叶级数（DFS） 第三节 离散傅里叶变换（DFT） 第四节 离散傅里叶变换的性质 测试信号分析与处理课程 第五节 快速傅里叶变换 第六节 IDFT的快速算法（IFFT） 第七节 实序列的FFT高效算法 第八节 频率域采样理论 第一节 序列的傅里叶变换 v已知序列x(n)的Z变换为： v如X(Z)在单位圆上是收敛的，则将在单位圆上 的Z变换定义为序列的傅里叶变换，即 v序列的傅立叶变换定义为单位圆上的Z变换，因 此其同Z变换具有相同的性质 一、定义 v二 、物理意义与存在条件 x(t) x(n) 正变换 反变换 分析 综合 连续非周期连续周期 序列傅立叶变换存 在条件 序列必须绝对可和 比较这两个反变换 三、特点与应用 v非周期序列的傅里叶变换（频谱）的特点在于 它是 周期为 的连续周期函数，其周期为 。 是连续周期函数，因此也可以进行傅立叶级数展开 v序列可以表示为复指数序列分量的叠加，而 对复指数序列的响应完全由系统的频率响应 确定，既可以推出输出的傅立叶变换为： 三、特点与应用 第二节 离散傅里叶级数（DFS） 一、傅里叶变换在时域和频域中的对称规律 v 第二节 离散傅里叶级数（DFS） v 第二节 离散傅里叶级数（DFS） v一个域中（时域或频域）是连续的，对应另一个 域中（频域或时域）是非周期的。 v一个域中（时域或频域）是离散的，对应另一个 域中（频域或时域）是周期的。 第二节 离散傅里叶级数（DFS） 二、离散傅里叶级数（定量表达周期序列的傅立叶级数展开式 ） v离散周期信号的频谱，即离散傅里叶级数(DFS) 。 v非周期序列的频谱 v一个非周期序列x(n)可以分解为一系列连续的 不同频率的复指数序列 的叠加积分，其频 谱 表示了这些不同频率分量的复幅度， 频率是周期性的，独立分量在 到 之间 。 v周期序列的频谱是非周期序列频谱的离散化，根 据频谱的含义，意味着一个周期序列可以分解成 一系列 为离散（ ）的指数序列分量 的叠加，其频率间隔： v设任意k次频率的复指数序列分量 的复幅度用 表示，则可以推出周期序列的傅立叶级数变换对 。 v离散傅里叶级数的变换对表达式 v离散傅立叶级数的正反变换，为数字信号 分析和处理做好了理论准备，因为时域和 频域都是离散化； v但是他们都是周期序列，需要在理论上对 序列的有限化进一步研究，以解决离散信 号分析处理或系统设计以及实现等实用化 方面的问题。 第三节 离散傅里叶变换（DFT） 第三节 离散傅里叶变换（DFT） 一、离散傅里叶变换DFT定义式 v离散傅里叶变换就是对有限长序列进行傅里叶变 换的表示式。定义一个周期序列在第一个周期内 的有限长序列值为此周期序列的主值区间，表示 为： 正变换 反变换 第三节 离散傅里叶变换（DFT） v矩阵形式 或 第三节 离散傅里叶变换（DFT） 二、DFT的物理意义 1 非周期序列的频谱，即它的傅立叶变换，是一个 连续的周期性频谱； 2 有限长序列的DFT却是离散的序列，两者虽然不 同，但存在着重要的联系。 可以证明：有限长序列的傅立叶变换DFT是该 序列频谱的抽样值。 v有限长序列的DFT就是序列在单位圆上的Z变换 （即有限长序列的傅里叶变换或频谱）以 为间隔的抽样值 第四节 离散傅里叶变换的性质 v线性特性 v时移特性 1）圆周移位序列 2）时移定理 v频移特性 过程、圆移位 序列在时域中圆周移位，频域上将产生附加相移 序列在时域上乘于复指数序列，则在频域上将发生圆周移位 第四节 离散傅里叶变换的性质 v圆周卷积特性 1）时域圆周卷积 2）频域圆卷积 若 v实数序列奇偶性（对称性） v 帕斯瓦尔定理：变换过程中能量是守恒的。 顺时针,左移,逆时针转动, 再顺时针读数. H(-n)NRN(n) H(1-n)NRN(n) H(2-n)NRN(n) H(3-n)NRN(n) y(0) 例：长度为4的两个有限长序列x(n)=1,2,3,4和h(n)=4,3,2,1) 计算其循环卷积（圆周卷积） 解：将x(n)按逆时针方向依次均匀分布在内圆上，将序列 h(n)按顺时针方向依次均匀分布在外圆上，依次逆时针旋转 外圆，增加时间序号，将内外圆数值对应相乘并求和。得到 y(n)=24,22,24,30. 第五节 快速傅里叶变换 DFT是利用计算机进行信号谱分析的理论依据，但计算量太大； 快速傅立叶变换是以较少计算量实现DFT的快速算法，FFT是数 字信号处理中最基本的算法。本节分析直接计算的工作量及DFT 的特点，最后研究基2时析型FFT（基2时间抽选法） 一、DFT直接运算的工作量 计算机运算时（编程实现）： N N次复乘，次复乘，N-1N-1次复加次复加 N N个点个点 复数乘法复数加法 一个X(k)NN 1 N个X(k) (N点DFT) N 2N (N 1) 实数乘法实数加法 一次复乘42 一次复加2 一个X (k)4N2N+2 (N 1)=2 (2N 1) N个X (k) (N点DFT) 4N 22N (2N 1) 运算量 (a+jb)(c+jd)=(ac-bd)+j(bc+ad) 第五节 快速傅里叶变换 按定义计算，需要 次复数乘和(N-1)N次复数加运算，若序列为 复数，则每次复数乘包括4次实数乘和2次实数加，每次复数加包 含2次实数加，因此对于长度为N的序列，运算总共有4 次实数 乘和2 +2(N-1)N次实数加。随着N的增加，实时处理就无法实 现。 例：计算一个 N点DFT ，共需N2次复乘。以做一次 复乘1s计，若N =4096，所需时间为 例：石油勘探，有24个通道的记录，每通道波形记 录长度为5秒，若每秒抽样500点/秒， 1）每通道总抽样点数：500*5=2500点 2）24通道总抽样点数：24*2500=6万点 3）DFT复乘运算时间：N2=(60000)2=36*108次 由于计算量大，且要求相当大的内存，难以实现实 时处理，限制了DFT的应用。长期以来，人们一直在寻 求一种能提高DFT运算速度的方法。 FFT便是 Cooley ;.; v5）时间序列是按时间先后顺序排列的，称 为自然顺序，但FFT计算时，需要符合快速 算法的要求，需要一种乱序输入，才能获 得X(K)按自然顺序的输出，也就是需要对 输入进行相应处理，即所谓的码位倒置或 输入重排。 第五节 快速傅里叶变换 序列输入 的 自然顺序 十进制二进制码 码位倒 置结果 （二进 制码） 乱序十 进制 序列乱 序的输 入顺序 4 输入重排（输入序列不再为原序列的自然顺序，需要重排） 第五节 快速傅里叶变换 5.运算量比较 N（ ）点的FFT总运算量为 复数乘 复数加 利用基2时析型FFT求序列的DFT同直接计 算序列的DFT的复数乘运算次数之比为 DFT有快速算法FFT，IDFT是否有快速算法呢？ IFFT是IDFT的快速算法。 第六节 IDFT的快速算法（IFFT） 一、IFFT算法 在FFT的时间抽取算法中，第一次分解的结果是 第六节 IDFT的快速算法（IFFT） 依次类推，可以求出x(n)的各点，下面是整个8点IFFT的信号流 程图。 如果不在每次迭代后增加1/2，可以最后的输出序列中每个元素除 以N。 二、利用FFT的程序求IFFT的方法 vIFFT与FFT的信号流图还是存在区别，不能用 FFT程序实现IFFT算法。 输入序列变输出序列，WN的不同，输出序列的每个元素除以N ，是X(k)倒序重排，x(n)自然顺序排列。 X(k)的共轭作为输入，结果取共轭，再除以N就得到了 x(n)。 第七节 实序列的FFT高效算法 v当输入序列为实数数据时，进一步可以提高FFT 运算效率 v 同时计算两组实序列的DFT （两组同长序列构成新的序 列） 由于x(n)和y(n)为 实序列，有 v用N点序列的DFT结果获得2N点长实序列的DFT结 果 求出z(n)对应的Z(K)，可以得到x(n)和y(n)对应的X(K)和 Y(K). x1(n)和x2(n）组成一个复序列，利用上面的结果求出X1(K)和 X2(K) 第八节 MATLAB中用于FFT计算的函数 v一 函数 fft v二 函数ifft 一维快速傅立叶正逆变换 v三 应用实例 vt=0:0.001:0.6; vx=sin(2*pi*50*t)+sin(2*pi*120*t); vy=x+1.5*randn(1,length(t); 正弦信号与随机噪声叠加 vY=fft(y,512); 求含噪声信号的离散傅立叶变换（数字谱） vP=Y.*conj(Y)/512; 计算功率谱 vf=1000*(0:255)/512; vplot(f,P(1:256); 功率谱中在频率50HZ，120HZ处存在该频率的 成分 第九节 频率域采样理论 v时域采样定理：在一定条件下可以由时域 离散采样信号恢复原来的连续信号，其中 内插函数是取样函数。 vX(K)是怎么样得到的？ v序列傅立叶变换的采样值得到，能否由 X(K)恢复原来的时域信号或者原来的频谱 函数呢？ 推导过程见书本，结论是：任意序列x(n)，对应的Z变换 为X(z)，X(z)在单位圆上的z变换就是序列的傅立叶变换， 具有连续的频谱，将其作N