第 3章 离散傅立叶变换
? DFS
? DFS的性质
? DFT
? DFT的性质
? 圆周卷积
? 利用 DFT计算线性卷积
? 频率域抽样
有限长序列的傅里叶分析
一、四种信号傅里叶表示
1,周期为 T0的连续时间周期信号
??
???
??
n
tnenXtx 0j
0 )()(
~ ??
dtetxTnX tnT 0
0
j
0
0 )(
~1)( ?? ?
?? ?? ?
频谱特点,离散非周期谱
2,连续时间非周期信号
??? ? deXtx t j)j(2 1)( ?? ? ????
dtetxX t j)()j( ?? ?????? ??
频谱特点,连续非周期谱
3,离散非周期信号
???? ?? ?? ? deeXeXkx kjjj )(2 1)([I DT F T][ ? ??
?
?
???
? ??? ? k
k
ekxkxeX j-j ][]}[{DT F T)(
频谱特点,周期为 2?的连续谱
4,周期为 N 的离散周期信号
mk
N
N
m
mkNN
m
WmXNemXNmXkx ?
?
?
?
?
????? ??
1
0
2j1
0
][~1][~1]}[~{I D F S][~
?
km
N
N
k
mkNN
k
WkxekxkxmX ????? ??
?
?
?
?
1
0
2j-1
0
][~][~]}[{D F S][~
?
频谱特点：周期为 N的离散谱
为了便于更好地理解 DFT的概念, 先讨论周期序列及其
离散傅里叶级数 （ DFS） 表示 。
一个周期为 N的周期序列，即
,k为任意整数, N为周期
周期序列不能进行 Z变换, 因为其在 n=-?到 +? 都周而
复始永不衰减, 即 z 平面上没有收敛域 。 但是, 正象连
续时间周期信号可用傅氏级数表达, 周期序列也可用离散
的傅氏级数来表示, 也即用周期为 N的正弦序列来表示 。
)(~)(~ kNnxnx ??
离散傅里叶级数（ DFS）
? ? nNjene /2
1 )(
??
? ? knNj
k ene
/2)( ??
周期为 N的正弦序列其基频成分为：
K次谐波序列为：
? ?? ? ? ? knNjnNkNj ee /2)(/2 ?? ??
但离散级数所有谐波成分中只有 N个是独立的，
这是与连续 傅 氏级数的不同之处，
即
因此
)()( nene kNk ??
将周期序列展成离散傅里叶级数时, 只需取 k=0 到
(N-1) 这 N个独立的谐波分量, 所以一个周期序列的离
散傅里叶级数只需包含这 N个复指数,
利用正弦序列的周期性可求解系数 。
将上式两边乘以, 并对一个周期
求和
? ?? ?
?
?
1
0
/2)(~1)(~
N
K
knNjekX
N
nx ?
)(~ kX
rnNje )/2( ??
? ?? ? ?
?
?
?
?
??
?
?
?
?
?
??
??
1
0
1
0
)(21
0
1
0
1
0
)(22
)(~1)(~1)(~
N
k
N
n
nrk
N
jN
n
N
n
N
k
nrk
N
jrn
N
j
ekX
N
ekX
N
enx
???
]
1
11)[(~1
0
/)(2
)(2
?
?
?
?
?
?
?? N
k
Nrkj
rkj
e
e
N
kX ?
?
rk
sNrk
e
N
N
n
nrk
N
j
?
??
?
?
?
??
?
?
?
0
11 1
0
))(
2
(
?
上式中 [ ]部分显然只有当 k=r时才有值为 1,其他任意 k值时均为
零,所以有
或写为
1) 可求 N 次谐波的系数
2） 也是一个由 N 个独立谐波分量组成的傅立叶级数
3） 为周期序列, 周期为 N。
)(~)(~
1
0
2
rXenx
N
n
rn
N
j
??
?
?
? ?
10)(~)(~
1
0
2
???? ?
?
?
?
?
??
?
??
NkenxkX
N
n
kn
N
j ?
)(~ kX
)(~ kX
)(~ kX
? ?
? ?
)(
~
)(
~
)(
~
)(
~
1
0
/2
1
0
)(/2
kXenx
enxmNkX
N
n
knNj
N
n
nmNkNj
??
??
?
?
?
?
?
?
?
??
?
?
?时域上周期序列的离散傅里叶级数在频域上仍是一个
周期序列。
是一个周期序列的离散傅里叶级数 (DFS)
变换对, 这种对称关系可表为：
习惯上：记,
)(~)(~ nxkX ?
? ??
?
?
???
1
0
/2)(~)](~[)(~
N
n
knNjenxnxD F SkX ?
? ??
?
?
??
1
0
/2)(~1)](~[)(~
N
n
nkNjekX
N
kXI D F Snx ?
? ?Nj
N eW
/2 ???
DFS变换对公式表明，一个周期序列虽然是无穷
长序列，但是只要知道它一个周期的内容（一个周期
内信号的变化情况），其它的内容也就都知道了，所
以这种无穷长序列实际上只有 N个序列值的信息是有
用的，因此周期序列与有限长序列有着本质的联系。
? ?
? ??
?
?
?
?
?
?
??
??
1
0
1
0
)(
~
)(
~1
)(~
)(~)(~)(
~
N
k
kn
N
N
n
kn
N
kXI D F SWkX
N
nx
nxD F SWnxkX
则 DFS变换对可写为
DFS[·] —— 离散傅里叶级数变换
IDFS[·]—— 离散傅里叶级数反变换。
DDFS的几个主要特性：
假设 都是周期为 N 的两个周期序列, 各自的
离散傅里叶级数为：
1） 线性
a,b为任意常数
)(~)(~ nynx,
? ?
? ???
?
?
?
)(~)(~
)(~)(~
nyD F SkY
nxD F SkX
? ? )(~)(~)(~)(~ kYbkXanybnxaD F S ???
2） 序列移位
证 因为 及 都是以 N为周期的函数,
所以有
? ?
? ???
?
??
?? ?
)(~)(~
)(~)(~
nxwlkXI D F S
kXwmnxD F S
nl
N
mk
N
)(~ nx kn
Nw
? ? ? ??
?
??
?
?????
1
0
1
)(~)(~)(~
N
n
mN
mi
km
N
ki
N
kn
N wwixwmnxmnxD F S
)(
~
)(
~
)(
~
1
0
1
kXwwixw
wixw
mk
N
N
i
ki
N
mk
N
mN
mi
ki
N
mk
N
?
?
?
?
??
?
?
??
?
?
?
由于 与 对称的特点，同样可证明)(~ nx )(~ kX
? ? )(~)(~ nxwlkXI D F S nlN??
3） 共轭对称性
对于复序列 其共轭序列 满足
? ?nx~ ? ?nx*~
? ?? ? ? ?kXnx ?? ** ~~D F S
? ?? ?
? ?kXWnx
Wnxnx
N
n
nk
N
N
n
nk
N
???
?
?
?
?
?
?
?
?
*
1
0
*
1
0
**
~
))(~(
)(~~D F S
证,
? ?? ? ? ?kXnx ** ~~D F S ??
同理,
进一步可得
? ?? ? ? ? ? ?
)](
~
)(
~
[
2
1
]~~[D F S
2
1
}~R e{D F S
*
*
kNXkX
nxnxnx
???
??
? ?? ?? ? ? ? )](~)(~[
2
1~~ReDF S *
e kNXkXkXnx ????
共轭偶对称分量
? ?? ?? ? ? ? )](~)(~[
2
1~~ImDF S *
o kNXkXkXnxj ????
共轭奇对称分量
4） 周期卷积
若
则
或
)(~)(~)(~ kYkXkF ?
? ? ? ?
?
???
1
0
)(~)(~)(~)(~
N
m
mnymxkFI D F Snf
?
?
?
??
1
0
)(~)(~
N
m
mnxmy
周 期 卷 积
证：
这是一个卷积公式, 但与前面讨论的线性卷积的差
别在于, 这里的卷积过程只限于一个周期内 （ 即
m=0~N-1）, 称为周期卷积 。
例：,,周期为 N=7,宽度分别为 4
和 3,求周期卷积。
结果仍为周期序列，周期为 N 。
? ? ? ?
?
???
1
0
)(~)(~1)(~)(~)(~
N
k
kn
NwkYkXNkYkXI D F Snf
? ?
?
?
?
?
??
1
0
1
0
)(~)(~1
N
k
N
m
nk
N
mk
N wkYwmxN
? ???
?
?
?
?
?
?? ???
?
?
??
?? 1
0
1
0
1
0
)( )(~)(~)(~1)(~
N
m
N
m
N
k
kmn
N mnymxwkYNmx
)(~ nx )(~ ny
)(~)(~)(~ nynxnf ?
?? ?
?
?
?
?????
1
0
1
0
)(~)(~1)(~)(~1)](~[)(~
N
l
N
l
lYlkXNlkYlXNnfD F SkF
由于 DFS与 IDFS的对称性，对周期序列乘
积，存在着频域的周期卷积公式，
若
则
我们知道周期序列实际上只有有限个序列值有意义, 因此
它的许多特性可推广到有限长序列上 。
一个有限长序列 x(n),长为 N，
为了引用周期序列的概念, 假定一个周期序列, 它
由长度为 N 的有限长序列 x(n) 延拓而成, 它们的关系：
???
?
???
? ????
n
Nnnxnx
其余0
10)()(
)(~ nx
?
?
?
?
?
?
?
?
?
? ???
?
?? ?
?
???
n
Nnnx
nx
rNnxnx
r
其它0
10)(~
)(
)()(~
离散傅里叶变换（ DFT）
周期序列的主值区间与主值序列：
对于周期序列, 定义其第一个周期 n=0~N-1,为
的, 主值区间,, 主值区间上的序列为主值序列 x(n)。
x(n)与 的关系可描述为：
数学表示：
RN（ n） 为矩形序列 。
符号 （（ n）） N 是余数运算表达式, 表示 n 对 N 求余数 。
)(~ nx
)(~ nx
)(~ nx
?
?
?
"")(~)(
)()(~
主值序列的是
的周期延拓是
nxnx
nxnx
?
?
?
??
?
)())(()()(~)(
))(()(~
nRnxnRnxnx
nxnx
NNN
N
)(~nx
)(nx
例,是周期为 N=8 的序列，求 n=11 和 n=-2
对 N的余数。
因此
)(~ nx
6))2((68)1(2
3))11((38111
8
8
?????????
??????
n
n
)6()2(~),3()11(~ xxxx ???
频域上的主值区间与主值序列：
周期序列 的离散付氏级数 也是一个
周期序列，也可给它定义一个主值区间
，以及主值序列 X(k)。
数学表示：
)(~ nx )(~ kX
10 ??? Nk
?
?
?
?
?
N
N
kXkX
kRkXkX
))(()(~
)()(~)(
10)(~)](~[)(~
1
0
????? ?
?
?
NkWnxnxD F SkX
N
n
kn
10)(~1)](~[)(~
1
0
????? ?
?
?
? NnWkX
NkXI D F Snx
N
n
kn
再看周期序列的离散傅里叶级数变换（ DFS）公式：
这两个公式的求和都只限于主值区间（ 0~N-1），它
们完全适用于主值序列 x(n) 与 X(k),因而我们可得到
一个新的定义 —— 有限长序列离散傅里叶变换定义。
长度为 N的有限长序列 x(n), 其离散傅里叶变换 X(k) 仍是
一个长度为 N 的有限长序列, 它们的关系为：
x(n) 与 X(k) 是一个有限长序列离散傅里叶变换对, 已知
x(n) 就能唯一地确定 X(k), 同样已知 X(k) 也就唯一地确定
x(n), 实际上 x(n) 与 X(k) 都是长度为 N 的序列 （ 复序列 ） 都
有 N个独立值, 因而具有等量的信息 。
有限长序列隐含着周期性。
?
?
?
??
?
?
?????
?????
?
?
?
?
?
?
?
10)(
1
)]([)(
10)()]([)(
1
0
1
0
NnWkX
N
kXI D F Tnx
NkWnxnxD F TkX
N
k
kn
N
N
n
kn
N
1,线性
? ? ? ? ? ?][D F T][D F T][][D F T 2121 kxbkxakbxkax ???
需将较短序列补零后，再按长序列的点数做 DFT
2,循环位移 (Circular shift of a sequence)
][])[(][ kRnkxky NN??
循环位移定义为
离散傅里叶变换的性质
x [ k ],N = 5
0 1 2 3 4
])[( Nkx
-5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9
])2[( 5?kx
-5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9
55 ])2[( Rkx ?
0 1 2 3 4
1
5
4
3
2
k=0
k==2
k=1
k=4
k=3
][~]}[~{D FS mXWnkx mnN????
? ? ][][])[(D FT mXWkRnkx mnNNN ???
][~]}[~{ lmXkxWD F S lkN ???
? ? ][])[(][D FT mRlmXkxW NNlkN ??
DFT频域循环位移特性
DFT时域循环位移特性
3,对称性 (symmetry)
周期共轭对称 (Periodic conjugate symmetry)定义为
周期共轭反对称 (Periodic conjugate antisymmetry)定义为
][*][])[(*][ kNxkRkxkx NN ????
][*][])[(*][ kNxkRkxkx NN ??????
当序列 x[k]为实序列时，周期偶对称序列满足
][][ kNxkx ??
当序列 x[k]为实序列时，周期奇对称序列满足
][][ kNxkx ???
对称特性
][~]}[~{D FS mXkx ??? ??
][~]}[~{D FS mXkx ?? ???
][~]}[])[({ mXkRkxD F T NN ?? ??
][])[(]}[{D FT mRmXkx NN?? ??
当 x[k]是实序列时
][])[(][ kRmXmX NN?? ?
4.循环卷积
定义 ][1 kx N ][2 kx ][])[(])[( 21
1
0
kRnkxnx NNN
N
n ?
????? ?? ?
?
?
x [ k ],N =4
0 1 2 3
1
2
3
4
h [ k ]
0 1 2 3
1
0 1 2 3
1
0 1 2 3
1
0 1 2 3
1
0 1 2 3
1
x [ k ] 4 h [ k ]
0 1 2 3
4
1
2
3
h[(?n)N]
h[(1?n)N]
h[(2?n)N]
h[(3?n)N]
卷积定理
? ? ][][][][D F T 2121 mXmXkxNkx ?
? ? ][][1][][D F T 2121 mXNmXNkxkx ?
序列 DFT与 z变换的关系
R e ( z )
j I m ( z )
N
?2
m
N
?2
0
z
平 面
)1(
2
?N
N
?
单 位 圆
- 1
1
j
- j
mNj
ez
mNj
k
N
kez
zkxzXmX
?? 22
|][)(][
1
0 ?
?
?
??
??? kmNN
k
ekx
?2j-1
0
][?
?
?
?
x[k]的 X[m]等于其 z变换 X(z)在单位圆上等间隔取样
设序列 x[k]的长度为 N
kN
k
zkxzX ?
?
?
?? ][)(
1
0
km
N
N
k
WkxmX ][][
1
0
?
?
?
?
11,0;)(][ 2 ???
?
NmzXmX
m
N
j
ez
??
][mX ?? ?? IDFT ][kx ??? ?? 变换Z )(zX
m
N
N
m
N
Wz
mX
N
zzX
??
?
?
?
?
?? ?
1
1
0 1
][)1()( (内插公式 )
问题提出, ? ? ][][][][D F T
2121 mXmXkxkx ??
实际需要,LTI系统响应 y[k]=x [k]?h[k]
可否利用 DFT计算线性卷积？
例,x1[k]={1,1,1},x 2[k]={1,1,0,1},N=4
一、两个有限长序列的线性卷积
][][ ],[][ 2121 kxkxkxkx ??
利用 DFT计算线性卷积
0 1
1
k
2
][2 kx
3
0
? 1
1
n
? 2
][1 nx ?
? 3
0
? 1
1
n
? 2
]1[1 nx ?
1
1
?
1
n
? 1
]2[1 nx ?
2
2
?
1
n
?
]3[1 nx ?
3
4
?
1
n
?
]5[1 nx ?
5
5
?
1
n
?
]6[1 nx ?
6
0 1
2
k
2
1
3
][*][ 21 kxkx
5
4
3
?
1
n
?
]4[1 nx ?
4
线性卷积的矩阵表示
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
]5[
]4[
]3[
]2[
]1[
]0[
y
y
y
y
y
y
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
]0[]1[]2[000
]0[]1[]2[00
]0[]1[]2[0
]0[]1[]2[
]0[]1[
]0[
111
111
111
111
11
1
xxx
xxx
xxx
xxx
xx
x
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0
0
]3[
]2[
]1[
]0[
2
2
2
2
x
x
x
x
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
111000
11100
1110
111
11
1
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0
0
1
0
1
1
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1
2
2
2
2
1
0 1
1
n
2
][1 nx
30 1
1
n
2
][2 nx
3
0 1
1
n
2
][])[(1 nRnx NN?
3
0 1
1
n
2
][])1[(1 nRnx NN?
3
0 1
1
n
2
][])2[(1 kRkx NN?
30 1
1
n
2
][])3[(1 kRkx NN?
30 1
2
k
2
3
3
][][ 21 kxkx ?
循环卷积的矩阵表示
?
?
?
?
?
?
?
?
?
?
?
?
?
]3[
]2[
]1[
]0[
y
y
y
y
?
?
?
?
?
?
?
?
?
?
?
?
]0[]1[]2[]3[
]3[]0[]1[]2[
]2[]3[]0[]1[
]1[]2[]3[]0[
1111
1111
1111
1111
xxxx
xxxx
xxxx
xxxx
?
?
?
?
?
?
?
?
?
?
?
?
]3[
]2[
]1[
]0[
2
2
2
2
x
x
x
x
?
?
?
?
?
?
?
?
?
?
?
?
?
1110
0111
1011
1101
?
?
?
?
?
?
?
?
?
?
?
?
1
0
1
1
?
?
?
?
?
?
?
?
?
?
?
?
?
2
2
3
2
0 1
1
k
2
][2 kx
3
0 1
1
n
2
][])[(1 nRnx NN?
30 1
1
n
2
][])1[(
1
nRnx
NN
?
3
0 1
1
n
2
][])2[(1 kRkx NN?
30 1
1
n
2
][])3[(1 kRkx NN?
30 1
1
n
2
][])4[(1 kRkx NN?
3 54
0 1
1
n
2
][])5[(1 kRkx NN?
3 540 1
2
k
2
1
3
][][
21
kxkx ?
54
循环卷积的矩阵表示
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
]5[
]4[
]3[
]2[
]1[
]0[
y
y
y
y
y
y
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
]0[]1[]2[000
0]0[]1[]2[00
00]0[]1[]2[0
000]0[]1[]2[
]5[000]0[]1[
]5[]4[000]0[
111
111
111
111
111
111
xxx
xxx
xxx
xxx
xxx
xxx
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0
0
]3[
]2[
]1[
]0[
2
2
2
2
x
x
x
x
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
111000
011100
001110
000111
100011
110001
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0
0
1
0
1
1
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1
2
2
2
2
1
若 x[k]的长度为 N,h[k]的长度为 M，则 L=N+M?1点
循环卷积等于 x[k] 与 h[k]的线性卷积。
补 L ? N 零
补 L ? M 零
L 点 DFT
L 点 DFT
L 点I DFT
][ kx
][ kh
][ ky
x 1 [ k ]
h 1 [ k ]
][][][][ 11 khkxkhkx ???
0 1 2 3 4 5 6
0
2
4
6
R e s u l t o f L i n e a r C o n v o l u t i o n
T i m e i n d e x k
A
m
p
l
it
u
d
e
0 1 2 3 4 5 6
0
1
2
3
x 1 0
- 1 5
T i m e i n d e x k
A
m
p
l
it
u
d
e
E r r o r M a g n i t u d e
直接计算与由 DFT间接计算结果比较
若 x1[k]为 M 点序列,x2[k]为 L 点序列, L?M
x1[k] L x2[k]中哪些点不是线性卷积的点?
k
?
][2 kx
L ? 1
k
?
][1 kx
M ? 1
问题讨论
n
?
][1 nx
M ? 1
n
?
][2 nx
L ? 1
n
?
L ? M ? 1 L ? 1
n
?
L ? M ? 2 L ? 1
n
?
M ? 1
][])1[(1 nRnMx LL?? 0? k ? M?2不是线性卷积
的结果，即前 (M?1)个点
与线性卷积不一样。
][])[(1 nRnx LL? ][])1[(1 nRnx LL?
线性卷积的矩阵表示
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
???
?
??
]0[]1[]2[]1[
]0[]3[]2[]1[
]0[]1[]2[
]0[]0[]1[
]0[]2[]1[
]0[]1[
]0[
1111
1111
111
111
111
11
1
xxMxMx
xMxMxMx
xxx
xxMx
xMxMx
xx
x
??
??
???
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0
0
0
0
]1[
]1[
]0[
2
2
2
?
?
Lx
x
x
? ? ??????? TMLyMLyMyMyMyyy ]1[]2[]1[][]1[]1[]0[ ??
循环卷积的矩阵表示
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
????
?
??
?
??
]0[]3[]2[]1[
0]4[]3[]2[]1[
0]0[]1[]2[
0]0[]0[]1[
0000]0[]2[]1[
]2[]1[000]0[]1[
]1[]1[]2[000]0[
1111
1111
111
111
111
1111
1111
xMxMxMx
MxMxMxMx
xxx
xxMx
xMxMx
xMxxx
xMxMxx
??
??
?????
??
??
??
??????
??
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? ]1[
0
0
0
0
]1[
]0[
2
2
2
Lx
x
x
?
?
? ? ????? TLyLyMyMyMyyy ]1[]2[]1[][]1[]1[]0[ ??
x1[k] L x2[k]
k=0 ~M?2,前 M?1个点不是线性卷积的点
k= M?1 ~ L?1,L?M+1个点与线性卷积的点对应
线性卷积 L ~ L+M?2 后 M ?1点没有计算
则 L点循环卷积
结论
若 x1[k]为 M 点序列,x2[k]为 L 点序列, L?M
长序列和短序列的线性卷积
直接利用 DFT计算的缺点：
(1) 信号要全部输入后才能进行计算，延迟太多
(2) 内存要求大
(3) 算法效率不高
解决问题方法：采用分段卷积
分段卷积可采用 重叠相加法 和 重叠保留法
1,重叠相加（ overlap add）
将长序列 x[k] 分为若干段长度为 L的序列
][][
0
nLkxkx n
n
?? ?
?
?
?
?
? ?????
0
10 ][
][
其它
LknLkx
kx n
k][ kx ][0 kx ][1 kx ][2 kx ][3 kxL L2 L3
其中
][][][][
0
khnLkxkhkx n
n
???? ?
?
?
][
0
nLky n
n
?? ?
?
?
y0[k]的非零范围 20 ???? MLk
y1[k?L]的非零范围 22 ???? MLkL
序列 y0[k],y1[k]的重叠部分 2???? MLkL
重叠的点数 L+M?2?L+1=M?1
][][][,khkxky nn ??记
依次将相邻两段的 M-1个重叠点相加，即得到最终的
线性卷积结果。
0 1
1
k
2
][ kh
M - 1
M = 4
0 1
1
k
2
][ kx 1?L
L = 7
重叠相加法分段卷积举例
0 1
k
2
][0 ky
4
3
1
2
3
96
0 1
k
2
][1 Lky ?
4
7 9
1
2
3
0 1
k
2
][][ nLkyky n ?? ?
4
3
1
2
3
方法：
(1) 将 x[k]长序列分段，每段长度为 L；
(2) 各段序列 xn[k]与 M点短序列 h[k]循环卷积；
(3) 从各段循环卷积中提取线性卷积结果。
2.重叠保留法 (overlap save)
前 M?1个点不是线性卷积的点因 yn[k]=xn [k] L h[k]
故分段时，每段与其前一段有 M?1个点重叠。
? ?x [k (M 1)]
M?1
? ?L (M 1)
L?1
x 0[k]
x 1[k]
2L?M k
)]1([][ ????? MLnkxkx n
第一段前需补 M-1个零
记 yn[k] =xn [k] L h[k]
0
1?L
k
0
][
1
k
y
k
1?L
][
0
k
y
M - 1
M - 1
y0[k]中的 [M?1,L?1]点对应于线性卷积
x[k]?h[k]中的 [0,L?M]点
y1[k]中的 [M?1,L?1]点对应于线性卷积
x[k]?h[k]中的 [ L?(M?1),2L?M?(M?1)]点
?
?
?
???????
0
)]1([][][][
n
n MLnkykhkxky
例 已知序列 x[k]=k+2,0?k?12,h[k]={1,2,1}试分别利用
重叠相加和保留法计算线性卷积,取 L=5 。
y[k]={2,7,12,16,20,24,28,32,36,40,44,48,52,41,14}
解, 重叠相加法
x1[k]={2,3,4,5,6} x2[k]={7,8,9,10,11} x3[k]={12,13,14}
y1[k]={2,7,12,16,20,17,6}
y2[k]={ 7,22,32,36,40,32,11}
y3[k]={12,37,52,41,14}
解, 重叠保留法
y[k]={2,7,12,16,20,24,28,32,36,40,44,48,52,41,14}
x1[k]={0,0,2,3,4} x2[k]={3,4,5,6,7} x3[k]={6,7,8,9,10}
y1[k]= x1[k]?h[k]= {11,4,2,7,12}
x4[k]={9,10,11,12,13}
y2[k]= x2[k]?h[k]= {23,17,16,20,24}
y3[k]= x3[k]?h[k]= {35,29,28,32,36}
y4[k]= x4[k]?h[k]= {47,41,40,44,48}
x5[k]={12,13,14,0,0}
y5[k]= x5[k]?h[k]= {12,37,52,41,14}
? DFS
? DFS的性质
? DFT
? DFT的性质
? 圆周卷积
? 利用 DFT计算线性卷积
? 频率域抽样
有限长序列的傅里叶分析
一、四种信号傅里叶表示
1,周期为 T0的连续时间周期信号
??
???
??
n
tnenXtx 0j
0 )()(
~ ??
dtetxTnX tnT 0
0
j
0
0 )(
~1)( ?? ?
?? ?? ?
频谱特点,离散非周期谱
2,连续时间非周期信号
??? ? deXtx t j)j(2 1)( ?? ? ????
dtetxX t j)()j( ?? ?????? ??
频谱特点,连续非周期谱
3,离散非周期信号
???? ?? ?? ? deeXeXkx kjjj )(2 1)([I DT F T][ ? ??
?
?
???
? ??? ? k
k
ekxkxeX j-j ][]}[{DT F T)(
频谱特点,周期为 2?的连续谱
4,周期为 N 的离散周期信号
mk
N
N
m
mkNN
m
WmXNemXNmXkx ?
?
?
?
?
????? ??
1
0
2j1
0
][~1][~1]}[~{I D F S][~
?
km
N
N
k
mkNN
k
WkxekxkxmX ????? ??
?
?
?
?
1
0
2j-1
0
][~][~]}[{D F S][~
?
频谱特点：周期为 N的离散谱
为了便于更好地理解 DFT的概念, 先讨论周期序列及其
离散傅里叶级数 （ DFS） 表示 。
一个周期为 N的周期序列，即
,k为任意整数, N为周期
周期序列不能进行 Z变换, 因为其在 n=-?到 +? 都周而
复始永不衰减, 即 z 平面上没有收敛域 。 但是, 正象连
续时间周期信号可用傅氏级数表达, 周期序列也可用离散
的傅氏级数来表示, 也即用周期为 N的正弦序列来表示 。
)(~)(~ kNnxnx ??
离散傅里叶级数（ DFS）
? ? nNjene /2
1 )(
??
? ? knNj
k ene
/2)( ??
周期为 N的正弦序列其基频成分为：
K次谐波序列为：
? ?? ? ? ? knNjnNkNj ee /2)(/2 ?? ??
但离散级数所有谐波成分中只有 N个是独立的，
这是与连续 傅 氏级数的不同之处，
即
因此
)()( nene kNk ??
将周期序列展成离散傅里叶级数时, 只需取 k=0 到
(N-1) 这 N个独立的谐波分量, 所以一个周期序列的离
散傅里叶级数只需包含这 N个复指数,
利用正弦序列的周期性可求解系数 。
将上式两边乘以, 并对一个周期
求和
? ?? ?
?
?
1
0
/2)(~1)(~
N
K
knNjekX
N
nx ?
)(~ kX
rnNje )/2( ??
? ?? ? ?
?
?
?
?
??
?
?
?
?
?
??
??
1
0
1
0
)(21
0
1
0
1
0
)(22
)(~1)(~1)(~
N
k
N
n
nrk
N
jN
n
N
n
N
k
nrk
N
jrn
N
j
ekX
N
ekX
N
enx
???
]
1
11)[(~1
0
/)(2
)(2
?
?
?
?
?
?
?? N
k
Nrkj
rkj
e
e
N
kX ?
?
rk
sNrk
e
N
N
n
nrk
N
j
?
??
?
?
?
??
?
?
?
0
11 1
0
))(
2
(
?
上式中 [ ]部分显然只有当 k=r时才有值为 1,其他任意 k值时均为
零,所以有
或写为
1) 可求 N 次谐波的系数
2） 也是一个由 N 个独立谐波分量组成的傅立叶级数
3） 为周期序列, 周期为 N。
)(~)(~
1
0
2
rXenx
N
n
rn
N
j
??
?
?
? ?
10)(~)(~
1
0
2
???? ?
?
?
?
?
??
?
??
NkenxkX
N
n
kn
N
j ?
)(~ kX
)(~ kX
)(~ kX
? ?
? ?
)(
~
)(
~
)(
~
)(
~
1
0
/2
1
0
)(/2
kXenx
enxmNkX
N
n
knNj
N
n
nmNkNj
??
??
?
?
?
?
?
?
?
??
?
?
?时域上周期序列的离散傅里叶级数在频域上仍是一个
周期序列。
是一个周期序列的离散傅里叶级数 (DFS)
变换对, 这种对称关系可表为：
习惯上：记,
)(~)(~ nxkX ?
? ??
?
?
???
1
0
/2)(~)](~[)(~
N
n
knNjenxnxD F SkX ?
? ??
?
?
??
1
0
/2)(~1)](~[)(~
N
n
nkNjekX
N
kXI D F Snx ?
? ?Nj
N eW
/2 ???
DFS变换对公式表明，一个周期序列虽然是无穷
长序列，但是只要知道它一个周期的内容（一个周期
内信号的变化情况），其它的内容也就都知道了，所
以这种无穷长序列实际上只有 N个序列值的信息是有
用的，因此周期序列与有限长序列有着本质的联系。
? ?
? ??
?
?
?
?
?
?
??
??
1
0
1
0
)(
~
)(
~1
)(~
)(~)(~)(
~
N
k
kn
N
N
n
kn
N
kXI D F SWkX
N
nx
nxD F SWnxkX
则 DFS变换对可写为
DFS[·] —— 离散傅里叶级数变换
IDFS[·]—— 离散傅里叶级数反变换。
DDFS的几个主要特性：
假设 都是周期为 N 的两个周期序列, 各自的
离散傅里叶级数为：
1） 线性
a,b为任意常数
)(~)(~ nynx,
? ?
? ???
?
?
?
)(~)(~
)(~)(~
nyD F SkY
nxD F SkX
? ? )(~)(~)(~)(~ kYbkXanybnxaD F S ???
2） 序列移位
证 因为 及 都是以 N为周期的函数,
所以有
? ?
? ???
?
??
?? ?
)(~)(~
)(~)(~
nxwlkXI D F S
kXwmnxD F S
nl
N
mk
N
)(~ nx kn
Nw
? ? ? ??
?
??
?
?????
1
0
1
)(~)(~)(~
N
n
mN
mi
km
N
ki
N
kn
N wwixwmnxmnxD F S
)(
~
)(
~
)(
~
1
0
1
kXwwixw
wixw
mk
N
N
i
ki
N
mk
N
mN
mi
ki
N
mk
N
?
?
?
?
??
?
?
??
?
?
?
由于 与 对称的特点，同样可证明)(~ nx )(~ kX
? ? )(~)(~ nxwlkXI D F S nlN??
3） 共轭对称性
对于复序列 其共轭序列 满足
? ?nx~ ? ?nx*~
? ?? ? ? ?kXnx ?? ** ~~D F S
? ?? ?
? ?kXWnx
Wnxnx
N
n
nk
N
N
n
nk
N
???
?
?
?
?
?
?
?
?
*
1
0
*
1
0
**
~
))(~(
)(~~D F S
证,
? ?? ? ? ?kXnx ** ~~D F S ??
同理,
进一步可得
? ?? ? ? ? ? ?
)](
~
)(
~
[
2
1
]~~[D F S
2
1
}~R e{D F S
*
*
kNXkX
nxnxnx
???
??
? ?? ?? ? ? ? )](~)(~[
2
1~~ReDF S *
e kNXkXkXnx ????
共轭偶对称分量
? ?? ?? ? ? ? )](~)(~[
2
1~~ImDF S *
o kNXkXkXnxj ????
共轭奇对称分量
4） 周期卷积
若
则
或
)(~)(~)(~ kYkXkF ?
? ? ? ?
?
???
1
0
)(~)(~)(~)(~
N
m
mnymxkFI D F Snf
?
?
?
??
1
0
)(~)(~
N
m
mnxmy
周 期 卷 积
证：
这是一个卷积公式, 但与前面讨论的线性卷积的差
别在于, 这里的卷积过程只限于一个周期内 （ 即
m=0~N-1）, 称为周期卷积 。
例：,,周期为 N=7,宽度分别为 4
和 3,求周期卷积。
结果仍为周期序列，周期为 N 。
? ? ? ?
?
???
1
0
)(~)(~1)(~)(~)(~
N
k
kn
NwkYkXNkYkXI D F Snf
? ?
?
?
?
?
??
1
0
1
0
)(~)(~1
N
k
N
m
nk
N
mk
N wkYwmxN
? ???
?
?
?
?
?
?? ???
?
?
??
?? 1
0
1
0
1
0
)( )(~)(~)(~1)(~
N
m
N
m
N
k
kmn
N mnymxwkYNmx
)(~ nx )(~ ny
)(~)(~)(~ nynxnf ?
?? ?
?
?
?
?????
1
0
1
0
)(~)(~1)(~)(~1)](~[)(~
N
l
N
l
lYlkXNlkYlXNnfD F SkF
由于 DFS与 IDFS的对称性，对周期序列乘
积，存在着频域的周期卷积公式，
若
则
我们知道周期序列实际上只有有限个序列值有意义, 因此
它的许多特性可推广到有限长序列上 。
一个有限长序列 x(n),长为 N，
为了引用周期序列的概念, 假定一个周期序列, 它
由长度为 N 的有限长序列 x(n) 延拓而成, 它们的关系：
???
?
???
? ????
n
Nnnxnx
其余0
10)()(
)(~ nx
?
?
?
?
?
?
?
?
?
? ???
?
?? ?
?
???
n
Nnnx
nx
rNnxnx
r
其它0
10)(~
)(
)()(~
离散傅里叶变换（ DFT）
周期序列的主值区间与主值序列：
对于周期序列, 定义其第一个周期 n=0~N-1,为
的, 主值区间,, 主值区间上的序列为主值序列 x(n)。
x(n)与 的关系可描述为：
数学表示：
RN（ n） 为矩形序列 。
符号 （（ n）） N 是余数运算表达式, 表示 n 对 N 求余数 。
)(~ nx
)(~ nx
)(~ nx
?
?
?
"")(~)(
)()(~
主值序列的是
的周期延拓是
nxnx
nxnx
?
?
?
??
?
)())(()()(~)(
))(()(~
nRnxnRnxnx
nxnx
NNN
N
)(~nx
)(nx
例,是周期为 N=8 的序列，求 n=11 和 n=-2
对 N的余数。
因此
)(~ nx
6))2((68)1(2
3))11((38111
8
8
?????????
??????
n
n
)6()2(~),3()11(~ xxxx ???
频域上的主值区间与主值序列：
周期序列 的离散付氏级数 也是一个
周期序列，也可给它定义一个主值区间
，以及主值序列 X(k)。
数学表示：
)(~ nx )(~ kX
10 ??? Nk
?
?
?
?
?
N
N
kXkX
kRkXkX
))(()(~
)()(~)(
10)(~)](~[)(~
1
0
????? ?
?
?
NkWnxnxD F SkX
N
n
kn
10)(~1)](~[)(~
1
0
????? ?
?
?
? NnWkX
NkXI D F Snx
N
n
kn
再看周期序列的离散傅里叶级数变换（ DFS）公式：
这两个公式的求和都只限于主值区间（ 0~N-1），它
们完全适用于主值序列 x(n) 与 X(k),因而我们可得到
一个新的定义 —— 有限长序列离散傅里叶变换定义。
长度为 N的有限长序列 x(n), 其离散傅里叶变换 X(k) 仍是
一个长度为 N 的有限长序列, 它们的关系为：
x(n) 与 X(k) 是一个有限长序列离散傅里叶变换对, 已知
x(n) 就能唯一地确定 X(k), 同样已知 X(k) 也就唯一地确定
x(n), 实际上 x(n) 与 X(k) 都是长度为 N 的序列 （ 复序列 ） 都
有 N个独立值, 因而具有等量的信息 。
有限长序列隐含着周期性。
?
?
?
??
?
?
?????
?????
?
?
?
?
?
?
?
10)(
1
)]([)(
10)()]([)(
1
0
1
0
NnWkX
N
kXI D F Tnx
NkWnxnxD F TkX
N
k
kn
N
N
n
kn
N
1,线性
? ? ? ? ? ?][D F T][D F T][][D F T 2121 kxbkxakbxkax ???
需将较短序列补零后，再按长序列的点数做 DFT
2,循环位移 (Circular shift of a sequence)
][])[(][ kRnkxky NN??
循环位移定义为
离散傅里叶变换的性质
x [ k ],N = 5
0 1 2 3 4
])[( Nkx
-5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9
])2[( 5?kx
-5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9
55 ])2[( Rkx ?
0 1 2 3 4
1
5
4
3
2
k=0
k==2
k=1
k=4
k=3
][~]}[~{D FS mXWnkx mnN????
? ? ][][])[(D FT mXWkRnkx mnNNN ???
][~]}[~{ lmXkxWD F S lkN ???
? ? ][])[(][D FT mRlmXkxW NNlkN ??
DFT频域循环位移特性
DFT时域循环位移特性
3,对称性 (symmetry)
周期共轭对称 (Periodic conjugate symmetry)定义为
周期共轭反对称 (Periodic conjugate antisymmetry)定义为
][*][])[(*][ kNxkRkxkx NN ????
][*][])[(*][ kNxkRkxkx NN ??????
当序列 x[k]为实序列时，周期偶对称序列满足
][][ kNxkx ??
当序列 x[k]为实序列时，周期奇对称序列满足
][][ kNxkx ???
对称特性
][~]}[~{D FS mXkx ??? ??
][~]}[~{D FS mXkx ?? ???
][~]}[])[({ mXkRkxD F T NN ?? ??
][])[(]}[{D FT mRmXkx NN?? ??
当 x[k]是实序列时
][])[(][ kRmXmX NN?? ?
4.循环卷积
定义 ][1 kx N ][2 kx ][])[(])[( 21
1
0
kRnkxnx NNN
N
n ?
????? ?? ?
?
?
x [ k ],N =4
0 1 2 3
1
2
3
4
h [ k ]
0 1 2 3
1
0 1 2 3
1
0 1 2 3
1
0 1 2 3
1
0 1 2 3
1
x [ k ] 4 h [ k ]
0 1 2 3
4
1
2
3
h[(?n)N]
h[(1?n)N]
h[(2?n)N]
h[(3?n)N]
卷积定理
? ? ][][][][D F T 2121 mXmXkxNkx ?
? ? ][][1][][D F T 2121 mXNmXNkxkx ?
序列 DFT与 z变换的关系
R e ( z )
j I m ( z )
N
?2
m
N
?2
0
z
平 面
)1(
2
?N
N
?
单 位 圆
- 1
1
j
- j
mNj
ez
mNj
k
N
kez
zkxzXmX
?? 22
|][)(][
1
0 ?
?
?
??
??? kmNN
k
ekx
?2j-1
0
][?
?
?
?
x[k]的 X[m]等于其 z变换 X(z)在单位圆上等间隔取样
设序列 x[k]的长度为 N
kN
k
zkxzX ?
?
?
?? ][)(
1
0
km
N
N
k
WkxmX ][][
1
0
?
?
?
?
11,0;)(][ 2 ???
?
NmzXmX
m
N
j
ez
??
][mX ?? ?? IDFT ][kx ??? ?? 变换Z )(zX
m
N
N
m
N
Wz
mX
N
zzX
??
?
?
?
?
?? ?
1
1
0 1
][)1()( (内插公式 )
问题提出, ? ? ][][][][D F T
2121 mXmXkxkx ??
实际需要,LTI系统响应 y[k]=x [k]?h[k]
可否利用 DFT计算线性卷积？
例,x1[k]={1,1,1},x 2[k]={1,1,0,1},N=4
一、两个有限长序列的线性卷积
][][ ],[][ 2121 kxkxkxkx ??
利用 DFT计算线性卷积
0 1
1
k
2
][2 kx
3
0
? 1
1
n
? 2
][1 nx ?
? 3
0
? 1
1
n
? 2
]1[1 nx ?
1
1
?
1
n
? 1
]2[1 nx ?
2
2
?
1
n
?
]3[1 nx ?
3
4
?
1
n
?
]5[1 nx ?
5
5
?
1
n
?
]6[1 nx ?
6
0 1
2
k
2
1
3
][*][ 21 kxkx
5
4
3
?
1
n
?
]4[1 nx ?
4
线性卷积的矩阵表示
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
]5[
]4[
]3[
]2[
]1[
]0[
y
y
y
y
y
y
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
]0[]1[]2[000
]0[]1[]2[00
]0[]1[]2[0
]0[]1[]2[
]0[]1[
]0[
111
111
111
111
11
1
xxx
xxx
xxx
xxx
xx
x
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0
0
]3[
]2[
]1[
]0[
2
2
2
2
x
x
x
x
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
111000
11100
1110
111
11
1
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0
0
1
0
1
1
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1
2
2
2
2
1
0 1
1
n
2
][1 nx
30 1
1
n
2
][2 nx
3
0 1
1
n
2
][])[(1 nRnx NN?
3
0 1
1
n
2
][])1[(1 nRnx NN?
3
0 1
1
n
2
][])2[(1 kRkx NN?
30 1
1
n
2
][])3[(1 kRkx NN?
30 1
2
k
2
3
3
][][ 21 kxkx ?
循环卷积的矩阵表示
?
?
?
?
?
?
?
?
?
?
?
?
?
]3[
]2[
]1[
]0[
y
y
y
y
?
?
?
?
?
?
?
?
?
?
?
?
]0[]1[]2[]3[
]3[]0[]1[]2[
]2[]3[]0[]1[
]1[]2[]3[]0[
1111
1111
1111
1111
xxxx
xxxx
xxxx
xxxx
?
?
?
?
?
?
?
?
?
?
?
?
]3[
]2[
]1[
]0[
2
2
2
2
x
x
x
x
?
?
?
?
?
?
?
?
?
?
?
?
?
1110
0111
1011
1101
?
?
?
?
?
?
?
?
?
?
?
?
1
0
1
1
?
?
?
?
?
?
?
?
?
?
?
?
?
2
2
3
2
0 1
1
k
2
][2 kx
3
0 1
1
n
2
][])[(1 nRnx NN?
30 1
1
n
2
][])1[(
1
nRnx
NN
?
3
0 1
1
n
2
][])2[(1 kRkx NN?
30 1
1
n
2
][])3[(1 kRkx NN?
30 1
1
n
2
][])4[(1 kRkx NN?
3 54
0 1
1
n
2
][])5[(1 kRkx NN?
3 540 1
2
k
2
1
3
][][
21
kxkx ?
54
循环卷积的矩阵表示
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
]5[
]4[
]3[
]2[
]1[
]0[
y
y
y
y
y
y
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
]0[]1[]2[000
0]0[]1[]2[00
00]0[]1[]2[0
000]0[]1[]2[
]5[000]0[]1[
]5[]4[000]0[
111
111
111
111
111
111
xxx
xxx
xxx
xxx
xxx
xxx
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0
0
]3[
]2[
]1[
]0[
2
2
2
2
x
x
x
x
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
111000
011100
001110
000111
100011
110001
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0
0
1
0
1
1
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1
2
2
2
2
1
若 x[k]的长度为 N,h[k]的长度为 M，则 L=N+M?1点
循环卷积等于 x[k] 与 h[k]的线性卷积。
补 L ? N 零
补 L ? M 零
L 点 DFT
L 点 DFT
L 点I DFT
][ kx
][ kh
][ ky
x 1 [ k ]
h 1 [ k ]
][][][][ 11 khkxkhkx ???
0 1 2 3 4 5 6
0
2
4
6
R e s u l t o f L i n e a r C o n v o l u t i o n
T i m e i n d e x k
A
m
p
l
it
u
d
e
0 1 2 3 4 5 6
0
1
2
3
x 1 0
- 1 5
T i m e i n d e x k
A
m
p
l
it
u
d
e
E r r o r M a g n i t u d e
直接计算与由 DFT间接计算结果比较
若 x1[k]为 M 点序列,x2[k]为 L 点序列, L?M
x1[k] L x2[k]中哪些点不是线性卷积的点?
k
?
][2 kx
L ? 1
k
?
][1 kx
M ? 1
问题讨论
n
?
][1 nx
M ? 1
n
?
][2 nx
L ? 1
n
?
L ? M ? 1 L ? 1
n
?
L ? M ? 2 L ? 1
n
?
M ? 1
][])1[(1 nRnMx LL?? 0? k ? M?2不是线性卷积
的结果，即前 (M?1)个点
与线性卷积不一样。
][])[(1 nRnx LL? ][])1[(1 nRnx LL?
线性卷积的矩阵表示
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
???
?
??
]0[]1[]2[]1[
]0[]3[]2[]1[
]0[]1[]2[
]0[]0[]1[
]0[]2[]1[
]0[]1[
]0[
1111
1111
111
111
111
11
1
xxMxMx
xMxMxMx
xxx
xxMx
xMxMx
xx
x
??
??
???
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0
0
0
0
]1[
]1[
]0[
2
2
2
?
?
Lx
x
x
? ? ??????? TMLyMLyMyMyMyyy ]1[]2[]1[][]1[]1[]0[ ??
循环卷积的矩阵表示
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
????
?
??
?
??
]0[]3[]2[]1[
0]4[]3[]2[]1[
0]0[]1[]2[
0]0[]0[]1[
0000]0[]2[]1[
]2[]1[000]0[]1[
]1[]1[]2[000]0[
1111
1111
111
111
111
1111
1111
xMxMxMx
MxMxMxMx
xxx
xxMx
xMxMx
xMxxx
xMxMxx
??
??
?????
??
??
??
??????
??
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? ]1[
0
0
0
0
]1[
]0[
2
2
2
Lx
x
x
?
?
? ? ????? TLyLyMyMyMyyy ]1[]2[]1[][]1[]1[]0[ ??
x1[k] L x2[k]
k=0 ~M?2,前 M?1个点不是线性卷积的点
k= M?1 ~ L?1,L?M+1个点与线性卷积的点对应
线性卷积 L ~ L+M?2 后 M ?1点没有计算
则 L点循环卷积
结论
若 x1[k]为 M 点序列,x2[k]为 L 点序列, L?M
长序列和短序列的线性卷积
直接利用 DFT计算的缺点：
(1) 信号要全部输入后才能进行计算，延迟太多
(2) 内存要求大
(3) 算法效率不高
解决问题方法：采用分段卷积
分段卷积可采用 重叠相加法 和 重叠保留法
1,重叠相加（ overlap add）
将长序列 x[k] 分为若干段长度为 L的序列
][][
0
nLkxkx n
n
?? ?
?
?
?
?
? ?????
0
10 ][
][
其它
LknLkx
kx n
k][ kx ][0 kx ][1 kx ][2 kx ][3 kxL L2 L3
其中
][][][][
0
khnLkxkhkx n
n
???? ?
?
?
][
0
nLky n
n
?? ?
?
?
y0[k]的非零范围 20 ???? MLk
y1[k?L]的非零范围 22 ???? MLkL
序列 y0[k],y1[k]的重叠部分 2???? MLkL
重叠的点数 L+M?2?L+1=M?1
][][][,khkxky nn ??记
依次将相邻两段的 M-1个重叠点相加，即得到最终的
线性卷积结果。
0 1
1
k
2
][ kh
M - 1
M = 4
0 1
1
k
2
][ kx 1?L
L = 7
重叠相加法分段卷积举例
0 1
k
2
][0 ky
4
3
1
2
3
96
0 1
k
2
][1 Lky ?
4
7 9
1
2
3
0 1
k
2
][][ nLkyky n ?? ?
4
3
1
2
3
方法：
(1) 将 x[k]长序列分段，每段长度为 L；
(2) 各段序列 xn[k]与 M点短序列 h[k]循环卷积；
(3) 从各段循环卷积中提取线性卷积结果。
2.重叠保留法 (overlap save)
前 M?1个点不是线性卷积的点因 yn[k]=xn [k] L h[k]
故分段时，每段与其前一段有 M?1个点重叠。
? ?x [k (M 1)]
M?1
? ?L (M 1)
L?1
x 0[k]
x 1[k]
2L?M k
)]1([][ ????? MLnkxkx n
第一段前需补 M-1个零
记 yn[k] =xn [k] L h[k]
0
1?L
k
0
][
1
k
y
k
1?L
][
0
k
y
M - 1
M - 1
y0[k]中的 [M?1,L?1]点对应于线性卷积
x[k]?h[k]中的 [0,L?M]点
y1[k]中的 [M?1,L?1]点对应于线性卷积
x[k]?h[k]中的 [ L?(M?1),2L?M?(M?1)]点
?
?
?
???????
0
)]1([][][][
n
n MLnkykhkxky
例 已知序列 x[k]=k+2,0?k?12,h[k]={1,2,1}试分别利用
重叠相加和保留法计算线性卷积,取 L=5 。
y[k]={2,7,12,16,20,24,28,32,36,40,44,48,52,41,14}
解, 重叠相加法
x1[k]={2,3,4,5,6} x2[k]={7,8,9,10,11} x3[k]={12,13,14}
y1[k]={2,7,12,16,20,17,6}
y2[k]={ 7,22,32,36,40,32,11}
y3[k]={12,37,52,41,14}
解, 重叠保留法
y[k]={2,7,12,16,20,24,28,32,36,40,44,48,52,41,14}
x1[k]={0,0,2,3,4} x2[k]={3,4,5,6,7} x3[k]={6,7,8,9,10}
y1[k]= x1[k]?h[k]= {11,4,2,7,12}
x4[k]={9,10,11,12,13}
y2[k]= x2[k]?h[k]= {23,17,16,20,24}
y3[k]= x3[k]?h[k]= {35,29,28,32,36}
y4[k]= x4[k]?h[k]= {47,41,40,44,48}
x5[k]={12,13,14,0,0}
y5[k]= x5[k]?h[k]= {12,37,52,41,14}
