第03章 离散傅氏变换DFT及其快速算法FFT《数字信号处理》程配清版课件

1、第三章 离散傅氏变换DFT及其快速算法FFT有时序列是有限时宽的，在这种特殊情况下可以导出另一种傅氏表示式，称作离散傅氏变换DFT(Discret Fourier Transform)。DFT在理论上有重要意义，利用DFT的快速算法FFT，可以在实现各种数字信号处理的算法中起到核心作用。3.1 问题的提出3.2 DFS与DFT导出3.3 DFS与DFT的性质3.4 z变换与DFS的关系3.5 快速傅氏变换算法FFT3.6 时间抽选法FFT3.7 频率抽选法 FFT3.8 基4FFT算法3.9 提高FFT运算效率的一些方法3.10 IDFT的快速算法IFFT3.11 Chirpz变换CZT算法3

2、.12 用DFT求线性卷积3.13 利用FFT进行频谱分析3.1 问题的提出本章所讨论的DFT就是在xa(t)为有限时宽时解决这一问题的方法。3.2 DFS与DFT导出设一连续信号 xa(t)是有限时宽的，其傅氏变换是限带的(根据信号理论，假设信号在时域内受限，即它被乘以矩形窗函数，那么在频域内将是无限的，反之亦然，因此，必须要限带)，如图3-1(a)所示，它们之间的傅氏变换关系为式(3-1)。图3-1 在时域或频域中对某一函数抽样，抽样函数在另一域中的映射2. DFS的分析以上定性分析了推导DFS与DFT的过程，现在进行定量分析。如果在时域内取样，取样周期为T，那么频域周期延拓，可用傅氏级数

3、来描述为傅氏级数的系数xa(nT)正是 xa(t)的取样函数，可写成3. DFT的导出DFT的条件对时域取样与频域取样间隔或取样率的要求，是实现DFT的条件，即其中，s 是时域取样频率；l是频域取样间隔。3.3 DFS与DFT的性质1. DFS的性质(1) 线性(2) 序列的移位(3) 对称性(4) 周期卷积2. DFT的性质(1) 线性关系如果有两个有限时宽序列x1(n)和x2(n)的线性组合，为x3(n)=ax1(n)+bx2(n)那么x3(n)的DFT为X3(k)=aX1(k)+bX2(k)式中a、b为任意常数(2) 序列的循环移位(3) 对称性因此，有必要对xe(n)和xo(n)的定义

4、根据DFT的特点进行修改，给出一种新的定义，即周期共轭对称分量和周期共轭反对称分量xep(n)和xop(n)。3.4 z变换与DFS的关系1.z变换在单位圆上的取样令x(n)是周期序列x(n)的一个周期，即z变换的内插表示设有一非周期有限长序列x(n)，其只在0nN-1范围内有值，其余皆为零。那么x(n)的z变换为3.5 快速傅氏变换算法FFTFFT是Fast Fourier Transform的缩写，换句话说，FFT是实现 DFT(Discret Fourier Transform)的一种快速运算手段。FFT算法可分为时间抽选法和频率抽选法。3.6 时间抽选法FFT时间抽选法，就是在时域内逐

5、次将序列分解成奇数子序列和偶数子序列，通过求子序列的DFT而实现整个序列的DFT，将计算DFT的运算量从N2复乘减少到(N2)log2N次复乘。1.根本原理设输入信号的列向量x(n)x(0)，x(1)，x(N-1)T，其DFT为X(k)X(0)，X(1)，X(N-1)T。将集合x(n)分解为两个交错集合，一个由偶数点组成，另一个由奇数点组成。采用如此分解方法，集合X(k)的前N2个元素可写成图3-6 8点DFT 分解为两个4 点DFT图3-7(a) 4点DFT分解为两个2点DF图3-7(b) 2点DFT信号流图图3-8 8点FFT 信号流图图3-9 FFT根本蝶形图设共有复数乘法Mc次，那么M

6、c=N/2log2N/2对于复数加法，每次迭代有N次复数相加，共有log2N次迭代含有复数相加，设复数相加的总数为Ac，那么Ac=Nlog2N4. Matlab的实现3.7 频率抽选法 FFT1.根本原理 频率抽选法就是在频域内将X(k)逐次分解成偶数点子序列和奇数点子序列，然后对这些分解得越来越短的子序列进行DFT运算，就可得整个频域内序列的FFT流图。 X(k)集合的元素也可分解成两个交错的子集，一个是偶数点序列，另一个是奇数点序列。偶数点序列可用两个矩阵乘积来表示，即2.信号流图偶数序列和奇数序列的X(k)可由TN/2方阵如图3-10所示那样得到。图3-10 分解TN为两个TN/2的根本

7、蝶形图图3-12频率抽选法N=8的FFT运算流图3.8 基4FFT算法与以前讲过的比较，基2和基4的加法次数算法相同，与基2相比基4算法的复乘数可以节约25%。经过分析可以得出基8比基4的复乘数相差不远，节约有限。3.9 提高FFT运算效率的一些方法在同时要进行两个长度相同的实序列的快速傅里叶变换时，可以用复序列的变换运算，一次求两个实序列的变换，从而节约了运算量。假设有两个长度相同的实序列h(n)和g(n)。可以把它们组合成一个复序列y(n)，即y(n)=h(n)+jg(n)3.8节已经介绍了基4 FFT的算法，它比基2 FFT算法可节约25%以上的运算量。基8或更高基的FFT运算，节约运算

8、量有限。但基数越大，相应的算法会越趋复杂，因此较少采用。3.10 IDFT的快速算法IFFT1. IFFT算法设有序列x(n)，其DFT为X(k)，那么IDFT为对于IFFT算法，输入是X(k)，输出是x(n)。在FFT的时间抽选法中得到了式(3-52)，即图3-15 N4IFFT的信号流图FFT的程序求IFFT的方法对DFT正变换式取共轭为再取一次共轭为得到利用FFT程序求IFFT的方法为(l) 将X(k)取共轭得X*(k)；(2) 将X*(k)进行FFT运算(用FFT程序)；(3) 对FFT的结果取共轭，并除以N得x(n)。3.11 Chirpz变换CZT算法1.Chirpz变换的推导Ch

9、irpz变换即线性调频z变换，为了帮助理解线性调频z变换这一概念我们先讨论一下连续系统的情况。设有一连续系统，如图3-16所示。图3-16 连续CZT系统模型如果信号S(t)和h(t)都是线性调频信号，它们的瞬时频率以相反的变化率变化，输入为f(t)Chirpz变换的步骤由图3-18所示可以列出进行Chirpz变换(CZT)的几个步骤。图3-18 离散CZT模型(l) 选择一个序列长度为LNM1，这个L是求离散卷积下出现重叠所需要的变换长度。选L为2的整数幂，以便进行FFT运算。(2) 构成一个L点序列y(n)为3计算yn的L点DFT，可利用FFT算法求得Y(v)。4定义一个L点序列h(n)为

10、3.Matlab实现4. Chirpz变换的特点(2) 与FFT运算比较这种Chirpz变换与标准的FFT算法相比有以下特点。(1) 输入与输出序列的长度不需要相等，即不需要MN。(2) N与M不必是2的整数幂，即两者都为合数或素数也可以。(3) zk点的间隔不必均匀相等，这样可以得到任意的分辨率。3.12 用DFT求线性卷积1.问题的提出在实际问题中遇到的大多数是求解线性卷积。例如图3-20所示的系统，输入信号是x(n)，系统的单位取样响应是 h(n)，输出信号是y(n)，那么它们的关系为图3-20 离散系统的模型设长度都为N的两个有限长序列x1(n)和x2(n)，它们的DFT分别为X1(K

11、)和X2(k), 如果有一序列x3(n)的DFT为X3(K)为那么X3(k) 的IDFT为下边讨论求循环卷积的方法。(1) 同心圆法将x1(n)与x2(n)分布在两个同心圆上： 用两个同心圆表示序列，如图3-21所示。外圆按逆时针方向刻度x2(n)的值，内圆按顺时针方向刻度x1(n)的值，两圆对应的数两两相乘后求和得x3(0)； 将x2(n)顺时针方向移一位，重复(a)得x3(1)； 依次类推得x3(n)，0nN1。图3-21 用同心圆作图求循环卷积(2) 波形作图法(3) 解析式法(4) Matlab实现当符合式(3-85)的条件时，利用循环卷积可以实现线性卷积。这是一个很重要的结果，这是因

12、为存在如下定理假设那么式中y(n)=x(n)*h(n)。5.重叠相加法重叠相加法是将待过滤的信号分割成长为N1的几段，每一段都可以和有限时宽单位取样响应作卷积，再将过滤后的各段重叠相加。6.重叠保存法重叠保存法相当于将xk(n)和h(n)作循环卷积，然后找出循环卷积中相当于线性卷积的局部。在这种情况下，将波形x(n)分为长为N的几段，每个输入段和前一段有M1个重叠点，将xk(n)定义为xk(n)=xn+k(N-M+1)0nN-1式中定义每一段的时间原点在该段的开始点而不是x(n)的原点。3.13 利用FFT进行频谱分析在本节我们简要地讨论对于一个有限长、限带信号x(t)，如何利用FFT算法求它的振幅频谱、相位频谱和功率谱。在第三章中较详细地讨论了对xa(t)在时域和频域同时取样可以得到DFS关系。进行频谱分析的步骤如下所示。(1) 准备数据进行FFT运算首先要求序列的长度N=2L。对x(n)取L，使得