程佩青《数字信号处理教程》(第4版)(名校考研真题详解 快速傅里叶变换(FFT))

第一章 离散时间信号与系统2.任意序列x(n)与δ(n)线性卷积都等于序列本身x(n)，与δ(n-n 0)卷积x(n- n 0),所以（1）结果为h(n) (3)结果h(n-2) （2（4）3 .已知 10,)1()(<<--=-a n u a n h n，通过直接计算卷积和的办法，试确定单位抽样响应为 )(n h 的线性移不变系统的阶跃响应。

4. 判断下列每个序列是否是周期性的,若是周期性的,试确定其周期：)6()( )( )n 313si n()( )()873cos()( )(ππππ-==-=n j e n x c A n x b n A n x a分析：序列为)cos()(0ψω+=n A n x 或)sin()(0ψω+=n A n x 时，不一定是周期序列，nmm m n n y n - - -∞ = - ⋅ = = ≥ ∑ 2 31 2 5 . 0 ) ( 01当 3 4n m nm m n n y n 2 2 5 . 0 ) ( 1⋅ = = - ≤ ∑ -∞ = - 当 aa a n y n a a an y n n h n x n y a n u a n h n u n x m m nnm mn -==->-==-≤=<<--==∑∑--∞=---∞=--1)(11)(1)(*)()(10,)1()()()(:1时当时当解①当=0/2ωπ整数，则周期为0/2ωπ；②；为为互素的整数）则周期、（有理数当 , 2 0Q Q P QP =ωπ ③当=0/2ωπ无理数 ，则)(n x 不是周期序列。

解：（1）0142/3πω=，周期为14 （2）062/13πω=，周期为6 （2）02/12πωπ=，不是周期的 7.（1）[][]12121212()()()()()()[()()]()()()()[()][()]T x n g n x n T ax n bx n g n ax n bx n g n ax n g n bx n aT x n bT x n =+=+=⨯+⨯=+所以是线性的T[x(n-m)]=g(n)x(n-m) y(n-m)=g(n-m)x(n-m) 两者不相等，所以是移变的y(n)=g(n)x(n) y 和x 括号内相等，所以是因果的。

2.3　名校考研真题详解1．已知某一序列为x （n ），它的傅里叶变换表示为（1）试画图举例说明序列x （2n ）与x （n ）的关系；（2）试求序列g （n ）＝x （2n ）的傅里叶变换，并说明与的关系。

[武汉理工大学2007研]解：（1）序列x（n ）与x （2n ）的关系图2-1如下：图2-1离散尺度变换只是去掉一些离散值。

（2）已知g（n ）＝x （2n ），设根据离散傅里叶变换的尺度变换性质得：其中F （n,2）又可写为：由上最终可得：2．已知x[k]的傅里叶变换，用表示信号)(Ωj e H )(Ωj e H的傅里叶变换。

[北京交通大学2006研]解：已知x[k]的傅里叶变换，且)(Ωj e H 根据已知所以对y[k]进行傅里叶变换得：3．线性时不变系统的输入为输出为。

（1）求系统的单位抽样响应；（2）判断系统的稳定性和因果性，并说明理由。

[华东理工大学2004研]解：（1）由Z 变换定义直接得：同理，y （n ）的Z 变换为：所以系统函数为：对H（z）求Z逆变换得对应抽样响应为：（2）由（1）知系统收敛域为3/4，包括单位圆和无穷远点，所以既是稳定的又是因果的。

4．若。

请借助线性卷积与Z变换的定义，证明：时域卷积对应子Z域乘积，即。

[南京邮电大学2000研]证明：由线性卷积与Z变换的定义知：即5．序列x（n）的自相关序列c（n）定义为试以x（n）的Z变换表示c（n）的Z变换。

[北京理工大学2007研]解：c（n）可以转化为：根据Z变换的对称性得：6．已知离散序列试求x（n）的Z变换X（z），确定其收敛域，并画出X（z）的零极点图。

[东南大学2007研]解：由Z变换定义可得：可能的零点为，其中；显然k＝0时的零点和极点相互抵消了，所以该Z变换在z＝0处有（N－1）阶极点，零点为：，其中，对应的收敛域为时的零极点图如下图2-2所示：图2-27．求的Z反变换。

[中国地质大学（北京）2006研]解：原式可化解为：由于收敛域，故：8．已知序列的双边Z变换为：解：根据由部分分式展开法，可得：可能对应以下序列：① 当收敛域为∣z∣＞0.5时：② 当收敛域为0.25＜∣z∣＜0.5时：③ 当收敛域为∣z∣＜0.25时：9．一个线性时不变因果系统由下列差分方程描述。

快速傅立叶变换FFT算法特点分析作者：徐美清孙晨亮来源：《科学与财富》2016年第28期摘要：快速傅立叶变换FFT是离散傅立叶变换DFT的一种快速算法，计算量小的显著的优点，使得FFT在现代数字信号处理与数据分析领域获得了广泛的应用。

但是在利用FFT算法对连续信号进行分析时，存在频谱混叠、栅栏效应及频谱泄露现象。

本文简单介绍了FFT算法，并对其存在的缺点进行了详细的分析。

关键词：傅立叶变换；频谱混叠；栅栏效应；频谱泄露1 FFT简介快速傅里叶变换（Fast Fourier Transform，简称为FFT）并不是一种新的变换，而是离散傅里叶变换（Discrete Fourier Transform，简称为DFT）的一种快速算法。

在相当长的时间里，由于DFT的计算量太大，即使采用计算机也很难对问题进行实时处理，所以并没有得到真正的运用。

直到1965年J.W.Cooley和J.W.Tukey首次提出了DFT运算的一种快速算法，后来又有G.Sande和J.W.Tukey的快速算法相继出现以后，情况才发生了根本的变化。

人们开始认识到DFT运算的一些内在规律，从而很快地发展和完善了一套高速有效的运算方法，这就是现在人们普遍称之为快速傅里叶变换FFT的算法。

2 FFT算法的优点FFT算法使DFT的运算大大简化，使其运算速度提高了1-2个数量级，从而使DFT的运算在实际中真正得到了广泛的应用。

3 FFT算法的缺点利用FFT对连续信号进行傅里叶分析时可能造成一定的误差，从而产生频谱混叠、频谱泄漏以及栅栏效应现象。

3.1 频谱混叠对连续信号进行采样时，通常假定所处理的信号是带限的。

假设连续信号的最高频率为fh，采样频率为fs，那么根据香农定理，为了不产生混叠现象，应该有如果不满足fs≥2fh，就会产生频谱的交叠，即频谱混叠，从而产生失真现象。

下面对频谱混叠现象进行举例说明，假定连续信号具有4个频率（5Hz，10Hz，50Hz，80Hz）分量，其采样点数为512个，采样频率fs为分别取50Hz和200Hz，用FFT对它进行频谱分析，其频谱图如下。

9.1　复习笔记一、用正整数D 的抽取——降低抽样率1. 从连续时域降低抽样率的分析由时域与频域的对应关系为利用序列的傅里叶变换与连续时间信号的傅里叶变换之间的关系式，可得图9-1表示了、和以及它们的频谱、、(t)a x (n)x (n)d x (j )a X ΩX(e )j T Ω以及用数字频率、表示的、，可以看出，抽样频率愈低，X (e )j T d 'Ωωω'X(e )j ωX (e )j d ω则周期延拓的各频谱分量靠得愈近。

图9-1 从模拟信号抽样的角度看序列的抽取2. 直接在序列域用正整数D 的抽取（1）抽取器的时域分析设x （n ）抽样率为f s ，则x d （n ）抽样率为f s ／D 。

把变成：将中每(n)x (n)d x(n)x 隔D －1个抽样点取出1个抽样点。

即实现这一过程的部件称为D 抽取器或抽样率压缩器，如图9-2所示。

图9-2 抽取器及其框图表示（2）抽取器的频域分析可表示成和一个脉冲串的相乘，即()p x n (n)x (n)p 频域间的关系为由于两序列乘积的傅里叶变换等于两序列各自的傅里叶变换的复卷积乘以，则有12 （3）通用抽取器在抽取器之前加上防混叠滤波器，防混叠滤波器的理想频率响应应满足图9-4 模拟信号、序列及抽取序列的频谱（D ＝２）二、用正整数I 的插值——提高抽样率每两个相邻抽样间插入（I －1）个抽样值的过程分为两步实现。

第一步是把两个相邻抽样值之间插入（I －1）个零值，第二步是用一个低通滤波器进行平滑插值，使这（I －1）个样点上经插值后出现相应的抽样值。

I 倍插值器系统如图9-3所示，图9-3 插值器系统的框图1．零值插入器零值插值器的输出为输出频谱为X (e )j I ω''图9-4画出了插值（I ＝3）全过程中的各信号及其频谱。

它不仅包含基带频谱，即之内的有用频谱，而且在的范围内还有基带信号的镜像，它们的中心频I ωπ'≤ωπ'≤率在，…处。

4.2　课后习题详解4-1 如果一台通用计算机的速度为平均每次复乘40ns ，每次复加5ns ，用它来计算512点的DFT[x （n ）]，问直接计算需要多少时问?用FFT 运算需要多少时间?若做128点快速卷积运算，问最低抽样频率应是多少?解：①直接利用DFT 计算：复乘次数为N 2，复加次数为N （N-1）。

②利用FFT计算：复乘次数为，复加次数为N㏒2N 。

（1）直接计算复乘所需时间复加所需时间所以（2）用FFT 计算复乘所需时间复加所需时间所以4-2 N ＝16时，画出基-2按频率抽选法的FFT 流图采用输入自然顺序，输出倒位序），统计所需乘法次数（乘±1，乘±j 都不计在内）。

根据任一种流图确定序列x （n ）＝4cos （n π／2）（0≤n ≤15）的DFT 。

解：按频率抽取法的FFT 流图中的复数乘法出现在减法之后，其运算量为复数乘法：；复数加法：；由于N ＝16，有，，，不需要乘法。

按频率抽取，见图4-1（a ）。

图4-1（a ）运算量：复数乘法：由于，，，不需要乘法。

由图P4.2（a ）可知，共有的个数为1＋2＋4＋8＝15有的个数为1＋2＋4＝7所以总的乘法次数为32-15-7＝10（个）复数加法：举例：对序列x （n ）＝4cos （n π／2）（0≤n ≤15）可表示为由于N ＝16，可采用P4.2（b ）的流图。

设Xi （k ）＝（i ＝1，2，3，4）分别为第i 级蝶形结构的输出序列，则由P4.2（b ）的流图可知由于采用的是顺序输入、逆序输出的结构，因此输出X （k ）与X 4（k ）为逆序关系，即，为k 二进制逆序值由此可知，x （n ）的DFT 为X （4）＝X 4（2）＝32，X （12）＝X 4（3）＝12图4-1（b ）4-3 用MATLAB 或C 语言编制以下几个子程序。

（1）蝶形结运算子程序；（2）求二进制倒位序子程序；（3）基-2 DIT FFT 流程图，即迭代次数计算子程序。

数字信号处理教程第四版（程佩青）第一章1 几种典型序列2 求序列的周期性3 线性，移不变，因果，稳定的判断方法4 线性卷积的计算5 抽样定理第三章第四章DIT-FFT 的运算量 直接DFT 的运算量 重叠相加法的步骤:重叠保存法的步骤：第五章IIR 滤波器的基本结构类型：直接型，级联型，并联型，转置型FIR 滤波器的基本结构类型：直接型，级联型，频率抽样型，快速卷积型第七章冲激响应不变法：优点：h(n)完全模仿模拟滤波器的单位抽样响应ha(t) 时域逼近良好 保持线性关系：ω=Ω*T线性相位模拟滤波器转变为线性相位数字滤波器 缺点：频率响应混迭只适用于限带的低通、带通滤波器1 脉冲响应不变法的映射是多值映射,导致频率响应交叠。

2 频率间关系：ω=Ω*T 从模拟到数字为线性变换3 存在混叠失真（ f >fs 2 时衰减越大，混叠越小）4 不能设计 高通 带阻5 特定频率处频率响应严格相等，可以较准确地控制截止频率位置双线性变换法：优点：避免了频率响应的混迭现象缺点：除了零频率附近Ω与ω之间严重非线性 1 S 平面到z 平面是单值映射关系（可以避免混叠失真） 2 频率间关系：)2tan(2wT=Ω 从模拟到数字为非线性变换3 频率预畸（为了克服临界频率点的非线性畸变）4 可以设计任何滤波器考点：设计巴特沃斯双线性滤波器第八章h(n)=h(N-1-n) N 为奇数关于0=w 、π、π2偶对称 （低通 高通 带通 带阻） h(n)=h(N-1-n) N 为偶数关于、偶对称 关于奇对称 （低通 带通）h(n)=-h(N-1-n) N 为奇数关于、、奇对称 （带通 微分器 希尔伯特） h(n)=-h(N-1-n) N 为偶数关于、奇对称 关于偶对称 （高通 带通 微分器 希尔伯特）窗函数法：要求：窗谱主瓣尽可能窄以获得较陡的过渡带尽量减少窗谱最大旁瓣的相对幅度以减小肩峰和波纹1 改变N 只能改变窗谱的主瓣宽度，但不能改变主瓣与旁瓣的相对比例。

第一章 离散时间信号与系统2.任意序列x(n)与δ(n)线性卷积都等于序列本身x(n)，与δ(n-n 0)卷积x(n- n 0),所以（1）结果为h(n) (3)结果h(n-2) （2（4）3 .已知 10,)1()(<<--=-a n u a n h n，通过直接计算卷积和的办法，试确定单位抽样响应为 )(n h 的线性移不变系统的阶跃响应。

4. 判断下列每个序列是否是周期性的,若是周期性的,试确定其周期：)6()( )( )n 313si n()( )()873cos()( )(ππππ-==-=n j e n x c A n x b n A n x a分析：序列为)cos()(0ψω+=n A n x 或)sin()(0ψω+=n A n x 时，不一定是周期序列，nmm m n n y n - - -∞ = - ⋅ = = ≥ ∑ 2 31 2 5 . 0 ) ( 01当 3 4n m nm m n n y n 2 2 5 . 0 ) ( 1⋅ = = - ≤ ∑ -∞ = - 当 aa a n y n a a an y n n h n x n y a n u a n h n u n x m m nnm mn -==->-==-≤=<<--==∑∑--∞=---∞=--1)(11)(1)(*)()(10,)1()()()(:1时当时当解①当=0/2ωπ整数，则周期为0/2ωπ；②；为为互素的整数）则周期、（有理数当 , 2 0Q Q P QP =ωπ ③当=0/2ωπ无理数 ，则)(n x 不是周期序列。

解：（1）0142/3πω=，周期为14 （2）062/13πω=，周期为6 （2）02/12πωπ=，不是周期的 7.（1）[][]12121212()()()()()()[()()]()()()()[()][()]T x n g n x n T ax n bx n g n ax n bx n g n ax n g n bx n aT x n bT x n =+=+=⨯+⨯=+所以是线性的T[x(n-m)]=g(n)x(n-m) y(n-m)=g(n-m)x(n-m) 两者不相等，所以是移变的y(n)=g(n)x(n) y 和x 括号内相等，所以是因果的。

6.3　名校考研真题详解1．已知一理想带通滤波器的幅频响应为：现要设计一个实系数线性相位的FIR 滤波器，使得：)(z H d （1）取N ＝9时，试写出得取值；)(2n mj d e H （2）求出N ＝9时h[k]的表示式，并判断是否满足线性相位条件；（3）画出该滤波线性相位直接型结构框图；（4）如所设计的滤波器阻带的最小衰减达不到指标，可采取何种方法增加阻带的最小衰减？[北京交通大学2002研]解：（1）当取N ＝9时，有：（2）求出N ＝9时h[k]的表示式为：由上式容易验证：所以这是一个I 型线性相位系统。

（3）对h[k]按定义求Z 变换得H （z ）为：由H （z ）各系数得出系统的直接型结构框图如下图6-1所示：图6-1（4）若所设计的滤波器阻带的最小衰减达不到指标，可采取在通带与阻带间增加过渡点的方法来提高阻带的最小衰减。

2．设为一时域离散线性相位低通滤波器的冲激响应，若另一滤波器()1h n ，该滤波器是否亦为低通滤波器？[北京理工大学2007研]()()21(1)n h n h n =-()2h n 解：的频率响应为：()1h n 又因为，所以有：()()21(1)nh n h n =-即：()2h n()1h n()1h n可以看出的频谱相对于平移了π；由于为低通滤波器，所以()2h n为高通滤波器。

3．一个线性非时变因果系统由下列差分方程描述试求该系统的系统函数H（z），画出零-极点图和收敛域，并说明该系统的滤波特性。

[武汉理工大学2007研]解：对差分方程描述两边取Z变换得：对上式变形可得系统函数为：由上式系统函数可以看出系统的零点是－1，极点是0.8，收敛域为：；零-极点图如图6-2所示：图6-2在H（z）中令可得：jz eω=分别讨论ω的不同取值如下：由上数据可以看出该滤波器是低通滤波器。

4．已知FIR传递函数为：试按如下结构构造此滤波器：（1）直联形式；（2）五个一阶单元的级联；（3）一个一阶单元和两个二阶单元的级联；（4）一个二阶单元和一个三阶单元的级联。

9.3　名校考研真题详解1．以20kHz 的采样率对最高频率为l0kHz 的带限信号采样，然后计算x（n ）的N ＝1000个采样点的DFT ，即：（1）求k ＝150对应的模拟频率是多少？k ＝800呢？（2）求频谱采样点之间的间隔为多少？[华南理工大学2007研]解：（1）根据数字频率与模拟频率的关系得：N 点的离散傅里叶变换DFT 是对离散信号的傅里叶变换DFT 在N 个频率点上的采样，即：所以，X （k ）对应的模拟频率为：所以，当N ＝1000时，序号k ＝150对应的模拟频率是f ＝3kHz 。

当k ＝800时，当N ＝1000时，，此时对应的模拟频率为：（2）由N 可得频谱采样点之间的间隔为：2．用DFT 对模拟信号进行谱分析，设模拟信号的最高频率为200Hz ，其频谱如图所示。

现以奈奎斯特频率采样得到时域离散序列，要求频率分辨率为10Hz 。

（1）求离散序列x （n ）的傅里叶变换，并画出其幅度频谱示意图；（2）求，并画出其谱线示意图；（3）求每个k值所对应的数字频率和模拟频率的取值，并在图中标出。

[中南大学2007研]解：（1）由题意知，最高频率，频率分辨率，所以采样频率为：所以：记录时间为：则采样点数为：对采样得：x （n）的傅里叶变换为：其幅度频谱示意图：（2）由（1）得：谱线示意图为：（3）的图示如下；由上分析可得：当时，对应的，由于得当时，对应的数字频率，与的对应关系为，其中。

3．已知连续时间信号为对该信号进行抽样，抽样频率为4kHz ，得到抽样序列x[n]，求x[nJ 的表达式。

[北京大学2005研]解：已知连续时间信号为：抽样频率后，直接令t ＝n ，代入x a （t ）得x （n ），即：s T4．利用数字系统处理模拟信号的框图如图所示，其中X （jw ）为连续信号x （t ）的频谱，是离散系统h[k]的频率响应。

当抽样间隔时，试画出信号x[k]、)(Ωj e H s T 401=y[k]、y （t ）的频谱。

9.2　课后习题详解9-1 图9-1所示系统输入为x （n ），输出为y（n ），零值插入系统在每一序列x （n ）值之间插入2个零值点，抽取系统定义为其中w（n ）是抽取系统的输入序列。

若输入试确定下列∞值时的输出y （n ）：图9-1解:（1）序列x （n ）的频谱为根据零值插入系统的性质，可知本题中I ＝3，由教程（9-3-4）式可知插值后序列x （n ）的频谱为当，此时输入序列频谱完全通过防混叠低通滤波器，因此有w （n ）的频谱为根据教程（9-2-22）式，可知输出序列对应的频谱为代入D ＝5和w （e jw）可得因此输 出序列y （n ）为（2）当w 1＞3/5π时，由（1）的解答过程可知，为由于通过截止频率叫w＝π/5的防混叠低通滤波器后频谱受到压缩，此时w （n）对应的频谱为根据教程（9-2-22）式，抽取后输出序列y （n ）对应的频谱为因此输出序列y （n ）为9-2 用两个离散时间系统T 1和T 2来实现理想低通滤波器（截止频率为π/4）。

系统T 1如图9-2（a ）所示，系统T 2如图9-2（b ）所示。

在此二图中，T A 表示一个零值插入系统，它在每一个输入样本之后插入一个零值点；T 表示一个抽取系统，它在每两个输入中取出一个。

问：（1）T1相当于所要求的理想低通滤波器吗?（2）T 2相当于所要求的理想低通滤波器吗?图9-2解:（1）对系统T 1，设输入序列x （n ）的频谱为（其中w ＞π/4）则经过T A 零插值系统后的输出信号频谱为这里I ＝2，所以有经过理想低通滤波器后信号频谱为再经过抽取系统T 后输出信号频谱为其中D ＝2，所以有对比输入输出信号的频谱，可知输出信号频谱被限制在w ＝π/4范围内，且幅度只相差一个常数，因此T 。

系统相当于所要求的理想低通滤波器。

（2）对T 系统，同样设输入x （n ）的频谱为其中w 0＞π/4。

则经过TB 抽取系统后的输出信号的频谱为这里D ＝2，所以有其中，当2w 0＜2π－2w 0，即w 0＜π/2时，无频谱混叠此时相当于所要求的理想低通。

第四章 快速傅立叶变换运算需要多少时间。

计算需要多少时间，用，问直拉点的，用它来计算每次复加速度为平均每次复乘需如果一台通用计算机的FFT DFT[x(n)]512s 5 s 50.1μμ 解: 解: ⑴ 直接计算:复乘所需时间: 复加所需时间:⑵用FFT 计算:复乘所需时间:复加所需时间:s N T N 01152.0 512log 105 log 105 2251262261=⨯⨯⨯=⨯⨯=--sT T T sN N T 013824.0 002304.0 512log 512105.0 log 105.0 2126262=+=∴=⨯⨯⨯=⨯⨯⨯=--sT T T sN N T 441536.1 130816.0 )1512(512105.0 )1(105.0 21662=+=∴=-⨯⨯⨯=-⨯⨯⨯=--s N T 31072.1 512105 105 26261=⨯⨯=⨯⨯=--运算一次完成。

点试用一个为了提高运算效率值求今需要从值的点实序列是两个已知IFFT N n y n x k Y k X DFT n y n x N k Y k X ,,)(),()(),(,)(),()(),(.2值的过程。

）（），（完成计算点）可用一次（）（）（综上所述，构造序列）（）（）（）（可得：）（）（）（再根据都是实序列，）（），（由原题可知：）（）（）（）（（）（）（性质：又根据可得序列点作对取序列依据题意解 ]Im[ ]Re[ ][][ ][ ).()( )()()( )()();()( ::n y n x IFFT N k jY k X k Z n z n y n z n x n jy n x n z n y n x n jy n x k Y jIDFT k X IDFT k jY k X IDFT DFT n z IFFT N k Z k jY k X k Z k Y n y k X n x +===+=+=+=++=⇔⇔。