数字信号处理复习资料1.doc

2011.6.9 信春哥 ❤逢考必过❤ 不挂科 作者：娟鹏
数字信号处理复习资料
第一章 时域离散信号和时域离散系统
一、常用的典型序列
1． 单位采样序列δ(n)

单位采样序列也称为单位脉冲序列，特点是仅在n=0时取值为1，其它均为零。它类似于模拟信号和系统中的单位冲激函数δ(t)，但不同的是δ(t)在t=0时，取值无穷大，t≠0 时取值为零，对时间t的积分为1。单位采样序列和单位冲激信号如图1.2.2所示。

图1.2.2单位采样序列和单位冲激信号
(a)单位采样序列； (b)单位冲激信号
2． 单位阶跃序列u(n)

　单位阶跃序列如图1.2.3所示。它类似于模拟信号中的单位阶跃函数u(t)。δ(n)与u(n)之间的关系如下列式所示：

图1.2.3 单位阶跃序列
3． 矩形序列RN(n)

式中，N称为矩形序列的长度。当N=4时，R4(n)的波形如图1.2.4所示。矩形序列可用单位阶跃序列表示，如下式：

图1.2.4 矩形序列
*4． 实指数序列
　　　　　　　　x(n)=anu(n)　　a为实数
如果|a|<1, x(n)的幅度随n的增大而减小，称x(n)为收敛序列；如果|a|>1，则称为发散序列。其波形如图1.2.5所示。

图1.2.5 实指数序列
*5． 正弦序列

　　　　
式中, 　　称为正弦序列的数字域频率(也称数字频率)，单位是弧度(rad)，它表示序列变化的速率，或者说表示相邻两个序列值之间变化的弧度数。
*6． 复指数序列
　　复指数序列用下式表示:

式中, ω0为数字域频率。
二、线性时不变系统的判断（计算题）
1、线性系统
　　系统的输入、输出之间满足线性叠加原理的系统称为线性系统。设x1(n)和x2(n)分别作为系统的输入序列，其输出分别用y1(n)和y2(n)表示，即

那么线性系统一定满足下面两个公式：
可加性
比例性或齐次性
式中a是常数。将以上两个公式结合起来，可表示成 下式中a和b均是常数

【例1.3.1】　证明y(n)=ax(n)+b(a和b是常数）所代表的系统是非线性系统。
　　证明

因此，该系统不是线性系统。用同样方法可以证明
　　　　　　　　　　　所代表的系统是线性系统。

2、时不变系统
　　如果系统对输入信号的运算关系T［·］在整个运算过程中不随时间变化，或者说系统对于输入信号的响应与信号加于系统的时间无关，则这种系统称为时不变系统，用公式表示如下：
式中n0为任意整数

【例1.3.2】　检查y(n)=ax(n)+b所代表的系统是否是时不变系统，式中a和b是常数。
　　解

因此该系统是时不变系统。
【例1.3.3】　检查y(n)=nx(n)所代表的系统是否是时不变系统。
　　解

因此该系统不是时不变系统。此例从物理概念上可以理解成该系统是一个放大器，其放大量是n，它随n变化，因此是一
个时变系统。依同样方法可以证明
所代表的系统也是时变系统。
三、线性时不变系统具备因果性的充要条件
如果系统n时刻的输出只取决于n时刻以及n时刻以前的输入序列，而和n时刻以后的输入序列无关，则称该系统具有因果性质，或称该系统为因果系统。如果n时刻的输出还取决于n时刻以后的输入序列，在时间上违背了因果性，系统无法实现，则系统被称为非因果系统。因此系统的因果性是指系统的可实现性。
　　线性时不变系统具有因果性的充分必要条件是系统的单位脉冲响应满足下式：

满足式的序列称为因果序列，因此因果系统的单位脉冲响应必然是因果序列。因果系统条件式从概念上也容易理解，因为单位脉冲响应是输入为δ(n)的零状态响应，在n=0时刻以前即n<0时，没有加入信号，输出只能等于零，因此得到因果性条件式。
例题
只要N≥1， 该系统就是因果系统， 因为输出只与n时刻的和n时刻以前的输入有关。
该系统是非因果系统， 因为n时间的输出还和n时间以后（（n+1）时间）的输入有关。
假设n0>0， 系统是非因果的， 因为输出还和x(n)的将来值有关。
四、序列周期的计算
例：判断下面的序列是否是周期的; 若是周期的，确定其周期。
(1)

(2) 公式： T=2π/ω

解： （1） 因为ω=　　π, 所以　　　　　, 这是有理数， 因此是周期序列， 周期T=14。
（2） 因为ω=　　, 所以　　　=16π, 这是无理数， 因此是非周期序列。

第二章 时域离散信号和系统的频域分析
一、
1.时域离散信号的傅里叶变换（实序列）（计算题）
序列x(n)的傅里叶变换定义为

FT[x(n)]存在的充分必要条件是序列x(n)满足绝对可和的条件，即满足下式：

X(ejω)的傅里叶反变换为
【例2.2.1】　设x(n)=RN(n)，求x(n)的傅里叶变换。
　　解

2.周期序列的傅里叶变换表示式
在模拟系统中， ， 其傅里叶变换是在Ω=Ωo处的单位冲激函数， 强度是2π， 即

对于时域离散系统中， x(n)=ejw0n， 2p /w0为有理数， 暂时假定其FT的形式与(2.3.8)式一样， 即是在w=w0处的单位冲激函数， 强度为2p ，但由于n取整数， 下式成立
为整数
因此 的FT为
(2.3.9)
式表示复指数序列的FT是在ω0+2πr处的单位冲激函数，强度为2π

表2.3.2　基本序列的傅里叶变换

【例2.3.3】　令　　　　　　　　　 为有理数，求其FT。
　　解　将　　 用欧拉公式展开：


按照（2.3.9）式，其FT推导如下：

式表明，cosω0n的FT是在ω=±ω0处的单位冲激函数，强度为π，且以2π为周期进行延拓，
二、序列福利也不会的性质及定理
*1． FT的周期性
在定义（2.2.1）式中，n取整数，因此下式成立： Ｍ为整数

观察上式，得到傅里叶变换是频率ω的周期函数，周期是2π。
*2． 线性
　　设X1(ejω)=FT[x1(n)], X2(ejω)=FT[x2(n)], 那么
式中, a，b是常数。
3．时移与频移
　　设X(ejω)=FT[x(n)], 那么
时移

频移
4． FT的对称性
　　在学习FT的对称性以前，先介绍什么是共轭对称与共轭反对称，以及它的性质。
　　设序列xe(n)满足下式： ①
则称xe(n)为共轭对称序列。为研究共轭对称序列具有什么性质，将xe(n)用其实部与虚部表示：
将上式两边n用－n代替，并取共轭，得到：

对比上面两公式，因左边相等，因此得到：

上面两式表明共轭对称序列其实部是偶函数，而虚部是奇函数。类似地，可定义满足下式的共轭反对称序列：
将xo(n)表示成实部与虚部，如下式：
可以得到：

即共轭反对称序列的实部是奇函数，而虚部是偶函数。
【例2.2.2】　试分析x(n)=ejωn的对称性。
　　解　因为
x*(－n)=ejωn=x(n)
满足式①，所以x(n)是共轭对称序列，如展成实部与虚部，则得到：
x(n)=cosωn+j sinωn
上式表明，共轭对称序列的实部确实是偶函数，虚部是奇函数。
一般序列可用共轭对称与共轭反对称序列之和表示，即
式中，xe(n)和xo(n)可以分别用原序列x(n)求出，将上式中的n用－n代替，再取共轭, 得到：
可得：

利用上面两式，可以用x(n)分别求出xe(n)和xo(n)。
　　对于频域函数X(ejω)，也有和上面类似的概念和结论：
　　　　　　　　X(ejω)=Xe(ejω)+Xo(ejω) （2.2.19）
式中，Xe(ejω)与Xo(ejω)分别称为共轭对称部分和共轭反对称部分，它们满足：

即

有了上面的概念和结论，下面研究FT的对称性。
　 (1) 将序列x(n)分成实部xr(n)与虚部xi(n)，即
x(n)=xr(n)+jxi(n)
将上式进行傅里叶变换，得到:
式中

上面两式中，xr(n)和xi(n)都是实数序列。容易证明：Xe(ejω)满足（2.2.20）式，具有共轭对称性，它的实部是偶函数，虚部是奇函数；Xo(ejω) 满足（2.2.21）式，具有共轭反对称性质，它的实部是奇函数，虚部是偶函数。
最后得到结论：序列分成实部与虚部两部分，实部对应的傅里叶变换具有共轭对称性，虚部和j一起对应的傅里叶变换具有共轭反对称性。
(2) 将序列分成共轭对称部分xe(n)和共轭反对称部分xo(n)，即
　　　　　　　　　x(n)=xe(n)+xo(n)
将上式重写如下：

将上面两式分别进行傅里叶变换，得到：



因此x(n)=xe(n)+xo(n)式的FT为

式表示：序列x(n)的共轭对称部分xe(n)对应着X(ejω)的实部XR(ejω)，而序列x(n)的共轭反对称部分xo(n)对应着X(ejω)的虚部(包括j)。
【例2.2.3】　x(n)=anu(n), 0<a<1。求其偶函数xe(n)和奇函数xo(n)。
　　解　x(n)=xe(n)+xo(n)
　　按式，得到：

*5． 时域卷积定理
　　设 y(n)=x(n)*h(n)
则
Y(ejω)=X(ejω)H(ejω)
*6． 频域卷积定理
　　设y(n)=x(n)h(n) 
则

*7． 帕斯维尔（Parseval）定理

表：序列傅里叶变换的性质定理

三、序列的Z变换及逆Z变换（留数法）
1. 序列的Z变换
在时域离散信号和系统中，用序列的傅里叶变换进行频域分析，Z变换则是其推广，用以对序列进行复频域分析。
序列x(n)的Z变换定义为

　　　　　　　　　　　　　　 （2.5.1）

式中z是一个复变量，它所在的复平面称为z平面。注意在定义中，对n求和是在－∞、＋∞之间求和，可以称为双边Z变换。还有一种称为单边Z变换的定义，如下式：

　　　　　　　　　　　　　　　　　　 （2.5.2）

这种单边Z变换的求和限是从零到无限大，因此对于因果序列，用两种Z变换定义计算的结果是一样的。本书中如不另外说明，均用双边Z变换对信号进行分析和变换。
　　（2.5.1）式Z变换存在的条件是等号右边级数收敛，要求级数绝对可和，即

　　　　　　　　　　　　　 （2.5.3）

使（2.5.3）式成立，Z变量取值的域称为收敛域。一般收敛域为环状域，即
图2.5.1　变换的收敛域
令z=rejω，代入上式得到Rx－<r<Rx＋，收敛域是分别以Rx＋和Rx－为收敛半径的两个圆形成的环状域(如图 2.5.1 中所示的斜线部分)。 当然，Rx－可以小到零，Rx＋可以大到无穷大。收敛域的示意图如图2.5.1所示。

常用的Z变换是一个有理函数，用两个多项式之比表示：

分子多项式P(z)的根是X(z)的零点，分母多项式Q(z)的根是X(z)的极点。在极点处Z变换不存在，因此收敛域中没有极点，收敛域总是用极点限定其边界。 
【例2.5.1】　x(n)=u(n), 求其Z变换。
　　解　


X(z)存在的条件是|z－1|<1，因此收敛域为|z|>1, 因此
X(z)表达式表明，极点是z=1，单位圆上的Z变换不存在，或者说收敛域不包含单位圆，该例同时说明一个序列的傅里叶变换不存在，但在一定收敛域内Z变换是可以存在的。
2.逆Z变换
已知序列的Z变换X(z)及其收敛域，求原序列x(n)的过程称为求逆Z变换。计算逆Z变换的方法有留数法、部分分式展开法和幂级数法（长除法）。下面仅介绍留数法和部分分式展开法，重点放在留数法。
1）． 用留数定理求逆Z变换
　　序列的Z变换及其逆Z变换表示如下：

式中, c是X(z)收敛域中一条包围原点的逆时针的闭合曲线，如图2.5.3所示。求逆Z变换时，直接计算围线积分是比较麻烦的，用留数定理求则很容易。为了表示简单，用F(z)表示被积函数：F(z)=X(z)zn－1。
图2.5.3　围线积分路径
如果F(z)在围线c内的极点用zk表示，则根据留数定理有
 （2.5.6）
式中, Res[F(z), zk]表示被积函数F(z)在极点z=zk的留数，逆Z变换是围线c内所有的极点留数之和。
如果zk是单阶极点，则根据留数定理有
　　如果zk是N阶极点，则根据留数定理有

　　　　　　　　　　　　　　　　　　　　　 （2.5.8）

（2.5.8）式表明，对于N阶极点，需要求N－1次导数，这是比较麻烦的。如果c内有多阶极点，而c外没有多阶极点，则可以根据留数辅助定理改求c外的所有极点留数之和，使问题简单化。
　　如果F(z)在z平面上有N个极点，在收敛域内的封闭曲线c将z平面上的极点分成两部分：一部分c是内极点，设有N1个极点，用z1k表示；另一部分是c外极点，有N2个，用z2k表示。N=N1+N2。根据留数辅助定理，下式成立：

（2.5.9）
注意：（2.5.9）式成立的条件是F(z)的分母阶次应比分子阶次高二阶以上。设X(z)=P(z)/Q(z), P(z)和Q(z)分别是M与N阶多项式。（2.5.9）式成立的条件是: N-M-n+1≥2
因此要求 n<N-M （2.5.10）
如果（2.5.10）式满足，c圆内极点中有多阶极点，而c圆外没有多阶极点，则逆Z变换的计算可以按照（2.5.9）式，改求c圆外极点留数之和，最后加一个负号。
　　【例2.5.7】　已知　　　　　　　　　　　 　, 求其逆变换x(n)。

例2.5.7中X(z)的极点
解　该例题没有给定收敛域，为求出唯一的原序列x(n)，必须先确定收敛域。分析X(z)， 得到其极点分布如图2.5.5所示。图中有两个极点：z=a和z=a-1，这样收敛域有三种选法，它们是
　　（1） |z|>|a-1|，对应的x(n)是因果序列；
　　（2） |z|<|a|，对应的x(n)是左序列；
　　（3） |a|<|z|<|a-1|，对应的x(n)是双边序列。
图2.5.5　下面分别按照不同的收敛域求其x(n)。
　　（1） 收敛域为|z|>|a-1|:



这种情况的原序列是因果的右序列，无须求n<0时的x(n)。当n≥0时，F(z)在c内有两个极点：z=a和z=a－1，因此

最后表示成：x(n)=(an-a-n)u(n)。
　　（2） 收敛域为|z|<|a|:
　　这种情况原序列是左序列，无须计算n≥0情况。实际上，当n≥0时，围线积分c内没有极点，因此x(n)=0。n<0时，c内只有一个极点z=0，且是n阶极点，改求c外极点留数之和。
　　n<0时,

最后将x(n)表示成封闭式：
x(n)=(a-n-an)u(-n-1)　　
　　（3） 收敛域为|a|<|z|<|a-1|:
　　这种情况对应的x(n)是双边序列。根据被积函数F(z)，按n≥0和n<0两种情况分别求x(n)。n≥0时，c内只有1个极点：z=a, x(n)=Res[F(z), a]=an
　　n<0时，c内极点有2个，其中z=0是n阶极点，改求c外极点留数，c外极点只有z=a-1， 因此
x(n)=-Res[F(z), a-1]=a-n
　　最后将x(n)表示为


表2.5.1　常见序列的Z变换
即 x(n)=a|n|

四、序列特性对收敛域的影响
　　序列的特性决定其Z变换收敛域，了解序列特性与收敛域的一般关系，对使用Z变换是很有帮助的。
　　1． 有限长序列
　　如序列x(n)满足下式：

即序列x(n)从n1到n2的序列值不全为零，此范围之外序列值为零，这样的序列称为有限长序列。其Z变换为

　　设x(n)为有界序列，由于是有限项求和，除0与∞两点是否收敛与n1、n2取值情况有关外，整个z平面均收敛。如果n1<0，则收敛域不包括∞点；如果n2>0，则收敛域不包括z=0点；如果是因果序列，收敛域包括z=∞点。具体有限长序列的收敛域表示如下：
　　n1<0, n2≤0时，0≤|z|<∞
　　n1<0, n2>0时，0<|z|<∞
　　n1≥0, n2>0时，0<|z|≤∞
【例2.5.2】　求x(n)=RN(n)的Z变换及其收敛域。
　　解
 
这是一个因果的有限长序列，因此收敛域为0<z≤∞。但由结果的分母可以看出，似乎z=1是X(z)的极点，但同时分子多项式在z=1时也有一个零点，极、零点对消，X(z)在单位圆上仍存在，求RN(n)的傅里叶变换，可将z=ejω代入X(z)得到，其结果和例题2.2.1中的结果（2.2.5）式是相同的。
2． 右序列
　　右序列是指在n≥n1时，序列值不全为零，而在n<n1时，序列值全为零的序列。 右序列的Z变换表示为


第一项为有限长序列，设n1≤-1，其收敛域为0≤|z|<∞。第二项为因果序列，其收敛域为Rx-<|z|≤∞，Rx-是第二项最小的收敛半径。将两收敛域相与，其收敛域为Rx-<|z|<∞。如果是因果序列，收敛域为Rx-<|z|≤∞。
【例2.5.3】　求x(n)=anu(n)的Z变换及其收敛域。　
解　
 
　　在收敛域中必须满足|az-1|<1，因此收敛域为|z|>|a|。
3． 左序列
　　左序列是指在n≤n2时，序列值不全为零，而在n>n2时，序列值全为零的序列。左序列的Z变换表示为


　　如果n2<0, z=0点收敛，z=∞点不收敛，其收敛域是在某一圆（半径为Rx+）的圆内，收敛域为0≤|z|<Rx+。如果n2≥0，则收敛域为0<|z|<Rx+。
【例2.5.4】　求x(n)=－anu(－n－1)的Z变换及其收敛域。
　　解　这里x(n)是一个左序列，当n≥0时，x(n)=0，
X(z)存在要求|a-1z|＜1，即收敛域为|z|＜|a|, 因此
4． 双边序列
　　一个双边序列可以看做是一个左序列和一个右序列之和，其Z变换表示为



X(z)的收敛域是X1(z)和X2(z)收敛域的交集。如果Rx+>Rx－，则其收敛域为Rx－<|z|<Rx+，是一个环状域；如果Rx+<Rx－，两个收敛域没有交集，X(z)则没有收敛域，因此X(z)不存在。
【例2.5.5】　x(n)=a|n|, a为实数，求x(n)的Z变换及其收敛域。
　　解　

第一部分收敛域为|az|<1，得|z|<|a|－1; 第二部分收敛域为|az－1|<1, 得到|z|>|a|。如果|a|<1, 两部分的公共收敛域为|a|<|z|<|a|－1, 其Z变换如下式:


图2.5.2　例2.5.5图
　如果|a|≥1，则无公共收敛域，因此X(z)不存在。当0<a<1时，x(n)的波形及X(z)的收敛域如图2.5.2所示。

同一个Z变换函数表达式，收敛域不同，对应的序列是不相同的。所以，X(z)的函数表达式及其收敛域是一个不可分离的整体，求Z变换就包括求其收敛域。
此外，收敛域中无极点，收敛域总是以极点为界的
第三章 离散傅里叶变换（DFT）
一、用DFT计算序列的线性卷积
用DFT计算循环卷积很简单。设h(n)和x(n)的长度分别为N和M, 其L点循环卷积为

且

则由DFT的时域循环卷积定理有


由此可见，循环卷积既可以在时域直接计算，也可以按照图3.4.1所示的计算框图在频域计算。由于DFT有快速算法，当L很大时，在频域计算循环卷积的速度快得多，因而常用DFT(FFT)计算循环卷积。
图3.4.1 用DFT计算循环卷积的原理框图

yc(n)等于yl(n)以L为周期的周期延拓序列的主值序列。
循环卷积等于线性卷积的条件是L≥N＋M－1
图3.4.2 线性卷积与循环卷积波形图

图3.4.2中画出了h(n)、x(n)、h(n)*x(n)以及L分别取6、8、10时h(n) L x(n)的波形。由于h(n)长度N=4，x(n)长度M=5，N＋M－1=8，因此只有L≥8时，h(n) L x(n)波形才与h(n)*x(n)相同。
二、DFT的应用
1.用DFT对连续信号进行谱分析
工程实际中，经常遇到连续信号xa(t)，其频谱函数Xa(jΩ)也是连续函数。为了利用DFT对xa(t)进行频谱分析，先对xa(t)进行时域采样，得到x(n)=xa(nT)，再对x(n)进行DFT，得到的X(k)则是x(n)的傅里叶变换X(ejω)在频率区间[0，2π]上的N点等间隔采样。这里x(n)和X(k)均为有限长序列。
然而，由傅里叶变换理论知道，若信号持续时间有限长，则其频谱无限宽；若信号的频谱有限宽，则其持续时间必然为无限长。所以严格地讲，持续时间有限的带限信号是不存在的。因此，按采样定理采样时，上述两种情况下的采样序列x(n)=xa(nT)均应为无限长，不满足DFT的变换条件。实际上对频谱很宽的信号，为防止时域采样后产生频谱混叠失真，可用预滤波器滤除幅度较小的高频成分，使连续信号的带宽小于折叠频率。
　　对于持续时间很长的信号，采样点数太多, 以致无法存储和计算，只好截取有限点进行DFT。由上述可见，用DFT对连续信号进行频谱分析必然是近似的，其近似程度与信号带宽、采样频率和截取长度有关。实际上从工程角度看，滤除幅度很小的高频成分和截去幅度很小的部分时间信号是允许的。因此，在下面分析中，假设xa(t)是经过预滤波和截取处理的有限长带限信号。
设连续信号xa(t)持续时间为Tp，最高频率为fc，如图3.4.6(a)所示。xa(t)的傅里叶变换为

对xa(t)以采样间隔T≤(2fc)-1(即fs=1/T≥2fc)采样得 x(n)=xa(nT)。设共采样N点，并对Xa(jf )作零阶近似(t=nT, dt=T) 得

显然， Xa( if )仍是 f 的连续周期函数，x(n)和X( jf )如图3.4.5(b)所示。 对 X(jf )在区间[0, Fs]上等间隔采样N点， 采样间隔为F， 如图3.4.5(c)所示。 参数Fs 、 Tp、 N和F满足如下关系式：

由于NT=Tp， 所以
将f=kF和式(3.4.5)代入X( jf )中可得Xa( jf )的采样
令
则

同理, 由

可以推出

图3.4.6 用DFT分析连续信号谱的原理示意图

　　所以，上述分析方法不丢失信息，即可由X(k)恢复Xa(jΩ)或xa(t)，但直接由分析结果X(k)看不到Xa(jΩ)的全部频谱特性，而只能看到N个离散采样点的谱线，这就是所谓的栅栏效应。对实信号，其频谱函数具有共轭对称性，所以分析正频率频谱就足够了。不存在频谱混叠失真时，正频率[0, Fs/2]频谱采样为
（3.4.12）
值得注意，如果xa(t)持续时间无限长，上述分析中要进行截断处理，所以会产生所谓的截断效应，从而使谱分析产生误差
【例 3.4.2】 对实信号进行谱分析，要求谱分辨率F≤10 Hz，信号最高频率fc=2.5 kHz， 试确定最小记录时间Tp min，最大的采样间隔Tmax，最少的采样点数Nmin。如果fc不变，要求谱分辨率提高1倍，最少的采样点数和最小的记录时间是多少？
　　解　

因此Tp min=0.1 s。因为要求Fs≥2fc，所以

　　为使用DFT的快速算法FFT，希望N符合2的整数幂，为此选用N =512点。为使频率分辨率提高1倍，即F=5 Hz，要求：



用快速算法FFT计算时，选用N=1024点。
　上面分析了为提高谱分辨率，又保持谱分析范围不变，必须增长记录时间Tp，增加采样点数。应当注意，这种提高谱分辨率的条件是必须满足时域采样定理，甚至采样速率Fs取得更高。
第四章 快速傅里叶变换（FFT）
一、FFT的定义及内涵（与FT及Z变换的关系）
1.直接计算DFT的特点及减少运算量的基本途径
　　 有限长序列x(n)的N点DFT为

　　　　　　　　　　　　　　　　　 (4.2.1)

考虑x(n)为复数序列的一般情况，对某一个k值，直接按(4.2.1)式计算X(k)的1个值需要N次复数乘法和(N-1)次复数加法。因此，计算X(k)的所有N个值，共需N2次复数乘法和N(N-1)次复数加法运算。
　　当　　　时，N(N-1)≈N2。由上述可见，N点DFT的乘法和加法运算次数均为N2。当N较大时，运算量相当可观。例如N=1024时，N2=1 048 576。这对于实时信号处理来说，必将对处理设备的计算速度提出难以实现的要求。所以，必须减少其运算量，才能使DFT在各种科学和工程计算中得到应用。　
　　如前所述，N点DFT的复乘次数等于N2。显然，把N点DFT分解为几个较短的DFT，可使乘法次数大大减少。另外，旋转因子具有明显的周期性和对称性。其周期性表现为

　　　　　　　　　　　　　　　 　　（4.2.2）

其对称性表现为 或者
FFT算法就是不断地把长序列的DFT分解成几个短序列的DFT，并利用　　的周期性和对称性来减少DFT的运算次数。算法最简单最常用的是基2FFT。
二、DIT-FFT的计算效率
1. DIT-FFT算法与直接计算DFT运算量的比较
　　由DIT-FFT算法的分解过程及图4.2.4可见，N=2M 时，其运算流图应有M级蝶形，每一级都由N/2个蝶形运算构成。因此，每一级运算都需要N/2次复数乘和N次复数加(每个蝶形需要两次复数加法)。所以，M级运算总共需要的复数乘次数为

复数加次数为
而直接计算DFT的复数乘为N2次，复数加为N(N－1)次。当N>>1时，N2>> (N/2) lbN，所以，DIT-FFT算法比直接计算DFT的运算次数大大减少。例如，N=210=1024时，



这样，就使运算效率提高200多倍。图4.2.5为FFT算法和直接计算DFT所需复数乘法次数CM与变换点数N的关系曲线。由此图更加直观地看出FFT算法的优越性，显然，N越大时，优越性就越明显。

三、基于2DIT-FFT，顺序输出与顺序输入之间的关系
这种经过M次偶奇抽选后的排序称为序列x(n)的倒序(倒位)。
DIT-FFT算法的输入序列的排序看起来似乎很乱，但仔细分析就会发现这种倒序是很有规律的。由于N=2M，因此顺序数可用M位二进制数(nM-1nM-2…n1n0)表示。M次偶奇时域抽选过程如图4.2.7所示。
　　第一次按最低位n0的0和1将x(n)分解为偶奇两组，第二次又按次低位n1的0、1值分别对偶奇组分组；依次类推，第M次按nM-1位分解，最后所得二进制倒序数如图4.2.7所示。

图4.2.7 形成例序的树状图（N=23）
　　 表4.2.1列出了N=8时以二进制数表示的顺序数和倒序数，由表显而易见，只要将顺序数(n2n1n0)的二进制位倒置，则得对应的二进制倒序值(n0n1n2)。按这一规律，用硬件电路和汇编语言程序产生倒序数很容易。但用有些高级语言程序实现时，直接倒置二进制数位是不行的，因此必须找出产生倒序数的十进制运算规律。
　　由表4.2.1可见，自然顺序数I增加1，是在顺序数的二进制数最低位加1，逢2向高位进位。而倒序数则是在M位二进制数最高位加1，逢2向低位进位。
表4.2.1 顺序和倒序二进制数对照表
例如，在(000)最高位加1，则得（100），而(100)最高位为1，所以最高位加1要向次高位进位，其实质是将最高位变为0，再在次高位加1，得到(010)。用这种算法，可以从当前任一倒序值求得下一个倒序值。
　　为了叙述方便，用J表示当前倒序数的十进制数值。对于N=2M，M位二进制数最高位的十进制权值为N/2，且从左向右二进制位的权值依次为N/4，N/8，…，2，1。因此，最高位加1相当于十进制运算J+N/2。如果最高位是0(J<N/2)，则直接由J+N/2得下一个倒序值；如最高位是1(J≥N/2), 则先将最高位变成0(J　J－N/2)，然后次高位加1(J+N/4)。但次高位加1时，同样要判断0、1值，如果为0(J<N/4)，则直接加1(JJ+N/4)， 否则将次高位变成0(JJ－N/4)，再判断下一位；依此类推，直到完成最高位加1，逢2向右进位的运算。图4.2.9所示的倒序的程序框图中的虚线框内就是完成计算倒序值的运算流程图。
　　形成倒序J后，将原数组A中存放的输入序列重新按倒序排列。设原输入序列x(I)先按自然顺序存入数组A中。例如，对N=8，A(0)，A(1)，…，A(7)中依次存放着x(0)，x(1)，x(2)，…，x(7)。对x(n)的重新排序(倒序)规律如图4.2.8所示。倒序的程序框图如图4.2.9所示。
由图4.2.8可见，第一个序列值x(0)和最后一个序列值x(N-1)不需要重排， 每计算出一个倒序值J，便与循环语句自动生成的顺序I比较，当I=J时，不需要交换，当I≠J时, A(I)与A(J)交换数据。 另外，为了避免再次调换前面已调换过的一对数据，框图中只对I<J的情况调换A(I)和A(J)的内容。

图4.2.8 倒序规律

第五章、时域离散系统的网络结构
一、无限长脉冲响应基本的网络结构的形式（直接、并联、级联）IIR
IIR网络的基本网络结构有三种，即直接型、级联型和并联型。
　　1． 直接型
　　将N阶差分方程重写如下：

对应的系统函数为



　　设M=N=2，按照差分方程可以直接画出网络结构如图5.3.1(a)所示。图中第一部分系统函数用H1(z)表示，第二部分用H2(z)表示，那么H(z)=H1(z)·Hz(z)，当然也可以写成H(z)=H2(z)·H1(z), 按照该式，相当于将图5.3.1(a)中两部分流图交换位置，如图5.3.1(b)所示。该图中节点变量w1=w2，因此前后两部分的延时支路可以合并，形成如图5.3.1(c)所示的网络结构流图，我们将图5.3.1(c)所示的这类流图称为IIR直接型网络结构。

图5.3.1 IIR网络直接型结构
M=N=2时的系统函数为


对照图5.3.1(c)的各支路的增益系数与H(z)分母分子多项式的系数可见，可以直接按照H(z)画出直接型结构流图。
【例5.3.1】 设IIR数字滤波器的系统函数H(z)为


画出该滤波器的直接型结构。
　　解 由H(z)写出差分方程如下：

按照差分方程画出如图5.3.2所示的直接型网络结构。

图5.3.2 例5.3.1图
2． 级联型
　　在(5.1.2)式表示的系统函数H(z)中，分子、分母均为多项式，且多项式的系数一般为实数。现将分子、分母多项式分别进行因式分解，得到：
　　　　　　　　　　　　　　　　　　　　（5.3.1）


式中, A是常数; Cr和dr分别表示H(z)的零点和极点。由于多项式的系数是实数，Cr和dr是实数或者是共轭成对的复数，将共轭成对的零点（极点）放在一起，形成一个二阶多项式，其系数仍为实数；再将分子、分母均为实系数的二阶多项式放在一起，形成一个二阶网络Hj(z)。
Hj(z)如下式： （5.3.2）

式中，β0j、β1j、β2j、α1j和α2j均为实数。这样H(z)就分解成一些一阶或二阶的子系统函数的相乘形式：
　　　　　　　　　　　　　　　　　　　（5.3.3）
式中Ｈi(z)表示一个一阶或二阶的数字网络的子系统函数，每个Hi(z)的网络结构均采用前面介绍的直接型网络结构，如图5.3.3所示，H(z)则由k个子系统级联构成。


(a) 直接型一阶网络结构