武汉科技大学_信号与系统习题精解 第5章.doc

第5章 离散傅里叶变换和快速傅里叶变换5.1 学习要点1. 离散傅里叶变换（DFT）的定义有限长序列的N点离散傅里叶变换的定义为： (5-1)离散傅里叶逆变换（IDFT）的定义为： (5-2)2. DFT的物理意义以看作序列的Z变换在Z平面单位圆上的N点等间隔采样值。 (5-3)也可以看作序列的傅里叶变换在区间0, 2上的N点等间隔采样。 (5-4)3. DFT的基本性质表5-1列出了DFT的一些基本性质，表中所有序列长度以及DFT变换区间长度均为N。表5-1 DFT的基本性质序号序 列离散傅里叶变换备 注12、为任意常数3对称定理4时间反转定理5时域循环移位定理6频域循环移位定理7时域循环卷积定理8频域循环卷积定理910111213144. 频域采样定理如果序列长度为，则只有当频域采样点数时，才能由频域采样恢复出和，否则产生时域混叠失真，无法由得到。5. 快速傅里叶变换（FFT）（1）算法FFT算法的基本思想就是将长序列的DFT分解成几组短序列的DFT，并且利用权函数的对称性和周期性减少运算量。（2）按时间抽取的基2 FFT算法在将长序列的DFT分解时都是有规律地按输入序列在时域上的偶、奇次序来抽取。8点FFT时间抽取算法运算流图如图5-1所示。图5-1 8点FFT时间抽取算法运算流图在FFT运算流图中每一级里的基本运算单元是蝶形运算如图5-2所示。图5-2 第m级蝶形运算 蝶形运算的基本关系式为： (5-5)按时间抽取的基2 FFT算法特点：蝶形运算互为独立单元，同一个存贮单元可以实现就地存贮输入、输出数据，即同址运算；序列的DFT输出如果按自然顺序排列，则输入的数据就必须是倒位序。点按时间抽取的基2 FFT算法运算量为： 复数乘法数： (5-6) 复数加法数： (5-7)直接计算DFT与按时间抽取的基2 FFT算法计算量之比为： (5-8)（3）按频率抽取的基2 FFT算法每一级的处理都是在频域里把序列分解为奇与偶的形式来进行计算。8点FFT频率抽取算法运算流图如图5-3所示。 图5-3 8点FFT频率抽取算法运算流图按频率抽取的基2 FFT算法蝶形运算关系复数乘法出现于减法运算之后，这是与按时间抽取的基2 FFT算法的不同之处。（4）快速傅里叶反变换（IDFT）与DFT的差别仅在于：权函数与的指数仅差一个负号；相差一个比例因子。则IDFT可表示为： (5-9)可以用FFT算法来计算IDFT。6. FFT的应用举例（1）利用FFT计算线性卷积用FFT计算线性卷积的方法：1）对长度分别为、的有限长序列、作补零延长序列处理，分别补、个零值，其中，并以L为周期进行周期延拓；2）作与的L点FFT与；3）求得；4）求得的L点IFFT，即；5）此时，。用分段卷积计算长序列卷积是一种有效的计算手段，可分为重叠相加法和重叠保留法。用FFT法实现重叠相加法的步骤：1) 计算的N点FFT， ；2) 计算的N点FFT，；3) 将和相乘，；4) 计算的N点IFFT，；5) 将各段（包括重叠部分）相加。（2）利用FFT对信号进行谱分析连续信号的频谱特性可以通过对连续信号采样并进行DFT，再乘以T的近似方法得到。根据DFT的物理意义，如果有限长序列的长度为M，则该序列的N（MN）点DFT就是其频率函数在频率区间0，2上的N点等间隔采样。所以离散信号的频谱特性可以通过DFT得到。5.2 精选例题例5.1 若为纯虚序列，分解为实部与虚部写作。试证明是的奇函数，是的偶函数。解：由于是纯虚序列，故可表示为,为实序列。根据定义式其中故是的奇函数。而故是的偶函数。例5.2 设为一有限长序列，当和时，且N等于偶数。已知，试利用来表示以下各序列的DFT：(1) ；(2) ；(3) ；(4) ；(5) ；(6) ；(7) 。解：(1)(2)(3)(4)(5)(6)(7)例5.3 已知是实序列，其8点DFT的前5点值为：0.25，0.125j0.3，0，0.125j0.06，0.5，试求：（1）8点DFT的后3点值；（2）如果，求出的8点DFT值。解：（1）因为是实序列，则其DFT只具有共轭对称分量，其8点DFT的后3点值分别为：0.125+j0.06，0和0.125+j0.3 (2) 根据DFT的循环移位定理得的8点DFT值为：0.25，0.3+j0.125，0，-0.06-j0.125，0.5，-0.06+j0.125，0，0.3-j0.125。例5.4 有限长序列的N点离散傅里叶变换相当于其Z变换在单位圆上的N点等间隔采样。希望求出在半径为r的圆上的N点等间隔采样，即试给出一种用DFT计算得到的方法。解：因为 所以即先对乘以指数序列，然后再进行N点DFT即可得到题中所要求的复频域采样。例5.5 画出N=16的FFT按时间抽取算法运算流图，输入序列按码位倒置顺序排列，输出为自然顺序排列。解：输入序列按码位倒置顺序排列应为自然顺序码位倒置顺序自然顺序码位倒置顺序00811899241053121113421235101311661477141515运算流图如图5-4所示。图5-4 16点FFT时间抽取算法运算流图例5.6 如果一台通用计算机计算一次复数乘法需要100，计算一次复数加法需要20，现在用它来计算N=1024点的DFT，问直接计算DFT和用FFT计算DFT各需要多少时间？ 解：直接计算DFT：复数乘法：次，复数加法：次，总计需要时间：用FFT计算DFT：复数乘法：次，复数加法：次，总计需要时间：例5.7 已知和是两个实序列，和分别是和的N点DFT，为提高运算效率，试设计用一次N点FFT来得到和。解：（1） 构成复数序列（2） 对进行DFT，得到（3） 由DFT的共轭对称性得到（4） 所以例5.8 设有一谱分析用的信号处理器，假定没有采用任何特殊的数据处理措施，要求频率分辨率10Hz，如果采用的时间采样间隔为0.1ms，试确定：（1） 最小记录长度；（2） 所允许处理的信号最高频率；（3） 在一个记录中的最少点数；（4） 在频带宽度不变的情况下，将频率分辨率提高一倍的最少采样点数。解：（1）最小记录长度：； （2）所允许处理的信号最高频率； （3）在一个记录中的最少点数； （4）在频带宽度不变的情况下，将频率分辨率提高一倍的最少采样点数。5.3 习题精解1. 计算以下诸序列的N点DFT，在变换区间内,序列定义为（1）（2）（3）（4）（5）解：（1）（2）（3）（4）因为所以（5）时， 时，所以，即2. 已知下列，求。（1）（2）其中，m为正整数，N为变换区间长度。解：（1） （2） 3. 长度为N=10的两个有限长序列 作图表示、和。循环卷积区间长度L=10。解：、和分别如题3解图（a）、（b）、（c）所示。题3解图4证明DFT的对称定理，即假设证明证明： 因为所以 由于 所以 5如果，证明DFT的初值定理证明： 由IDFT定义式可知当时6设长度N，且，令 ，r为正整数，求与的关系式。解： 令 ，则因为 所以7已知长度为N， 求与的关系。解： 8已知是N点的有限长序列，现将的每两点之间补进r-1个零值点，得到一个rN点的有限长序列试求的rN点与的关系。解：由DFT的定义得 所以9设,是长为N的有限长序列，证明（1） 如果（2）当N为偶数时，如果，则证明： （1）证明： （2）10两个有限长序列和的零值区间为对每个序列作20点DFT，即如果试问在哪些点上，为什么？解：记，而。长度为27，长度为20，二者的关系为只有在如上周期延拓序列中无混叠的点上，才满足所以11设（1）求的4点DFT。（2）若是与的4点循环卷积，求及其4点DFT。解：（1）（2）由上式得到12如果是一个周期为N的周期序列，则它也是周期为2N的周期序列，把看作周期为N的周期序列，其DFT为，再把看作周期为2N的周期序列，其DFT为，试利用确定。解：由DFT的定义得 令，则把用代换，把用代换，得 所以 13两个长为的矩形序列，分别作线形卷积和L=8点的循环卷积。问循环卷积的结果中哪些序列值与线形卷积的结果相同,并说明理由。 解：题13解图所示的是两个长为N=5的矩形序列进行线性卷积和L=8 点的循环卷积的示意图。可以看出，由于循环卷积的点数（L=8）比线性卷积的长度2N-1=9少1点，因此在移位为0时，循环卷积有混叠现象，而在移位为1以后，循环卷积的混叠现象消失。所以，移位为1至7的循环卷积的值与线性卷积的值相同。题13解图14已知序列，对的Z变换在单位圆上等间隔采样N点，采样值为求有限长序列。解：由于 是以2为周期的周期函数，所以以N为周期，将看作一周期序列的DFS系数，则代入由于 所以 由题意知 所以根据有关与的周期延拓序列的DFS系数的关系有由于，所以因此 15已知复序列。其中和是实序列。序列的Z变换在单位圆的下半部的值为零。求的离散傅里叶变换后一半的值，并说明理由。解：设N为偶数，的后一半是指所对应的的值。由于，其中， 所以也对应于在单位圆下半部等间隔点上的取样值，因此的后一半的值全为零。16用微处理机对实数序列作谱分析，要求谱分辨率，信号最高频率为1kHZ，试确定以下各参数：（1）最小记录时间；（2）最大采样间隔；（3）最少采样点数；（4）在频带宽度不变的情况下，将频率分辨率提高一倍的N值。解：（1）已知，（2）（3）（4）频带宽度不变就意味着采样间隔T不变，应该使记录时间扩大一倍为0.04s实现频率分辨率提高一倍（F变为原来的1/2）17用微处理机对实数序列作谱分析,要求谱分辨率，信号最高频率为，试确定以下各参数：（1）最小记录时间；（2）最大采样间隔；（3）最少采样点数；（4）在频带宽度不变的情况下，将频率分辨率提高一倍的N值。解：（1）因此（2）因为要求所以（3）（4）在频带宽度不变的情况下，将频率分辨率提高一倍，即18希望利用长度为N=50的FIR滤波器对一段很长的数据序列进行滤波处理，要求采用重叠保留法通过DFT来实现。所谓重叠保留法，就是对输入序列进行分段（本题设每段长度为M=100个采样点），但相邻两段必须重叠V个点，然后计算各段与的L点（本题取L=128）循环卷积，得到输出序列，m表示第m段计算输出。最后，从中取出个，使每段取出的个采样点连接得到滤波输出。（1）求V；（2）求B；（3）确定取出的B个采样应为中的哪些采样点。解：为了便于叙述，规定循环卷积的输出序列的序列标号为0，1，2，,127。先以与各段输入的线性卷积考虑，中，第0点到48点（共49个点）不正确，不能作为滤波输出，第49点到第99点（共51个点）为正确的滤波输出序列的一段，即B=51。所以，为了去除前面49个不正确点，取出51个正确的点连续得到不间断又无多余点的，必须重叠100-51=49个点，即V=49。下面说明，对128点的循环卷积，上述结果也是正确的。我们知道因为长度为N+M-1=50+100-1=149所以从n=20到127区域， ，当然，第49点到第99点二者亦相等，所以，所取出的第51点为从第49到99点的。综上所述，总结所得结论V=49，B=51选取中第4999点作为滤波输出。19如果通用计算机的速度为平均每次复数乘法需要5，每次复数加法需要1，用来计算N=1024点DFT，问直接计算需要多少时间。用FFT计算呢？照这样计算，用FFT进行快速卷积对信号进行处理时，估算可实现实时处理的信号最高频率。解：当时，直接计算DFT的复数运算次数为次复数加法计算次数为次直接计算所用计算时间为用FFT计算1024点DFT所需计算时间为快速卷积时，要计算一次N点FFT（考虑到已计算好存入内存），一次N点IFFT和N次频率复数乘法。所以，计算1024点快速卷积的计算时间约为所以，每秒钟处理的采样点数（即采样频率）/秒。由采样定理知，可实时处理的信号最高频率为应当说明，实际实现时，还要你小一些。这是由于采样频率高于奈奎斯特速率，而且在采用重叠相加法时，重叠部分还要计算两次。重叠部分长度与长度有关，而且还有存取数据指令周期等。20已知和是两个N点实序列和的DFT，若要从和求和，为提高运算效率，试设计用一次N点IFFT来完成。解：因为和均为实序列，所以，和为共轭对称序列，j为共轭反对称序列。可令和j分别作为复序列的共轭对称分量和共轭反对称分量，即计算一次N点IFFT得到由DFT的共轭对称性可知，故21设是长度为2N的有限长实序列，为的2N点DFT。（1）试设计用一次N点FFT完成计算的高效算法。（2）若已知，试设计用一次N点IFFT实现求的2N点IDFT运算。解：（1）在时域分别抽取偶书点和奇数点得到两个N点实序列和：根据DIT-FFT的思