《刘顺兰数字信号处理--第三章.ppt》由会员分享，可在线阅读，更多相关《刘顺兰数字信号处理--第三章.ppt（39页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章第三章 快速傅里叶变换（快速傅里叶变换（FFT）3.1 引言3.2 直接计算DFT的问题及改进的途径3.3 按时间抽取（DIT）的基2FFT算法3.4 按频率抽取（IDFT）的基2FFT算法3.5 N为复合数的FFT算法混合基算法3.6 线性调频Z变换（Chirp-z变换）算法3.7 利用FFT分析时域连续信号频谱3.8 FFT的其他应用本章内容本章内容一、一、FFTFFT变换的思想变换的思想二、如何利用二、如何利用FFTFFT分析时域连续信号频谱分析时域连续信号频谱三、三、FFTFFT变换的简单应用变换的简单应用3.1 3.1 引言引言FFTFFT不不是是一一种种新新的的变变换换，而而
2、是是DFTDFT的的一一种种快快速速算法。算法。3.2 3.2 直接计算直接计算DFTDFT的问题及改进的途径的问题及改进的途径一、直接计算一、直接计算DFTDFT的运算量的运算量二、如何减小运算量二、如何减小运算量长度为长度为N N的有限长序列的有限长序列x(nx(n)的的DFTDFT为为对某一个对某一个k k值，计算值，计算X(kX(k)值需要值需要N N次复数乘法、次复数乘法、(N-1)(N-1)次复数加法。次复数加法。N N点点DFTDFT的复数乘法次数等于的复数乘法次数等于N N2 2、N(N-1)N(N-1)次复数加法。次复数加法。一、直接计算一、直接计算DFTDFT的运算量的运算
3、量一次复数乘法需要一次复数乘法需要四四次实数乘法和次实数乘法和两两次实数加法次实数加法一次复数加法需要一次复数加法需要两次两次实数加法。实数加法。对某一个对某一个k k值，计算值，计算X(kX(k)值需要值需要4N4N次实数乘法次实数乘法N N点点DFTDFT的实数乘法次数等于的实数乘法次数等于4N4N2 2、2N(2N-1)2N(2N-1)次实数加法。次实数加法。1 1、根据、根据 的周期性，对称性，可约性，减小的周期性，对称性，可约性，减小DFTDFT运算量运算量二、如何减小运算量二、如何减小运算量2 2、当、当N N很大时，将很大时，将N N点点DFTDFT分解为几个较短的分解为几个较短
4、的DFTDFT进行计算进行计算如：分解为如：分解为M M个个N/MN/M点点DFTDFT则：复数乘法运算量为则：复数乘法运算量为 ,下降到原下降到原来的来的1/M1/M。FFT按时间抽取（按时间抽取（DITDIT）的基）的基2FFT2FFT算法算法按频率抽取（按频率抽取（IDFTIDFT）的基）的基2FFT2FFT算法算法 设序列设序列x(n)x(n)的长度为的长度为N N，且满足且满足为自然数为自然数 按按n n的奇偶把的奇偶把x(n)x(n)分解为两个分解为两个N/2N/2点的子序列点的子序列3.3 3.3 按时间抽取（按时间抽取（DITDIT）的基）的基2FFT2FFT算法算法算法原理：
5、把序列算法原理：把序列x x（n n）按奇偶分解为越来越短的序列。）按奇偶分解为越来越短的序列。X X1 1(k)(k)和和X X2 2(k)(k)分别为分别为x x1 1(r)(r)和和x x2 2(r)(r)的的N/2N/2点点DFTDFT，即即 由于由于X X1 1(k)(k)和和X X2 2(k)(k)均以均以N/2N/2为周期，且为周期，且 时间抽取法蝶形运算流图符号时间抽取法蝶形运算流图符号-1-1 N N点点DFTDFT的一次时域抽取分解图的一次时域抽取分解图(N=8)(N=8)与与第第一一次次分分解解相相同同，将将x x1 1(r)(r)按按奇奇偶偶分分解解成成两两个个N/4N
6、/4长的子序列长的子序列x x3 3(l)(l)和和x x4 4(l)(l)，即即那么，那么，X X1 1(k)(k)又可表示为又可表示为 式中式中 同理，由同理，由X X3 3(k)(k)和和X X4 4(k)(k)的周期性和的周期性和W Wm m N/2N/2的对称的对称性性 W Wk+N/4k+N/4 N/2N/2=-W=-Wk k N/2N/2 最后得到：最后得到：用同样的方法可计算出用同样的方法可计算出其中其中 N N点点DFTDFT的第二次时域抽取分解图的第二次时域抽取分解图(N=8)(N=8)N N点点DITFFTDITFFT运算流图运算流图(N=8)(N=8)DITFFTDIT
7、FFT算法与直接计算算法与直接计算DFTDFT运算量的比较运算量的比较 复数加次数为复数加次数为 例如，例如，N=2N=21010=1024=1024时时 每一级运算都需要每一级运算都需要N/2N/2次复数乘和次复数乘和N N次复数加次复数加(每个蝶形每个蝶形需要两次复数加法需要两次复数加法)。所以，。所以，M M级运算总共需要的复数乘次级运算总共需要的复数乘次数为数为3.4 3.4 按频率抽取（按频率抽取（IDFTIDFT）的基）的基2FFT2FFT算法算法算法原理：把序列算法原理：把序列X X（k k）按奇偶分解为越来越短的序列。）按奇偶分解为越来越短的序列。为自然数为自然数 设设X X（
8、k k）序列的点数为）序列的点数为 在把输出序列按奇偶分组前，在把输出序列按奇偶分组前，先把序列先把序列x x（n n）按前一）按前一半后一半分开半后一半分开，把，把N N点点DFTDFT写成两部分：写成两部分：n=0,1,N/2-1n=0,1,N/2-1r=0,1,N/2-1r=0,1,N/2-1频率抽取法时域蝶形运算流图符号频率抽取法时域蝶形运算流图符号-1-1-1-1频率抽取法频域蝶形运算流图符号频率抽取法频域蝶形运算流图符号3.7 3.7 利用利用FFTFFT分析时域连续信号频谱分析时域连续信号频谱一、有限长序列的一、有限长序列的DFTDFT与序列的傅里叶变换与序列的傅里叶变换的关系的
9、关系二、利用二、利用FFTFFT分析时域连续信号频谱方法分析时域连续信号频谱方法三、分析过程中可能出现的误差三、分析过程中可能出现的误差频谱分析就是计算信号各个频率分量的幅频谱分析就是计算信号各个频率分量的幅值、相位和功率。值、相位和功率。有限长序列的有限长序列的DFTDFT和傅里叶变换的区别：和傅里叶变换的区别：（1 1）定义式不同）定义式不同长度为长度为N N的有限长序列的有限长序列x(nx(n)的的DFTDFT为为该序列的傅里叶变换为该序列的傅里叶变换为一、有限长序列的一、有限长序列的DFTDFT与序列的傅里叶变换的关系与序列的傅里叶变换的关系和和 的意义不同的意义不同（2 2）无单位，
10、只能取整数值，对于任意一点无单位，只能取整数值，对于任意一点 ，对应，对应的实际频率为的实际频率为为数字域频率，单位是为数字域频率，单位是rad，可连续取值。，可连续取值。有限长序列的有限长序列的DFTDFT和傅里叶变换的联系：和傅里叶变换的联系：T T为采样周期为采样周期f f为采样频率为采样频率离散的频率第离散的频率第k k点对应的模拟频率为点对应的模拟频率为离散频率、数字域频率以及模拟频率的联系：离散频率、数字域频率以及模拟频率的联系：N N为采样点数为采样点数二、利用二、利用FFTFFT分析时域连续信号频谱方法分析时域连续信号频谱方法1 1、基本步骤、基本步骤LPFLPFA/DA/DD
11、FTDFT低通滤波器，消低通滤波器，消除频谱混叠的影除频谱混叠的影响响窗函数，用于截窗函数，用于截取数据取数据谱线间距：又称频谱分辨率（单位：谱线间距：又称频谱分辨率（单位：HzHz），用），用F F表示，指表示，指可分辨的两频率的最小间距。可分辨的两频率的最小间距。样本长度：用样本长度：用t tp p表示，指截取的连续信号的长度。表示，指截取的连续信号的长度。由采样定理得：由采样定理得：实际中，根据信号的最高频率实际中，根据信号的最高频率f fh h和频谱分辨率和频谱分辨率F F的要求，确定的要求，确定T T、t tp p和和N N的大小。的大小。（1 1）T T的确定的确定由采样定理得：由
12、采样定理得：（2 2）由频谱分辨率）由频谱分辨率F F和和T T确定确定N N(3)(3)已知已知T T和和N N，即可确定样本长度，即可确定样本长度t tp p 。例例3-3 3-3 有一频谱分析用的有一频谱分析用的FFTFFT处理器，假定没有采用任何特殊处理器，假定没有采用任何特殊的数据处理措施，已给条件为：的数据处理措施，已给条件为：（1 1）频率分辨率小于等于）频率分辨率小于等于10Hz10Hz（2 2）信号最高频率小于）信号最高频率小于4kHz.4kHz.试确定以下参量：试确定以下参量：（1 1）求求t tp p；（2 2）最大采样间隔）最大采样间隔（3 3）在一个记录中的最少点数）
13、在一个记录中的最少点数N.N.三、三、可能出现的误差可能出现的误差1 1、频谱混叠失真、频谱混叠失真信号的最高频率信号的最高频率与频率分辨率矛与频率分辨率矛盾盾.解决办法：增加记录长度的点数解决办法：增加记录长度的点数N。2 2、栅栏效应、栅栏效应 利用利用FFTFFT计算频谱，只能在离散点上看到信号的频谱，这计算频谱，只能在离散点上看到信号的频谱，这就像是通过一个就像是通过一个“栅栏栅栏”观看信号的频谱，称之观看信号的频谱，称之“栅栏效应栅栏效应”。缺点：缺点：如果在两个离散的谱线间有一个特别大的频谱分量，如果在两个离散的谱线间有一个特别大的频谱分量，就无法检测出来。就无法检测出来。改变方法
14、：改变方法：增加频域采样点数增加频域采样点数N N。3 3、频谱泄漏与谱间干扰、频谱泄漏与谱间干扰 原信号在时域乘以一个窗函数后所得信号的频谱与原信原信号在时域乘以一个窗函数后所得信号的频谱与原信号的频谱不同，造成频谱号的频谱不同，造成频谱“扩散扩散”，这就是所谓的，这就是所谓的“频谱泄频谱泄漏漏”。后果：导致频谱混叠，降低频谱的分辨率，同时引起后果：导致频谱混叠，降低频谱的分辨率，同时引起不同频率间的干扰即谱间干扰。不同频率间的干扰即谱间干扰。解决方法：解决方法：（1）在计算量和存储量允许的情况下尽可能增加窗的时在计算量和存储量允许的情况下尽可能增加窗的时域宽度；域宽度；（2）不用矩形窗而采用缓变的窗。）不用矩形窗而采用缓变的窗。功率谱功率谱PSDPSD频谱图频谱图功率谱功率谱PSD:PSD:功率谱具有突出主频率的特性，在分析带有噪声干扰的功率谱具有突出主频率的特性，在分析带有噪声干扰的信号时特别有用。信号时特别有用。频谱图频谱图将将绘成图形称为频谱图。绘成图形称为频谱图。根据频谱图可以知道信号存在哪些频率分量。根据频谱图可以知道信号存在哪些频率分量。功率谱功率谱PSDPSD频谱图频谱图