数字信号处理讲义--第8章 离散傅里叶变换

第8章 离散傅里叶变换

教学目的

1．理解离散傅里叶级数、傅里叶变换的概念和性质，掌握循环卷积的计算方法；

2．掌握用离散傅里叶变换实现线性卷积的条件和方法。 教学重点与难点 重点：

1．理解离散傅里叶级数、傅里叶变换的概念和性质，掌握循环卷积的计算方法；

2．掌握用离散傅里叶变换实现线性卷积的条件和方法。 难点：

１． 循环卷积的计算方法。

２． 离散傅里叶变换实现线性卷积的条件与方法。 8.0 引 言

在前面讨论了序列的傅里叶变换和Z变换。由于数字计算机只能计算有限长离散序列，因此有限长序列在数字信号处理中就显得很重要， 当然可以用Z变换和傅里叶变换来研究它， 但是，这两种变换无法直接利用计算机进行数值计算。针对序列“有限长”这一特点，可以导出一种更有用的变换：离散傅里叶变换（Discrete Fourier Transform， 简写为DFT）。它本身也是有限长序列。 作为有限长序列的一种傅里叶表示法，离散傅里叶变换除了在理论上相当重要之外，而且由于存在有效的快速算法——快速离散傅里叶变换，因而在各种数字信号处理的算法中起着核心作用。  有限长序列的离散傅里叶变换（DFT）和周期序列的离散傅里叶级数（DFS）本质上是一样的。为了讨论离散傅里叶级数与离散傅里叶变换，我们首先来回顾并讨论傅里叶变换的几种可能形式，见图8-1所示。

|X( j?)| x(t)1 (a)oo?t－?－??? x(t)|X( jk??)| (b)otok?T ?|X( e?)|x(nT) 1/T

(c)nT oo－???TN点 |X( e??)|x(n)

aa00pppjjkspoN点n(d)－?oN点?s??

图 ８-1 各种形式的傅里叶变换

一个非周期实连续时间信号xa(t)的傅里叶变换，即频谱Xa(jΩ)是一个连续的非周期函数，这一变换对的示意图见图8-1(a)。 该变换关系与第1章“连续时间信号的采样”中所涉及到的非周期连续时间信号xa(t)的情况相同。 

一个周期性连续时间信号xp(t)，其周期为Tp，该信号可展成傅里叶级数，其傅里叶级数的系数为 ，即xp(t)的傅里叶变换或频谱Xp(jkΩ)是由各次谐波分量组成的，并且是非周期离散频率函数，xp(t)和Xp(jkΩ)的示意图见图８-1(b)。其中，离散频谱相邻两谱线之间的角频率间隔为Ω=2πF=2π/Tp，k为谱谐波序号。

在第２章里讨论了一个非周期连续时间信号xa(t)经过等间隔采样的信号（x(nT)），即离散时间信号——序列x(n)，其傅里叶变换X(ejω

)是以2π为周期的连续函数，振幅特性如图8-1(c)所示。 这里的ω是数字频率，它和模拟角频率Ω的关系为ω=ΩT。若振幅特性的频率轴用Ω表示，则周期为Ωs=2π/T。 

比较图8-1(a)、（b）和(c)可发现有以下规律：如果信号频域是离散的，表现为周期性的时间函数。相反，在时域上是离散的， 则该信号在频域必然表现为周期性的频率函数。不难设想，一个离散周期序列，它一定具有既是周期又是离散的频谱， 其振幅特性如图8-1(d)所示。

表8-1 四种傅里叶变换形式的归纳 时间函数 连续和非周期 连续和周期 离散和非周期 离散和周期 频率函数 非周期和连续 非周期和离散 周期和连续 周期和离散 可以得出一般的规律：一个域的离散对应另一个域的周期延拓， 一个域的连续必定对应另一个域的非周期。表8-1对这四种傅里叶变换形式的特点作了简要归纳。 

下面我们先从周期性序列的离散傅里叶级数开始讨论，然后讨论可作为周期函数一个周期的有限长序列的离散傅里叶变换。 8.1 周期序列的离散傅里叶级数(DFS) ~x(n)设 是一个周期为N的周期序列， 即

~ x(n)?~x(n?rN)

r为任意整数

周期序列不是绝对可和的，所以不能用Z变换表示，因为在任何z值下，其Z变换都不收敛，也就是 ? |~x(n)||z?n|???n???

但是，正如连续时间周期信号可以用傅里叶级数表示一样， 周期序列也可以用离散傅里叶级数来表示，该级数相当于成谐波关系的复指~x(n)数序列（正弦型序列）之和。也就是说，复指数序列的频率是周期序列 的基频（?2??2π/N）的整数倍。这些复指数序列ek(n)的形式j??kn?N?ek(n)?e?ek?rN(n)为

（8-1） 式中, k, r为整数。

由式（8-1）可见，复指数序列ek(n)对k呈现周期性，周期也为N。也就是说, 离散傅里叶级数的谐波成分只有N个独立量，这是和连续傅里叶级数的不同之处（后者有无穷多个谐波成分），因而对离散傅里叶级数，只能取k=0 到N-1的N个独立谐波分量， 不然就会产生二义性。因而 可展成如下的离散傅里叶级数，即 2?jkn1N?1~~x(n)??X(k)eN（8-2）

Nk?0

式中，求和号前所乘的系数1/N是习惯上已经采用的常数， 是k次谐波的系数。

~下面我们来求解系数X(k ) ，这要利用复正弦序列的正交特性，即

~x(n)1e?Nn?0N?1j2?rnN11?e?2?jrN1?eN?1r=mN, m为整数 ???0其他r

（8-3）

j2?rNN 2??jrnNe将式（8-2）两端同乘以 ，然后从n=0 到N-1的一个周期内求和，

则得到 2?2?N?1N?1N?1?jrnj(k?r)n1~~ x(n)eN???X(k)eN?Nn?0k?0n?0

2?N?1~?1N?1jN(k?r)n? ??X(k)??e?N k?0n?0??~ ?X(r)

把r换成k可得 2?N?1?jkn~~ X(k)??x(n)eN n? 0 （8-4）

~~这就是求k=0 到N-1的N个谐波系数 的公式。同时看出 也是X(k)X(k)一个以N为周期的周期序列，即

2?2?N?1N?1?j(k?mN)n?jkn ~~X(k?mN)??~x(n)eN??~x(n)eN?X(k) n?0n?0~这和离散傅里叶级数只有N个不同的系数 的说法是一致X(k)~~x(n)X(k)的。可以看出，时域周期序列 的离散傅里叶级数在频域（即~x(n)其系数 也是一个周期序列。因而 与 是频域与时域的一个周期序列对， 式（8-2）与式（8-4）一起可看作是一对相互表达周期序列的离散傅里叶级数（DFS）对。 

为了表示方便，常常利用复数量WN来写这两个式子。WN定义为

2??j NWN?e （8-5）

使用WN， 式（8-4）及式（8-2）可表示为: N? 1 2? nk N ?1 （8-5） ?j~nkx(n)]??~x(n)eN??~x(n)WN X(k)?DFS[~n?0n?0 2?N?1N?11~~x(n)?IDFS[X(k)]?N（8-5）

jnk1~NX(k)e??Nk?0~X?(k)WN?nkk?0

式中，DFS［·］表示离散傅里叶级数正变换，IDFS［·］表示离散傅里叶级数反变换。

从上面看出，只要知道周期序列一个周期的内容，其他的内容也都知道了。 所以，这种无限长序列实际上只有一个周期中的N个序列值有信息。 因而周期序列和有限长序列有着本质的联系。

~)例8-1 设 x (n 为周期脉冲串

? ~x(n)???(n?rN) r???

~(n)??(n)~(n)因为对于0≤n≤Nx-1， , 所以利用x式（8-6）求出 的DFS系数为 N?1N?1~nknk~? ?n) X (k ) ? x ( n )W N ? ( W N ? 1 （8-9） ?n?0n?0

~在这种情况下，对于所有的k)值 均相同。于是，将式X(k（8-9）代入式（8-7）可以得出表示式

? ~ ? 1 N? 1 ?nk 1 N ? 1 j 2N nk （8-10） x(n)???(n?rN)??WN??eNk?0Nk?0 r???

~例8-2 已知周期序列X(k) 如图8-2所示，其周期N=10, 试求解

~X(k)它的傅里叶级数系数 。 ~x(n) ……

－10012345678910n

~x(n) （周期N=10） 图8-2 例8-2的周期序列

由式（8-6）

2?10?14?jnk ~nkX(k)??~x(n)W10??e10 n ? 0 （8-11） 0 n?

这一有限求和有闭合形式 10 ? 1 4 2? ?jnk~x)W X ( k ) ? ? ~ ( n 10 nk ? ? e 10 （8-12） n?0n?0

|~x(k)|

5

~ x(n)……

－10123456789101520k

~图 8-3 图8-2所示序列的傅里叶级数系数 的幅值 X(k)

~~x(n)式（8-6）中的周期序列 k ) 可看成是对 的第一个周期x(n)X(作Z变换，然后将Z变换在Z平面单位圆上按等间隔角2π/N采样而得到的。令

~?x(n)~x(n)?x(n)?RN(n)???00≤n≤N-1 其他n

~x(通常称x(n)为 n ) 的主值区序列，则x(n)的Z变换为

?N?1 X ( ) z ?n （8-13） ? n z)??x(n)z??~x (n n???n?0

把式（8-13）与式（8-6）比较可知

~ X(k)?X(z)z?W?e

~ （8-14）

X(k)可以看出，当0≤k≤N-1 时， 是对X(z)在Z平面单位圆上的

~X(k)N点等间隔采样，在此区间之外随着k的变化， 的值呈周期变

?kN?2??j???N?KG?*4]k化。 图8-4画出了这些特点。

jIm[z]

2

1|z|＝13 2? / N 4o k＝0Re[z]

57(＝N－1)

6

图2-4图8-4 Z平面单位圆上的N点等间隔采样

~~x(n)由于单位圆上的Z变换即为序列的傅里叶变换，所以周期序列 X(k )

也可以解释为 的一个周期x(n)的傅里叶变换的等间隔采样。 因为

N?1N?1 j??j?nX(e)??x(n)e??~x(n)e?j?n n? 0 n ? 0 （8-15）

比较式（8-15）和式（8-6），可以看出

~X(k)?X(ej?)（8-16） ??2?k/N

这相当于以2π/N的频率间隔对傅里叶变换进行采样。

~(n)~例8-3 为了举例说明傅里叶级 和周期信号 X(k)数系数 x~~x(n)x(8-2n)所示的序的一个周期的傅里叶变换之间的关系，我们再次研究图

列 。 在序列 的一个周期中：

?1x(n)???0~0≤n≤4 其他

（8-17）

则 x (n ) 的一个周期的傅里叶变换是 41?e?j5?j??j?n?j2?sin(5?/2) X(e)??e??e1?e?j?sin(5?/2)n?0

可以证明，若将ω=2πk/10 代入式（8-18）， 即

4?k?j sin(5?k/10)~j?X(k)?X(e)?e10??2?k/10 sin(?k/10)

|X(e)| 5

……

o?2?3?4??

图 8-5 对图2-2所示序列的一个周期作傅里叶变换的幅值

|X(e)| , |X(k)| 5

……

o?2?3?4?? 01020k

图8-6 图2-3和图2-5的重叠图，它表明一个周期序列的DFS系数等于主值区序列的傅里叶变换的采样

8.2 离散傅里叶级数（DFS）的性质 由于可以用采样Ｚ变换来解释DFS，因此它的许多性质与Ｚ变换性质~~x(n)X(k)非常相似。但是，由于 和 两者都具有周期性， 这就使它与Z变换性质还有一些重要差别。此外，DFS在时域和频域之间具有严格的对偶关系，这是序列的Z变换表示所不具有的。

~~x1(n) 和x2 ( n)设 皆是周期为N的周期序列，们各自的DFS分别为：

~ ~ X 1(k)?DFS[x1(n)]~ X2(k)?DFS[~x2(n)]

8.2.1 线性 ~~DFS[a~x1(n)?b~x2(n)]?aX1(k)?bX2(k)

j?j?（8-19）

式中，a和b为任意常数，所得到的频域序列也是周期序列，周期为N。这一性质可由DFS定义直接证明，留给读者自己去做。 8.2.2 序列的移位 2?jmk~?mk~~NDFS[x(n?m)]?WX(k)?eX(k) N~nl~（8-20） DFS[WNx(n)?X(k?l)（8-21a）

或 ~x(n)2??jnl~（8-21b） nl~IDFS[X(k?l)]?WNx(n)?eN~x(n)证 N?1nk~DFS[x(n?m)]??~x(n?m)WN

n?0 N?1?mki?mk ??~x(i)WNWN i ?m i=n+m

kix (i )及由于 ~ W N 都是以N为周期的周期函数， 故 N?1?mkki?mk~~DFS[x(n?m)]?WN?~x(i)WN?WNX(k)

i?0

~(n)~由于x X (k与) 的对称特点，可以用相似的方法证明式（8-21a）： N?1N?1~nl~nl~kn(l?k)nDFS[WNx(n)]??WNx(n)WN??~x(n)WN?X(k?l)

n?08.2.3 周期卷积 i?0如果

~~~ Y(k)?X1(k)X2(k)

N?1~则 ~y(n)?IDFS[Y(k)]??~x1(m)~x（2n?m） m?0或 ~ N ? 1~ (8-22) y(n)??x2(m)~x（1n?m） m?0证 1N?1~~~~?kn~y(n)?IDFS[X(k)X(k)]?X(k)X（?1212k）WN Nk?0代入

N?1~ mkX1(n)??~x1(m)WN m?0

得

1N?1N?1~~ ?(n?m)k~y(n)???x1(m)X（2k）WN Nk?0m?0N?1 ?1N?1~?(n?m)k?~?x(m)X（k）W?1??2N? Nm?0k?0?? N?1??~x1(m)~x2(n?m)

m?0

将变量进行简单换元，即可得等价的表示式 N?1~y(n)??~x2(m)~x（ 1n?m）m?0

~x1(m)式（8-22）是一个卷积公式， 但是它与非周期序列的线性卷积不同。

~~~x2(n?m) x2(m) （或x1(n?m) 和 都是变量m的周首先，和

期序列，周期为N，故乘积也是周期为N的周期序列; 其次，求和只在一个周期上进行，即m=0到N-1，所以称为周期卷积。

~x(n)周期卷积的过程可以用图8-7来说明，这是一个N=7 的周期卷积。~x(n)每一个周期里 有一个宽度为4的矩形脉冲， 有一个~x(n?m)宽度为3的矩形脉冲，图中画出了对应于n=0, 1, 2 时的 。

~~周期卷积过程中一个周期的某一序列值移出计算区间时，相邻的同一x(m)x(n?m)~y(n)位置的序列值就移入计算区间。运算在m=0到N-1区间内进行， 即

在一个周期内将 与 逐点相乘后求和，先计算出n=0, 1, …, N-1的结果，然后将所得结果周期延拓，就得到所求的整个周期序列

~x(n)

(a) 0Nn－N ~x(n)

1

(d) 0nN－N~ x(m) (c)0N－1m

图 8-7 两个周期序列（N=7）的周期卷积

~x(0?m) n＝0122211212(d)0~x2(1?m)N－1mn＝1(e)

图 8-7 两个周期序列（N=7）的周期卷积 ~x(2?m)n＝2 ( f )0N－1m

~y(n)

33

22

…11… ( g )n －N0N

图 8-7 两个周期序列（N=7）的周期卷积

由于DFS和IDFS变换的对称性，可以证明（请读者自己证明）时域周期序列的乘积对应着频域周期序列的周期卷积。即，如果

~y(n)?~x1(n)~x2(n)

则 N?11N?1~~~nk~~Y(k)?DFS[y(n)]??y(n)WN??X1(l)X2(k?l) Nl?0n?0

1N?1~~ ??X2(l)X1(k?l)Nl?0

(8-23) 8.3 周期序列DFS表示的性质的汇总

2

8.4周期信号的傅里叶变换 8.4.1 定义

对周期序列， 若不满足平方可和或绝对可和; 那么：

DTFT

?

2? ? ? (? ? ? 0?2?r)j?0nr???

DTFT和DFS:

2?jkn ~1N?1~~~DFSi.e.,x[n]??X[k]eNx[n]????X[k] Nk?0

若 2??~2?k~j?DTFT~x[n]????X(e)?X[k]?(??) ? Nk???N 则

2??~2?k ~~j?DTFTx[n]????X(e)?X[k]?(??) N k? N (8-24) ???

e

谱由一系列冲激组成，其权由DFS决定。

2?N?1jkn 1~~x[n]??X[k]eN Nk?02? jkn1N?1~~NDTFT(x[n])?X[k](DTFT(e))? Nk?0 ?1N?1~2? ??X[k]?2??(??k?2?r)

Nk?0Nr???

2??N?1~2?(k?rN) ?X(k)?(??)??Nr???k?0N

2??~2?k? ? ?X(k?rN)?(??)?NN k???? 2??~2?k ?X(k)?(??)? Nk???N

8.4.2 DTFT 和 DFS的关系

令x[n] 是长度为N 的序列，对其周期拓展得 :

~x[n]?x[n]?~p[n]

其中，

?? ~~p[n]???[n?rN], 则 x[n]??x[n?rN] r???r??? 在 DTFT 域: ?2?2?k~j?j?~j?j?) X(e)?X(e)P(e)?X(e)??(??NNk??? 2?k?j2?2?k ?X(eN)?(??) ? N k ??? N (8-25)

通过比较(8-24) & (8-25)，可得：

~ X[k]?X(ej?)2?k??N

8.5 对傅立叶变换的采样

首先，考虑一个任意的绝对可和的非周期序列x(n)，它的Z变换为

?

X(z)??x(n)z?n n???由于绝对可和，所以其傅里叶变换存在且连续，故Z变换收敛域包括单位圆。如果我们对X(z)在单位圆上进行N点等距采样： ?(n? 0 ,1 X (k ) ? X ( z) z ?W ? x )W Nnk k ,? N ? 1 ??kNn???（8-25）

问题在于，这样采样以后是否仍能不失真地恢复出原序列x(n)。 也就是说，频率采样后从X(k)的反变换中所获得的有限长序列， 即

~X(k)xN(n)=IDFT［X(k)］，能不能代表原序列x(n)？为此，我们先来分析~xN(n)X(k)的周期延拓序列 的离散傅里叶级数的反变换， 令其为 。

1N?1~1N?1~?nk~ xN(n)?IDFS[X(k)]??X(k)WN??X(k)WN?nkNk?0Nk?0

将式（2-64）代入此式，可得 ?1N?1???1N?1(m?n)k?mk??nk~ xN(n)????x(m)WN?WN??x(m)??WN?Nk?0?m???Nk?0m??????

由于

1(m?n)kWN?Nk?0

所以

~xN(n)??r???N?1?1???0m=n+rN, r为任意整数 其他m

?x(n?rN)8-26）

~~X(kxN(n)这说明由 ) 得到的周期序列 是原非周期序列x(n)

的周期延拓，其时域周期为频域采样点数N。在前面已经知道，时域

采样造成频域的周期延拓，这里又看到一个对称的特性，即频域采样同样会造成时域的周期延拓。

1） 如果x(n)是有限长序列，点数为M，则当频域采样不够密，即当

~xN(n)N

就不能不失真地恢复出原信号x(n)来。因此，对于M点的有限长序列x(n)

频域采样不失真的条件是频域采样点数N要大于或等于时域采样点

?x(n)x(n)???00≤n≤M-1 其他n

数M（时域序列长度），即满足

N≥M （8-27） 此时可得到 ?~? rN(nN(N x N (n ) ? x n ) R N (n ) ? ? x (n )R ) ? x ( n )

r???N≥M （8-28）

也就是说，点数为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ω)。 讨论如下： N?1X(z)??x(n)z?n

n?0 由于

1N?1 ?nkx(n)??X(k)WN Nk?0

将它代入X(z)式子中，得到

N?1N?1 1N?1?1N?1?nk??n?nk?nX(z)????X(k)WN?z??X(k)[?WNz] NNn?0?k?0k?0n?0??Nk?N 1?WNz1N?1?X(k)? ?k?1Nk?01?WNz

由于WN-Nk=1，因此

1?zN?1X(k)X(z)? ??k?1Nk?01?WNz （8-29）

这就是用N个频率采样X(k)来表示X(z)的内插公式。它可以表示为 N?1X ( z) ? X ( k )? k( z ) （8-30） ?k?0式中

11?z?N （8-31）

?k(z)??k?1N1?WNz

称为内插函数。令其分子为零，得

z?e 即内插函数在单位圆的N等分点上（也即采样点上）有N个零点。 而

-k分母为零，则有z=W= 的一个极点，它将和第k个零Ne点相抵消。因而，插值函数Φk(z)只在本身采样点r=k处不为零，在其他（N-1）个采样点r上（r=0, 1, …, N-1，但r≠k）都是零点（有（N-1）个零点）。而它在z=0 处还有（N-1）阶极点，如图8-8所示。

jIm[z]

|z|＝1 e e＝1 o(N－1)阶Re[z]

e

图 8-8 内插函数的零极点

现在来讨论频率响应，即求单位圆上z=ejω的Z变换。由式（8-29）可得

N?1 j?X(e)??X(k)?k(ej?) k? 0 （8-32） 而 ??N?sin???N?1k???j?N?? ? ? ( e j? ) ? 1 1 ? e ? 1 ? 2 ? e ? j?? 2 N?k2??j(??k)2?? NN?Nk????1?eN? sin?2?? ????

?????? sin?N??k??k?N?11 ?2N??jN(N?1)?j2???ee N sin ? ? ? ? k ?

??2N（8-33） ??

jj2πkN2?jNr=0, 1, …, k, …, N-1

2?kNj0j2π(N?1)N可将Φk(ejω)表示成更为方便的形式:

2???j??(e)????k?? （8-34） k

N??

?N?1???式中： 1sin(?N/2)?j??2??(?)?e Nsin(?/2) （8-35）

这样式（8-31）又可改写为 N ? 1 2???|??(?)|j?X(e)?X(k)??? ? 1? k ? （8-36）

N?N＝5?k?04π4π －NN 2πo2π?－2?－??2?－NN

arg[??(?)] 1π(1 －)N2π －N?2? －?－2?2πo? N1－π(1 －) N

2???图8-9 内插函数幅度特性与相位特性(N=5) ????k?N2??当变量ω=0 时， Φ(ω)=1， Φ??当?i （i=1, 2, …, N-1)时，

N 满足以下关系： (ω)=0。因而可知，

2??1??k??k ????k2?????N??? ? N ? ? 0 ? ? i 2 ? （8-37） ??i,i?k?N?

2??2?????????k????k也就是说，函数 2N ????1???k ?? 在本采样点NN??

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

2???,i?k???i?iN??2???????k?N???2?????i?kN?k??k??

X(ej?)??注意，一般来说，这里的X(ejω)和X(k)都是复数

?X(k)?的?权k插??加??各采样点之间的X(ejω)值由各采点?样?值函数

????2???N??2?kN?X(k) 在所求ω点上的值的叠加得到的。 

在以后章节中，我们将会看到，频率采样理论为FIR滤波器的结构设计，以及FIR滤波器传递函数的逼近提供了又一个有力的工具。 

8.5.2 采样的图解说明

例8-4: 序列长度 L 小于采样点数 N

图8-10

X(ej?) x[n]

~XN(k)~xN[n]

图8-11

8.5.3 实例

例8?6： 设 ~x[n] 是下述x[n]的周期拓展?1, 0?n?4,x[n]??其 它.?0, sin(5?/2).令 N?10,sin(?/2)n?0sin(k?/2)~则 X(k)?X(ej?)?e?j4k?/10.??2k?/Nsin(k?/10)X(e)??ej?n?e?j2?j?42?N

~X(ej?),X(k)?0 2N ? 2? ?0 5 10 k 图8-12 例8-7:

例8-7:

x[n]~j?~X(e)?X(k)采样

周期化 ~x[n]

8-6 有限长序列离散傅里叶变换（DFT） 8.6.1 DFT的定义

我们前面讨论的周期序列实际上只有有限个序列值有意义， 因而它和有限长序列有着本质的联系。本节将根据周期序列和有限长序列之间的关系， 由周期序列的离散傅里叶级数表示式推导得到有限长序列的离散频域表示即离散傅里叶变换（DFT）。

设x(n)为有限长序列，长度为N，即x(n)只在n=0到N-1点上有值，其他n时，x(n)=0。即

??x(n)0?n?N?1x(n)???其他n?0

x(Nn)的周期序列 为了引用周期序列的概念，我们把它看成周期为

~的一个周期，而把 看成x(n)的以N为周期的周期延拓， 即表x(n)~示成:

~??x(n)0?n?N?1x(n)???其他n?0~x(n)?r????x(n?rN)?这个关系可以用图8-14来表明。 的第一个周期n=0 ~x通常把(n)~到n=N-1 定义为”， 故x(n)是 的“主值序列”，即主值x(“n主值区间)区间上的序列。而称 为x(n)的周期延拓。对不同r值x(n+rN)之间

彼此并不重叠，故上式可写成

图8-14

－N0主值区间2-8N－1n0N－1n~x(n)?x(nmodN)?x((n))Nx(n) (8-38)

~x(n)用((n))N表示（n mod N），其数学上就是表示“n对N取余数”， 或称“n对N取模值”。 令

0≤n1≤N-1, m为整数 则n1为n对N的余数。

例如， 是周期为N=9的序列，则有： ~x ( n)

~x(8)?x((8))9?x(8)~x(13)?x((13))?x(4)~x(22)?x((22))9?x(4)~x(?1)?x((?1))?x(8)99n?n1?mN利用前面的矩形序列RN(n)，式（8-24）可写成 ~ (8-39)

x(n)?x(n)RN(n)~同理，频域的周期序列X(k) 也可看成是对有限长序列X(k)的周期

~X(k)X(k)可看成是周期序列 的主值序列，延拓，而有限长序列

即:

~ X ( k ) ? X (( k )) N (8-40)

~X(k)?X(k)RN(k)(8-41)

我们再看表达DFS与IDFS的式(8-6)和式(8-7)：

N?1~nk~X(k)?DFS[x(n)]??~x(n)WNn?01~~x(n)?IDFS[X(k)]?N~X?(k)WN?nkk?0N?1这两个公式的求和都只限定在n=0到N-1和k=0 到N-1 的主值区间进行，它们完全适用于主值序列x(n)与X(k)，因而我们可以得到有限长序列的离散傅里叶变换的定义:

nkX(k)?DFT[x(n)]??x(n)WNN?1 n ? （8-41） 0 0≤k≤N-1 N ?1 0≤n≤N-1 8-42）

1 x(n)?IDFT[X(k)]??X(k)WN?nkNk?0x(n)和X(k)是一个有限长序列的离散傅里叶变换对。我们称式(8- 41)为x(n)的N点离散傅里叶变换(DFT), 称式(8-42)为X(k)的N点离散傅里叶反变换(IDFT)。已知其中的一个序列，就能惟一地确定另一个序列。这是因为x(n)与X(k)都是点数为N的序列，都有N个独立值（可以是复数），所以信息当然等量。 

此外，值得强调得是，在使用离散傅里叶变换时，必须注意所处理的有限长序列都是作为周期序列的一个周期来表示的。 换句话说，离散傅里叶变换隐含着周期性。

例8-8已知序列x(n)=δ(n)，求它的N点DFT。  解 单位脉冲序列的DFT很容易由DFT的定义式（8-41）得到： N ? 1 k=0, 1, …, N-1

nk0X(k)???(n)WN?WN?1

?0δ(n)的nX(k)如图8-15。这是一个很特殊的例子，它表明对序列δ(n)来说，不论对它进行多少点的DFT，所得结果都是一个离散矩

??(n)X(k)形序列。 11

…

图8-15 序列δ(n)及其离散傅里叶变换 012N－1k例 8-9 已知x(n)=cos(nnπ/6)0是一个长度N=12的有限长序列， 求它的N点DFT。 

解 由DFT的定义式（8-41）

n?n??11 ?jnk??j2n?nk111?j6612??X(k)??cosW12???e?e?e 62n?0n?0?? 2?2?1?11?j12n(k?1)11?j12n(k?1)????e??e）式，再考虑到利用复正弦序列的正交特性（8-3k的取值区间，可???2?n?0n?0?得 ??6k?1,11X(k)??

??0其他k,k?[0,11]

x(n)X(k)

图 8-16 有限长序列及其DFT 01211n0111n例8-10 已知如下X(k): ?3X(k)???1k=0 1≤k≤9

求其10点IDFT。 解 X(k)可以表示为

X(k)=1+2δ(k) 0≤k≤9

写成这种形式后，就可以很容易确定离散傅里叶反变换。 由于一个单位脉冲序列的DFT为常数：

x1(n)??(n)

X1(k)?DFT[x1(n)]?18.6.2 DFT与序列傅里叶变换、Z变换的关系

若x(n)是一个有限长序列，长度为N，对x(n)进行Z变换

N?1

X(z)??x(n)z?n-kN

比较Z变换与DFT，我们看到，当z=W时 n?0 N?1nkX(z)z?W??x(n)WN?DFT[x(n)]即

n?0 X ( （8-43） k)?X(z)z?W 表明 2 ? 的W 是Z平面单位圆上幅角为 ??kz?W?eN点，也即将Z平面单位圆N等分后的第k点，所以X(k)也就是对X(z)在Z平面单位圆上N点等间隔采样值，如图8-17所示。此外， 由于序列的傅里叶变换X(ejω)即是单位圆上的Z变换，根据式（8-43）， DFT与序列傅里叶变换的关系为

X(k)?X(ej?)2??X(ejk?)（8-44） ??kN（8-45）

2??N?

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

jIm(z)

WX(e?) X(k)WW

ok＝0Re[z]图 8-17 DFT与序列傅里叶变换、Z变换的关系 W例 8-11 有限长序列x(n)为 o??W 0≤n≤4

1? x ( n)?? 其余n

求其N=5 点离散傅里叶变换X(k)。 ?0解 序列x(n)如图8-18（a）所示。在确定DFT时，我们可以将

?kN?kN?2??j??k?N??kN?kNN?2N?1N0Nj?(N?2)N?(N?3)N~x(n)~x(n)x(n)看作是一个长度N≥5的任意有限长序列。首先我们以N=5 为周期将x(n)延拓成周期序列 ，如图8-18（b）， 的DFS与x(n)的DFT相对应。因为在图8-18（ b）中的序列在区间0≤n≤N-1 上为常数值，所以可以得出

?Nk=0, ±N, ±2N, … 1?e?j2?k~ N?1?j(2?k/N)nN 的整数倍处才有非零的DFS系数X也就是说，(k)?e只有在k=0 ?和k=???j（2?k/N)0 其他 1?e8-18（c）所示。为了说明傅里叶级 值。这些DFS系数如图n?0?x (k数 ~ ) 与x(n)的频谱X(ejω)间的关系，在图8-18（c）中也画出了

jω)在频率ωk=2π傅里叶变换的幅值|X（ejω)|。显然， 就是X(e

~k/N 处的样本序列。按照式（8-40），x(n)的DFT对应于取 的一X(k)个周期而得到的有限长序列X~(k)。这样，x(n)的5点DFT如图8-18

X(k)（d）所示。

~ X(k)2?5?1 ?jnk=0, 1, 2, 3, 4 5 X ( k ) ? x ( n ) e k k=0 n?0x(n)

j2?k5 ? 1?e?(a)???0~4n 2?x(n)?jk0 k=0, 1, 2, 3, 4 ? 51?e……

(b)n0图 8-18 DFT的举例说明 ~X(k)（a） 有限长序列x(n); 5 |X（b） 由x(n)形成的周期N=5(e)|的周期序列;  (c)1234567891011k－10O ~（c） 对应于 ~ 的傅里叶级数 和x(n)的傅里叶变换2?4??x(n)X(k)X(k)5的幅度特性|X(ejω)|; （d） x(n)的DFT X(k) (d)kx(n)01234 1

(a)04 n~x(n)

1

(b)010 图 8-19 － 10 DFT的举例说明 4n|X(k)| 由x(n)形成的周期N=10的周期（a） 有限长序列x(n); （5b）??j?3.243.24~x(n)(c)－1001.2411.2410k

圆周卷积正是周期卷积取主值序列

y(n)?x1(n)L 因此 ???y(n)?y(n?rL)所以要使圆周卷积等于线性卷积而不产生混叠的必要条件为 ??1?RL(n)?r???? N ? N ? 1 （8-51） L ?12满足此条件后就有 y(n)?y1(n)即 x1(n) ○x2(n)=x1(n)*x2(n) 图8-16（d）、（e）、（f）正反映了（8-50）式的圆周卷积与线性卷积的关系。在图8-22（d）中，L=6小于N1+N2-1=8，这时产生混叠现象，其圆周卷积不等于线性卷积；而在图8-22（e）、（f）中, L=8和L=10，这时圆周卷积结果与线性卷积相同，所得y(n)的前8点序列值正好代表线性卷积结果。 所以只要L≥N1+N2-1，圆周卷积结果就能完全代表线性卷积。

图8-22 线性卷积与圆周卷积0 1234~x2(n)?y(n)RL(n)

x1(n)1(a)N1＝40123x2(n)1(b)N2＝5nn

(d)(c)L x(n)x1(n) y1(n)2N1＋N2－1＝84L＝64332211012345n－1012345678910nLx1(n) x(n)2(e)线性卷积与圆周卷积 图8-22 012345674321L＝8

例 8-12 一个有限长序列为 x(n) x(n)x(n)??(n)?2?(n?5)43211Ln2（1） 计算序列x(n)的10点离散傅里叶变换。  （2） 若序列( f )y(n)的DFT为

L＝10Y(k)?x(n)e10X10(k)点离散傅里叶变换，求序列y(n)。 式中，X(k)是的j2k01234567892?n（3）若10点序列y(n)的10点离散傅里叶变换是

式中, X(k)是序列x(n)的10点DFT，W(k)是序列w(n)的10点DFT

Y(k)?X(k)W(k)?1w(n)???0求序列y(n)。

解 （1） 由式（8-30）可求得x(n)的10点DFT

0≤n≤6 其他

X(k)??x(n)Wn?0N?1nkNnk??[?(n)?2?(n?5)]W10n?010?12?（2）X(k)乘以一个5kWNkm?j形式的复指数相当于是x(n)圆周移5kk10?1?2W10?1?2e?1?2(?1)位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｝ 圆周卷积为 ???y(n)?z(n?10r)在 0≤n≤9 求和中，仅有序列z(n)和z(n+10)有非零值，用表???R10(n)?r????列出z(n)和z(n+10)的值，对n=0, 1, 2, …, 9求和，得到： 0 1 2 3 4 5 6 10 n 7 8 9 11 1 1 1 1 1 3 3 Z(n) 2 2 2 2 2 z(n+10) 2 2 0 0 0 0 0 0 0 0 0 0 3 3 1 1 1 3 3 __ y(n) 2 2 2 __

所以10点圆周卷积为

y(n)=｛3, 3, 1, 1， 1, 3, 3, 2, 2, 2｝ 8.7.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)

证

?N?1nk?nk?DFT[x*(n)]??x*(n)WNRN(k)???x(n)WN?RN(k)n?0?n?0?*N?1*

?N?1(N?k)n??X*((?k))R(k)?x(n)WR≤ 0k)≤N-1 N(k N N ? ? N ??n?0?这里利用了

?X*((N?k))NRN(k)?X*(N?k)nNWN?e?e?j2?n?1因为X(k)的隐含周期性，故有X(N)=X(0)。  用同样的方法可以证明

?j2?nNN

也即

DFT[x*((?n))NRN(n)]?DFT[x*((N?n))NRN(n)]?X*(k)

在前面列出了序列傅里叶变换的一些对称性质，且定义了共轭对称序列与共轭反对称序列的概念。在那里， 对称性是指关于坐标原点的纵坐标的对称性。 DFT也有类似的对称性，但在DFT中，涉及的序列x(n)及其离散傅里叶变换X(k)均为有限长序列，且定义区间为 0 到N-1，所以，这里的对称性是指关于N/2 点的对称性。 

设有限长序列x(n)的长度为N点，则它的圆周共轭对称分量xep(n)和圆周共轭反对称分量xop(n)分别定义为:

1 xep(n)?[x(n)?x*(N?n)] 2 （8-54）

1 xop(n)?[x(n)?x*(N?n)] 2 （8-55） 则两者满足:

8-53 DFT [ x * ( ? n )] ? （NX*(k)）

xep(n)?x(N?n)xop(n)??x(N?n)*op*ep０≤n≤N-1 （8-56）

０≤n≤N-1

（8-57）

如同任何实函数都可以分解成偶对称分量和奇对称分量一样，

任何有限长序列x(n)都可以表示成其圆周共轭对称分量xep(n)和圆周共轭反对称分量xop(n)之和，即

x(n)=xep(n)+xop(n) 0≤n≤N-1

由式（8-53）及式（8-54），并利用式（8-55）及式（8-56） ， 可得圆周共轭对称分量及圆周共轭反对称分量的DFT分别为： DFT［xep(n)］=Ｒe［X(k)］ (8-59) DFT［xop(n)］=j Im ［X(k)］(8-60) 证

?1?*DFT[x(n)]?DFT(x(n)?x(N?n)) ep???2?

11?DFT[x(n)]?DFT[x*(N?n)]

22

利用式（8-53），可得 1DFT[x(n)]?[X(k)?X*(k)]?Re[X(k)] ep2

则式(8-59)得证。同理可证式（8-60）。

下面我们再来讨论序列实部与虚部的DFT。 

若用xr(n)及xi(n)分别表示有限长序列x(n)的实部及虚部，即 x(n)=xr(n)+jxi(n) (8-62) 式中：

1xr(n)?Re[x(n)][x(n)?x*(n)]

2 1jxi(n)?jIm[x(n)]?[x(n)?x*(n)]

2 则有：

1 DFT[xr(n)]?Xep(k)?[X(k)?X*(N?k)]2

1 DFT[jxi(n)]?Xop(k)?[X(k)?X*(N?k)]2

式中，Xep(k)为X(k)的圆周共轭对称分量且Xep(k)=X*ep(N-k)，Xop(k)为X(k)的圆周共轭反对称分量且Xop(k)=-X*op(N-k)。

证

DFT[x(n)]?1{DFT[x(n)]?DFT[x*(n)]}r2

利用式（8-56）， 有

1 DFT[x(n)]?{X(k)?X*(N?k)]?X(k)r2ep

这说明复序列实部的DFT等于序列DFT的圆周共轭对称分量。同理可证式（8-62）。式（8-62）说明复序列虚部乘以j的DFT等于序列DFT的圆周共轭反对称分量。

此外，根据上述共轭对称特性可以证明有限长实序列DFT的共轭对称特性。 

若x(n)是实序列，这时x(n)=x*(n)，两边进行离散傅里叶变换并利用式（8-57），有

 X(k)=X*((N-k))NRN(k)=X*(N-k) (8-63)

由上式可看出X(k)只有圆周共轭对称分量。  若x(n)是纯虚序列，则显然X(k)只有圆周共轭反对称分量， 即满足 X(k)=-X*((N-k))NRＮ(k)=-X*(N-k)

8.7.6 DFT形式下的帕塞伐定理 N?11N?1*x(n)y(n)??X(k)Y*(k) ?Nk?0n?0

证 N?1*N?1N?11???kn x(n)y*(n)??x(n)??Y(k)WN??Nk?0n?0n?0??

1N?1*N?11N?1kn ??Y(k)?x(n)WN??X(k)Y*(k)Nk?0Nn?0n?0

如果令y(n)=x(n)，则式（8-63）变成 N?11N?1*x(n)x(n)??X(k)X*(k) ?Nk?0n?0 即

这表明一个序列在时域计算的能量与在频域计算的能量是相等的。 

最后我们在表8-3中列出了DFT的性质，以供参考。

表 8-3 DFT性质表(序列长皆为Ｎ点)

8.9用离散傅里叶变换实现线性卷积 根据线性卷积的原理 :

x[n] ? y[n] DTF T X(e jω)Y( e jω), 且，

w[n] = x[n] ? y[n] 可用下式求得： F－1 {X(e jω)Y( e jω)}. 线性与圆周卷积分别由下式给出：

w[n]?x[n]?y[n]?m????x[m]y[n?m]N?1m?0?wp[n]?x[n] y[n]??x[m]y[((n?m))N]RN[n]N 何时 wp[n] 等于 w[n] ? 注意:

设: x[n] : 0≤n ≤P －1 ? 0≤m ≤P －1

y[n]: 0≤n ≤L －1 ? 0≤n － m ≤L －1 w[n]的最大长度为 ：L+P-1. 单 wp[n] 的长度为 N. 时域分析：

wp[n]??x[m]y[((n?m))N]RN[n]m?0N?1 ??(x[m]?y[n?m?kN])RN[n]m?0?k???N?1? ? ?k???m?0???x[m]y[(n?kN)?m]R?w[n?kN]RN?1m?0NN?1N[n] [n]k???其中, w[n]??x[m]y[n?m].若 N?L?P-1, w[n]?x[n]?y[n]?wp[n].频域分析：

w[n]?x[n]?y[n],???n??.W(ej?)?X(ej?)Y(ej?),???R.For??2?k/N,~~~j2?k/NW(k)?W(e)?X(e)Y(e)?X(k)Y(k)~~W(k)?X(k)Y(k)RN(k)?X(k)Y(k).jj2?kN2?kNIf N?L?P-1, W(k)?WP(k)?X(k)Y(k), so W(k) is 下列两项的DFT : ?r????w[n?rN],?0?n?N?1x[n] N y[n]

?X(k)Y(k)

?若无重叠，则, wp[n] = w[n]

8.9.2用 DFT实现线性卷积的例子 例8-13 N1=P=11 N2= L=15

x[n] y[n] y[?n] y[1?n] y[2?n]y[23?n]y[24?n]8-23 图

x[n] y[n] y[N?n] y[N?n?1] y[N?n?2]y[N?n?23]y[ N?n?24]

例8-14 N1= N2= 15

x[n] y[n] y[?n] y[1?n] y[2?n]y[13?n]y[14?n]

x[n] y[n]y[((?n))15]y[((1?n))15]]y[((2?n))15]y[((13?n))15]y[((14?n))15]图8-24

例8-15 N1= N2= 15

x[n] y[n] y[?n] y[1?n] y[2?n]y[13?n]y[14?n] x[n] y[n]y[((?n))15]y[((1?n))15]]y[((2?n))15]y[((13?n))15] y[((14?n))15]图8-25

小结:

当N≥L+P －1 , wp[n] = w[n]; 当 N ≤ L+P－1, wp[n] ≠ w[n]; 线性与圆周卷积一致的样本为:

P+L－N－1≤n≤N －1 8.9.3 用DFT的LTI系统的实现 （1）原理

LTI 系统: 如 x[n] (0?n?L-1) 为输入信号； h[n] (0?n?P-1)为 为系统的脉冲响应：则 , y[n]?x[n]?h[n] , (0?n?L?P-2).进一步，若 DFT(x[n])?X(k), DFT(h[n])?H(k) x[n] y[n]?X[k]H[k] N?L?P-1, x[n]?h[n]?x[n] y[n]?IDFT(X(k)H(k)).用DFT 实现 LTI 系统 DFT:(1) x[n]?X(k); h[n]?H[k](2) Y(k)?X(k)H(k)(3) y[n]?IDFT?X(k)Y(k)?当x(n)的点数很多时，即当L>>M。通常不允许等x(n)全部采集齐后再进行卷积; 否则，使输出相对于输入有较长的延时。此外，若

N=L+M-1 太大，h(n)必须补很多个零值点，很不经济，且FFT的计算时间也要很长。这时FFT法的优点就表现不出来了，因此需要采用分段卷积或称分段过滤的办法。即将x(n)分成点数和h(n)相仿的段，分别求出每段的卷积结果，然后用一定方式把它们合在一起，便得到总的输出，其中每一段的卷积均采用FFT方法处理。有两种分段卷积的办法: 重叠相加法和重叠保留法。

（２）重叠相加法

设h(n)的点数为M，信号x(n)为很长的序列。我们将x(n)分解为很多段，每段为L点，L选择成和M的数量级相同，用xi(n)表示x(n)的第i段：

?x(n)xi(n)???0iL≤n≤(i+1)L-1 其他n

i=0, 1, … （8-68）

则输入序列可表示成

? （8-69）

x((nn))和??)i(这样，xh(xn)n的线性卷积等于各xi(n)与h(n)的线性卷积

i?0之和，即

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

?yi(n)?xi(n)N 由于xi(n)为L点，而yi(n)为（L+M-1）点（设N=L+M-1），

故相邻两段输出序列必然有（M-1）个点发生重叠，即前一段的后（M-1）个点和后一段的前（M-1）个点相重叠，如图8-26 所示。按照式（8-70），应该将重叠部分相加再和不重叠的部分共同组成输出y(n)。

h(n) 0N－1nM－1 x(n)

L

0x0(n)0x(n)L－1N－1L＋N－1n2L3Lnh(n)

本文来源：https://www.bwwdw.com/article/hso6.html