第3章 离散傅里叶变换（DFT） 离散傅里叶变换（Discrete Fourier Transform，DFT）是数字信号处理课程两大知识点之一。本章首先介绍周期序列的离散傅里叶级数，从离散傅里叶级数引出离散傅里叶变换，随后介绍离散傅里叶变换的性质。本章还将介绍用于分析窄带信号的线性调频z变换（Chirp zTransform，CZT）算法，以及时域采样定理的对偶定理——频域采样定理。 3.1周期序列的离散傅里叶级数（DFS） 200多年前，法国科学家傅里叶（Fourier）在研究热传导方程时提出“任何周期函数都可以表示成正弦函数和余弦函数之和的形式”，这即为傅里叶级数的雏形。傅里叶当时并没有严格证明该结论成立的条件，后面经过柯西（Cauchy）、泊松（Poisson），尤其是狄利克雷（Dirichlet）和黎曼（Riemann）等人的努力，才逐渐给出了傅里叶级数收敛的严格证明，从而开创了数学物理学的新时代。 对于级数的概念我们并不陌生，在高等数学中已经学习过幂级数、泰勒级数和麦克劳林级数等。本章将从离散傅里叶级数（Discrete Fourier Series，DFS）出发，引出离散傅里叶变换的概念。 3.1.1离散傅里叶级数的定义 在“信号与系统”课程中已经学习过周期信号的傅里叶级数，即连续时间傅里叶级数（Continuous Time Fourier Series，CTFS），在此简要回顾。如果周期信号x(t)满足狄利克雷条件，那么该周期信号就能分解为三角形式的傅里叶级数，即 x(t)=a0+∑∞k=1akcoskΩ0t+bksinkΩ0t（3.1.1） 其中，k=1,2,3,…,Ω0=2π/T表示基波频率，简称基频； T为信号周期； a0、ak、bk分别表示信号x(t)的直流分量、余弦分量和正弦分量的幅度，可由三角函数信号集的正交性计算： a0=1T∫t0+Tt0x(t)dt（3.1.2） ak=2T∫t0+Tt0x(t)coskΩ0tdt（3.1.3） bk=2T∫t0+Tt0x(t)sinkΩ0tdt（3.1.4） 其中，(t0,t0+T)表示时长为T的任意区间。 图3.1.1给出了周期矩形信号的CTFS示意图。从时域的视角来观察，周期矩形信号是由无穷多余弦信号叠加而成的； 从频域的视角来观察，周期信号映射成了无穷多的线段，这些线段的位置表示余弦信号的频率，线段的长度表示余弦信号的幅度。 图3.1.1从时域和频域同时观察信号（CTFS） 根据欧拉公式，也可以将x(t)分解为指数形式的傅里叶级数，即 x(t)=∑∞k=-∞XkejkΩ0t（3.1.5） 二维码 其中k=0,±1,±2,…，Xk表示傅里叶复系数， Xk=1T∫T/2-T/2x(t)e-jkΩ0tdt（3.1.6） 设x～(n)表示周期为N的周期序列，即 x～(n)=x～(n+rN)（3.1.7） 其中，r为任意整数，周期N为使等式成立的最小正整数。 采用类似的方法，也可以将周期序列x～(n)表示为离散傅里叶级数的形式，即 x～(n)=1N∑N-1k=0X～(k)ej2πNkn=1N∑N-1k=0X～(k)ejω0kn（3.1.8） 其中，ω0=2π/N表示基频，X～(k)表示第k次谐波的系数。 为便于学习和比较，表3.1将连续时间周期信号和离散时间周期信号的傅里叶级数进行了归纳。 表3.1CTFS和DTFS 连续/离散时间 傅里叶级数周期基频基频序 列/信号k次 谐波备注 x(t)=∑∞k=-∞XkejkΩ0tTΩ0=2πTejΩ0tejkΩ0t无穷多个谐波分量 x～(n)=1N∑N-1k=0X～(k)ejω0kn Nω0=2πNejω0nejkω0nN个独立谐波分量 接下来计算k次谐波的系数X～(k)，这需要用到下面的关系式 1N∑N-1n=0ej2πNrn=1N1-ej2πNrN1-ej2πNr=1,r=mN，m为任意整数 0,其他r（3.1.9） 将式（3.1.8）两端同时乘以e-j2πNrN后在n=0~n=N-1的周期内求和，代入式（3.1.9）的结论可得 ∑N-1n=0x～(n)e-j2πNrN=1N∑N-1n=0∑N-1k=0X～(k)ej2πN(k-r)n =∑N-1k=0X～(k)1N∑N-1n=0ej2πN(k-r)n =X～(r)（3.1.10） 将变量r替换为k，可得k次谐波的系数X～(k)的计算公式如下 X～(k)=∑N-1n=0x～(n)e-j2πNkn（3.1.11） 式（3.1.11）表示时域到频域的变换，称为离散傅里叶级数的正变换，用DFS［·］表示； 式（3.1.8）表示频域到时域的变换，称为离散傅里叶级数的反变换，用IDFS［·］表示。DFS和IDFS的关系如下： X～(k)=DFS［x～(n)］=∑N-1n=0x～(n)e-j2πNkn,k=0,±1,±2,… （3.1.12） x～(n)=IDFS［X～(k)］=1N∑N-1k=0X～(k)ej2πNkn,n=0,±1,±2,… （3.1.13） X～(k)也是一个以N为周期的周期序列，即 X～(k+rN)=∑N-1n=0x～(n)e-j2πN(k+rN)N=∑N-1n=0x～(n)e-j2πNkN=X～(k)（3.1.14） 因为x～(n)和X～(k)都是离散周期序列，只需要N个样本即可代表x～(n)和X～(k)的形状，其余部分均是这N个样本的重复出现，故只需要研究它们一个完整周期的样本值即可。 3.1.2离散傅里叶级数的性质 DFS的性质与CTFT、DTFT的性质有许多相似之处，可以对照参考，但最大的不同点在于： DFS的时域序列x～(n)和频域序列X～(k)都是周期的，在DFS性质的证明和使用中要格外注意其周期特性，故DFS的性质中加以“周期”二字来强调，如“周期移位”“周期卷积”。 1. 线性 DFSax～(n)+by～(n)=aX～(k)+bY～(k)（3.1.15） 其中，x～(n)和y～(n)都是周期为N的周期序列，它们各自的DFS分别为X～(k)和Y～(k)，a和b为任意常数。 2. 周期时频翻转 DFS［x～(-n)］=X～(-k)（3.1.16） 证明： DFSx～(-n)=∑N-1n=0x～(-n)e-j2πNkn=∑-(N-1)m=0x～(m)ej2πNkm 因为x～(m)与ej2πNkm都是以N为周期的，即 ∑-(N-1)m=0x～(m)ej2πNkm=∑N-1m=0x～(m)ej2πNkm=X～(-k) 因此 DFS［x～(-n)］=X～(-k) 3. 周期时移特性 DFS［x～(n+m)］=ej2πNkmX～(k)（3.1.17） 证明： DFS［x～(n+m)］=∑N-1n=0x～(n+m)e-j2πNkn =∑N-1+mi=mx～(i)e-j2πNkiej2πNkm =ej2πNkm∑N-1+mi=mx～(i)e-j2πNki 因为x～(i)与e-j2πNki都是以N为周期的，即 ∑N-1+mi=mx～(i)e-j2πNki=∑N-1i=0x～(i)e-j2πNki=X～(k) 因此 DFS［x～(n+m)］=ej2πNkmX～(k) 4. 周期频移特性 DFS［e-j2πNrnx～(n)］=X～(k+r)（3.1.18） 证明： DFSe-j2πNrnx～(n)=∑N-1n=0e-j2πNrnx～(n)e-j2πNkn =∑N-1n=0x～(n)e-j2πN(k+r)n =X～(k+r) 5. 对偶性 DFS［X～(n)］=Nx～(-k)（3.1.19） 证明： 根据IDFS变换公式可得 Nx～(-n)=∑N-1k=0X～(k)e-j2πNkn 上式等号右边与DFS变换公式相同，故将变量n和k互换， Nx～(-k)=∑N-1n=0X～(n)e-j2πNkn 把上式与DFS变换关系结合起来对照，可以看出周期序列X～(n)的k次谐波系数为Nx～(-k)，也就是说X～(n)和Nx～(-k)为DFS变换关系对，即DFS［X～(n)］=Nx～(-k)。 6. 周期共轭对称特性 DFS［x～(n)］=X～(-k)（3.1.20） 证明： 对于复序列x～(n)，其共轭序列x～(n)的DFS为 DFSx～(n)=∑N-1n=0x～(n)e-j2πNkn=∑N-1n=0x～(n)ej2πNkn=X～(-k) 同理可以证明 DFSx～(-n)=X～(k) 进一步可证 DFSRex～(n)=DFS12x～(n)+x～(n)=12X～(k)+X～(-k)=X～e(k) 其中把X～e(k)称作X～(k)的共轭偶对称分量（下标e表示even）。 同理可证， DFSjImx～(n)=12X～(k)-X～(-k)=X～o(k) 其中把X～o(k)称作X～(k)的共轭奇对称分量（下标o表示odd）。 式（3.1.21）归纳了周期序列x～(n)的实（虚）部与其DFS系数共轭偶（奇）对称分量的对偶关系。 x～(n)=Rex～(n)+jImx～(n)  X～(k)=X～e(k)+X～o(k)（3.1.21） 式（3.1.22）归纳了周期序列x～(n)的共轭偶（奇）对称分量与其DFS系数实（虚）部的对偶关系。 x～(n)=x～e(n)+x～o(n)  X～(k)=ReX～(k)+jImX～(k)（3.1.22） 其中x～(n)的共轭偶对称分量为x～e(n)，共轭奇对称分量为x～o(n)，定义如下 x～e(n)=12x～(n)+x～(-n) x～o(n)=12x～(n)-x～(-n) 7. 时域周期卷积定理 若Y～(k)=X～1(k)X～2(k)，则 y～(n)=IDFSY～(k)=∑N-1m=0x～1(m)x～2(n-m)（3.1.23） 证明： y～(n)=IDFSX～1(k)X～2(k)=1N∑N-1k=0X～1(k)·X～2(k)ej2πNkn 代入X～1(k)=∑N-1m=0x～1(m)e-j2πNkm可得 y～(n)=1N∑N-1k=0∑N-1m=0x～1(m)e-j2πNkm·X～2(k)ej2πNkn =1N∑N-1k=0∑N-1m=0x～1(m)X～2(k)e-j2πNk(m-n) =∑N-1m=0x～1(m)1N∑N-1k=0X～2(k)e-j2πNk(m-n) =∑N-1m=0x～1(m)x～2(n-m) 上式为两个周期序列的卷积，故卷积结果也为周期的，且求和只在一个周期上进行（m=0到m=N-1），故把这种卷积称作周期卷积，这与非周期序列的线性卷积不同。 8. 频域周期卷积定理 若y～(n)=x～1(n)x～2(n)，则 Y～(k)=DFSy～(n)=1N∑N-1r=0X～1(r)X～2(k-r)（3.1.24） 例3.1试计算周期序列x(n)=4cos(2.4πn)+2sin(3.2πn)的DTFS，并画出一个周期内的幅度谱和相位谱。 解： 设余弦序列cos(2.4πn)的周期为N1，则 cos［2.4π(n+N1)］=cos(2.4πn)=cos(2.4πn+2mπ) 可得 N1=2π2.4πm=56m 取m=6可使56m成为最小正整数，故余弦序列的周期为N1=5。 同理可得，正弦序列sin(3.2πn)的周期N2=5，取N1和N2的最小公倍数，可知整个序列x(n)的周期为N=5，基波频率ω0=2πN=0.4π，周期序列的x(n)的DTFS表达式为 x(n)=1N∑N-1k=0X～(k)ejω0kn =0.2X～(0)+0.2X～(1)ej0.4πn+0.2X～(2)ej0.8πn+0.2X～(3)ej1.2πn+0.2X～(4)ej1.6πn 根据欧拉公式，序列x(n)可以展开为 x(n)=412ej2.4πn+e-j2.4πn+212jej3.2πn-e-j3.2πn =2ej2.4πn+2e-j2.4πn-jej3.2πn+je-j3.2πn 根据周期关系，如ej2.4πn=ej(2.4πn-2πn)=ej0.4πn，可将上式改写如下 x(n)=2ej0.4πn+2ej1.6πn-jej1.2πn+jej0.8πn =2ej0.4πn+jej0.8πn-jej1.2πn+2ej1.6πn 将上式与DTFS表达式逐项对比可知， 0.2X～(0)=0 0.2X～(1)=2 0.2X～(2)=j 0.2X～(3)=-j 0.2X～(4)=2X～(0)=0 X～(1)=10 X～(2)=5j X～(3)=-5j X～(4)=10 图3.1.2给出了周期序列DTFS在一个周期内的幅度谱和相位谱。 图3.1.2周期序列DTFS的幅度谱和相位谱（一个周期内） 为便于学习，表3.2归纳了离散傅里叶级数的性质。 表3.2离散傅里叶级数的性质 周期序列（周期N）DFS系数（周期N）备注 ax～(n)+by～(n)aX～(k)+bY～(k)线性 x～(-n)X～(-k)周期时频翻转 x～(n+m)ej2πNkmX～(k)周期时移特性 e-j2πNrnx～(n)X～(k+r)周期频移特性 X～(n)Nx～(-k)对偶性 x～(n)X～(-k) x～(-n)X～(k) x～e(n)=12x～(n)+x～(-n)ReX～(k) x～o(n)=12x～(n)-x～(-n)jImX～(k) Rex～(n)X～e(k)=12X～(k)+X～(-k) jImx～(n)X～o(k)=12X～(k)-X～(-k)周期共轭对称特性 ∑N-1m=0x～1(m)x～2(n-m)Y～(k)=X～1(k)·X～2(k)时域周期卷积定理 y～(n)=x～1(n)x～2(n)1N∑N-1r=0X～1(r)X～2(k-r)频域周期卷积定理 3.2有限长序列的离散傅里叶变换（DFT） 3.2.1离散傅里叶变换的定义 3.1节学习了用离散傅里叶级数表示周期序列的方法，这一方法同样适用于有限长序列。对于一个长度为N的有限长序列x(n)，可以把它看作是周期为N的周期序列x～(n)的一个周期，即 x(n)=x～(n),0≤n≤N-1 0,其他n（3.2.1） 如果引入矩形序列RN(n)，式（3.2.1）还可以写为 x(n)=x～(n)RN(n)（3.2.2） 也可以把x～(n)看成x(n)的周期延拓，即 x～(n)=∑∞k=-∞x(n+kN)（3.2.3） 为方便起见，把第一个周期（n=0~n=N-1）称作x～(n)的“主值区间”，或者称x(n)为x～(n)的“主值序列”，即主值区间上的序列。 此时引入符号((n))N表示n对N求余数，令n=n1+n2N，其中0≤n1≤N-1，则n1为n对N的余数，记作n1=((n))N。这样，式（3.2.3）又可以写为 x～(n)=x((n))N（3.2.4） 同理，有限长序列X(k)也可以看作是周期序列X～(k)的主值序列，即 X(k)=X～(k)RN(k)（3.2.5） 从式（3.1.12）和式（3.1.13）可以看出，DFS和IDFS的求和只限定在主值区间，故变换关系也完全适用于主值序列x(n)和X(k)。因此，可得到有限长序列离散傅里叶变换（DFT）及其反变换（IDFT）的定义如下 正变换 X(k)=DFT［x(n)］=∑N-1n=0x(n)e-j2πNkn,k=0,1,…,N-1 （3.2.6） 反变换 x(n)=IDFTX(k)=1N∑N-1k=0X(k)ej2πNkn,n=0,1,…,N-1 （3.2.7） 式（3.2.6）和式（3.2.7）构成了离散傅里叶变换对关系，已知x(n)就能唯一地确定X(k)，同样，已知X(k)也就唯一地确定了x(n)。但是应该记住： 在DFT关系中，有限长序列都是作为周期序列的一个周期来表示的，即DFT具有隐含的周期特性。 也可以在DFT运算中引入矩形序列来代替对k（或n）取值范围的声明，即 正变换 X(k)=DFT［x(n)］=∑N-1n=0x(n)e-j2πNknRN(k) （3.2.8） 反变换 x(n)=IDFTX(k)=1N∑N-1k=0X(k)ej2πNknRN(n) （3.2.9） 3.2.2离散傅里叶变换与其他变换的关系 1. DFT与DFS： 主值序列与周期延拓 DFT具有隐含的周期特性，也就是在DFT的讨论中，有限长序列都是作为周期序列的一个周期来表示的。对于DFT的任何处理，都是先把 图3.2.1DFT与DFS的关系 有限长序列进行周期延拓，再做相应的处理，然后取主值序列后得到处理结果。 换句话说，在频域，DFT结果是DFS的主值序列，DFS是DFT的周期延拓； 在时域，IDFT结果是IDFS的主值序列，IDFS是IDFT的周期延拓，具体关系如图3.2.1所示。 2. DFT与DTFT： 频域均匀采样 周期序列x～(n)的主值序列为x(n)，根据式（2.3.1）可知x(n)的DTFT结果为 X(ejω)=DTFT［x(n)］=∑N-1n=0x(n)e-jωn（3.2.10） 将上式与式（3.2.6）对比可知，当ω=2πNk时，DFT与DTFT结果相同，即 X(k)=X(ejω)|ω=2πNk,k=0,1,…,N-1（3.2.11） X(ejω)是以2π为周期的周期函数，式（3.2.11）的结论表明： X(k)是对X(ejω)在频域上的一个周期内的均匀采样，采样间隔为2π/N。这个关系意味着信号在频域也成为了有限长的离散序列，这就为计算机分析信号频谱打开了通道。 3. DFT与z变换： 单位圆上均匀采样 X(ejω)是单位圆上的z变换，结合式（3.2.10）可知，DFT是z变换在单位圆上的均匀采样，即 X(k)=X(z)|z=ej2πNk,k=0,1,…,N-1（3.2.12） 需要注意的是，在学习和应用DFT与其他变换的关系时，都不要忘记了DFT隐含的周期特性，即强调k的取值范围为k=0,1,…,N-1。如果k的取值为所有整数，那么DFT的结果就会周期性出现（即周期延拓）： 对于DTFT而言，相当于在若干个2π周期内均匀采样，得到的结果为DFS； 对于z变换而言，相当于在单位圆上一圈又一圈地逆时针均匀采样，得到的结果仍然是DFS。 图3.2.2给出了有限长序列DFT与其他变换关系的示意图，可从“三横两纵”来理解有限长序列DFT的推导过程。 “三横”指三种变换关系，即DTFT、DFS和DFT。仍然可用2.3.2节的两句话来深刻理解这三种变换关系，即“傅里叶变换是时域到频域的桥梁”以及“一个域的离散对应另外一个域的周期延拓”。对于N点的DFT变换关系对，在时域和频域都是N点长的样本序列，其周期特性被取主值操作给“隐含”了。 “两纵”指在时、频两个域同时进行的操作。在时域经过了“均匀采样→周期延拓→取主值序列”操作，对应于在频域进行的“周期延拓→均匀采样→取主值序列”操作。通过DFT变换，从时域的N点样本序列出发，得到频域的N点样本序列。 图3.2.2DFT与其他变换关系示意图（“三横两纵”） 例3.2试计算N点长矩形序列的DTFT和DFT结果，并画出它们的幅度谱。 解： 根据定义，N点长矩形序列的DTFT结果为 WN(ejω)=DTFT［RN(n)］=∑N-1n=0e-jωn=1-e-jωN1-e-jω 令ω=2πNk，即可得DFT结果为 二维码 WN(k)=WN(ejω)|ω=2πNk=1-e-jω2kπ1-e-j2πNk=N,k=0 0,其他k N点矩形序列的DTFT和DFT幅度谱如图3.2.3所示，从图中可以形象地看出，DFT是DTFT在［0,2π)区间上的均匀采样。DTFT的包络形状与长度N是密切相关的： N取值越大，幅度谱中的“小山包”（旁瓣）数量越多，宽度越窄； 如果N值确定了，DTFT的包络形状就确定了。 图3.2.3N点矩形序列的DTFT和DFT幅度谱 当DTFT的包络形状确定以后，DFT就只能在这个确定的包络上进行均匀采样。从图3.2.3还可以看出，除了k=0这点，DFT在其他采样点上都“很不幸”地采到了零值，这个结果与理论分析也是吻合的。这些零值都是有意义的，它们如实反映了DTFT包络的变化规律。 如果想让DFT在其他非零值的时刻进行采样，需要提高频域采样的密集程度，可以通过在数据后面补零的方式来实现，下一个例题将进行简要介绍。 例3.3在N点长矩形序列后面补M个零，再计算补零后序列的DTFT和DFT结果，并画出它们的幅度谱。 解： 在N点矩形序列后面补M个零，得到N+M点的数据序列，根据DTFT的定义可得 X(ejω)=DTFT［x(n)］=∑N+M-1n=0RN(n)e-jωn=1-e-jωN1-e-jω=WN(ejω) 与例3.2的结果相比较可以看出，补零前后DTFT的表达式是相同的。此时令ω=2πM+Nk，即可得补零后序列的DFT结果 X(k)=WN(ejω)|ω=2πM+Nk,k=0,1,…,M+N-1 为便于比较，设N=5，图3.2.4给出了不同补零点数的DTFT和DFT幅度谱。 图3.2.4N=5点矩形序列补零后的DTFT和DFT幅度谱 从图3.2.4看出，数据长度N决定了DTFT包络形状，而DFT变换点数N+M决定了采样密集程度。也就是说，只要矩形序列长度确定以后（N=5），DTFT的包络随即固定下来，此时在序列后面补零，只会增加采样的密集程度，但并不能改变DTFT的包络形状。 3.2.3圆周移位与圆周卷积 DFT中的运算与CTFT、DTFT和DFS中的运算有所不同，根本原因就在于DFT具有隐含的周期特性，在此介绍DFT的两个典型运算，即圆周移位和圆周卷积。 1. 圆周移位 圆周移位在有的教材上也称作“循环移位”，可以用“先周期延拓，再线性移位，最后取主值序列”来概括圆周移位。 N点长序列x(n)的m点圆周移位xm(n)是指： 以N为周期对x(n)进行周期延拓，得到周期序列x～(n)，将周期序列x～(n)进行m点线性移位，然后取主值区间（n=0到n=N-1）上的序列值，其定义如下 xm(n)=x((n+m))NRN(n)（3.2.13） 式中得到的xm(n)仍然是一个N点长的序列。x((n+m))N表示周期序列x～(n)的m点线性移位，m为正表示左移，m为负表示右移，即 x((n+m))N=x～(n+m)（3.2.14） 线性移位、周期移位和圆周移位这三种“移位”是有区别的。线性移位可以在时间轴上任意移动； 周期移位移动的对象是周期序列x～(n)，也可以在时间轴上任意移动； 圆周移位移动的对象是有限长序列x(n)，最终受到主值区间的“约束”。 例3.4计算有限长序列x(n)={1,2,3,4,5}0的圆周移位结果x3(n)。 解： 用图示法来分析圆周移位会更加方便。 图3.2.5给出了序列圆周移位的3个过程，即“周期延拓→线性移位→取主值序列”，可以看出，x3(n)表示将周期序列x～(n)左移3位后的主值序列，即 x3(n)={4,5,1,2,3}0 图3.2.5序列的圆周移位过程 二维码 从图3.2.5还可以看出，当对周期序列线性移位时，从主值区间一端移出一段序列值，同时也从主值区间的另外一端移进来相同的一段序列值。借用数据结构中“先进先出”的概念，可以用“左进右出，右进左出”来描述圆周移位的过程，还可以把这个过程想象成在圆周上旋转的过程，这也就是圆周移位中“圆周”二字的缘由，如图3.2.6所示。 图3.2.6圆周移位示意图 2. 圆周卷积 设x1(n)为N1点长序列（0≤n≤N1-1），x2(n)为N2点长序列（0≤n≤N2-1），则y(n)=x1(n)○L x2(n)表示x1(n)和x2(n)的L点圆周卷积，定义如下 y(n)=∑L-1m=0x1(m)x2((n-m))LRL(n) =∑L-1m=0x2(m)x1((n-m))LRL(n)（3.2.15） 其中要求圆周卷积点数L≥max(N1,N2)。一般用符号○L 表示L点圆周卷积，有的教材也把圆周卷积称作“循环卷积”。 式（3.2.15）中的x2((n-m))L或x1((n-m))L只在主值区间取值，表明L点圆周卷积是以L为周期的周期卷积的主值序列。L的取值不同，则延拓的周期就不同，取主值序列得到的圆周卷积结果也就不同。 圆周卷积运算中是圆周移位，线性卷积运算中是线性移位，满足一定条件时，可以用圆周卷积来计算线性卷积，这部分内容将在第4章进行讲解。 例3.5计算序列x1(n)={1,2,3,4}0和x2(n)={3,2,1}0的L点圆周卷积，分别取为L=4和L=6。 解： 可以按照“周期延拓→周期卷积→取主值序列”的步骤，根据定义来计算圆周卷积，结果如下 x1(n)④x2(n)={14,12,20,14}0 x1(n)⑥x2(n)={3,8,14,20,11,4}0 也可以利用MATLAB函数cconv计算两个序列的圆周卷积。如图3.2.7所示，从L=4开始，随着L取值的不同，圆周卷积结果也随之改变，从L=6之后，圆周卷积结果在后面简单补零即可，具体原因将在第4章进行讲解。 图3.2.7L点圆周卷积 3.3离散傅里叶变换的性质 DFS在时域和频域都是周期的，其性质一般加以“周期”二字强调，如“周期移位”“周期卷积”； DFT在时域和频域都是有限长的，通过对DFS取主值序列获得，具有隐含的周期特性，其性质一般加以“圆周”二字强调，如“圆周移位”“圆周卷积”等。除此之外，DFT和DFS的性质是非常相似的，可以对照参考。 1. 线性 DFT［ax(n)+by(n)］=aX(k)+bY(k)（3.3.1） 其中，x(n)和y(n)都是N点长序列，各自的DFT分别为X(k)和Y(k)，a和b为任意常数。 如果x(n)和y(n)的点数不相等，设x(n)为N1点（0≤n≤N1），y(n)为N2点（0≤n≤N2），如果对ax(n)+by(n)进行DFT，则需要分别对x(n)和y(n)进行补零，补到都是N点长序列，且N≥max(N1,N2)。 2. 圆周时频翻转 DFT［x((-n))NRN(n)］=X((-k))NRN(k)（3.3.2） 证明： DFT［x((-n))NRN(n)］=∑N-1n=0x((-n))Ne-j2πNknRN(k) =∑0n=-(N-1)x((n))Nej2πNknRN(k) =∑N-1n=0x((n))Nej2πNknRN(k) =X(（-k)）NRN(k) 该性质表明，有限长序列在时域的圆周翻转，对应着频域的圆周翻转。圆周时域翻转是指： 有限长序列由圆周对称中心在时域进行翻转后取主值序列，对称中心为n=0或n=N/2，根据定义可知，x(n)的圆周时域翻转序列为x((-n))NRN(n)。 根据圆周时域翻转的定义，表达式x((-n))NRN(n)和x(N-n)是相同的（注意： 两种表达式都是在主值区间上取值），故圆周时频翻转性质还可写成 DFT［x(N-n)］=X(N-k)（3.3.3） 为便于大家理解，表3.3给出了有限长序列x(n)圆周时域翻转前后对照表。 表3.3圆周时频翻转对照表 n012…N-2N-1 x(n)x(0)x(1)x(2)…x(N-2)x(N-1) x((-n))NRN(n) 或x(N-n)x(0)x(N-1)x(N-2)…x(2)x(1) 圆周时域翻转后的序列不能写成x(-n)，这是因为DFT中的“移位”“翻转”等操作都是在圆周上进行的，观测/取值区间必须在主值区间上，x(-n)显然不在主值区间范围内。 3. 圆周时移特性 DFT［x((n+m))NRN(n)］=ej2πNmkX(k)RN(k)（3.3.4） 证明： DFT［x((n+m))NRN(n)］=∑N-1n=0x((n+m))Ne-j2πNkn =∑N+m-1p=mx((p))Ne-j2πNk(p-m) =ej2πNmk∑N+m-1p=mx((p))Ne-j2πNkp =ej2πNmk∑N-1p=0x((p))Ne-j2πNkp =ej2πNmkX(k)RN(k) 圆周时移特性表明，序列在时域上的圆周移位，在频域中只引入了一个与频率ωk=2πNk呈正比的线性相移因子，对幅度是没有影响的。 4. 圆周频移特性 DFTe-j2πNrnx(n)=X((k+r))NRN(k)（3.3.5） 证明： DFTe-j2πNrnx(n)=∑N-1n=0e-j2πNrnx(n)e-j2πNknRN(k) =∑N-1n=0x(n)e-j2πN(k+r)nRN(k) =X((k+r))NRN(k) 序列的圆周频移特性和圆周时移特性是对偶的。圆周频移特性表明，序列在频域上的圆周移位，等效于在时域的调制（相乘），因此该特性也称作“调制特性”。 5. 对偶性 DFT［X(n)］=Nx(N-k)（3.3.6） 证明： 根据IDFT公式可得 Nx(N-n)=∑N-1k=0X(k)ej2πNk(N-n)RN(n)=∑N-1k=0X(k)e-j2πNknRN(n) 上式等号右边与DFT变换公式相同，故将变量n和k互换， Nx(N-k)=∑N-1n=0X(n)e-j2πNknRN(k) 把上式与DFT变换关系结合起来对照，可以看出有限长序列X(n)的k次谐波系数为Nx(N-k)，即X(n)和Nx(N-k)为DFT变换关系对，故DFT［X(n)］=Nx(N-k)。 要形成对偶关系，时频变量必须都是离散的或者都是连续的才行。故在CTFT、DFS和DFT中都存在对偶关系，在DTFT中无对偶关系，这是因为DTFT中时域变量是离散的，频域变量是连续的，无法交换变量，当然就不可能存在对偶关系。 6. 圆周共轭对称特性 DFT［x(n)］=X(N-k)（3.3.7） 证明： DFT［x(n)］=∑N-1n=0x(n)e-j2πNknRN(k) =∑N-1n=0x(n)ej2πNknRN(k) =X((-k))NRN(k) =X((N-k))NRN(k) =X(N-k) 结合圆周时频翻转特性，亦可证明 DFT［x(N-n)］=X(k) 进一步可证 DFT［Re(x(n))］=DFT12(x(n)+x(n))=12［X(k)+X(N-k)］=Xep(k) 其中把Xep(k)称作X(k)的圆周共轭偶对称分量，与DFS中的共轭偶对称分量X～e(k)相比，多了一个下标p（p表示周期periodic）。 同理可证， DFT［jIm(x(n))］=12［X(k)-X(N-k)］=Xop(k) 其中把Xop(k)称作X(k)的圆周共轭奇对称分量。 式（3.3.8）归纳了有限长序列x(n)实（虚）部与其DFT的圆周共轭偶（奇）对称分量的对偶关系。 x(n)=Re［x(n)］+jIm［x(n)］  X(k)=Xep(k)+Xop(k)（3.3.8） 式（3.3.9）归纳了有限长序列x(n)圆周共轭偶（奇）对称分量与其DFT实（虚）部的对偶关系。 x(n)=xep(n)+xop(n)  X(k)=ReX(k)+jImX(k)（3.3.9） 其中，x(n)的圆周共轭偶对称分量为xep(n)，圆周共轭奇对称分量为xop(n)，定义如下 xep(n)=12［x(n)+x(N-n)］ xop(n)=12［x(n)-x(N-n)］ 7. 时域圆周卷积定理 设x1(n)为N1点长序列（0≤n≤N1-1），x2(n)为N2点长序列（0≤n≤N2-1），取L≥max(N1,N2)，将序列x1(n)和x2(n)分别补零到L点长序列，再分别做L点的DFT，结果分别为X1(k)和X2(k)。若 y(n)=x1(n)○L x2(n)（3.3.10） 则 Y(k)=DFT［y(n)］=X1(k)X2(k)（3.3.11） 证明： Y(k)=DFT［y(n)］=∑L-1n=0∑L-1m=0x1(m)x2((n-m))LRL(n)e-j2πLkn =∑L-1m=0x1(m)∑L-1n=0x2((n-m))Le-j2πLkn =∑L-1m=0x1(m)e-j2πLkmX2(k) =X1(k)X2(k) 证明的倒数第2步用到了圆周时移特性。该定理表明，两个有限长序列在时域的圆周卷积，等价于在频域的相乘运算。 8. 频域圆周卷积定理 有限长序列x1(n)和x2(n)的定义同上，将它们分别补零到L点长序列，再分别做L点的DFT，结果分别为X1(k)和X2(k)。若 y(n)=x1(n)x2(n)（3.3.12） 则 Y(k)=DFT［y(n)］=1LX1(k)○L X2(k)（3.3.13） 该定理表明，两个有限长序列在时域的相乘运算，等价于在频域的圆周卷积（提醒： 乘法运算中有一个比例因子）。 9. DFT形式下的帕塞瓦尔定理 对长度N的有限长序列x(n)和y(n)，N点DFT结果分别为X(k)和Y(k)，则 ∑N-1n=0x(n)y(n)=1N∑N-1k=0X(k)Y(k)（3.3.14） 若x(n)=y(n)，则有 ∑N-1n=0|x(n)|2=1N∑N-1k=0|X(k)|2（3.3.15） 若x(n)=y(n)且都是实序列，则有 ∑N-1n=0x2(n)=1N∑N-1k=0X2(k)（3.3.16） DFT形式下的帕塞瓦尔定理与其他形式的帕塞瓦尔定理类似，都是表明信号能量在时域计算的结果与频域计算的结果是相等的，只不过DFT形式下的帕塞瓦尔定理，时域和频域都是离散且有限长的。 例3.6设x1(n)和x2(n)都是N点长的实序列，试只用一次N点的DFT运算就给出各自的DFT结果。 解： 可利用DFT的圆周共轭对称特性，仅用一次N点的DFT运算计算出两个N点实序列的DFT结果，从而减少运算量。在此设X1(k)=DFT［x1(n)］，X2(k)=DFT［x2(n)］。 首先，将x1(n)和x2(n)组合为一个N点的复序列，即 y(n)=x1(n)+jx2(n) 故 Y(k)=DFT［y(n)］=DFT［x1(n)+jx2(n)］ =DFT［x1(n)］+jDFT［x2(n)］ =X1(k)+jX2(k) 根据式（3.3.8）可知， X1(k)=Yep(k)=12［Y(k)+Y(N-k)］ 同理 X2(k)=1jYop(k)=12j［Y(k)-Y(N-k)］ 也就是说，利用一次DFT运算求出N点复序列的DFT结果，再按照上式即可求出两个N点长实序列的DFT结果。 例3.7设x(n)为N=8点的有限长实序列，x(n)={1,2,3,-2,4,0,1,3}0，X(k)为N点DFT结果，试计算以下表达式的值。 （1） X(0) （2） ∑N-1k=0X(k) （3） ∑N-1k=0|X(k)|2 解： （1） 根据DFT的公式可得 X(0)=∑N-1n=0x(n)e-j2πNknk=0=∑N-1n=0x(n) 故X(0)=∑N-1n=0x(n)=1+2+3-2+4+0+1+3=12。 （2） 根据IDFT公式x(n)=1N∑N-1k=0X(k)ej2πNknRN(n)，令n=0可得 x(0)=1N∑N-1k=0X(k) 故∑N-1k=0X(k)=Nx(0)=8×1=8。 （3） 根据DFT形式下的帕塞瓦尔定理可知， ∑N-1k=0|X(k)|2=N∑N-1n=0|x(n)|2 =8×12+22+32+(-2)2+42+02+12+32 =352 为便于学习，表3.4归纳了离散傅里叶变换的性质。 表3.4离散傅里叶变换的性质 N点序列N点DFT备注 ax(n)+by(n)aX(k)+bY(k)线性 x((-n))NRN(n) 或x(N-n)X((-k))NRN(k) 或X(N-k)圆周时频翻转 x((n+m))NRN(n)ej2πNmkX(k)圆周时移特性 e-j2πNrnx(n)X((k+r))NRN(k)圆周频移特性 X(n)Nx(N-k)对偶性 x(n)X(N-k) x(N-n)X(k) xep(n)=12x(n)+x(N-n)ReX(k) xop(n)=12x(n)-x(N-n)jImX～(k) Re［x(n)］Xep(k)=12X(k)+X(N-k) jIm［x(n)］Xop(k)=12X(k)-X(N-k)圆周共轭对称特性 x1(n)○L x2(n)X1(k)X2(k)时域圆周卷积定理 x1(n)x2(n)1LX1(k)○L X2(k)频域圆周卷积定理 ∑N-1n=0|x(n)|2=1N∑N-1k=0|X(k)|2DFT形式下的帕塞瓦尔定理 3.4频域采样定理 一个域的离散，对应另外一个域的周期延拓，这个关系是对偶的。在时域采样，频域会产生周期延拓，延拓的周期就是采样率； 在频域采样，时域也会产生周期延拓，延拓的周期就是频域采样点数。 2.1节介绍了时域采样定理与插值重构，本节将学习频域采样定理与插值重构。 3.4.1频域采样 频域采样定理： 设M点有限长序列x(n)的离散时间傅里叶变换为X(ejω)，对X(ejω)在区间［0,2π)上作N点均匀采样，得到频域样本XN(k)。只有当N≥M时，才能由频域样本值无失真地恢复原时域序列x(n)。 可以根据DFT与其他变换的关系来理解频域采样定理，图3.4.1给出了“频域采样，时域周期延拓”的示意图。 图3.4.1频域采样，时域周期延拓 对X(ejω)在区间［0,2π)上作N点均匀采样，对应着时域的周期延拓，延拓周期为N，得到周期序列x～(n) x～(n)=∑∞k=-∞x(n+kN)（3.4.1） 在主值区间n=0~n=N-1取值，可得时域序列xN(n)为 xN(n)=∑∞k=-∞x(n+kN)RN(n)（3.4.2） 很显然，并不能保证N点的xN(n)与M点的原始序列x(n)完全相同。只有当采样点数N≥M时，在时域周期延拓的过程中才不会发生混叠现象，此时才能用N点的xN(n)去完全（无失真）恢复出M点的x(n)。 图3.4.2所示为时域周期延拓过程中未发生混叠的情况，此时频域采样点数大于原始序列长度。与原始序列x(n)相比，xN(n)在后端多出来(N-M)个零。 图3.4.3所示为时域周期延拓过程中发生混叠的情况，此时频域采样点数小于原始序列长度。只有在M-N≤n≤N-1范围内未发生混叠，在这个区间内，才有xN(n)=x(n)。 例3.8设x(n)为M=11点的三角形序列，即 x(n)=n,0≤n≤5 -n+10,61表示螺旋线内旋，W0<1表示螺旋线外旋，W0=1表示是半径为A0的一段圆弧。0表示相邻样本点之间的角度差，0>0表示螺旋线是逆时针旋转，0<0表示螺旋线是顺时针旋转。 采样点zk的轨迹如图3.5.1所示。如果M=N，A=A0ejθ0=1，W=W0ej0=e-j2πN，zk均匀分布在整个单位圆上，此时的CZT算法就简化为DFT算法。 图3.5.1CZT在z平面上采样的螺线轨迹 更一般地，X(z)在zk处的采样值为 X(zk)=∑N-1n=0x(n)z-nk,k=0,1,…,M-1（3.5.4） 代入zk=AW-k可得 X(zk)=∑N-1n=0x(n)A-nWnk,k=0,1,…,M-1（3.5.5） 根据布鲁斯坦等式 nk=12［n2+k2-(k-n)2］（3.5.6） 可知X(zk)可以通过求g(n)与h(n)的线性卷积，再乘以Wk22得到 X(zk)=Wk22·∑N-1n=0x(n)A-nWn22W-(k-n)22 =Wk22·∑N-1n=0g(n)h(k-n),k=0,1,…,M-1（3.5.7） 其中 g(n)=x(n)A-nWn22（3.5.8） h(n)=W-n22（3.5.9） CZT算法的流程如图3.5.2所示，输入的是N点有限长序列x(n)，输出的是z平面上的M个采样值X(zk)。由于h(n)=W-n22是一个频率随时间n线性增长的复指数序列，在雷达系统中这种信号称为线性调频信号（这种信号听起来像鸟叫声，英文是Chirp Signal），故这种变换称作线性调频z变换，常用于雷达和声呐信号的脉冲压缩处理。 图3.5.2CZT算法流程图 在图3.5.2中，g(n)与h(n)线性卷积的过程可由圆周卷积实现，而圆周卷积的过程可由DFT算法来解决（第4章内容），而DFT算法还可由FFT算法来快速实现（第5章内容），因此整个CZT算法流程完全可以由FFT算法快速实现。 习题 1. 图T3.1中所示的序列周期为4，请确定该序列的DFS系数。 图T3.1 2. 如果x～(n)是一个周期为N的周期序列，则它也是周期为2N的周期序列。将x～(n)看作周期为N的周期序列，用X～1(k)表示其DFS系数，再将x～(n)看作周期为2N的周期序列，用X～2(k)表示其DFS系数，试用X～1(k)来表示X～2(k)。 3. 周期序列x～(n)和y～(n)的周期分别为N和M，且 w～(n)·x～(n)=y～(n) （1） 试证明w～(n)也是周期序列，且周期为MN。 （2） 设周期序列x～(n)、y～(n)和w～(n)的DFS系数分别为X～(k)、Y～(k)和W～(k)，试用X～(k)和Y～(k)来表示W～(k)。 4. 计算以下序列的DFT。 （1） {1,1,-1,-1}0 （2） {1,j,-1,-j}0 （3） x(n)=cnRN(n) （4） x(n)=sin2πNnRN(n) 5. 请给出以下序列的DFT闭合表达式。 （1） x(n)=ejω0nRN(n)（2） x(n)=cos(ω0n)·RN(n) （3） x(n)=sin(ω0n)·RN(n)（4） x(n)=nRN(n) 6. 已知序列x(n)如下所示,请计算其10点和20点的DFT结果。 x(n)=an,6≤n≤9 0,其他n 7. 已知序列x(n)的DFT结果如下，求其IDFT结果，其中m为正整数，且0