第三章 离散傅立叶变换
3．1 引言
有限长序列在数字信号处理是很重要的一种序列，当然可以用Z变换和傅里叶变换来研究它，但是，可以导出反映它的"有限长"特点的一种有用工具是离散傅里叶变换(DFT)。离散傅里叶变换除了作为有限长序列的一种傅里叶表示法在理论上相当重要之外，而且由于存在着计算离散傅里叶变换的有效快速算法，因而离散傅里叶变换在各种数字信号处理的算法中起着核心的作用。
有限长序列的离散傅里叶变换(DFT)和周期序列的离散傅里叶级数(DFS)本质上是一样的。为了更好地理解DFT，需要先讨论周期序列的离散傅里叶级数DFS。而为了讨论离散傅里叶级数及离散傅里叶变换，我们首先来回顾并讨论傅里叶变换的几种可能形式。
(连续时间信号：如果在讨论的时间间隔内，除若干不连续点之外，对于任意时间值都可给出确定的函数值，此信号就称为连续时间信号。)
一、连续时间、连续频率——连续傅立叶变换（FT）
设x(t)为连续时间非周期信号，傅里叶变换关系如下图所示：
可以看出时域连续函数造成频域是非周期的谱，而时域的非周期造成频域是连续的谱。
二、连续时间，离散频率------傅 里 叶 级 数
设f(t)代表一个周期为T1的周期性连续时间函数，f(t)可展成傅里叶级数，其傅里叶级数的系数为，f(t)和组成变换对，表示为:
（）
注意符号：如果是周期性的采样脉冲信号p(t)，周期用T表示（采样间隔）。采样脉冲信号的频率为
可以看出时域连续函数造成频域是非周期的谱，而时域的周期造成频域是离散的谱
三、离散时间，连续频率------序列的傅里叶变换
正变换：DTFT[x(n)]=
反变换：DTFT-1
级数收敛条件为||=
可以看出时域离散函数造成频域是周期的谱，而时域的非周期造成频域是连续的谱
四、离散时间，离散频率------离散傅里叶变换
上面讨论的三种傅里叶变换对，都不适用在计算机上运算，因为至少在一个域(时域或频域)中，函数是连续的。因为从数字计算角度，我们感兴趣的是时域及频域都是离散的情况，这就是我们这里要谈到的离散傅里叶变换。
时域抽样间隔T，频域周期Ws=2p/T，
时域周期T1，频域抽样间隔W1=2p/T1
周期序列的离散傅里叶级数（DFS）
设是周期为N的一个周期序列，即，r为任意整数。和连续时间周期信号一样，周期序列可用离散傅里叶级数来表示。
离散傅里叶级数（DFS）对：
正变换=DFS[] = =
反变换=IDFS[]==
式中，，和均为整数。
观察=。是一个周期序列吗？如是，周期为多少？
=。
所以。是一个周期序列，周期为N。
，周期为N
，周期也为N。
观察=，与连续时间信号与系统中的傅里叶级数对应，表明将周期序列分解成N个独立谐波分量。第0次谐波序列，基波序列，…，第k次谐波序列，第N-1次谐波序列。谐波频率，k=0，1，2，…，N-1，幅度为。例如：基波分量的频率为2p/N，幅度是。一个周期序列可以用其DFS表示它的频谱分布规律。
例题：如图所示，求的DFS
解：=DFS[] = =
====
==，
||如下图所示。
离散傅立叶变换（DFT）
周期序列实际上只有有限个序列值才有意义，因而它的离散傅里叶级数表示式也适用于有限长序列，这就可以得到有限长序列的傅里叶变换(DFT)。
设x(n)是一个长度为M的有限长序列，
正变换=DFT[] = =
k=0，1，2，…，N-1 （3.1.1）
反变换=IDFT[]==
n=0，1，2，…，N-1 （3.1.2）
式中，N称为DFT变换区间长度，N≥M。
例3．1．1：= R4(n)，求的8点和16点DFT。
解：（1）DFT变换区间N=8，则：
====
=，k=0，1，…，7
（2）DFT变换区间N=16，则：
==
=，k=0，1，…，15
DFS与DFT的关系
1、 有限长序列和周期序列的关系
设x(n)是一个长度为M的有限长序列，以N（N≥M）为周期进行周期延拓得。是x(n)的周期延拓。如下图所示：
M=4，N=8，以N=8进行周期延拓。的周期为8 。
用式子表示：
＝
或＝x(n 模 N)＝x((n))N，(n 模 N)表示n对N取余数
例：设是以N=8周期对有限长序列x(n)（长度M=4）进行周期延拓得到的。＝x(3)，=x(2)。
有限长序列进行周期延拓得到周期序列。
定义：周期序列中从n=0到N-1的第一个周期为的主值区间，而主值区间上的序列称为的主值序列
周期序列的主值序列是有限长序列
利用前面的矩形序列符号RN(n)
RN(n)= 1 ，0≤n≤N-1
0 ，其他n
x(n)= RN(n)
x(n)的周期延拓序列是；＝x((n))N
的主值序列是x(n)； x(n)= RN(n)
同理把频域周期序列也看作是有限长序列X(k)的周期延拓。 X(k)是 的主值序列
X(k)的周期延拓序列是；＝X((k))N
的主值序列是X(k)； X(k)= RN(n)
具体而言，我们把时域周期序列看作是有限长序列x(n)的周期延拓；同理把频域周期序列也看作是有限长序列X(k)的周期延拓。这样我们只要把DFS的定义式两边取主值区间，就得到了一个关于有限长序列的时频域对应的变换对。这就是数字信号处理课程里最重要的变换-------离散傅里叶变换(DFT)。
离散傅立叶级数（DFS）对：
正变换=DFS[] = =
反变换=IDFS[]==
式中，，和均为整数。
离散傅里叶变换(DFT)
正变换：＝DFT[x(n)]= ，0≤k≤N-1
反变换：x(n)=IDFT[]=，0≤n≤N-1
或：＝ RN(k)＝ RN(k)
x(n)= RN(n) = RN(n)
DFT隐含有周期性。
DFT和Z变换的关系
设序列x(n)的长度为N，其Z变换和DFT分别为：
＝DFT[x(n)]= ，0≤k≤N-1
比较上面两式可以得到：
＝|，0≤k≤N-1 （3.1.3）
或
=|，0≤k≤N-1 （3.1.4）
（3.1.3）表明序列x(n)的N点DFT是x(n)的Z变换在单位圆上的N点等间隔采样。（3.1.4）表明是x(n)的傅立叶变换在区间[0，2π]上的N点等间隔采样。这就是DFT的物理意义。由此可见，DFT的变换区间长度N不同，表示对在[0，2π]区间上的采样间隔和采样点数不同，所以DFT的变换结果不同。例3．1．1中，= R4(n)， DFT变换区间长度N分别取8点和16点，结果不同。下图为R4(n)的傅立叶变换和R4(n)的8点、16点的对应图。
3．2 离散傅立叶变换的性质
一、线性
设x1(n)、x2(n)是两个有限长序列，长度分别为N1，N2，且y(n)=a x1(n)+b x2(n)，a，b为常数。N=max[N1，N2]。
x1(n) 有限长序列，长度为N；
x2(n) 有限长序列，长度为N；
y(n) 有限长序列，长度为N；
x1(n)的N点DFT为： X1(k)=DFT[x1(n)]=
0≤k≤N-1
x2(n)的N点DFT为： X2(k)=DFT[x2(n)]=
0≤k≤N-1
y(n)的N点DFT为： Y(k)=DFT[y(n)] =
==a X1(k)+b X2(k)
0≤k≤N-1
二、循环移位定理
1、 序列的循环移位
设x(n)为有限长序列，长度为N，则x(n)的循环移位定义为
（3.2.2）
（3.2.2）表明先将x(n)以N为周期进行周期延拓得到序列= x((n))N，再将左移得到，最后取主值区间（n=0到N-1）上的序列值，则得到有限长序列x(n)的循环移位序列。
过程如下图所示：
2、 时域循环移位定理
设x(n)为有限长序列，长度为N，为 x(n)的循环移位序列，即，则
DFT[]=
其中=DFT[x(n)]，0≤k≤N-1
证明：
=
令n+m=n’，则有
=
=
由于上式中求和项以N为周期，所以对其在任一周期上的求和结果相同。将上式的求和区间改在主值区间，则得：
=
=
=，0≤k≤N-1
3、 频域循环移位定理
如果=DFT[x(n)]，0≤k≤N-1
=
则：y(n)=IDFT[]=x(n)
证明：y(n) =IDFT[]=
=
令=，则有：
y(n)=
=（）
=（）
=（）
= x(n)
三、循环卷积定理
有限长序列x1(n)和x2(n)，长度分别为N1和N2， N=max[N1，N2]。
x1(n)和x2(n)的N点DFT分别为：
X1(k)=DFT[x1(n)]
X2(k)=DFT[x2(n)]
如果X(k)= X1(k) X2(k)
则：x(n)= IDFT[X(k)]=
循环卷积过程：
循环卷积过程中，要求对循环反转，循环移位，特别是两个长度位N的序列的循环卷积长度仍为N。显然与一般的线性卷积不同，故称为循环卷积。记为：x(n)
=
四、复共轭序列的DFT
设是的复共轭序列，长度为N，
已知 ＝DFT[]，
则 DFT[]= 0≤k≤N-1
且
证明：DFT[]= RN(k)
= RN(k)
= RN(k)
= RN(k)
=，0≤k≤N-1
已知 ＝DFT[]，
则 DFT[]=
证明： ∵＝DFT[]，即
=IDFT[]==
=
=
=[]
=
=IDFT[]
即DFT[]=
五、DFT的共轭对称性
第二章2.2节中已详细讨论了序列傅立叶变换的对称性，那里的对称性是指关于坐标原点的纵坐标对称性。DFT也有对称性，但由于DFT中讨论的序列及其离散傅立叶变换均为有限长序列，且定义区间为0到N-1，所以这里的对称性是指关于N/2点的对称性。下面讨论DFT的共轭对称性质。
1、 有限长共轭对称序列和共轭反对称序列
为了区别于序列傅立叶变换中所定义的共轭对称和共轭反对称序列，下面用和分别表示有限长共轭对称序列和共轭反对称序列。二者的定义如下：
=，0≤n≤N-1
=－，0≤n≤N-1
(关于N/2点的对称性)
当N 为偶数时，将上式的n换成N/2-n，得到
=，0≤n≤N/2-1
当N为奇数时，将上式的n换成(N-1)/2-n，得到
=，0≤n≤(N-1)/2-1
任意有限长序列可表示成共轭对称分量和共轭反对称分量之和。
=+ 0≤n≤N-1
将上式中的n换成N-n，并取复共轭，得到：
=+
=-
∴=（+）
=（）
2、 DFT 的共轭对称性
（1）将有限长序列x(n)分成实部与虚部，即：
=+j
则：
证明：=（+）
DFT[]=（+）
=
j=（）
DFT[j]=（）
=
（2）将有限长序列x(n)分成共轭对称部分和共轭反对称部分，即
=+，0≤n≤N-1
则：
证明：=（+）
DFT[]=（+）
=
=（）
DFT[]=（）
=
3．3 频率域抽样理论
时域采样定理告诉我们，在一定条件下，可以由时域采样信号恢复原来的连续信号。那么能不能也由频域采样信号恢复频域连续信号？频域采样理论是什么？
已知序列及序列的长度为M。的Z变换为：。因为收敛域包含单位圆，所以其序列傅立叶变换存在。
对在区间[0，2π] 上进行N点等间隔采样（对X(z)在单位圆上进行N点等间隔采样），得到或
＝|=，0≤k≤N-1
将 进行IDFS得周期序列，取的主值序列，与原序列相等吗？相等的条件是什么？由此导出频域采样定理。
=IDFS[]
=
=
=
=
=，r为整数
=
式中= 1 m=n+rN，r为整数
0 其他m
＝
从上式得：X(z)在单位圆上的N点等间隔采样的IDFS，为原序列以N为周期的周期延拓序列。
=RN(n)=RN(n) (3.3.3)
所以只有当频域采样点数N≥M时，才有
=IDFT[]=
即可由频域采样恢复原序列，否则产生时域混叠现象。这就是频域采样定理。
满足频域采样定理，N≥M，即可由频域采样来表示的。
设序列长度为M，在频域0~2π之间等间隔采样N点，N≥M。
＝|，0≤k≤N-1
根据频域抽样定理，
=IDFT[]=
∴
=
=
=
，称为内插函数
∴=，称为内插公式
当z=时，
=
进一步化简，可得：
=
在数字滤波器的结构与设计中，我们将会看到，频域采样理论及有关公式可提供一种有用的滤波器结构和滤波器设计途径。
3. 4 DFT的应用举例
一、求两个不同实序列、的N点DFT。
=+j
→→→（+）→（）
利用DFT的共轭对称性
DFT[]=（+）
=
DFT[j]=（）
=
DFT[]= （）
二、用DFT计算线性卷积
1、 线性卷积
循环卷积
和的N点DFT分别为：
X1(k)=DFT[]
X2(k)=DFT[]
如果X(k)= X1(k) X2(k)，0≤k≤N-1
则：x(n)= IDFT[X(k)]=
x(n)
3、 循环卷积的计算
由于DFT有快速算法FFT，当N很大时，在频域计算的速度快得多，因而常用DFT（FFT）计算循环卷积。
4、 利用循环卷积计算线性卷积
在实际应用中，为了分析时域离散线性系统对序列进行滤波处理等，需要计算两个序列的线性卷积。与计算循环卷积一样，为了提高运算速度，也希望用DFT（FFT）计算线性卷积。而DFT只能直接用来计算循环卷积。
线性卷积和循环卷积之间有什么关系？
假设h(n)和x(n)都是有限长序列，长度分别是N和M。它们的线性卷积
=x(n)* h(n)= h(n)*x(n)=
=，长度为N+M-1。
取L≥max[N，M]，h(n)和x(n)的循环卷积
h(n) éx(n) =
＝x((n))L =
∴
=
= (3.4.3)
上式说明，等于以L为周期进行周期延拓序列的主值序列。的长度为N+M-1，因此只有当循环卷积长度L≥N+M-1时，等于。
例如：如下图所示，N=4，M=5，线性卷积长度=8，当取循环卷积长度为6时，≠
当取循环卷积长度为8时，=
当取循环卷积长度为10时，=
小结：取L=N+M-1，可用DFT计算线性卷积。这种方法称为快速卷积。用DFT计算线性卷积的框图如下：
当M＞＞N时，L=N+M-1，h(n)需补很多零点，且长序列必须全部输入后才能进行快速计算。因此要求存储容量大，运算时间长，如在处理地震信号和语音信号时。实际中采用的方法是将长序列分段计算，这种分段处理方法有两种：重叠相加法和重叠保留法。
5、 重叠相加法
设序列h(n)长度为N，x(n)为无限长序列。将x(n)均匀分段，每段长度取M，则
式中
h(n)和x(n)的线性卷积
h(n)*x(n)= h(n)*
=
=
式中
运算过程如下图所示：
每一分段卷积的长度为N+M-1，因此与有N-1个点重叠，必须把重叠部分的与相加，才能得到完整的卷积序列。这种方法不要求大的存储容量，且运算和延时也大大减少。
三、用DFT对信号进行谱分析
所谓信号的谱分析，就是计算信号的傅立叶变换。连续信号与系统的傅立叶分析显然不便于直接用计算机进行计算，使其应用受到限制，而DFT是一种时域和频域均离散化的变换，适合数值运算。对连续信号和系统，可以通过时域采样，应用DFT进行近似谱分析。
1、 用DFT对连续信号进行谱分析
傅立叶变换理论：
若信号持续时间有限长，则其频谱无限宽；若频谱有限宽，则其持续时间无限长。
所以，严格地讲，持续时间有限的带限信号是不存在的。
但在工程中，常用DFT对连续信号进行谱分析。
对于持续时间无限长的信号，采样点数太多以至无法存储和计算，只好截取有限点；对于频谱很宽的信号，为防止时域采样后频谱混叠失真，可用预滤波法滤除幅度较小的高频成分，使连续信号的带宽小于折叠频率。这样，连续信号持续时间为有限长，为有限带宽。为了利用DFT对进行频谱分析，先对进行时域采样得x(n)，再对x(n)进行DFT得到X(k)，X(k)为x(n)的傅立叶变换在频率区间[0，2p]上的N点等间隔采样。这里X(k)和x(n)均为有限长。所以用DFT对连续信号进行谱分析是近似的，其近似程度与信号带宽、采样频率和截取长度有关。
设连续信号持续时间为，最高频率为
对以采样间隔采样得x(n)=。设共采样N点，并对作零阶近似，t=nT，dt=T 得： 。
显然，仍是f的连续周期函数，如上图b所示。
对在区间[0，]上等间隔采样N点，采样间隔为F，如下图c所示。
参数、、N、F的关系：
=，=
=，=
∴F=/N=
将代入，得到的采样：
，0≤k≤N-1
令=，x(n)=，
= (3.4.7)
用同样的方法，由
=
推出： =
t=nT，df=F，
x(n)==
=
= (3.4.8)
(3.4.7)说明，连续信号的频谱特性可以通过对连续信号采样并进行DFT再乘以T的近似方法得到。时域采样信号可由(3.4.8)得到。
2、 用DFT进行谱分析存在的问题
栅栏效应：只能看见N个离散采样点的谱特性，看不到的全部频谱特性。
由于栅栏效应，有可能漏掉(挡住)大的频谱分量。为了把原来被“栅栏”挡住的频谱分量检测出来，可以采用在原序列尾部补零的方法，改变序列长度N(即改变DFT变换区间长度)，从而增加频域采样点数和采样点位置，使原来漏掉的某些频谱分量被检测出来。
频率响应的混叠失真及参数选择：
设信号最高频率为，按时域抽样定理，抽样频率＞2，采样间隔（时域抽样之前用预滤波器将高于频率的信号分量加以滤除），否则会产生频率响应的混叠失真。一般情况下取
=（2.5~3.0）
对于DFT，频率函数也要抽样变成离散序列，抽样间隔为F，时域周期为=。F称为频率分辨率，显然F越小，谱分析的结果就越接近原连续信号频谱。所以F较小时，我们称频率分辨率较高。
一组参数：，，T，F，N，。
抽样定理： 2
=NF
F=/N
当N保持不变，要提高谱的分辨率，必须降低。但受抽样定理的限制。如维持不变，为提高频率分辨率可以增加采样点数N，因为NT=，所以只有增加对信号的观察时间。
参数选择：由 2，得N ，
≥
例3.4.1：对实信号进行谱分析，要求谱分辨率F≤10Hz，信号最高频率=2.5kHz，试确定最小记录时间，最少的采样点数。如果不变，要求谱分辨率增加一倍，最少的采样点数和最小的记录时间是多少？
解：F≤10Hz
N =2×2500/10=500
≥=1/10=0.1s
为使频率分辨率提高1倍，F=5Hz，
N =2×2500/5=1000
≥=1/5=0.2s
截断效应：如果持续时间无限长，上述分析中要进行截断处理，所以会产生频率混叠和泄漏现象，从而使谱分析产生误差。
如上图所示，无限长序列的频谱为（只画出一个周期），现截取一个时间段信号，其频谱为。这里，截取有限长个数据，就相当于在时域乘一个矩形窗函数，窗内的数据并不改变。时域中相乘，频域中相当于卷积。卷积的结果与原来的频谱不相同，有失真。这种失真最主要的是造成频谱的“扩散”（拖尾、变宽）。这就是所谓的“频谱泄漏”
应该说明，泄漏也会造成混叠，因为泄漏会导致频谱的扩展，从而使最高频率有可能超过折叠频率/2，造成频率响应的混叠失真。
减小泄漏的方法，首先是取更长的数据，也就是窗宽加宽，当然数据太长，必然使运算存储量都增加，其次数据不要突然截断，也就是不要加矩形窗，而是要缓慢截断，即加各种缓变的窗（例如三角形窗、升余弦窗等），使得窗谱的旁瓣能量更小，卷积后造成的泄漏减小。这个问题在FIR滤波器设计一章中将会讨论到。
