第3章离散傅里叶变换

第3章离散傅里叶变换(DFT)3.1离散傅里叶变换的定义及物理意义3.2离散傅里叶变换的基本性质3.3频率域采样3.4DFT的应用举例习题与上机题傅里叶变换和Z变换是数字信号处理中常用的重要数学变换。对于有限长序列，还有一种更为重要的数学变换，即本章要讨论的离散傅里叶变换(DiscreteFourierTransform，DFT)。DFT之所以更为重要，是因为其实质是有限长序列傅里叶变换的有限点离散采样，从而实现了频域离散化，使数字信号处理可以在频域采用数值运算的方法进行，这样就大大增加了数字信号处理的灵活性。更重要的是，DFT有多种快速算法，统称为快速傅里叶变换(FastFourierTransform，FFT)，从而使信号的实时处理和设备的简化得以实现。因此，时域离散系统的研究与应用在许多方面取代了传统的连续时间系统。所以说，DFT不仅在理论上有重要意义，而且在各种信号的处理中亦起着核心作用。本章主要讨论DFT的定义、物理意义、基本性质以及频域采样和DFT的应用举例等内容。3.1离散傅里叶变换的定义及物理意义3.1.1DFT的定义设x(n)是一个长度为M的有限长序列，则定义x(n)的N点离散傅里叶变换为

(3.1.1)

X(k)的离散傅里叶逆变换(InverseDiscreteFourierTransform,IDFT)为式中，

，N称为DFT变换区间长度。通常称(3.1.1)式和(3.1.2)式为离散傅里叶变换对。为了叙述简洁，常常用DFT［x(n)］N和IDFT［X(k)］N分别表示N点离散傅里叶变换和N点离散傅里叶逆变换。下面证明IDFT［X(k)］的唯一性。(3.1.2)

把(3.1.1)式代入(3.1.2)式，有由于所以，在变换区间上满足下式：IDFT［X(k)］=x(n)0≤n≤N－1由此可见，(3.1.2)式定义的离散傅里叶逆变换是唯一的。

例3.1.1已知序列x(n)=δ(n)，求它的N点DFT。

解单位脉冲序列的DFT很容易由DFT的定义式（2-30）得到：

k=0,1,…,N-1

δ(n)的X(k)如图2-9。这是一个很特殊的例子，它表明对序列δ(n)来说，不论对它进行多少点的DFT，所得结果都是一个离散矩形序列。图2-9序列δ(n)及其离散傅里叶变换

例3.1.2

已知x(n)=cos(nπ/6)是一个长度N=12的有限长序列，求它的N点DFT。

解由DFT的定义式（2-30）利用复正弦序列的正交特性（2-3）式，再考虑到k的取值区间，可得图2-10有限长序列及其DFT［例3.1.3

］已知如下X(k):k=01≤k≤9求其10点IDFT。解X(k)可以表示为X(k)=1+2δ(k)0≤k≤9写成这种形式后，就可以很容易确定离散傅里叶反变换。由于一个单位脉冲序列的DFT为常数：同样，一个常数的DFT是一个单位脉冲序列：x2(n)=1X2(k)=DFT［x2(n)］=Nδ(k)所以

3.1.2DFT与傅里叶变换和Z变换的关系设序列x(n)的长度为M，其Z变换和N(N≥M)点DFT分别为比较上面二式可得关系式

(3.1.3)或(3.1.4)X(k)也可以看作序列x(n)的傅里叶变换X(ejω)在区间［0,2π］上的N点等间隔采样，其采样间隔为ωN=2π/N，这就是DFT的物理意义。显而易见，DFT的变换区间长度N不同，表示对X(ejω)在区间［0,2π］上的采样间隔和采样点数不同，所以DFT的变换结果也不同。

X(ejω)在区间［0,2π］上的N点等间隔采样。这就是DFT的物理意义。由此可见，DFT的变换区间长度N不同，表示对X(ejω)在区间［0,2π］上的采样间隔和采样点数不同，所以DFT的变换结果不同。上例中，x(n)=R4(n)，DFT变换区间长度N分别取8、16时，X(ejω)和X(k)的幅频特性曲线图如图3.1.1所示。由此容易得到x(n)=R4(n)的4点DFT为X(k)=DFT［x(n)］4=4δ(k)，这一特殊的结果在下面将得到进一步解释。图3-1DFT与序列傅里叶变换、Z变换的关系3.1.3DFT的隐含周期性前面定义的DFT变换对中，x(n)与X(k)均为有限长序列，但由于

的周期性，使(3.1.1)和(3.1.2)式中的X(k)隐含周期性，且周期均为N。对任意整数m，总有所以(3.1.1)式中，X（k)满足：(3.1.5)(3.1.6)上述关系如图3.1.2（a）和（b）所示。一般称周期序列中从n=0到N－1的第一个周期为的主值区间，而主值区间上的序列称为的主值序列。因此x(n)与的上述关系可叙述为：是x(n)的周期延拓序列，x(n)是的主值序列。实际上，任何周期为N的周期序列都可以看做长度为N的有限长序列x(n)的周期延拓序列，而x(n)则是的一个周期，即为了以后叙述简洁，当N大于等于序列x(n)的长度时，将(3.1.5)式用如下形式表示：

(3.1.7)式中x((n))N表示x(n)以N为周期的周期延拓序列，((n))N表示模N对n求余，即如果n=MN+n10≤n1≤N－1,M为整数则((n))N=n1

例如，

,则有所得结果符合图3.1.2（a）和（b）所示的周期延拓规律。

图3.1.2x(n)及其周期延拓序列应当说明，若x(n)实际长度为M，延拓周期为N，则当N<M时，(3.1.5)式仍表示以N为周期的周期序列，但(3.1.6)和(3.1.7)式仅对N≥M时成立。图3.1.2（a）中x(n)实际长度M=6，当延拓周期N=4时，如图3.1.2（c）所示。如果x(n)的长度为M，且，N≥M，则可写出的离散傅里叶级数表示式(3.1.8)(3.1.9)式中即X(k)为的主值序列。将(3.1.8)和(3.1.9)式与DFT的定义(3.1.1)和(3.1.2)式相比较可知，有限长序列x(n)的N点离散傅里叶变换X(k)正好是x(n)的周期延拓序列x((n))N的离散傅里叶级数系数的主值序列，即。后面要讨论的频域采样理论将会加深对这一关系的理解。我们知道，周期延拓序列频谱完全由其离散傅里叶级数系数确定，因此，X(k)实质上是x(n)的周期延拓序列x((n))N的频谱特性，这就是N点DFT的第二种物理解释（物理意义）。(3.1.10)例3.1.4

有限长序列x(n)为0≤n≤4其余n

求其N=5点离散傅里叶变换X(k)。

解序列x(n)如图2-12（a）所示。在确定DFT时，我们可以将x(n)看作是一个长度N≥5的任意有限长序列。首先我们以N=5为周期将x(n)延拓成周期序列，如图2-12（b），的DFS与x(n)的DFT相对应。因为在图2-12（b）中的序列在区间0≤n≤N-1上为常数值，所以可以得出k=0,±N,±2N,…其他(2-35)也就是说，只有在k=0和k=N

的整数倍处才有非零的DFS系数 值。这些DFS系数如图2-12（c）所示。为了说明傅里叶级数 与x(n)的频谱X(ejω)间的关系，在图2-12（c）中也画出了傅里叶变换的幅值|X（ejω)|。显然，就是X(ejω)在频率ωk=2πk/N

处的样本序列。按照式（2-29），x(n)的DFT对应于取 的一个周期而得到的有限长序列X(k)。这样，x(n)的5点DFT如图2-12（d）所示。

k=0,1,2,3,4

k=0

k=0,1,2,3,4图3-3DFT的举例说明（a）有限长序列x(n);（b）由x(n)形成的周期N=10的周期序列x(n);（c）DFT的幅值~图3-2DFT的举例说明（a）有限长序列x(n);（b）由x(n)形成的周期N=5的周期序列;（c）对应于 的傅里叶级数 和x(n)的傅里叶变换的幅度特性|X(ejω)|;（d）x(n)的DFTX(k)

【例3.1.2】设x(n)=R4(n)，X(ejω)=FT［x(n)］。分别计算X(ejω)在频率区间［0，2π］上的16点和32点等间隔采样，并绘制X(ejω)采样的幅频特性图和相频特性图。

解由DFT与傅里叶变换的关系知道，X(ejω)在频率区间［0，2π］上的16点和32点等间隔采样，分别是x(n)的16点和32点DFT。调用fft函数求解本例的程序ep312.m如下:

%例3.1.2程序ep312.m

%DFT的MATLB计算

xn=［1111］;%输入时域序列向量xn=R4(n)

Xk16=fft(xn,16);%计算xn的16点DFT

Xk32=fft(xn,32);%计算xn的32点DFT

%以下为绘图部分（省略，程序集中有）程序运行结果如图3.1.3所示。图3.1.3程序ep312.m运行结果现在解释DFT［R5(n)］5=5δ(k)。根据DFT第二种物理解释可知，DFT［R5(n)］5表示R5(n)以5为周期的周期延拓序列R5((n))5的频谱特性，因为R5((n))5是一个直流序列，只有直流成分（即零频率成分）。3.1.4用MATLAB计算序列的DFT

MATLAB提供了用快速傅里叶变换算法FFT(算法见第4章介绍)计算DFT的函数fft，其调用格式如下:Xk=fft(xn,N)；调用参数xn为被变换的时域序列向量，N是DFT变换区间长度，当N大于xn的长度时，fft函数自动在xn后面补零。函数返回xn的N点DFT变换结果向量Xk。当N小于xn的长度时，fft函数计算xn的前面N个元素构成的N长序列的N点DFT，忽略xn后面的元素。

Ifft函数计算IDFT，其调用格式与fft函数相同，可参考help文件。3.2离散傅里叶变换的基本性质3.2.1线性性质如果x1(n)和x2(n)是两个有限长序列，长度分别为N1和N2，且y(n)=ax1(n)+bx2(n)式中，a、b为常数，取N=max［N1,N2］,则y(n)的N点DFT为Y(k)=DFT［y(n)］N=aX1(k)+bX2(k)0≤k≤N－1

(3.2.1)其中X1(k)和X2(k)分别为x1(n)和x2(n)的N点DFT。3.2.2循环移位性质

1．序列的循环移位设x(n)为有限长序列，长度为M，M≤N，则x(n)的循环移位定义为y(n)=x((n+m))NRn(n)(3.2.2)(3.2.2)式表明，将x(n)以N为周期进行周期延拓得到，再将左移m得到，最后取的主值序列则得到有限长序列x(n)的循环移位序列y(n)。M=6,N=8,m=2时，x(n)及其循环移位过程如图3.2.1所示。显然，y(n)是长度为N的有限长序列。观察图3.2.1可见，循环移位的实质是将x(n)左移m位，而移出主值区(0≤n≤N－1)的序列值又依次从右侧进入主值区。“循环移位”就是由此得名的。由循环移位的定义可知，对同一序列x(n)和相同的位移m，当延拓周期N不同时，y(n)=x((n+m))NRn(n)则不同。请读者画出N=M=6，m=2时，x(n)的循环移位序列y(n)波形图。图3.2.1x(n)及其循环移位过程

2．时域循环移位定理设x(n)是长度为M（M≤N）的有限长序列，y(n)为x(n)的循环移位，即y(n)=x((n+m))NRn(n)则

(3.2.3)其中X(k)=DFT［x(n)］N

0≤k≤N－1

证明1令n+m=n′，则有由于上式中求和项

以N为周期，因此对其在任一周期上的求和结果相同。将上式的求和区间改在主值区，则得

证明2

3．频域循环移位定理如果

X(k)=DFT［x(n)］N0≤k≤N－1 Y(k)=X((k+l))NRN(k)则

(3.2.4)(3.2.4)式的证明方法与时域循环移位定理类似，直接对Y(k)=X((k+l)NRN(k)进行IDFT即得证。说明本性质与时域移位性质成对偶关系.

本性质又称调制特性,时域序列的调制等效于频域移位.注意是圆周移位.

由此性质可得出以下两个公式:3.2.3循环卷积定理时域循环卷积定理是DFT中最重要的定理，具有很强的实用性。已知系统输入和系统的单位脉冲响应，计算系统的输出，以及FIR滤波器用FFT实现等，都是基于该定理的。下面首先介绍循环卷积的概念和计算循环卷积的方法，然后介绍循环卷积定理。

1．两个有限长序列的循环卷积设序列h(n)和x(n)的长度分别为N1和N2

。h(n)与x(n)的N点循环卷积定义为 （3.2.5）式中，L称为循环卷积区间长度，L≥max［N，M］。上式显然与第1章介绍的线性卷积不同，为了区别线性卷积，用*表示循环卷积，用表示L点循环卷积，即yc(n)=h(n)

x(n)。观察（3.2.5）式，x((n－m))L是以L为周期的周期信号，n和m的变化区间均是［0,L－1］，1、圆周卷积定义2、圆周卷积的实现步骤圆周卷积卷积过程可以用图3-15来表示。圆周卷积过程中，求和变量为m,n为参变量。先将x2(m)周期化，形成x2((m))N，再反转形成x2((-m))N，取主值序列则得到x2((-m))NRN(m)，通常称之为x2(m)的圆周反转。对x2(m)的圆周反转序列圆周右移n，形成x2((n-m))NRN(m)，当n=0,1,2,…,N-1时，分别将x1(m)与x2((n-m))NRN(m)相乘，并在m=0到N-1区间内求和，便得到圆周卷积y(n)。可以看出,它和周期卷积过程是一样的，只不过这里要取主值序列。特别要注意，两个长度小于等于N的序列的N点圆周卷积长度仍为N，这与一般的线性卷积不同。圆周卷积用符号○来表示。圆周内的N表示所作的是N点圆周卷积。N图3-15圆周卷积过程示意图图3-15圆周卷积过程示意图当n=0,1,2,…,L－1时，由x(n)形成的序列为:{x(0),x(1),…,x(L－1)}。令n=0,m=0,1,…,L－1，由式（3.2.5）中x((n-m))L形成x(n)的循环倒相序列为与序列x(n)进行对比，相当于将第一个序列值x(0)不动，将后面的序列反转180°再放在x(0)的后面。这样形成的序列称为x(n)的循环倒相序列。直接计算该式比较麻烦。计算机中采用矩阵相乘或快速傅里叶变换（FFT）的方法计算循环卷积。令n=1,m=0,1,…,L-1，由式（3.2.5）中x((n-m))L形成的序列为观察上式等号右端序列，它相当于x(n)的循环倒相序列向右循环移一位，即向右移1位，移出区间［0,L－1］的序列值再从左边移进。再令n=2,m=0,1,…,L－1，此时得到的序列又是上面的序列向右循环移1位。依次类推，当n和m均从0变化到L-1时，得到一个关于x((n－m)L的矩阵如下：

（3.2.6）上面矩阵称为x(n)的L点“循环卷积矩阵”，其特点是:（1）第1行是序列{x(0),x(1),…,x(L－1)}的循环倒相序列。注意，如果x(n)的长度M<L，则需要在x(n)末尾补L－M个零后，再形成第一行的循环倒相序列。（2）第1行以后的各行均是前一行向右循环移1位形成的。（3）矩阵的各主对角线上的序列值均相等。有了上面介绍的循环卷积矩阵，就可以写出式（3.2.5）的矩阵形式如下:（3.2.7）按照上式，可以在计算机上用矩阵相乘的方法计算两个序列的循环卷积，这里关键是先形成循环卷积矩阵。上式中如果h(n)的长度N<L，则需要在h(n)末尾补L－N个零。

【例3.2.1】计算下面给出的两个长度为4的序列h(n)与x(n)的4点和8点循环卷积。

解按照式（3.2.21）写出h(n)与x(n)的4点循环卷积矩阵形式为h(n)与x(n)的8点循环卷积矩阵形式为h(n)和x(n)及其4点和8点循环卷积结果分别如图3.2.2(a)、(b)、(c)和(d)所示。请读者计算验证本例的8点循环卷积结果等于h(n)与x(n)的线性卷积结果。后面将证明，当循环卷积区间长度L大于等于y(n)=h(n)*x(n)的长度时，循环卷积结果就等于线性卷积。

图3.2.2序列及其循环卷积波形

2.循环卷积定理有限长序列x1(n)和x2(n)的长度分别为N1和N2，N=max［N1,N2］，x1(n)和x2(n)的N点循环卷积为

（3.2.8）则x(n)的N点DFT为

其中N

（3.2.9）

证明直接对(3.2.8)式两边进行DFT，则有令n－m=n′，则有因为上式中

是以N为周期的，所以对其在任一个周期上求和的结果不变。因此由于，因此即循环卷积亦满足交换律。

作为习题请读者证明以下频域循环卷积定理:如果x(n)=x1(n)x2(n)，则(3.2.10a)N

或

(3.2.10b)式中相对频域循环卷积定理，称(3.2.9)式为时域循环卷积定理。N

补充：循环反褶性质补充：有限长序列的线性卷积与圆周卷积

时域圆周卷积在频域上相当于两序列的DFT的乘积，而计算DFT可以采用它的快速算法——快速傅里叶变换（FFT）（见第4章），因此圆周卷积与线性卷积相比，计算速度可以大大加快。但是实际问题大多总是要求解线性卷积。例如，信号通过线性时不变系统，其输出就是输入信号与系统的单位脉冲响应的线性卷积，如果信号以及系统的单位脉冲响应都是有限长序列，那么是否能用圆周卷积运算来代替线性卷积运算而不失真呢？下面就来讨论这个问题。设x1(n)是N1点的有限长序列（0≤n≤N1-1），x2(n)是N2点的有限长序列（0≤n≤N2-1）。（1）先看它们的线性卷积x1(m)的非零区间为0≤m≤N1-1x2(n-m)的非零区间为0≤n-m≤N2-1(2-43)将两个不等式相加，得到0≤n≤N1+N2-2在上述区间外，不是x1(m)=0就是x2(n-m)=0，因而y1(n)=0。所以y1(n)是N1+N2-1点有限长序列，即线性卷积的长度等于参与卷积的两序列的长度之和减1。（2）我们再来看x1(n)与x2(n)的圆周卷积。先假设进行L点的圆周卷积，再讨论L取何值时，圆周卷积才能代表线性卷积。设y(n)=x1(n)○x2(n)是两序列的L点圆周卷积，L≥max［N1,N2］，这就要将x1(n)与x2(n)都看成是L点的序列。在这L个序列值中，x1(n)只有前N1个是非零值，后L-N1个均为补充的零值。同样，x2(n)只有前N2个是非零值，后L-N2个均为补充的零值。则LL（2-44）为了分析其圆周卷积，我们先将序列x1(n)与x2(n)以L为周期进行周期延拓它们的周期卷积序列为（2-45）前面已经分析了y1(n)具有N1+N2-1个非零值。因此可以看到，如果周期卷积的周期L<N1+N2-1，那么y1(n)的周期延拓就必然有一部分非零序列值要交叠起来，从而出现混叠现象。只有在L≥N1+N2-1时，才没有交叠现象。这时,在y1(n)的周期延拓中，每一个周期L内，前N1+N2-1个序列值正好是y1(n)的全部非零序列值，而剩下的L-(N1+N2-1)个点上的序列值则是补充的零值。圆周卷积正是周期卷积取主值序列L因此(2-46)所以要使圆周卷积等于线性卷积而不产生混叠的必要条件为（2-47）满足此条件后就有即 x1(n)○x2(n)=x1(n)*x2(n)L下图（d）、（e）、（f）正反映了（2-46）式的圆周卷积与线性卷积的关系。在图2-16（d）中，L=6小于N1+N2-1=8，这时产生混叠现象，其圆周卷积不等于线性卷积；而在图2-16（e）、（f）中,L=8和L=10，这时圆周卷积结果与线性卷积相同，所得y(n)的前8点序列值正好代表线性卷积结果。所以只要L≥N1+N2-1，圆周卷积结果就能完全代表线性卷积。图

线性卷积与圆周卷积例

一个有限长序列为（1）计算序列x(n)的10点离散傅里叶变换。（2）若序列y(n)的DFT为式中，X(k)是x(n)的10点离散傅里叶变换，求序列y(n)。（3）若10点序列y(n)的10点离散傅里叶变换是式中,X(k)是序列x(n)的10点DFT，W(k)是序列w(n)的10点DFT0≤n≤6其他求序列y(n)。

解

（1）由式（2-30）可求得x(n)的10点DFT（2）X(k)乘以一个WNkm形式的复指数相当于是x(n)圆周移位m点。本题中m=-2,x(n)向左圆周移位了2点，就有y(n)=x((n+2))10R10(n)=2δ(n-3)+δ(n-8)（3）X(k)乘以W(k)相当于x(n)与w(n)的圆周卷积。为了进行圆周卷积，可以先计算线性卷积再将结果周期延拓并取主值序列。x(n)与w(n)的线性卷积为z(n)=x(n)*w(n)=｛1,1,1,1,1,3,3,2,2,2,2,2｝圆周卷积为在0≤n≤9求和中，仅有序列z(n)和z(n+10)有非零值，用表列出z(n)和z(n+10)的值，对n=0,1,2,…,9求和，得到：n01234567891011Z(n)z(n+10)11111332222200000000

200y(n)3311133222____所以10点圆周卷积为y(n)=｛3,3,1,1，1,3,3,2,2,2｝2.5.5共轭对称性设x*(n)为x(n)的共轭复序列，则DFT［x*(n)］=X*((-k))NRN(k)=X*((N-k))NRN(k)=X*(N-k)0≤k≤N-1且X(N)=X(0)（2-48）证0≤k≤N-13.2.4复共轭序列的DFT

设x*(n)是x(n)的复共轭序列，长度为N，X(k)=DFT［x(n)］N，则

(3.2.11)且X(N)=X(0)。

证明根据DFT的唯一性，只要证明(3.2.11)式右边等于左边即可。DFT［x*(n)］=X*((-k))NRN(k)=X*((N-k))NRN(k)=X*(N-k)0≤k≤N-1又由X(k)的隐含周期性，有X(N)=X(0)用同样的方法可以证明

(3.2.12)这里利用了3.2.5DFT的共轭对称性

1．有限长共轭对称序列和共轭反对称序列为了区别于傅里叶变换中所定义的共轭对称（或共轭反对称）序列，下面用xep(n)和xop(n)分别表示有限长共轭对称序列和共轭反对称序列，则二者满足如下关系式：

(3.2.13a)

(3.2.13b)当N为偶数时，将上式中的n换成N/2－n，可得到：上式更清楚地说明了有限长序列共轭对称序列是关于n=N/2点对称。容易证明，如同任何实函数都可以分解成偶对称分量和奇对称分量一样，任何有限长序列x(n)都可以表示成其共轭对称分量和共轭反对称分量之和，即(3.2.14)将上式中的n换成N－n，并取复共轭，再将(3.2.13a)式和(3.2.13b)式代入，得到：

(3.2.15)(3.2.14)式分别加减(3.2.15)式，可得

(3.2.16a)

(3.2.16b)

2．DFT的共轭对称性

(1)如果将x(n)表示为

x(n)=xr(n)+jxi(n)(3.2.17)其中那么，由(3.2.11)式和(3.2.16a)式可得(3.2.18)由(3.2.11)式和(3.2.16b)式可得

(3.2.19)由DFT的线性性质即可得

(3.2.20)其中，Xop(k)=DFT［xr(n)］是X(k)的共轭对称分量，Xop(k)=DFT［jxi(n)］是X(k)的共轭反对称分量。

(2)如果将x(n)表示为

(3.2.21)其中，

是x(n)的共轭对称分量，是x(n)的共轭反对称分量,那么，由(3.2.12)式可得因此

(3.2.22)其中

综上所述，可总结出DFT的共轭对称性质：如果序列x(n)的DFT为X(k)，则x(n)的实部和虚部（包括j）的DFT分别为X(k)的共轭对称分量和共轭反对称分量；而x(n)的共轭对称分量和共轭反对称分量的DFT别为X(k)的实部和虚部乘以j。

共轭对称性XX10-23

另外，请读者根据上述共轭对称性证明有限长实序列DFT的共轭对称性（见本章习题题7）。设x(n)是长度为N的实序列，且X(k)=DFT［x(n)］N，设x(n)是长度为N的实序列，且X(k)=DFT［x(n)］N，则X(k)满足如下对称性：

(1)X(k)共轭对称，即

X(k)=X*(N-k)k=0,1,…,N-1(3.2.23)

(2)如果x(n)是偶对称序列，即x(n)=x(N－n)，则X(k)实偶对称，即

X(k)=X(N－k)(3.2.24)

(3)如果是奇对称序列，即x(n)=－x(N－n)，则X(k)纯虚奇对称，即

X(k)=－X(N－k)(3.2.25)奇偶虚实关系表

奇----指序列是圆周奇对称序列偶----指序列是圆周偶对称序列虚----指序列是纯虚序列实----指序列是实序列圆周奇对称序列圆周偶对称序列1)各序列都是有限长序列(隐含周期性)2)根据时域,频域的对偶性质,

上表的时域与频域可以互调实际中经常需要对实序列进行DFT，利用上述对称性质，可减少DFT的运算量，提高运算效率。例如，计算实序列的N点DFT时，当N=偶数时，只需计算X(k)的前面N/2+1点，而N=奇数时，只需计算X(k)的前面(N+1)/2点，其他点按照(3.2.22)式即可求得。例如，X(N－1)=X*(1),X(N－2)=X*(2),…这样可以减少近一半运算量。X(k)=X*(N-k)k=0,1,…,N-1

【例3.2.2】利用DFT的共轭对称性，设计一种高效算法，通过计算一个N点DFT，就可以计算出两个实序列x1(n)和x2(n)的N点DFT。

解构造新序列x(n)=x1(n)+jx2(n)，对x(n)进行DFT，得到：由(3.2.17)、(3.2.18)和(3.2.19)式得到：所以，由X(k)可以求得两个实序列x1(n)和x2(n)的N点DFT：补充.Parseval’srelation:补充.Duality(对偶性)-----补充3.３频域采样理论首先，考虑一个任意的绝对可和的非周期序列x(n)，它的Z变换为由于绝对可和，所以其傅里叶变换存在且连续，故Z变换收敛域包括单位圆。如果我们对X(z)在单位圆上进行N点等距采样：（3-64）问题在于，这样采样以后是否仍能不失真地恢复出原序列x(n)。也就是说，频率采样后从X(k)的反变换中所获得的有限长序列，即xN(n)=IDFT［X(k)］，能不能代表原序列x(n)？为此，我们先来分析X(k)的周期延拓序列的离散傅里叶级数的反变换，令其为。将式（3-64）代入此式，可得由于m=n+rN,r为任意整数其他m

所以（3-65）

这说明由得到的周期序列是原非周期序列x(n)的周期延拓，其时域周期为频域采样点数N。已经知道，时域采样造成频域的周期延拓，这里又看到一个对称的特性，即频域采样同样会造成时域的周期延拓。

（1）如果x(n)是有限长序列，点数为M，则当频域采样不够密，即当N<M时，x(n)以N为周期进行延拓，就会造成混叠。这时，从就不能不失真地恢复出原信号x(n)来。因此，对于M点的有限长序列x(n)0≤n≤M-1其他n

频域采样不失真的条件是频域采样点数N要大于或等于时域采样点数M（时域序列长度），即满足N≥M

（3-66）此时可得到

N≥M

（3-67）

也就是说，点数为N（或小于N）的有限长序列，可以利用它的Z变换在单位圆上的N个等间隔点上的采样值精确地表示。

（2）如果x(n)不是有限长序列（即无限长序列），则时域周期延拓后，必然造成混叠现象，因而一定会产生误差;当n增加时信号衰减得越快，或频域采样越密（即采样点数N越大），则误差越小，即xN(n)越接近x(n)。既然N个频域采样X(k)能不失真地代表N点有限长序列x(n)，那么这N个采样值X(k)也一定能够完全地表达整个X(z)及频率响应X(ejω)。讨论如下：由于将它代入X(z)式子中，得到由于WN-Nk=1，因此

这就是用N个频率采样X(k)来表示X(z)的内插公式。它可以表示为（3-68）（3-69）式中（3-70）称为内插函数。令其分子为零，得即内插函数在单位圆的N等分点上（也即采样点上）有N个零点。而分母为零，则有z=WN-k=的一个极点，它将和第k个零点相抵消。因而，插值函数Φk(z)只在本身采样点r=k处不为零，在其他（N-1）个采样点r上（r=0,1,…,N-1，但r≠k）都是零点（有（N-1）个零点）。而它在z=0处还有（N-1）阶极点，如图3-17所示。图3-17内插函数的零极点

现在来讨论频率响应，即求单位圆上z=ejω的Z变换。由式（3-69）可得（3-71）而（3-72）可将Φk(ejω)表示成更为方便的形式:式中：（3-73）（3-74）这样式（3-71）又可改写为（3-75）图3-18内插函数幅度特性与相位特性(N=5)

当变量ω=0时，

Φ(ω)=1，当（i=1,2,…,N-1)时，Φ(ω)=0。因而可知，满足以下关系：（3-76）

k=0,1,…,N-1请注意，一般来说，这里的X(ejω)和X(k)都是复数。

也就是说，函数 在本采样点 ，而在其他采样点 上，函数。整个X(ejω)就是由N个函数分别乘上X(k)后求和。所以很明显，在每个采样点上X(ejω)就精确地等于X(k)（因为其他点的插值函数在这一点上的值为零，没有影响）即

各采样点之间的X(ejω)值由各采样点的加权插值函数 在所求ω点上的值的叠加得到的。在以后章节中，我们将会看到，频率采样理论为FIR滤波器的结构设计，以及FIR滤波器传递函数的逼近提供了又一个有力的工具。

【例3.3.1】长度为26的三角形序列x(n)如图3.3.1(a)所示。编写MATLAB程序验证频域采样理论。

解解题思想：先计算x(n)的32点DFT，得到其频谱函数X(ejω)在频率区间［0，2π］上等间隔32点采样X32(k)，再对X32(k)隔点抽取，得到X(ejω)在频率区间［0，2π］上等间隔16点采样X16(k)。最后分别对X16(k)和X32(k)求IDFT,得到：绘制x16(n)和x32(n)波形图验证频域采样理论。MATLAB求解程序ep331.m如下：%《数字信号处理(第三版）》第3章例3.3.1程序ep331.%频域采样理论验证M=26;N=32;n=0:M;xa=0:M/2;xb=ceil(M/2)-1:-1:0;xn=［xa,xb］;

%产生M长三角波序列x(n)Xk=fft(xn,512);

%512点FFT［x(n)］X32k=fft(xn,32);

%32点FFT［x(n)］x32n=ifft(X32k);

%32点IFFT［X32(k)］得到x32(n)X16k=X32k(1:2:N);%隔点抽取X32k得到X16(k)x16n=ifft(X16k,N/2);%16点IFFT［X16(k)］得到x16(n)以下绘图部分省略。程序运行结果如图3.3.1所示。图3.3.1(a)和(b)分别为X(ejω)和x(n)的波形；图3.3.1(c)和(d)分别为X(ejω)的16点采样|X16(k)|和x16(n)=IDFT［X16(k)］16波形图；图3.3.1(e)和(f)分别为X(ejω)的32点采样|X32(k)|和x32(n)=IDFT［X32(k)］32波形图；由于实序列的DFT满足共轭对称性，因此频域图仅画出［0，π］上的幅频特性波形。本例中x(n)的长度M=26。从图中可以看出，当采样点数N=16<M时，x16(n)确实等于原三角序列x(n)以16为周期的周期延拓序列的主值序列。由于存在时域混叠失真，因而x16(n)≠x(n)；当采样点数N=32>M时，无时域混叠失真，x32(n)=IDFT［X32(k)］=x(n)。图3.3.1频域采样定理验证 3.4DFT的应用举例3.4.1用DFT计算线性卷积用DFT计算循环卷积很简单。设h(n)和x(n)的长度分别为N和M,其L点循环卷积为且L则由DFT的时域循环卷积定理有由此可见，循环卷积既可以在时域直接计算，也可以按照图3.4.1所示的计算框图在频域计算。由于DFT有快速算法，当L很大时，在频域计算循环卷积的速度快得多，因而常用DFT(FFT)计算循环卷积。图3.4.1用DFT计算循环卷积的原理框图在实际应用中，为了分析时域离散线性时不变系统或者对序列进行滤波处理等，需要计算两个序列的线性卷积。与计算循环卷积一样，为了提高运算速度，也希望用DFT(FFT)计算线性卷积。而DFT只能直接用来计算循环卷积，因此，下面先导出线性卷积和循环卷积之间的关系以及循环卷积与线性卷积相等的条件，最后得出用图3.4.1线性卷积的条件。假设h(n)和x(n)都是有限长序列，长度分别是N和M。它们的线性卷积和循环卷积分别表示如下：

其中所以(3.4.1)(3.4.2)L对照(3.4.1)式可以看出，上式中即

(3.4.3)(3.4.3)式说明，yc(n)等于yl(n)以L为周期的周期延拓序列的主值序列。我们知道，yl(n)长度为N＋M－1，因此只有当循环卷积长度L≥N＋M－1时，yl(n)以L为周期进行周期延拓时才无时域混叠现象。此时取其主值序列显然满足yc(n)=yl(n)。由此证明了循环卷积等于线性卷积的条件是L≥N＋M－1。图3.4.2中画出了h(n)、x(n)、h(n)*x(n)以及L分别取6、8、10时h(n)Lx(n)的波形。由于h(n)长度N=4，x(n)长度M=5，N＋M－1=8，因此只有L≥8时，h(n)

L

x(n)波形才与h(n)*x(n)相同。

图3.4.2线性卷积与循环卷积波形图综上所述，取L≥N＋M≥1，则可按照如图3.4.1所示的计算框图用DFT(FFT)计算线性卷积。其中DFT和IDFT通常用快速算法(FFT)来实现，故常称其为快速卷积。实际上，经常遇到两个序列的长度相差很大的情况，例如M>>N。若仍选取L≥N＋M－1，以L为循环卷积区间，并用上述快速卷积法计算线性卷积，则要求对短序列补很多零点，而且长序列必须全部输入后才能进行快速计算。因此要求存储容量大，运算时间长，并使处理延时很大，不能实现实时处理。Xl10-28图3.4.1用DFT计算循环卷积的原理框图复习况且在某些应用场合，序列长度不定或者认为是无限长，如电话系统中的语音信号和地震检测信号等。显然，在要求实时处理时，直接套用上述方法是不行的。解决这个问题的方法是将长序列分段计算，这种分段处理方法有重叠相加法和重叠保留法两种。重叠相加法设h(n)的点数为M，信号x(n)为很长的序列。我们将x(n)分解为很多段，每段为L点，L选择成和M的数量级相同，用xi(n)表示x(n)的第i段：iL≤n≤(i+1)L-1其他n

i=0,1,…（4-68）则输入序列可表示成（4-69）这样，x(n)和h(n)的线性卷积等于各xi(n)与h(n)的线性卷积之和，即（4-70）

每一个xi(n)*h(n)都可用上面讨论的快速卷积办法来运算。由于xi(n)*h(n)为L+M-1点，故先对xi(n)及h(n)补零值点，补到N点。为便于利用基-2FFT算法，一般取N=2m≥L+M-1，然后作N点的圆周卷积：N

由于xi(n)为L点，而yi(n)为（L+M-1）点（设N=L+M-1），故相邻两段输出序列必然有（M-1）个点发生重叠，即前一段的后（M-1）个点和后一段的前（M-1）个点相重叠，如图4-27所示。按照式（4-70），应该将重叠部分相加再和不重叠的部分共同组成输出y(n)。图4-27重叠相加法图形图4-27重叠相加法图形和上面的讨论一样，用FFT法实现重叠相加法的步骤如下:

①计算N点FFT，H(k)=DFT［h(n)］；②计算N点FFT，Xi(k)=DFT［xi(n)］；③相乘，Yi(k)=Xi(k)H(k)；④计算N点IFFT，yi(n)=IDFT［Yi(k)］；⑤将各段yi(n)（包括重叠部分）相加， 。重叠相加的名称是由于各输出段的重叠部分相加而得名的。重叠保留法此方法与上述方法稍有不同。先将x(n)分段，每段L=N-M+1个点，这是相同的。不同之处是，序列中补零处不补零，而在每一段的前边补上前一段保留下来的（M-1）个输入序列值，组成L+M-1点序列xi(n)，如图4-28（a）所示。如果L+M-1<2m，则可在每段序列末端补零值点，补到长度为2m，这时如果用DFT实现h(n)和xi(n)圆周卷积，则其每段圆周卷积结果的前（M-1）个点的值不等于线性卷积值，必须舍去。图4-28重叠保留法示意图图4-28重叠保留法示意图图4-29用保留信号代替补零后的局部混叠现象图4-29用保留信号代替补零后的局部混叠现象

为了说明以上说法的正确性，我们来看一看图4-29。任一段xi(n)（为N点）与h(n)（原为M点，补零值后也为N点）的N点圆周卷积N（4-71）由于h(m)为M点，补零后作N点圆周移位时，在n=0,1,…,M-2的每一种情况下，h((n-m))NRN(m)在0≤m≤N-1范围的末端出现非零值，而此处xi(m)是有数值存在的，图4-29（c），（d）为n=0,n=M-2的情况，所以在0≤n≤M-2

这一部分的yi(n)值中将混入xi(m)尾部与h((n-m))N·RN(m)尾部的乘积值，从而使这些点的yi(n)不同于线性卷积结果。但是从n=M-1开始到n=N-1，h((n-m))NRN(m)=h(n-m)（如图4-29（e），（f）所示），圆周卷积值完全与线性卷积值一样，yi(n)就是正确的线性卷积值。因而必须把每一段圆周卷积结果的前(M-1)个值去掉，如图4-29（g）所示。

因此，为了不造成输出信号的遗漏，对输入分段时，就需要使相邻两段有M-1个点重叠（对于第一段，即x0(n)，由于没有前一段保留信号，则需要在序列前填充M-1个零值点），这样，若原输入序列为x′(n)（n≥0时有值），则应重新定义输入序列0≤n≤M-2M-1≤n

(4-72a)而0≤n≤N-1其他n

i=0,1,…(4-72b)

在这一公式中，已经把每一段的时间原点放在该段的起始点，而不是x(n)的原点。这种分段方法示于图4-28中，每段xi(n)和h(n)的圆周卷积结果以yi(n)表示，如图4-28（b）所示，图中已标出每一段输出段开始的(M-1)个点，0≤n≤M-2部分舍掉不用。把相邻各输出段留下的序列衔接起来，就构成了最后的正确输出，即（4-73）式中:M-1≤n≤N-1其他n

（4-74）这时，每段输出的时间原点放在yi′(n)的起始点，而不是y(n)的原点。

MATLAB信号处理工具箱中提供了一个函数fftfilt，该函数用重叠相加法实现线性卷积的计算。调用格式为：y=fftfilt(h,x，M)。式中,h是系统单位脉冲响应向量；x是输入序列向量；y是系统的输出序列向量（h与x的卷积结果）；M是由用户选择的输入序列x的分段长度，缺省M时，默认输入序列x的分段长度M=512。

【例3.4.1】假设h(n)=R5(n)，x(n)=［cos(πn/10)

+cos(2πn/5)］u(n)，用重叠相加法计算y(n)=h(n)*x(n)，并画出h(n)、x(n)和y(n)的波形。

解

h(n)的长度为N=5,对x(n)进行分段，每段长度为M=10。计算h(n)和x(n)的线性卷积的MATLAB程序如下：

%例3.4.1重叠相加法的MATLAB实现程序：ep341.mLx=41;N=5;M=10; %Lx为信号序列x(n)长度

hn=ones(1,N);hn1=［hnzeros(1,Lx-N)］;

%产生h(n)，其后补零是为了绘图好看

n=0:L-1;xn=cos(pi*n/10)+cos(2*pi*n/5);%产生x(n)的Lx个样值

yn=fftfilt(hn,xn,M);%调用fftfilt用重叠相加法计算卷积

%以下为绘图部分,省略

运行程序画出h(n)、x(n)和y(n)的波形如图3.4.4所示。请读者从理论上证明y(n)的稳态波形是单一频率的正弦波。运行绘图程序fig345.m可以得到用重叠相加法求解本例题的xk(n),yk(n)和y(n)=y0(n)+y1(n)+y2(n)+y3(n),如图3.4.5所示。图3.4.4例3.4.1的求解程序运行结果图3.4.5重叠相加法时域波形3.4.2用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(jΩ)，对xa(t)进行时域采样得到x(n)=xa(nT)，x(n)的傅里叶变换为X(ejω)。由假设条件可知x(n)的长度为

(3.4.5)式中，T为采样间隔，Fs=1/T为采样频率。用X(k)表示x(n)的N点DFT，下面推导出X(k)与Xa(jΩ)的关系，最后由此关系归纳出用X(k)表示Xa(jΩ)的方法，即用DFT对连续信号进行谱分析的方法。由（2.4.3）式知道，x(n)的傅里叶变换X(ejω)与xa(t)的傅里叶变换Xa(jΩ)满足如下关系：将ω=ΩT代入上式，得到:

(3.4.6)式中def表示模拟信号频谱Xa(jΩ)的周期延拓函数。由x(n)的N点DFT的定义有

(3.4.7)将(3.4.7)式代入(3.4.6)式,得到：

(3.4.8)(3.4.8)式说明了X(k)与Xa(jΩ)的关系。为了符合一般的频谱描述习惯，以频率f为自变量，整理（3.4.8）式。令def则（3.4.8）式变为由此可得（3.4.10）(3.4.9)式中，F表示对模拟信号频谱的采样间隔，所以称之为频率分辨率，Tp=NT为截断时间长度。

(3.4.11)N11ssFNTTF===图3.4.6用DFT分析连续信号谱的原理示意图bb-11-4(3.4.10)式说明，可以通过对连续信号采样并进行DFT再乘以T，近似得到模拟信号频谱的周期延拓函数在第一个周期［0,fs］上的N点等间隔采样，如图3.4.6所示。对满足假设的持续时间有限的带限信号，在满足时域采样定理时，包含了模拟信号频谱的全部信息（k=0,1,2,…,N/2,表示正频率频谱采样;k=N/2+1，N/2+2，…，N－1,表示负频率频谱采样）。所以，上述分析方法不丢