第3章 离散傅里叶变换(DFT) 及其快速算法(FFT) 3.1　学习要点与重要公式 3.2　频率域采样 3.3　循环卷积和线性卷积的快速计算以及信号的频谱分析 3.4　例题 3.5　教材第3章习题与上机题解答 3.6　教材第4章习题与上机题解答

3.1 学习要点与重要公式 3.1.1 学习要点 （1） DFT的定义和物理意义， DFT和FT、 ZT之间的关系； 3.1 学习要点与重要公式 3.1.1 学习要点 　　 （1） DFT的定义和物理意义， DFT和FT、 ZT之间的关系； 　　 （2） DFT的重要性质和定理： 隐含周期性、 循环移位性质、 共轭对称性、 实序列 DFT的特点、 循环卷积定理、 离散巴塞伐尔定理； 　　 （3） 频率域采样定理； 　　 （4） FFT的基本原理及其应用。

3.1.2 重要公式 　　1） 定义 k=0, 1, …, N－1 k=0, 1, …, N－1 　　2） 隐含周期性

　　3） 线性性质 若 ，则 　　4） 时域循环移位性质 　　5) 频域循环移位性质

　　6） 循环卷积定理 　　 循环卷积： L x(n) 循环卷积的矩阵表示：

循环卷积定理： 若 　　　　　　　yc(n)=h(n) L x(n) 则 Yc(k)=DFT［yc(n)］L=H(k)X(k) k=0, 1, 2, …, L－1 其中 H(k)=DFT［h(n)］L, X(k)=DFT［x(n)］L 　　6) 离散巴塞伐尔定理

　　7） 共轭对称性质 　　(1) 长度为N的共轭对称序列xep(n)与反共轭对称序列xop(n): 序列x(n)的共轭对称分量与共轭反对称分量：

　　（2） 如果　　x(n)=xr(n)+jxi(n) 且　　　　　　　　X(k)=Xep(k)+Xop(k) 则　　　　Xep(k)=DFT［xr(n)］, Xop(k)=DFT［jxi(n)］ （3） 如果x(n)=xep(n)+xop(n) 且　　　　X(k)=Xr(k)+jXi(k) 则　　　　Xr(k)=DFT［xep(n)］, jXi(k)=DFT［xop(n)］ （4） 实序列DFT及FT的特点: 假设x(n)是实序列， X(k)=DFT［x(n)］， 则 　　　　　X(k)=X*(N－k) 　　　　　|X(k)|=|X(N－k)|, θ(k)=－θ(N－k)

3.2 频 率 域 采 样 我们知道， 时域采样和频域采样各有相应的采样定理。 频域采样定理包含以下内容: 　　 3.2 频 率 域 采 样 　　我们知道， 时域采样和频域采样各有相应的采样定理。 频域采样定理包含以下内容: 　　（1） 设 x(n)是任意序列， X(ejω)=FT［x(n)］，对X(ejω)等间隔采样得到 k=0，1，2，3，…，N－1 则

　　(2) 如果x(n)的长度为M， 只有当频域采样点数N≥M时， xN(n)=x(n)， 否则 　　通过频率域采样得到频域离散序列xN(k)， 再对xN(k)进行IDFT得到的序列xN(n)应是原序列x(n)以采样点数N为周期进行周期化后的主值区序列， 这一概念非常重要。

　　(3) 如果在频率域采样的点数满足频率域采样定理， 即采样点数N大于等于序列的长度M， 则可以用频率采样得到的离散函数X(k)恢复原序列的Z变换X(z)， 公式为 式中 上面第一式称为z域内插公式， 第二式称为内插函数。

以及信号的频谱分析 3.3.1 循环卷积的快速计算 3.3 循环卷积和线性卷积的快速计算 　　　3.3 循环卷积和线性卷积的快速计算 　　　　以及信号的频谱分析 3.3.1 循环卷积的快速计算 　　如果两个序列的长度均不很长， 可以直接采用循环卷积的矩阵乘法计算其循环卷积； 如果序列较长， 可以采用快速算法。 快速算法的理论基础是循环卷积定理。 设h(n)的长度为N， x(n)的长度为M, 计算yc(n)=h(n) L x(n)的快速算法如下：

（1） 计算 k=0,1,2,3,…，L－1，L=max［N, M］ 　　（2） 计算 　　　　Yc(k)=H(k)X(k) k=0, 1, 2, …, L－1 　　（3） 计算 　　　　yc(n)=IDFT［Yc(k)］L n=0, 1, 2, …, L－1 　　说明： 如上计算过程中的DFT和IDFT均采用FFT算法时， 才称为快速算法， 否则比直接在时域计算循环卷积的运算量大3倍以上。

3.3.2 线性卷积的快速计算——快速卷积法 序列h(n)和x(n)的长度分别为N和M， L=N+M－1， 求y(n)=h(n)*x(n)的方法如下：  　　（1）在h(n)的尾部加L－N个零点， 在x(n)的尾部加L－M个零点； 　　（2）计算L点的H(k)=FFT［h(n)］和L点的X(k)=FFT［x(n)］; 　　（3） 计算Y(k)=H(k)X(k)； 　　（4） 计算Y(n)=IFFT［Y(k)］， n=0，1，2，3，…，L-1。 　　但当h(n)和x(n)中任一个的长度很长或者无限长时， 需用书上介绍的重叠相加法和重叠保留法。

3.3.3 用DFT/FFT进行频谱分析 　　对序列进行N点的DFT/FFT就是对序列频域的N点离散采样， 采样点的频率为ωk=2πk/N, k=0, 1, 2, …, N－1。  　　对信号进行频谱分析要关心三个问题： 频谱分辨率、 频谱分析范围和分析误差。 　　DFT的分辨率指的是频域采样间隔2π/N， 用DFT/FFT进行频谱分析时， 在相邻采点之间的频谱是不知道的， 因此频率分辨率是一个重要指标， 希望分辨率高， 即2π/N要小， DFT的变换区间N要大。

　　当然， 截取信号的长度要足够长。 但如果截取的长度不够长， 而依靠在所截取的序列尾部加零点， 增加变换区间长度， 也不会提高分辨率。 例如， 分析周期序列的频谱， 只观察了一个周期的1/4长度， 用这些数据进行DFT， 再通过尾部增加零点， 加大DFT的变换区间N， 也不能分辨出是周期序列， 更不能得到周期序列的精确频率。  用DFT/FFT对序列进行频谱分析， 频谱分析范围为π; 用DFT/FFT对模拟信号进行频谱分析， 频谱分析范围为采样频率的一半， 即0.5Fs。  用DFT/FFT对信号进行谱分析的误差表现在三个方面， 即混叠现象、 栅栏效应和截断效应。 截断效应包括泄漏和谱间干扰。

　　 3.4 例 题 　　［例3.4.1］ 设x(n)为存在傅里叶变换的任意序列， 其Z变换为X(z)，X(k)是对X(z)在单位圆上的N点等间隔采样， 即 　　求X(k)的N点离散傅里叶逆变换（记为xN(n)）与x(n)的关系式。  　　解: 由题意知

即X(k)是对X(ejω)在［0, 2π］上的N点等间隔采样。 由于X(ejω)是以2π为周期的， 所以采样序列 即　　　以N为周期。 所以它必然与一周期序列　　　相对应， 　　为　　　的DFS系数。

　　为了导出　　　与x(n)之间的关系， 应将上式中的 所以

因为 所以 即　　　是x(n)的周期延拓序列， 由DFT与DFS的关系可得出

xN(n)=IDFT［X(k)］为x(n)的周期延拓序列（以N为延拓周期）的主值序列。 以后这一结论可以直接引用。  　　［例3.4.2］ 已知 　　　　　　x(n)=R8(n), X(ejω)=FT［x(n)］ 对X(ejω)采样得到X(k)， 求

　　解：直接根据频域采样概念得到 　　［例3.4.3］ 令X(k)表示x(n)的N点DFT， 分别证明： 　（1） 如果x(n)满足关系式 　　　　　　　　x(n)=－x(N－1－n) 则 　　　　　　　　　X(0)=0 （2） 当N为偶数时， 如果 　　　　　　　　　x(n)=x(N－1－n)

　　证 （1） 直接按DFT定义即可得证。 因为 所以 ① 令n=N－1－m， 则 ② ①式+②式得

所以 　　　　　　　　　　　X(0)=0 （2） 因为x(n)=x(N－1－n)， 所以 令m=N－1－n， 则上式可写成

当　　　时（N为偶数）， 因为 所以 因此证得

　　［例3.4.4］　有限时宽序列的N点离散傅里叶变换相当于其Z变换在单位圆上的N点等间隔采样。 我们希望求出X(z)在半径为r的圆上的N点等间隔采样， 即 试给出一种用DFT计算得到　　　的算法。 　　解: 因为

所以 由此可见， 先对x(n)乘以指数序列r－n， 然后再进行N点DFT， 即可得到题中所要求的复频域采样　　　。

　　［例3.4.5］ 长度为N的一个有限长序列x(n)的N点DFT为X(k)。 另一个长度为2N的序列y(n)定义为 试用X(k)表示y(n)的2N点离散傅里叶变换Y(k)。 　　解: 该题可以直接按DFT定义求解。

上面最后一步采用的是X(k)以N为周期的概念。

　　［例3.4.6］ 用DFT对模拟信号进行谱分析， 设模拟信号xa(t)的最高频率为200 Hz， 以奈奎斯特频率采样得到时域离散序列x(n)=xa(nT)， 要求频率分辨率为10 Hz。 假设模拟 信号频谱Xa(jΩ)如图3.4.1所示， 试画出X(ejω)=FT［x(n)］和X(k)=DFT［x(n)］的谱线图， 并标出每个k值对应的数字频率ωk和模拟频率fk的取值。

图3.4.1

　　解: 因为最高频率fmax=200 Hz， 频率分辨率F=10 Hz， 所以采样频率fs为 观察时间 采样点数 　　　　　　N=Tρfs=0.1×400=40个 所以， 对xa(t)进行采样得 　　　　　　x(n)=xa(nT) n=0, 1, …, 39

Xa(jf)、 X(ejω)及X((k))N分别如图3.4.2（a）、 （b）、 （c）所示。

图3.4.2

　　当fs=2fmax时， f=fmax 对应　　　　　　　　　　　　， 由　　　 　 可求得　　　 ； 当fs>2fmax时，fmax对应 的数字频率ω=2πfmaxT<π。 Xa(if)与X(k)的对应关系（由图3.4.2（a）、 （c）可看出）为

　　该例题主要说明了模拟信号xa(t)的时域采样序列x(n)的 N点离散傅里叶变换X(k)与xa(t)的频谱Xa(jf)之间的对应关 系。 只有搞清该关系， 才能由X(k)看出Xa(jf)的频谱特征。 否则， 即使计算出X(k)， 也搞不清X(k)的第k条谱线对应于Xa(jf)的哪个频率点的采样， 这样就达不到谱分析的目的。 实际中， X(k)求出后， 也可以将横坐标换算成模拟频率， 换算公式为fk=kF=k/(NT)。 直接作Xa(kF)=Xa(fk)=TX(k)谱线图。

　　［例3.4.7］ 已知x(n)长度为N， X(z)=ZT［x(n)］。 要求计算X(z)在单位圆上的M个等间隔采样。 假定M<N， 试设计一种计算M个采样值的方法， 它只需计算一次M点DFT。 　解: 这是一个典型的频域采样理论应用问题。 根据频域采样、 时域周期延拓以及DFT的惟一性概念， 容易解答该题。 　　由频域采样理论知道， 如果 即X(k)是X(z)在单位圆上的M点等间隔采样, 则

当然 即首先将x(n)以M为周期进行周期延拓， 取主值区序列xM(n)， 最后进行M点DFT则可得到 　　应当注意， M<N， 所以周期延拓x(n)时， 有重叠区， xM(n)在重叠区上的值等于重叠在n点处的所有序列值相加。

显然， 由于频域采样点数M<N， 不满足频域采样定理， 所以， 不能由X(k)恢复x(n)，即丢失了x(n)的频谱信息。  ［例3 　　显然， 由于频域采样点数M<N， 不满足频域采样定理， 所以， 不能由X(k)恢复x(n)，即丢失了x(n)的频谱信息。 　［例3.4.8］ 已知序列 　　　　　x(n)={1, 2, 2, 1}, h(n)={3, 2, －1, 1} （1）计算5点循环卷积y5(n)=x(n) L h(n);  　　（2）用计算循环卷积的方法计算线性卷积y(n)=x(n)*h(n)。 　　解：(1)这里是2个短序列的循环卷积计算， 可以用矩阵相乘的方法(即用教材第82页式(3.2.7)）计算， 也可以用类似于线性卷积的列表法。 因为要求5点循环卷积， 因此每个序列尾部加一个零值点， 按照教材式(3.2.7)写出

得到y5(n)={4, 9, 9, 6, 2}。 注意上面矩阵方程右边第一个5×5矩阵称为x(n)的循环矩阵， 它的第一行是x(n)的5点循环倒相， 第二行是第一行的向右循环移一位， 第三行是第二行向右循环移一位， 依次类推。

用列表法可以省去写矩阵方程， 下面用列表法解：

　　表中的第一行是h(n)序列， 第2、 3、 4、 5、 6行的前五列即是x(n)的循环矩阵的对应行。 同样得到y5(n)={４, 9, 9, 6, 2}。  　　（2） 我们知道只有当循环卷积的长度大于等于线性卷积结果的长度时， 循环卷积的结果才能等于线性卷积的结果。 该题目中线性卷积的长度为L＝4+4－1=7， 因此循环卷积的长度可选L=7， 这样两个序列的尾部分别加3个零点后， 进行7点循环卷积， 其结果就是线性卷积的结果。 即

得到 　　　　　　y(n)=x(n)*h(n)={3, 8, 9, 6, 2, 1, 1}

　　［例3.4.9］　已知实序列x(n)和y(n)的DFT分别为X(k)和Y(k)， 试给出一种计算一次IDFT就可得出x(n)和y(n)的计算方法。 （选自2004年北京交通大学硕士研究生入学试题。） 　　解： 令 w(n)=x(n)+jy(n) 对其进行DFT， 得到 　　　　　　　　　W(k)=X(k)+jY(k) 　　　　　　　　　w(n)=IDFT［W(k)］ 因为x(n)和y(n)分别为实序列， 因此 　　　　　　　　　x(n)=Re［w(n)］ 　　　　　　　　　y(n)=Im［w(n)］

　　［例3.4.10］已知x(n) (n=0， 1， 2， …， 1023)， h(n) (n=0， 1， 2， …， 15)。 在进行线性卷积时， 每次只能进行16点线性卷积运算。 试问为了得到y(n)=x(n)*h(n)的正确结果， 原始数据应作怎样处理， 并如何进行运算。 （选自1996年西安电子科技大学硕士研究生入学试题。） 　　解： 将x(n)进行分组后， 采用书上介绍的重叠相加法。 x(n)的长度为1024点， 按照16分组， 共分64组， 记为xi(n), i=0, 1, 2, …, 63。 即

式中， yi(n)=xi(n)*h(n), i=0, 1, 2, …, 63。 可以用FFT计算16点的线性卷积yi(n)。 最后结果y(n)的长度为1024+16－1＝1039。 　　［例3.4.11］ x(n)是一个长度M=142的信号序列， 即： x(n)=0， 当n<0或n≥M时。现希望用N＝100的DFT来分析频谱。试问：如何通过一次N=100的DFT求得　　　　　　　　　　,　　 k=0, 1, 2, …, 99； 这样进行频谱分析是否存在误差？

　　解： 通过频率域采样得到频域离散函数， 再对其进行IDFT得到的序列应是原序列x(n)以N为周期进行周期化后的主值序列。 按照这一概念， 在频域0~2π采样100点， 那么相应的时域应以100为周期进行延拓后截取主值区。 该题要求用一次100点的DFT求得， 可以用下式计算： 式中, k对应的频率为　　　　　　。 这样进行频谱分析存在误差， 误差是因为时域混叠引起的。

3.5 教材第3章习题与上机题解答 1． 计算以下序列的N点DFT， 在变换区间0≤n≤N－1内， 序列定义为 (1) x(n)=1 　　3.5 教材第3章习题与上机题解答 　　 1． 计算以下序列的N点DFT， 在变换区间0≤n≤N－1内， 序列定义为 　　 (1) x(n)=1 　　 (2) x(n)=δ(n) 　　 (3) x(n)=δ(n－n0) 0<n0<N 　　 (4) x(n)=Rm(n) 0<m<N 　　 (5) 　　　　　　　　　　　  　 (6) 　　　　　　　　　　　 

　　(7) x(n)=ejω0nRN(n) 　 (8) x(n)=sin(ω0n)RN(n) 　 (9) x(n)=cos(ω0n)RN(N) 　 (10) x(n)=nRN(n) 　　解： (1)

（2） （3） (4)

(5) 0≤k≤N－1

(6)

0≤k≤N－1 (7)

或 （8） 解法一 直接计算：

　　解法二 由DFT的共轭对称性求解。 　　因为 所以 所以

即 　　结果与解法一所得结果相同。 此题验证了共轭对称性。 　　(9) 解法一 直接计算:

　　解法二 由DFT共轭对称性可得同样结果。  　　因为

（10） 解法一 上式直接计算较难， 可根据循环移位性质来求解X(k)。 因为x(n)=nRN(n)， 所以 x(n)－x((n－1))NRN(n)+Nδ(n)=RN(n) 等式两边进行DFT， 得到 X(k)－X(k)WkN+N=Nδ(k)

故 当k=0时， 可直接计算得出X(0)为 这样， X(k)可写成如下形式：

解法二 k=0时， k≠0时，

，即 所以， 　 2． 已知下列X(k)， 求x(n)=IDFT［X(k)］ (1)

(2) 其中， m为正整数， 0<m<N/2, N为变换区间长度。

解: （1） n=0, 1, …, N－1

(2) n=0, 1, …, N－1

　　3． 已知长度为N=10的两个有限长序列： ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ 做图表示x1(n)、 x2(n)和y(n)=x1(n) * x2(n)， 循环卷积区间长度L=10。  　　解: x1(n)、 x2(n)和y(n)=x1(n) * x2(n)分别如题3解图（a）、 （b）、 （c）所示。

题3解图

　　4． 证明DFT的对称定理， 即假设X(k)=DFT［x(n)］， 　　　　　　　　　DFT［X(n)］=Nx(N－k) 证： 因为 所以

由于 ≤ ≤ 所以 DFT［X(n)］=Nx(N－k) k=0, 1, …, N－1 5． 如果X(k)=DFT［x(n)］， 证明DFT的初值定理 证: 由IDFT定义式

可知 　　6． 设x(n)的长度为N， 且 　　　　X(k)=DFT［x(n)］ 0≤k≤N－1 令 　　　h(n)=x((n))NRmN(n) m为自然数 　　　H(k)=DFT［h(n)］mN 0≤k≤mN－1 求H(k)与X(k)的关系式。  　　解: H(k)=DFT［h(n)］ 0≤k≤mN－1 　　令n=n′+lN, l=0, 1, …, m－1, n′=0, 1, …, N－1, 则

因为

所以 　　7． 证明: 若x(n)为实序列， X(k)=DFT［x(n)］N， 则X(k)为共轭对称序列， 即X(k)=X*（N－k)； 若x(n)实偶对称， 即x(n)=x(N－n)， 则X(k)也实偶对称； 若x(n)实奇对称， 即x(n)=－x(N－n)， 则X(k)为纯虚函数并奇对称。

　　证: (1) 由教材(3.2.17)~(3.2.20)式知道， 如果将x(n)表 示为 　　　　　　x(n)=xr(n)+jxi(n) 则 　　　　X(k)=DFT［x(n)］=Xep(k)+Xop(k) 其中， Xep(k)=DFT［xr(n)］， 是X(k)的共轭对称分量； Xop(k)=DFT［jxi(n)］, 是X(k)的共轭反对称分量。 所以， 如果x(n)为实序列， 则Xop(k)=DFT［jxi(n)］=0， 故X(k)= DFT［x(n)］=Xep(k)， 即X(k)=X*(N－k)。

（2） 由DFT的共轭对称性可知， 如果 　　　　　x(n)=xep(n)+xop(n) 且 　　　　　X(k)=Re［X(k)］+j Im［X(k)］ 则 　　Re［X(k)］=DFT［xep(n)］, j Im［X(k)］=DFT［xop(n)］ 所以， 当x(n)=x(N－n)时， 等价于上式中xop(n)=0, x(n)中只有xep(n)成分， 所以X(k)只有实部， 即X(k)为实函数。 又由（1）证明结果知道， 实序列的DFT必然为共轭对称函数， 即X(k)=X*(N－k)=X(N－k)， 所以X(k)实偶对称。

　　同理， 当x(n)=－x(N－n)时， 等价于x(n)只有xop(n)成分（即xep(n)=0）， 故X(k)只有纯虚部， 且由于x(n)为实序列， 即X(k)共轭对称， X(k)=X*(N－k)=－X(N－k), 为纯虚奇函数。　8． 证明频域循环移位性质： 设X(k)=DFT［x(n)］， Y(k)=DFT［y(n)］， 如果Y(k)=X((k+l))NRN(k)， 则

证：

令m=k+l, 则 9． 已知x(n)长度为N， X(k)=DFT［x(n)］， ≤ ≤ ≤ ≤

≤ ≤ 求Y(k)与X(k)的关系式。  　　解:

　　10． 证明离散相关定理。 若 　　　　　　　　　X(k)=X1* (k)Ｘ2(k) 则 证： 根据DFT的惟一性， 只要证明 即可。

令m=l+n， 则 所以 ≤ ≤

当然也可以直接计算X(k)=X1 *(k)X2(k)的IDFT。 0≤n≤N－1

由于 0≤n≤N－1 所以

　　11． 证明离散帕塞瓦尔定理。 若X(k)=DFT［x(n)］， 则 证：

　　12． 已知f(n)=x(n)+jy(n)， x(n)与y(n)均为长度为N的实序列。 设 　　　　　F(k)=DFT［f(n)］N 0≤k≤N－1 (1) 　　(2) 　　F(k)=1+jN 试求X(k)=DFT［x(n)］N， Y(k)=DFT［y(n)］N以及x(n)和y(n)。 　　解: 由DFT的共轭对称性可知 　　　　　　x(n)　　X(k)=Fep(k) 　　　　　　jy(n)　　jY(k)=Fop(k)

方法一 （1）

0≤n≤N－1 由于 0≤n, m≤N－1

所以 x(n)=an 0≤n≤N－1 同理 y(n)=bn 0≤n≤N－1 （2） F(k)=1+jN ，

方法二 令 只要证明A(k)为共轭对称的，B(k)为共轭反对称， 则就会有 A(k)=Fep(k)=X(k), B(k)=Fop(k)=jY(k) 因为 ，共轭对称

，共轭反对称 所以

由方法一知 x(n)=IDFT［X(k)］=anRN(n) 　　　　 y(n)=IDFT［Y(k)］=bnRN(n) 13． 已知序列x(n)=anu(n)， 0<a<1, 对x(n)的Z变换X(z)在单位圆上等间隔采样N点， 采样序列为 求有限长序列IDFT［X(k)］N。  　　解: 我们知道， , 是以2π为周期的周期函数， 所以

① 　　　以N为周期， 将　　　看作一周期序列　　　的DFS系数， 则 ② 由式①知　　　为 ③

将式③代入式②得到 由于 所以

由题意知 所以根据有关X(k)与xN(n)的周期延拓序列的DFS系数的关系有

由于0≤n≤N－1， 所以 ≥ ≥ 因此 说明： 平时解题时， 本题推导

的过程可省去， 直接引用频域采样理论给出的结论（教材中式（3.3.2）和(3.3.3)）即可。 　　14． 两个有限长序列x(n)和y(n)的零值区间为 　　　　　x(n)=0 n<0, 8≤n 　　　　　y(n)=0 n<0, 20≤n 对每个序列作20点DFT， 即 　　　　　X(k)=DFT［x(n)］ k=0, 1, …, 19 　　　　　Y(k)=DFT［y(n)］ k=0, 1, …, 19 试问在哪些点上f(n)与x(n)*y(n)值相等, 为什么？

　　解: 如前所述， 记fl(n)=x(n)*y(n)，而f(n)=IDFT［F(k)］=x(n) 20 y(n)。 fl(n)长度为27， f(n)长度为20。 由教材中式（3.4.3）知道f(n)与fl(n)的关系为 只有在如上周期延拓序列中无混叠的点上， 才满足f(n)=fl(n),所以 f(n)=fl(n)=x(n)*y(n) 7≤n≤19

　　15． 已知实序列x(n)的8点DFT的前5个值为0.25, 0.125-j0.3018, 0, 0.125-j0.0518, 0。  　　（1） 求X(k)的其余3点的值；  （2） 求X1(k)=DFT［x1(n)］8； ，求 。 （3）

解： （1）因为x(n)是实序列， 由第7题证明结果有X(k)=X. (N－k)， 即X(N－k)=X 　　解： （1）因为x(n)是实序列， 由第7题证明结果有X(k)=X*(N－k)， 即X(N－k)=X*(k), 所以， X（k）的其余3点值为 　　　{X(5), X(6), X(7)}={0.125+j0.0518, 0, 0.125+j0.3018 （2） 根据DFT的时域循环移位性质， (3)

　　16． x(n)、 x1(n)和x2(n)分别如题16图(a)、 (b)和(c)所示， 已知X(k)=DFT［x(n)］8。 求 ［注: 用X(k)表示X1(k)和X2(k)。］ 　　解： 因为x1(n)=x((n+3))8R8(n), x2(n)=x((n－2))8R8(n)， 所以根据DFT的时域循环移位性质得到

　　17． 设x(n)是长度为N的因果序列， 且 试确定Y(k)与X(ejω)的关系式。

　　解： y(n)是x(n)以M为周期的周期延拓序列的主值序列， 根据频域采样理论得到 　　18． 用微处理机对实数序列作谱分析， 要求谱分辨率F≤50 Hz， 信号最高频率为 1 kHz， 试确定以下各参数： 　　 　　(1) 最小记录时间Tp min；  　 (2) 最大取样间隔Tmax；  　　(3) 最少采样点数Nmin；  　　(4) 在频带宽度不变的情况下， 使频率分辨率提高1倍（即F缩小一半）的N值。 

　　解: （1） 已知F=50 Hz， 因而 （2） （3）

　　（4） 频带宽度不变就意味着采样间隔T不变， 应该使记录时间扩大1倍， 即为0.04 s， 实现频率分辨率提高1倍（F变为原来的1/2）。 　　19． 已知调幅信号的载波频率fc=1 kHz， 调制信号频率fm=100 Hz， 用FFT对其进行谱分析， 试求：  　 (1) 最小记录时间Tp min; 　 (2) 最低采样频率fs min; 　 (3) 最少采样点数Nmin。

　　解： 调制信号为单一频率正弦波时， 已调AM信号为 　　　　x(t)=cos(2πfct+jc)［1+cos(2πfmt+jm)］ 所以， 已调AM信号x(t) 只有3个频率： fc、 fc+fm、 fc－fm。 x(t)的最高频率fmax=1.1 kHz， 频率分辨率F≤100 Hz（对本题所给单频AM调制信号应满足100/F=整数， 以便能采样到这三个频率成分）。 故 (1) (2)

(3) 　　（注意， 对窄带已调信号可以采用亚奈奎斯特采样速率采样， 压缩码率。 而在本题的解答中， 我们仅按基带信号的采样定理来求解。 ） 　　20． 在下列说法中选择正确的结论。 线性调频Z变换可以用来计算一个有限长序列h(n)在z平面实轴上诸点{zk}的Z变换H(zk)， 使

(1) zk=ak, k=0, 1, …, N－1, a为实数，　a≠1;  　 (3) (1)和(2)都不行， 即线性调频Z变换不能计算H(z)在z平面实轴上的取样值。  　　解： 在chirp-Z变换中， 在z平面上分析的N点为 　　　　　　　zk=AW－k k=0, 1, …, N－1 其中 所以 　　当A0=1, ω0=0, W0=a－1, j=0时，  　 　　　　　　zk=ak 故说法（1）正确, 说法（2）、 （3）不正确。 

　　 21． 我们希望利用h(n)长度为N=50的FIR滤波器对一段很长的数据序列进行滤波处理， 要求采用重叠保留法通过DFT(即FFT)来实现。 所谓重叠保留法， 就是对输入序列进行分段(本题设每段长度为M=100个采样点)， 但相邻两段必须重叠V个点， 然后计算各段与h(n)的L点(本题取L=128)循环卷积， 得到输出序列ym(n)， m表示第m段循环卷积计算输出。 最后， 从ym(n)中选取B个样值， 使每段选取的B个样值连接得到滤波输出y(n)。

　　 (1) 求V；  　　 (2) 求B；  　　 (3) 确定取出的B个采样应为ym(n)中的哪些样点。  　　解: 为了便于叙述， 规定循环卷积的输出序列ym(n)的序列标号为n=0, 1, 2, …, 127。  　　先以h(n)与各段输入的线性卷积ylm(n)分析问题， 因为当h(n)的50个样值点完全与第m段输入序列xm(n)重叠后， ylm(n)才与真正的滤波输出y(n)相等， 所以， ylm(n)中第0点到第48点（共49个点）不正确， 不能作为滤波输出， 第49点到第99点（共51个点）为正确的滤波输出序列y(n)的第m段， 即B=51。

　　所以， 为了去除前面49个不正确点， 取出51个正确的点连接, 得到不间断又无多余点的y(n)， 必须重叠100－51 =49个点， 即V=49。  　　下面说明， 对128点的循环卷积ym(n)， 上述结果也是正确的。 我们知道 因为ylm(n)长度为 N+M－1=50+100－1=149

所以n从21到127区域无时域混叠， ym(n)=ylm(n)， 当然， 第49点到第99点二者亦相等， 所以， 所取出的51点为从第49点到第99点的ym(n)。  　　综上所述， 总结所得结论： 　　　　　　　V=49, 　B=51 选取ym(n)中第49～99点作为滤波输出。  　　读者可以通过作图来理解重叠保留法的原理和本题的解答。 

　　22． 证明DFT的频域循环卷积定理。  　　证： DFT的频域循环卷积定理重写如下:  　　设h(n)和x(n)的长度分别为N和M， 　　　　ym(n)=h(n)x(n) 　　　　H(k)=DFT［h(n)］L, X(k)=DFT［X(n)］L 则 L X(k) 其中， L≥max［N， M］。

　　根据DFT的惟一性， 只要证明ym(n)=IDFT［Ym(k)］=h(n)x(n)， 就证明了DFT的频域循环卷积定理。

　　23*． 已知序列x(n)={1, 2, 3, 3, 2, 1}。  　　（1） 求出x(n)的傅里叶变换X(ejω)， 画出幅频特性和相频特性曲线(提示： 用1024点FFT近似X(ejω))；  　　（2） 计算x(n)的N（N≥6）点离散傅里叶变换X(k)， 画出幅频特性和相频特性曲线；  　　（3） 将X(ejω)和X(k)的幅频特性和相频特性曲线分别画在同一幅图中， 验证X(k)是X(ejω)的等间隔采样， 采样间隔为2π/N；  　　（4） 计算X(k)的N点IDFT， 验证DFT和IDFT的惟一性。

解： 该题求解程序为ex323. m， 程序运行结果如题23 　　解： 该题求解程序为ex323.m， 程序运行结果如题23*解图所示。 第（1）小题用1024点DFT近似x(n)的傅里叶变换； 第（2）小题用32点DFT。 题23*解图(e)和(f)验证了 X(k)是X(ejω)的等间隔采样， 采样间隔为2π/N。 题23*解图(g) 验证了IDFT的惟一性。

题23*解图

　　24*．给定两个序列: x1(n)={2, 1, 1, 2} , x2(n)={1, －1, －1, 1}。  　　（2） 用DFT计算x1(n)与x2(n)的卷积， 总结出DFT的时域卷积定理。  　　解： 设x1(n)和x2(n)的长度分别为M1和M2， 　 X1(k)=DFT［x1(n)］N, X2(k)=DFT［x2(n)］N 　 Yc(k)=X1(k)X2(k), yc(n)=IDFT［Yc(k)］N 所谓DFT的时域卷积定理， 就是当N≥M1+M2－1时， yc(n)=x1(n)*x2(n)。

　　本题中， M1=M2=4， 所以， 程序中取N=7。 本题的求解程序ex324.m如下：  　　x1n=［2 1 1 2］； x2n=［1 －1 －1 1］；  　　%时域直接计算卷积yn：  　　yn=conv(x1n， x2n) 　　%用DFT计算卷积ycn：  　　M1=length(x1n)；M2=length(x2n)； N=M1+M2－1； 　　X1k=fft(x1n， N)； %计算x1n的N点DFT 　　X2k=fft(x2n， N)； %计算x2n的N点DFT 　　Yck=X1k.*X2k； ycn=ifft(Yck， N)

　　程序运行结果：  　　直接在时域计算x1(n)与x2(n)的卷积yn和用DFT计算x1(n)与x2(n)的卷积ycn如下：  　　yn=［2 －1 －2 2 －2 －1 2］ 　　ycn=［　2.0000 －1.0000 －2.0000 2.0000 　　　　　－2.0000 －1.0000 2.0000］

　　25*．已知序列h(n)=R6(n), x(n)=nR8(n)。  　　（1） 计算yc(n)=h(n) 8 x(n)；  　　（2） 计算yc(n)=h(n) 16 x(n)和y(n)=h(n)*x(n)； 　　（3） 画出h(n)、 x(n)、 yc(n)和y(n)的波形图， 观察总结循环卷积与线性卷积的关系。  　　解： 本题的求解程序为ex325.m。 程序运行结果如题25*解图所示。 由图可见， 循环卷积为线性卷积的周期延拓序列的主值序列； 当循环卷积区间长度大于等于线性卷积序列长度时， 二者相等， 见图（b）和图(c)。

题25*解图

　　程序ex325.m如下：  　　%程序ex325.m  　　hn=［1 1 1 1］； xn=［0 1 2 3］；  　　%用DFT计算4点循环卷积yc4n：  　　H4k=fft(hn， 4)； %计算h(n)的4点DFT 　　X4k=fft(xn， 4)； %计算x(n)的4点DFT 　　Yc4k=H4k.*X4k； yc4n=ifft(Yc4k， 4)；  　　%用DFT计算8点循环卷积yc8n：  　　H8k=fft(hn， 8)； 　 %计算h(n)的8点DFT 　　X8k=fft(xn， 8)； 　%计算x(n)的8点DFT 　　Yc8k=H8k.*X8k； 　yc8n=ifft(Yc8k， 8)；  　　yn=conv(hn， xn)；　 %时域计算线性卷积yn：

　　26*． 验证频域采样定理。 设时域离散信号为 ≤ 其中a=0.9， L=10。  　　（1） 计算并绘制信号x(n)的波形。  （2）证明：

（3） 按照N=30对X(ejω)采样得到 （4） 计算并图示周期序列 试根据频域采样定理解释序列　　　与x(n)的关系。

　　（5） 计算并图示周期序列 ，比较 　　　与　　　验证（4）中的解释。  　　（6） 对N=15， 重复（3）～（5）。  　　解： 求解本题（1）、 （3）、 （4）、 （5）、 （6）的程序为ex326.m。 下面证明（2）。

N=30和N=15时， 对频域采样Ck进行离散傅里叶级数展开得到的序列分别如题26 　　 N=30和N=15时， 对频域采样Ck进行离散傅里叶级数展开得到的序列分别如题26*解图(b)和(c)所示。 由图显而易见， 如果Ck表示对X(ejω)在［0， 2π］上的N点等间隔采样， 则 简言述之： xN(n)是x(n)以N为周期的周期延拓序列　　　的主值序列。

　　程序ex326.m如下： 程序中直接对（2）中证明得到的结果采样得到Ck。  　　% 频域采样理论验证 　　clear all； close all；  　　a=0.9； L=10； n=-L： L；  　　%====== N=30 =============== 　　N=30；  　　xn=a.∧abs(n)； %计算产生序列x(n) 　　subplot(3， 2， 1)； stem(n， xn， ′.′)； 　　axis(［－15， 15， 0， 1.2］)； %(1)显示序列x(n) 　　title(′(a)x(n)的波形 ′)； xlabel(′n′)； 　　ylabel(′x(n)′)； box on

　　% 对X(jw)采样30点：  　　for k=0： N－1，  　　 Ck(k+1)=1；  　　 for m=1： L，  　 　 Ck(k+1)=Ck(k+1)+2*xn(m+L+1)*cos(2*pi*k*m/N); 　　　　　%(3)计算30点%采样Ck 　　 end 　　end 　　x30n=ifft(Ck， N)； %(4)30点IDFT得到所要求的周期序列的主值序列  　　%以下为绘图部分 　　n=0： N－1； 

　　subplot(3， 2， 2)； stem(n， x30n， ′.′)； 　　axis(［0， 30， 0， 1.2］)； box on  　　title(′(b)N=30由Ck展开的的周期序列的主值序列 ′)； 　　 　　xlabel(′n′)； ylabel(′x30(n)′) 　　%======= N=15 ================ 　　N=15；  　　% 对X(jw)采样15点：  　　for k=0： N－1，  　　 Ck(k+1)=1；  　　 for m=1： L，  　　 Ck(k+1)=Ck(k+1)+2*xn(m+L+1)*cos(2*pi*k*m/N); 　 %(3)计算30点%采样Ck 　　 end 　　end

　　x15n=ifft(Ck， N)； 　　　%(4)15点IDFT得到所要求的周期序列的主值序列  　　%以下为绘图部分 　　n=0： N－1；  　　subplot(3， 2， 3)； stem(n， x15n， ′.′)； 　　axis(［0， 30， 0， 1.2］)； box on  　　title(′(c)N=15由Ck展开的的周期序列的主值序列 ′)； 　　xlabel(′n′)； ylabel(′x15(n)′) 　　程序运行结果如题26*解图所示。

题26*解图

　　27*． 选择合适的变换区间长度N， 用DFT对下列信号进行谱分析， 画出幅频特性和相频特性曲线。  　　（1） x1(n)=2 cos(0.2πn) 　 （2） x2(n)=sin(0.45πn)sin(0.55πn) 　　（3） x3(n)=2－|n|R21(n+10) 　　解： 求解本题的程序为ex327.m， 程序运行结果如题27*解图所示。 本题选择变换区间长度N的方法如下：

　　对x1(n)， 其周期为10， 所以取N1=10； 因为 x2(n)=sin(0.45πn) sin(0.55πn)=0.5［cos(0.1πn)－cos(πn)］， 其周期为20， 所以取N2=20； x3(n)不是因果序列， 所以先构造其周期延拓序列（延拓周期为N3）， 再对其主值序列进行N3点DFT。  　　x1(n)和x2(n)是周期序列， 所以截取1个周期， 用DFT进行谱分析， 得出精确的离散谱。 x3(n)是非因果、 非周期序列，通过试验选取合适的DFT变换区间长度N3进行谱分析。

题27*解图

x1(n)的频谱如题27. 解图(a)和(b)所示， x2(n)的频谱如 题27 　　x1(n)的频谱如题27*解图(a)和(b)所示， x2(n)的频谱如 题27*解图(c)和(d)所示。 用32点DFT对x3(n)的谱分析结果见 题27*解图(e)、 (f)和(g)， 用64点DFT对x3(n)的谱分析结果见题27*解图(h)、 (i)和(j)。 比较可知， 仅用32点分析结果就可以了。  　　请注意， x3(n)的相频特性曲线的幅度很小， 这是计算误差引起的。 实质上， x3(n)是一个实偶对称序列， 所以其理论频谱应当是一个实偶函数， 其相位应当是零。

　　程序ex327.m如下：  　　%程序ex327.m 　　% 用DFT对序列谱分析 　　n1=0： 9； n2=0： 50； n3=-10： 10；  　　N1=10； N2=20； N3a=32； N3b=64；  　　x1n=2*cos(0.2*pi*n1)； %计算序列x1n 　　x2n=2*sin(0.45*pi*n2).*sin(0.55*pi*n2)； %计算序列 x2n 　　x3n=0.5.∧abs(n3)； %计算序列x3n 　　x3anp=zeros(1， N3a)； 　　　　%构造x3n的周期延拓序列， 周期为N3a 　　for m=1： 10，

 x3anp(m)=x3n(m+10)；x3anp(N3a+1-m)=x3n(11－m)； 　　end 　　x3bnp=zeros(1， N3b)； 　　　　%构造x3n的周期延拓序列， 周期为N3b 　　for m=1： 10，  　　 x3bnp(m)=x3n(m+10)； 　　　　x3bnp(N3b+1－m)=x3n(11－m)；  　　end 　　X1k=fft(x1n， N1)； 　　%计算序列x1n的N1点DFT 　X2k=fft(x2n， N2)； 　　%计算序列x2n的N2点DFT 　　X3ak=fft(x3anp， N3a)； %计算序列x3n的N3a点DFT 　 X3bk=fft(x3bnp， N3b)； %计算序列x3n的N3b点DFT 　　%以下为绘图部分（省略）

　　3.6 教材第4章习题与上机题解答 　　快速傅里叶变换（FFT）是DFT的快速算法， 没有新的物理概念。 FFT的基本思想和方法教材中都有详细的叙述， 所以只给出教材第4章的习题与上机题解答。  　　1． 如果某通用单片计算机的速度为平均每次复数乘需要4 μs， 每次复数加需要1 μs， 用来计算N=1024点DFT， 问直接计算需要多少时间。 用FFT计算呢？照这样计算， 用FFT进行快速卷积对信号进行处理时， 估计可实现实时处理的信号最高频率。

　　解: 当N=1024=210时， 直接计算DFT的复数乘法运算次数为 复数加法运算次数为 　　　　　N（N－1）=1024×1023=1 047 552次 直接计算所用计算时间TD为 　　　　TD=4×10－6×10242+1 047 552×10－6=5.241 856 s 用FFT计算1024点DFT所需计算时间TF为

　　快速卷积时， 需要计算一次N点FFT（考虑到H(k)= DFT［h(n)］已计算好存入内存）、 N次频域复数乘法和 一次N点IFFT。 所以， 计算1024点快速卷积的计算时间Tc约为

所以， 每秒钟处理的采样点数（即采样速率） 由采样定理知， 可实时处理的信号最高频率为

　　应当说明， 实际实现时， fmax还要小一些。 这是由于实际中要求采样频率高于奈奎斯特速率， 而且在采用重叠相加法时， 重叠部分要计算两次。 重叠部分长度与h(n)长度有关， 而且还有存取数据和指令周期等消耗的时间。 　　2． 如果将通用单片机换成数字信号处理专用单片机TMS320系列， 计算复数乘和复数加各需要10 ns。 请重复做上题。  　　解: 与第1题同理。  　　直接计算1024点DFT所需计算时间TD为 TD=10×10－9×10242+10×10－9×1 047 552=20.961 28 ms

用FFT计算1024点DFT所需计算时间TF为 快速卷积计算时间Tc约为

可实时处理的信号最高频率fmax为 ≤ · · 由此可见， 用DSP专用单片机可大大提高信号处理速度。 所以， DSP在数字信号处理领域得到广泛应用。 机器周期小于1 ns的DSP产品已上市， 其处理速度更高。

　　3． 已知X(k)和Y(k)是两个N点实序列x(n)和y(n)的DFT， 希望从X(k)和Y(k)求x(n)和y(n)， 为提高运算效率， 试设计用一次N点IFFT来完成的算法。  　　解: 因为x(n)和y(n)均为实序列， 所以， X(k)和Y(n)为共轭对称序列， jY(k)为共轭反对称序列。 可令X(k)和jY(k)分别作为复序列F(k)的共轭对称分量和共轭反对称分量， 即 　　　　　F(k)=X(k)+jY(k)=Fep(k)+Fop(k) 计算一次N点IFFT得到 　　　　　f(n)=IFFT［F(k)］=Re［f(n)］+j Im［f(n)］

由DFT的共轭对称性可知 　　Re［f(n)］=IDFT［Fep(k)］=IDFT［X(k)］=x(n) 　　j Im［f(n)］=IDFT［Fop(k)］=IDFT［jY(k)］=jy(n) 故 　　4． 设x(n)是长度为2N的有限长实序列， X(k)为x(n)的2N点DFT。  　　(1) 试设计用一次N点FFT完成计算X(k)的高效算法。 　　(2) 若已知X(k) ，试设计用一次N点IFFT实现求X(k)的2N点IDFT运算。

　　解: 本题的解题思路就是DIT-FFT思想。 　　（1） 在时域分别抽取偶数和奇数点x(n)， 得到两个N点实序列x1(n)和x2(n)： 　　　x1(n)=x(2n) 　 n=0, 1, …, N－1 　　　x2(n)=x(2n+1) n=0, 1, …, N－1 　　根据DIT-FFT的思想， 只要求得x1(n)和x2(n)的N点DFT， 再经过简单的一级蝶形运算就可得到x(n)的2N点DFT。 因为x1(n)和x2(n)均为实序列， 所以根据DFT的共轭对称性， 可用一次N点FFT求得X1(k)和X2(k)。 具体方法如下：

令 　　　　y(n)=x1(n)+jx2(n) 　　　　Y(k)=DFT［y(n)］ k=0, 1, …, N－1 则 2N点DFT［x（n）］=X（k）可由X1(k)和X2(k)得到

　　这样， 通过一次N点IFFT计算就完成了计算2N点DFT。 当然还要进行由Y(k)求X1(k)、 X2(k)和X(k)的运算(运算量相对很少)。  　　（2） 与（1）相同， 设 　　　　x1(n)=x(2n) 　　　　n=0, 1, …, N－1 　　　　x2(n)=x(2n+1) 　　　n=0, 1, …, N－1 　　　　X1(k)=DFT［x1(n)］ k=0, 1, …, N－1 　　　　X2(k)=DFT［x2(n)］ k=0, 1, …, N－1 则应满足关系式

由上式可解出 由以上分析可得出运算过程如下：  　　① 由X(k)计算出X1(k)和X2(k):

　　② 由X1(k)和X2(k)构成N点频域序列Y(k): 　　　　　Y(k)=X1(k)+jX2(k)=Yep(k)+Yop(k) 其中， Yep(k)=X1(k), Yop(k)=jX2(k)， 进行N点IFFT， 得到 y(n)=IFFT［Y(k)］=Re［y(n)］+j Im［y(n)］ n=0, 1, …, N－1 由DFT的共轭对称性知

　　③ 由x1(n)和x2(n)合成x(n): ，0≤n≤2N－1 在编程序实现时， 只要将存放x1(n)和x2(n)的两个数组的元素分别依次放入存放x(n)的数组的偶数和奇数数组元素中即可。

　　5． 分别画出16点基2DIT-FFT和DIF-FFT运算流图， 并计算其复数乘次数， 如果考虑三类碟形的乘法计算， 　　试计算复乘次数。  　　解： 本题比较简单， 仿照教材中的8点基2DIT-FFT和DIF-FFT运算流图很容易画出16点基2DIT-FFT和DIF-FFT运算流图。 但画图占篇幅较大， 这里省略本题解答， 请读者自己完成。

　　6*． 按照下面的IDFT算法编写MATLAB语言 IFFT程序， 其中的FFT部分不用写出清单， 可调用fft函数。 并分别对单位脉冲序列、 矩形序列、 三角序列和正弦序列进行FFT和IFFT变换， 验证所编程序。

　　解： 为了使用灵活方便， 将本题所给算法公式作为函数编写ifft46.m如下：  　　%按照所给算法公式计算IFET 　　function xn=ifft46(Xk， N) 　　Xk=conj(Xk)； 　　 　%对Xk取复共轭 　　xn=conj(fft(Xk， N))/N； %按照所给算法公式计算IFFT 　　分别对单位脉冲序列、 长度为8的矩形序列和三角序列进行FFT， 并调用函数ifft46计算IFFT变换， 验证函数ifft46的程序ex406.m如下：

　　%程序ex406.m 　　%调用fft函数计算IDFT 　　x1n=1； 　　　 %输入单位脉冲序列x1n 　　x2n=［1 1 1 1 1 1 1 1］； %输入矩形序列向量x2n 　　x3n=［1 2 3 4 4 3 2 1］； %输入三角序列序列向量x3n　N=8；  　　X1k=fft(x1n， N)； %计算x1n的N点DFT 　　X2k=fft(x2n， N)； %计算x2n的N点DFT 　　X3k=fft(x3n， N)； %计算x3n的N点DFT

　　x1n=ifft46(X1k， N) %调用ifft46函数计算X1k的IDFT 　　x2n=ifft46(X2k， N) %调用ifft46函数计算X2k的IDFT 　　x3n=ifft46(X3k， N) %调用ifft46函数计算X3k的IDFT 　　运行程序输出时域序列如下所示， 正是原序列x1n、 x2n和x3n。  　　x1n = 1 0 0 0 0 0 0 0 　　x2n = 1 1 1 1 1 1 1 1 　　x3n = 1 2 3 4 4 3 2 1