第二章离散傅立叶变换与快速算法.ppt

第二章 离散傅里叶变换及其快速算法(8学时 ) 引言 2.1 离散傅里叶变换（DFT）2.2 快速傅里叶变换(FFT)2.3 FFT应用 引言： 离散傅里叶变换不仅具有明确的物理意义，更便于用计算机处理。但是，直至上个世纪六十年代，由于数字计算机的处理速度较低以及离散傅里叶变换的计算量较大，离散傅里叶变换长期得不到真正的应用，快速离散傅里叶变换算法的提出，才得以显现出离散傅里叶变换的强大功能，并被广泛地应用于各种数字信号处理系统中。近年来，计算机的处理速率有了惊人的发展，同时在数字信号处理领域出现了许多新的方法，但在许多应用中始终无法替代离散傅里叶变换及其快速算法。 2.1离散傅里叶变换（DFT） 1. DFT （Discrete Fourier Transform） 是重要的变换 1）分析有限长序列的有用工具。 2）在信号处理的理论上有重要意义。 3）在运算方法上起核心作用，谱分析、 卷积、相关都可以通DFT在计算机上 实现。 2. DFT是现代信号处理桥梁 DFT要解决两个问题： 一是离散与量化， 二是快速运算。 2.2.1周期序列及其离散傅里叶级数（DFS） 1.离散傅里叶级数 说明 DFS变换对公式表明，一个周期序列虽然是无穷长序列，但是只要知道它一个周期的内容（一个周期内信号的变化情况），其它的内容也就都知道了，所以这种无穷长序列实际上只有N个序列值的信息是有用的，因此周期序列与有限长序列有着本质的联系。 2.DFS的性质 1）线性 2）周期性 周期卷积与线性卷积的区别： 例周期延拓 6、DFT的性质 b)时域循环卷积过程： 1）补零 2）周期延拓 3）翻褶，取主值序列 4）循环移位 5）相乘相加 线性卷积与循环卷积步骤比较 循环卷积程序 x1 = [1,2,2]; x2 = [1,2,3,4]; y = circonvt(x1,x2,4) Stem(y) 线性卷积 function [y,ny]=conv_improve(x,nx,h,nh) %[x,nx]为第一个信号;%[h,nh]为第二个信号 %conv(x,h)可以实现两个有限长度序列的卷积 ny1=nx(1)+nh(1); ny2=nx(length(x))+nh(length(h)); ny=[ny1:ny2]; y=conv(x,h); 在命令窗口调用卷积函数。x=[3 4 0 -2 2 3 5]; nx=[-3:3]; h=[1 4 5 6 0 1]; nh=[N:N+5]; 例 2.2 利用DFT进行连续信号的频谱分析 1、混叠 2、泄漏 3、栏栅效应 4、DFT的分辨率 5、周期信号的谱分析 2.3 快速傅里叶变换 有限长序列通过离散傅里叶变换 (DFT)将其频 域离散化成有限长序列.但其计算量太大(与N的平方成正比）, 很难 实时地处理问题 , 因 此 引 出 了 快 速 傅 里 叶 变 换(FFT) . FFT 并 不 是 一 种 新 的 变 换 形 式 ,它 只 是 DFT 的 一 种 快 速 算 法 . 并 且 根 据 对 序 列 分 解 与 选 取 方 法 的 不 同 而 产 生 了 FFT 的 多 种 算 法 . FFT 在 离 散 傅 里 叶 反 变 换 、 线 性 卷 积 和 线 性 相 关 等 方 面 也 有 重 要 应 用。 5、 FFT的计算工作量 FFT算法对于N点DFT,仅需(N/2)log2N 次复数乘法运算和Nlog2N 次复数加法。 6. FFT算法分类： 1.按抽取方法分： 时间抽取法(DIT Decimation-In-Time); 频率抽取法(DIF Decimation-In-Frequency) 2.按“基数”分：基-2FFT算法；基-4FFT算法；混合基FFT算法；分裂基FFT算法 3.其它方法：线性调频Z变换(Chrip-z法) 2.3.1 按时间抽取的DFT 1、 的特性 2、DFT的基本思想 快速傅里叶变换( FFT ) 就是在此特性基础上发展起来的： （1）利用DFT系数的对称性和周期性,合并DFT运算中的某些项； （2）将长序列分解为短序列,从而减少其运算量。 ?? 因合并与分解方法的不同产生了多种DFT的快速算法。 2.3.1 时域抽取法基2FFT基本原理Decimation-in-Time(DIT) 1、时域抽取算法原理 设输入序列长度为N=2M(M为正整数，将该序列按时间顺序的奇偶分解为越来越短的子序列，称为基2按时间抽取的FFT算法。也称为Coolkey-Tukey算法。 其中基数2----N=2M，M为整数.若不满足这个条件，可以人为地加上若干