1
第三章离散傅里叶变换
(Discrete Fourier Transform
)
2
§
3-1
傅里叶变换的几种形式时域
x(t)
、
x(n)
与频域
X(j
)
、
X(e
j
ω
)
之间的变换关一、连续时间与连续频率的傅立叶变
)
(
),
(
j
X
t
x
a
a
∫
∞
∞
=
dt
e
t
x
j
X
t
j
a
a
)
(
)
(
=
∫
∞
∞
d
e
j
X
t
x
t
j
a
a
)
(
2
1
)
(
π
)
(
t
x
a
t
)
(
j
X
a
结论
：一非周期连续时间函数对应于一非周期连续频率函数
3
二、连续时间与离散频率的傅里叶表示（变换）
即周期性信号的傅里叶表示：
∑
∞
∞
=
=
m
t
jm
a
e
m
X
t
x
)
(
)
(
)
(
t
x
a
)
(
m
X
∫
=
2
2
)
(
1
)
(
T
T
t
jm
a
dt
e
t
x
T
m
X
)
(
t
x
a
t
)
(
m
X
T
π
2
=
m
4
T
π
2
=
相邻两谱线间隔为结论：周期性连续的时间函数对应于非周期的离散频率函数三、离散时间与连续频率的傅里叶变换 即：时域离散序列的傅里叶变换
∑
∞
∞
=
=
n
n
j
j
e
n
x
e
X
ω
ω
)
(
)
(
∫
∞
∞
=
ω
π
ω
ω
d
e
e
X
n
x
n
j
j
)
(
2
1
)
(
5
)
(
n
x
n
T
π
2
)
(
ω
j
e
X
ω
结论：非周期的离散时间函数对应于周期性连续频率函数
。
四、离散时间与离散频率的傅里叶变换对傅里叶变换，
t
与
f
是对称的因此在频域上取样将在时域上得到周期函数
6
)
(
~
k
X
N
π
2
k
....
)
(
~
n
x
T
周期离散
)
(
~
n
x
周期离散
)
(
~
k
X
即：周期性的离散时间函数对应于周期性离散频率函数 ---
离散傅里叶级数
DFS
7
§
3-2
离散傅里叶级数
(DFS)
一、定义已知
x(n) 0
≤
n
≤
N-1
有限长
,
则其傅里叶变换
）
周期为
π
ω
ω
2
(
)
(
)
(
1
0
∑
=
=
N
n
n
j
j
e
n
x
e
X
)
(
~
ω
j
e
X
记为：
∑
=
=
1
0
)
(
)
(
~
N
n
n
j
j
e
n
x
e
X
ω
ω
)
(
~
n
x
对频域取样，一周期内取样
N
点，将使时域
x(n)
周期化为
8
k
N
k
π
ω
2
=
ω被离散化：
正变换
DFS
e
n
x
e
X
k
X
N
n
kn
N
j
k
N
j
=
=
∴
∑
=
=
1
0
2
2
)
(
~
)
(
~
)
(
~
π
π
ω
ω
)
(
~
)
(
~
)
(
~
)
(
~
1
0
2
1
0
)
(
2
k
X
e
n
x
e
n
x
N
k
X
N
n
kn
N
j
N
n
n
N
k
N
j
=
=
=
+
∑
∑
=
=
+
π
π
显然
π
2
反变换：
kr
N
j
e
两边同乘并对一周期求和
∑∑
∑∑
∑
=
=
=
=
=
=
=
1
0
1
0
)
(
2
2
1
0
1
0
2
1
0
2
)
(
~
)
)
(
~
(
)
(
~
N
n
N
k
n
r
k
N
j
kr
N
j
N
k
N
n
kn
N
j
N
k
kr
N
j
e
n
x
e
e
n
x
e
k
X
π
π
π
π
9
正交原理）
而
(
0
)
(
sin
)
(
sin
11
)
(
)
(
)
(
2
)
(
2
1
0
)
(
2
≠
=
=
=
=
=
∑
n
r
n
r
N
n
r
N
e
n
r
e
ee
e
n
r
N
j
n
r
j
n
r
N
j
n
r
j
N
k
n
r
k
N
j
π
π
π
π
ππ
π
)
(
~
)
(
~
1
0
2
r
x
N
e
k
X
N
k
kr
N
j
=
∴
∑
=
π
nk
N
j
N
k
e
k
X
N
n
x
π
2
1
0
)
(
~
1
)
(
~
∑
=
=
∴
N
j
N
e
W
π
2
=
记
[]
[]
∑
∑
=
=
=
=
=
=
nk
N
N
n
nk
N
N
k
W
n
x
n
x
DFS
k
X
W
k
X
N
k
X
IDFS
n
x
1
0
1
0
)
(
~
)
(
~
)
(
~
)
(
~
1
)
(
~
)
(
~
则有
10
二、
的物理意义
)
(
~
k
X
{
1
0
)
(
~
else
0
)
(
≤
≤
=
N
n
n
x
n
x
∑
∑
=
=
=
=
1
0
1
0
)
(
~
)
(
)
(
N
n
n
N
n
n
z
n
x
z
n
x
z
X
k
N
j
k
N
e
z
W
z
z
X
z
X
k
X
π
2
)
(
)
(
)
(
~
=
=
=
=
即是在的一个周期所得序列的
Z
变换单位圆上等间隔取样得到的。每循环一次，得到的一个周期
)
(
~
k
X
)
(
~
n
x
)
(
~
k
X
[
]
Z
jI
m
N
π
2
[
]
Z
R
e
1
=
Z
11
)
(
~
)
(
~
)
(
~
2
1
3
n
x
b
n
x
a
n
x
+
=
)
(
~
)
(
~
)
(
~
2
1
3
k
X
b
k
X
a
k
X
+
=
三、
DFS
的性质
1
、线性：
[
]
)
(
~
)
(
~
k
X
W
m
n
x
DFS
mk
N
=
+
[]
nk
N
N
n
W
m
n
x
m
n
x
DFS
∑
=
+
=
+
1
0
)
(
~
)
(
~
2
、序列移位：
(1)
时域移位令
i=n+m
ik
N
m
N
m
i
mk
N
mk
N
ik
N
m
N
m
i
W
i
x
W
W
W
i
x
∑
∑
+
=
+
=
=
=
∴
1
1
)
(
~
)
(
~
上式
)
(
~
)
(
~
1
0
k
X
W
W
i
x
W
mk
N
ik
N
N
i
mk
N
=
=
=
∑
[
]
)
(
~
)
(
~
n
x
W
l
k
X
IDFS
l
N
n
=
+
(2)
频域移位
12
3
、周期卷积
（
1
）时域卷积两个周期信号（序列）的卷积，只限在一个周期内卷积。
)
(
~
)
(
~
1
1
k
X
n
x
→
)
(
~
)
(
~
2
2
k
X
n
x
→
[]
)
(
~
)
(
~
)
(
~
)
(
~
2
1
2
1
k
X
k
X
n
x
n
x
DFS
=
则，
∑
∑
=
=
=
=
1 0
1
2
1 0
2
1
2
1
)
(
~
)
(
~
)
(
~
)
(
~
)
(
~
)
(
~
N m
N m
m
n
x
m
x
m
n
x
m
x
n
x
n
x
而
13
[]
)
(
~
)
(
~
)
(
~
)
(
~
)
),
(
(
)
(
~
)
(
~
)
(
~
)
(
~
)
(
~
)
(
~
)
(
~
)
(
~
2
1
1
0
2
1
2
1
2
1
)
(
1
0
2
1 0
1
1
0
1 0
2
1
2
1
k
X
k
X
W
r
x
k
X
N
W
r
x
W
r
x
k
X
m
n
r
W
m
n
x
W
m
x
W
m
n
x
m
x
n
x
n
x
DFS
rk
N
N
r
rk
N
rk
N
m
N
m
r
k
m
n
N
N
n
mk
N
N m
N
n
nk
N
N m
=
=
=
=
=
=
∑
∑
∑
∑
∑∑
=
=
=
=
=
=
为周期均以
，则原式令证：
如下
)
(
~
),
(
~
2
1
n
x
n
x
3
=
N
12
0
1
..
.
...
14
周期卷积
01
2
m
)
(
~
1
m
x
)
(
~
)
(
~
2
1
n
x
n
x
...
.
...
.
n
-3
-2
-1
0
1
2
3
4
5
1
2
)
(
~
2
m
x
...
...
m
0
2
1
15
(2)
频域卷积定理
)
(
~
)
(
~
)
(
~
2
1
3
n
x
n
x
n
x
=
)
(
~
)
(
~
1
)
(
~
)
(
~
1
)
(
~
2
1
0
1
2
1
3
l
k
X
l
X
N
k
X
k
X
N
k
X
N
l
=
=
∑
=
)
(
~
)
(
~
)
(
~
1
)
(
~
1
)
(
~
)
(
~
1
)
(
~
1
)
(
~
2
1
)
(
1
0
2
1
0
1
1
0
1
0
2
1
2
1
0
3
3
n
x
n
x
W
l
k
X
N
W
l
X
N
W
l
k
X
l
X
N
W
k
X
N
n
x
l
k
n
N
N
k
nl
N
N
l
N
k
nk
N
N
l
N
k
nk
N
=
=
=
=
=
=
=
=
=
∑
∑
∑∑
∑
16
§
3
离散傅里叶变换
(DFT)
也称有限长序列的傅里叶级数。 即
DFT
是将有限长序列看成周期为
N
的时间序列的一个周期。
一、定义
:
1
0
≤
≤
N
n
设有限长序列
x(n)
∑
∞
∞
=
+
=
r
rN
n
x
n
x
)
(
)
(
~
则可把
x(n)
周期延拓
：
)
(
)
(
~
)
(
))
((
)
(
~
,
)
(
~
)
(
n
R
n
x
n
x
n
x
n
x
n
x
n
x
N
N
=
=
记为：
的主值序列为而
)
(
)
(
~
)
(
))
((
)
(
~
k
R
k
X
k
X
k
X
k
X
N
N
==
同理：
17
表示可得的关系
、
据
DFT
k
X
n
x
,
)
(
~
)
(
~
∑
∑
≤
≤
=
≤
≤
=
=
=
1
0
)
(
)
(
1
0
)
(
1
)
(
1
0
1
0
N
k
W
n
x
k
X
N-
n
W
k
X
N
n
x
kn
N
N
n
kn
N
N
k
二、
DFT
性质
1
、线性
)
(
)
(
2
1
n
x
n
x
、
[
]
)
(
)
(
1
1
n
x
DFT
k
X
=
[
]
)
(
)
(
2
2
n
x
DFT
k
X
=
N
列长
)
(
)
(
)
(
2
1
3
n
bx
n
ax
n
x
+
=
若
)
(
)
(
)
(
2
1
3
k
bX
k
aX
k
X
+
=
则
18
2
、
IDFT
的另一种表示方法：
∑
=
=
1
0
)
(
1
)
(
N
k
nk
N
W
k
X
N
n
x
[]
[]
=
=
=
∑
)
(
1
)
(
1
)
(
1
0
k
X
DFT
N
W
k
X
N
n
x
N
k
nk
N
取两次共轭
3
、对称定理：
[
]
)
(
)
(
))
((
)
(
k
N
Nx
k
R
k
Nx
n
X
DFT
N
N
=
=
则
)
(
)
(
k
X
n
x
∑
=
=
1
0
)
(
1
)
(
N
k
nk
N
W
k
X
N
n
x
Q
∑
=
=
∴
1
0
)
(
1
)
(
))
((
N
k
nk
N
N
N
W
k
X
N
n
R
n
x
19
交换
n,k
得：
[]
)
(
))
((
)
(
k
R
k
Nx
n
X
DFT
N
N
=
即
X(n)
的频谱与
x(n)
的形状在时间上互为倒置
)
(
)
(
k
X
n
x
4
、反转定理：
)
(
))
((
)
(
))
((
k
R
k
X
n
R
n
x
N
N
N
N
)
(
))
((
)
(
)
(
))
((
1
0
1 0
k
R
k
X
W
m
x
W
n
R
n
x
N
N
N
n
N m
mk
N
n
m
nk
N
N
N
=
=
∑∑
=
=
=
证明：
)
(
))
((
)
(
))
((
k
R
k
X
n
R
n
x
N
N
N
N
∴
20
5
、序列的总和
∑
∑
=
=
=
=
=
=
=
1
0
0
1
0
0
)
0
(
)
(
)
(
)
(
N
n
k
N
n
kn
N
k
X
n
x
W
n
x
k
X
∑
=
=
1
0
)
(
1
)
0
(
N
k
k
X
N
x
6
、序列的始值
7
、序列的循环移位（圆周移位）
x(n),n:0---N-1,
移位后仍在
[0
，
N-1]
取值将发生信息丢失右移一位
)
(
n
x
0
1
2
0 1 2 3
0
1 2
21
为避免发生信息丢失，移位时应先将周期延拓成再移位
，然后再取
[0
，
N-1]
上的值
)
(
n
x
N
n
x
n
x
))
((
)
(
~
=
)
(
)
(
~
n
R
m
n
x
N
+
∴
循环移位可表示成
)
(
~
n
x
)
1
(
~
n
x
)
(
)
1
(
~
n
R
n
x
N
3
=
N
n
0 1 2
….
……
-3 -2 -1 0 1 2 3 4 5
……
……
0 1 2
显然没有信息丢失，只不过从右端移出去的值又从左端移入 主值区间。仿佛是序列
x(n)
排列在一个
N
等分的圆周上，故称圆周移位
22
[
]
)
(
~
)
(
~
k
X
W
m
n
x
DFS
km
N
=
+
由
DFS
性质：
[]
)
(
)
(
))
((
)
(
))
((
k
X
W
k
R
k
X
W
n
R
m
n
x
DFT
km
N
N
N
km
N
N
N
=
=
+
知
(
)
线性移位注：
)
(
)
(
))
((
m
n
x
n
R
m
n
x
N
N
+
≠
+
[]
)
(
)
(
))
((
n
x
W
k
R
l
k
X
IDFT
nl
N
N
N
=
+
同理频域移位：
8
、圆周卷积
)
(
)
(
)
(
2
1
3
k
X
k
X
k
X
=
若
∑
∑
=
=
=
=
=
1 0
1
2
1 0
2
1
2
1
3
)
(
))
((
)
(
)
(
))
((
)
(
)
(
)
(
)
(
N
m
N
N
N m
N
N
n
R
m
n
x
m
x
n
R
m
n
x
m
x
n
x
n
x
n
x
则
23
证明：将
X
3
(k)
周期延拓
)
(
~
)
(
~
)
(
~
1
2
3
k
X
k
X
k
X
=
[
]
∑∑
=
=
=
=
=
∴
1 0
1 0
2
1
2
1
3
3
))
((
)
(
)
(
~
)
(
~
)
(
~
)
(
~
N m
N m
N
m
n
x
m
x
m
n
x
m
x
k
X
IDFS
n
x
∑
=
=
=
∴
1 0
2
1
3
3
)
(
))
((
)
(
)
(
)
(
~
)
(
N m
N
N
N
n
R
m
n
x
m
x
n
R
n
x
n
x
24
圆周卷积过程：
例：求下列两序列的
3
点圆周卷积
(N=3)
)
(
2
n
x
0
1
2
1
0
1
2
1
)
(
1
n
x
解
,(1)
先将
，
周期延拓，作出
)
(
2
n
x
)
(
~
2
m
x
)
(
1
n
x
)
(
~
1
m
x
)
(
~
1
m
x
...
(2)
作周期卷积得
)
(
~
3
n
x
..
.
01
2
3
)
(
~
2
m
x
01
2
1
...
...
25
)
(
)
(
~
)
3
(
3
3
n
x
n
x
主值序列得的一个周期取
即列长为
N
的两有限长序列的圆周卷积的结果也是一列长为
N
的有限长序列，而线性卷积的列长为
2N-1
。
0 1 2
)
(
3
n
x
3
9
、利用圆周卷积求线性卷积
:
例上例：
)
(
)
(
2
1
n
x
n
x
线卷列长为
5
（
2N-1
或
N+M-1)
因此可以将两个序列补零到
2N-1,
然后再作圆周卷积。
(1)
补零到
2N-1
点序列
,
并周期延拓
12
0
n
34
26
)
(
1
n
x
)
(
2
n
x
1
01
2
34
1
1
2
3
04
)
(
~
1
m
x
)
(
~
2
m
x
1
1
2
3
04
1
0
1234
(2)
作周期卷积
)
(
)
(
)
(
2
1
3
n
x
n
x
n
x
=
(3)
取主值序列，得：
)
(
~
3
n
x
12
0
n
34
...
...
12
0
n
34
)
(
)
(
)
(
)
(
2
1
2
1
n
x
n
x
n
x
n
x
=
此时
27
综上所述，由
DFT
求线卷过程。已知
x
1
(n)->N,x
2
(n)->M
<1>
将
x
1
(n),x
2
(n)
分别补零到列长为
L,L
≥
N+M-1
。
<2>
将补零后的
x
1
(n),x
2
(n)
以
L
为周期进行周期延拓，并作周期卷积 <3>
取周期卷积的主值序列，得圆周卷积
?
线卷
28
10
、分段卷积：
若
x(n)
很长，要先将
x(n)
分段，再进行
DFT
。设
h(n)
列长为
M
，分段方法有两种：重叠相加法和重叠保留法。
(1)
重叠相加法：
将
x(n)
分段，每段长为
N
点，则第
K
段
x
k
(n),
+
≤
≤
=
else
N
k
n
kN
n
x
n
x
k
0
1
)
1
(
)
(
)
(
∑
∞
∞
=
=
k
k
n
x
n
x
)
(
)
(
而
∑
∞
∞
=
=
=
∴
k
k
n
h
n
x
n
h
n
x
n
y
)
(
)
(
)
(
)
(
)
(
29
由于
x
k
(n)
与
h(n)
线卷之后列长为
N+M-1
即先要将
x
k
(n)
及
h(n)
均补零到
N+M-1,
因此每一段卷积的结果都多出
M-1
个非零点。
如下图所示：
0
12
3
4
5
6
)
(
m
x
k
)
(
m
h
-2
-1
0
-3
0123
456
)
(
)
(
n
h
n
x
k
30
显然前
N
个点卷积结果是正确的，而后
M-1
点卷积结果是不正确的。实际上还应将下一段的前
M-1
点卷积结果加到前一段卷积的后
M-1
点，即前后有
M-1
点重叠相加。
(2)
重叠保留法上面分段序列中的补零部分不是补零，而是保留原来的输入序列值
(
每段的后
M-1
点保留在下一段的前端
)
。
如图所示：
点
1
M
....
点新值
N
保留
{
31
因为每一段的前
M-1
点卷积值已在前一段求出，保留这
M-1
点是为了计算第
M
点卷积结果，所以前
M-1
点结果要舍去。然后把第
M
点以后的卷积输出接起来即是最终的输出。
---“
迭接舍去法
”
。
11
、圆周相关定理（循环相关）
)
(
)
(
)
(
2
1
3
k
X
k
X
k
X
=
若
[]
∑
=
+
=
=
1
0
2
*
1
3
3
)
(
))
((
)
(
)
(
)
(
N
l
N
N
n
R
n
l
x
l
x
k
X
IDFT
n
x
则
[]
nk
N
N k
W
k
X
k
X
N
k
X
IDFT
n
x
=
∑
=
=
)
(
)
(
1
)
(
)
(
2
1
0
1
3
3
证明：
nk
N
N m
mk
N
N
k
N
l
kl
N
W
W
m
x
W
l
x
N
=
=
=
=
∑
∑∑
1 0
2
1
0
1
0
1
)
(
)
(
1
=
=
=
=
=
=
=
=
∑
∑∑
∑
∑∑
k
l
n
m
N k
N
N
l
N m
nk
N
mk
N
N m
N k
lk
N
N
l
W
N
m
x
l
x
W
W
m
x
W
l
x
N
)
(
1
0
1
0
2
1 0
1
1 0
2
1
0
1
0
1
1
)
(
)
(
)
(
)
(
1
32
{
1 0
1
0
)
(
1
=
∑
=
N
k
l
n
m
k
N
W
N
已知：
时当时当
rN
l
n
m
rN
l
n
m
≠
=
rN
n
l
m
+
+
=
即
∑
=
+
=
∴
1
0
2
1
3
)
(
))
((
)
(
)
(
N
l
N
N
n
R
n
l
x
l
x
n
x
是实数，则设
)
(
1
l
x
)
(
))
((
)
(
)
(
1
0
2
1
3
n
R
n
l
x
l
x
n
x
N
N
l
N
+
=
∑
=
线性相关为
∑
∞
∞
=
+
=
m
m
n
x
m
x
n
x
)
(
)
(
)
(
2
1
3
而：
与卷积不同：不需要折叠运算，但移位相乘和相加二者完全相同。
33
能量守恒定理
12
、帕斯维尔定理：
∑∑
=
=
=
1
0
1
0
2
2
)
(
1
)
(
N
n
N
k
k
X
N
n
x
[
]
则若
)
(
)
(
n
x
DFT
k
X
=
在圆周相关定理中，取
x
2
(
l
)=x
1
(
l
)
，且
n=0
，则：
∑∑
=
=
=
1
0
0
1
0
)
(
)
(
1
)
(
)
(
N
l
N
N
k
W
k
X
k
X
N
l
x
l
x
∑
∑
=
=
=
∴
1
0
2
1
0
2
)
(
1
)
(
N
k
N
n
k
X
N
n
x
频域能量离散时域能量
34
13
、
DFT
的奇偶性和对称性：
<1>
周期性共轭对称和共轭反对称分量上一章讲过：任一序列可分解为一共轭对称与一共轭反对称两个分量之和
[] []
=
+
=
)
(
)
(
21
)
(
)
(
)
(
21
)
(
n
x
n
x
n
x
n
x
n
x
n
x
oe
)
(
)
(
)
(
n
x
n
x
n
x
o
e
+
=
由于
x
e
(n)
与
x
o
(n)
列长均为
2N-1
，一般
DFT
不用此定义，
而采用周期性的序列来分析
DFT
的对称性质。
即将
x(n)
分解成两个列长为
N
的有限长序列。
)
(
)
(
)
(
n
x
n
x
n
x
op
ep
+
=
35
即先将
x(n)
周期延拓其共轭对称与反对称
[] []
=
+
=
)
(
~
)
(
~
21
)
(
~
)
(
~
)
(
~
21
)
(
~
n
x
n
x
n
x
n
x
n
x
n
x
oe
取主值周期：
[]
[
]
)
(
)
(
21
)
(
))
((
))
((
21
)
(
n
N
x
n
x
n
R
n
x
n
x
n
x
N
N
N
ep
+
=
+
=
[]
[
]
)
(
)
(
21
)
(
))
((
))
((
21
)
(
n
N
x
n
x
n
R
n
x
n
x
n
x
N
N
N
op
=
=
)
(
~
)
(
~
)
(
~
n
x
n
x
n
x
o
e
+
=
Q
[
]
)
(
)
(
)
(
)
(
~
)
(
~
)
(
)
(
~
)
(
n
x
n
x
n
R
n
x
n
x
n
R
n
x
n
x
op
ep
N
e
e
N
+
=
+
=
=
∴
36
x
ep
(n)
和
x
op
(n)
分别称为列长为
N
的序列
x(n)
的周期性共轭对称分量和周期性共轭反对称分量 当
x
ep
(n)
和
x
op
(n)
为实序列时
---
分别称周期性偶分量和奇分量。
[
]
则：
已知
)
(
)
(
n
x
DFT
k
X
=
)
(
))
((
)
(
)
(
k
R
k
X
n
x
a
N
N
<2>
对称性质
)
(
)
(
))
((
)
(
k
X
n
R
n
x
b
N
N
[
]
)
(
)
(
Re
)
(
k
X
n
x
c
ep
[
]
)
(
)
(
)
(
k
X
n
x
jI
d
op
m
[
]
)
(
)
(
)
(
k
X
R
n
x
e
e
ep
[
]
)
(
)
(
)
(
k
X
jI
n
x
f
m
op
37
证明：
)
(
))
((
)
(
)
(
)
(
1
0
1
0
k
R
k
X
W
n
x
W
n
x
a
N
N
N
n
nk
N
N
n
nk
N
=
=
=
=
∑
∑
)
(
)
(
))
((
)
(
))
((
)
(
1
0
1
0
k
X
W
n
R
n
x
W
n
R
n
x
b
N
n
nk
N
N
N
N
n
kn
N
N
N
=
=
=
=
∑
∑
[]
[
]
[
]
)
(
)
(
))
((
)
(
21
)
(
)
(
21
)
(
Re
)
(
1
0
1
0
k
X
k
R
k
X
k
X
W
n
x
n
x
W
n
x
c
ep
N
N
N
n
kn
N
nk
N
N
n
=
+
=
+
=
=
=
∑
∑
[]
[
]
[
]
)
(
)
(
))
((
)
(
21
)
(
)
(
21
)
(
)
(
1
0
1
0
k
X
k
R
k
X
k
X
W
n
x
n
x
W
n
x
jI
d
op
N
N
N n
kn
N
nk
N
N
n
m
=
=
=
=
=
∑
∑
[
]
[
]
[]
)
(
Re
)
(
)
(
21
)
(
))
((
)
(
21
)
(
)
(
1
0
1
0
k
X
k
X
k
X
W
n
R
n
x
n
x
W
n
x
e
N
n
kn
N
N
N
nk
N
N
n
ep
=
+
=
+
=
=
=
∑
∑
[
]
[
]
[]
)
(
)
(
)
(
21
)
(
))
((
)
(
21
)
(
)
(
1
0
1
0
k
X
jI
k
X
k
X
W
n
R
n
x
n
x
W
n
x
f
m
N
n
kn
N
N
N
nk
N
N
n
op
=
=
=
=
=
∑
∑
38
若
x(n)
为实序列，则有：
[
]
[
]
)
(
))
((
Re
)
(
Re
)
1
(
k
R
k
X
k
X
N
N
=
[
]
[
]
)
(
))
((
)
(
)
2
(
k
R
k
X
I
k
X
I
N
N
m
m
=
)
(
))
((
)
(
)
3
(
k
R
k
X
k
X
N
N
=
[
]
[
]
)
(
))
((
arg
)
(
arg
)
4
(
k
R
k
X
k
X
N
N
=
)
(
)
(
n
x
n
x
=
∴
是实序列
)
(
n
x
Q
由前面性质
(a)
得
)
(
))
((
)
(
k
R
k
X
k
X
N
N
=
利用共轭的性质就可证得性质（
1
）
---
（
4
）
39
§
4
、频域取样一、取样：设
x(n)
为任意非周期序列，其
Z
变换为
X(z)
对
X(z)
在单位圆上进行等间隔取样。设
M
为取样点数，则：
∑
∞
∞
=
=
=
=
n
nk
M
W
z
W
n
x
z
X
k
X
k
M
)
(
)
(
)
(
M
j
M
e
W
π
2
=
式中问题：频率取样后，能否用
X(k)
恢复出
x(n)
？在什么条件下能恢复？
设
x’(n)
为频率取样后所得序列，则：
∑∑
∑
=
∞
∞
=
=
=
=
′
1
0
1
0
)
(
1
)
(
1
)
(
M
km
nk
M
mk
M
M
k
nk
M
W
W
m
x
M
W
k
X
M
n
x
∑∑
∞
∞
=
=
=
m
M
k
k
n
m
M
W
M
m
x
1
0
)
(
1
)
(
40
+
=
=
=
∑
=
else
rM
n
m
rM
n
m
W
M
M
k
k
n
m
M
0
)
(
1
1
1
0
)
(
Q
∑
∞
∞
=
+
=
′
∴
r
rM
n
x
n
x
)
(
)
(
是任意整数
r
Q
即
x’(n)
是原序列
x(n)
以
M
为周期的周期延拓序列
,
对列长为
N
的有限长序列
,
频率取样不失真的条件：
N
M
≥
∑
∞
∞
=
+
=
′
=
r
M
M
n
R
rM
n
x
n
R
n
x
n
x
)
(
)
(
)
(
)
(
)
(
此时
，
41
二、
X(z)
的内插：
由
X(k)--->X(z),
即
N
个
X(k)
如何表达整个
X(z)
函数？
∑
=
=
1
0
)
(
1
)
(
N
k
nk
N
W
k
X
N
n
x
n
N
n
N
k
nk
N
N
n
n
z
W
k
X
N
z
n
x
Z
X
=
=
=
∑∑
∑
=
=
1
0
1
0
1
0
)
(
1
)
(
)
(
(
)
∑
∑∑
=
=
=
=
=
1
0
1
1
0
1
0
1
1
1
)
(
1
)
(
1
N
k
k
N
N
kN
N
N
k
N
n
n
k
N
z
W
z
W
k
X
N
z
W
k
X
N
∑
=
=
∴
1
0
1
1
)
(
1
)
(
N
k
k
N
N
z
W
k
X
N
z
z
X
1
2
=
=
kN
N
j
kN
N
e
W
π
Q
即
X(z)
的内插公式
42
§
5
、利用
DFT
计算信号的频谱
∫
∞
∞
=
dt
e
t
x
X
t
j
)
(
)
(
非周期信号
x(t)
的近似频谱：
代入上式，则得即将小段的积分值再累加，
不变，则分别求出每一内设
。在长分为无限个小段，每段将
)
(
,
,
)
(
)
,
(
→
=
→∞
∞
∫
∑
∞
∞
∞
∞
=
X
nT
t
T
dt
t
x
T
T
n
T
e
nT
x
x
n
nT
j
≈
∑
∞
∞
=
)
(
)
(
若信号从
t=0
到
T
0
有值，则将
0---T
0
分为
N
小段，
即在时域取样
N
点，则：
∑
=
≈
1
0
)
(
)
(
N
n
nT
j
e
nT
x
T
X
43
为：
相邻频率取样点的间隔点，则段，也即取样频率范围分成将频率离散化
，将为周期的连续频谱，再即是一个以据时域取样，
N
N
T
T
X
s
s
π
π
ω
π
2
0
)
2
(
2
)
(
=
=
0
0
0
2
2
2
2
F
T
TN
N
T
π
π
π
π
=
=
=
=
NT
F
1
0
=
频率间隔
N
T
π
ω
2
0
0
=
=
数字化频率
T
0
代表非周期信号的时间长度。
F
0
,
0
表示非周期信号的频谱经离散化后样点之间的频率间隔离散化后的频率点及频谱：
44
NT
k
k
π
2
0
=
=
∑
=
≈
1
0
2
0
)
(
)
(
N
n
N
n
jk
e
n
x
T
k
X
π
[
]
)
(
)
(
0
n
x
DFT
T
kF
X
=
或
1
2
,
1
,
0
=
N
k
L
[]
)
(
1
)
(
0
kF
X
IDFT
T
n
x
=
而
45
例：利用
DFT
近似求出的幅度频率样值并与理论值进行比较。
)
(
)
(
t
u
e
t
x
t
=
2
1
1
)
(
+
=
∴
X
∫
∞
+
=
=
0
1
1
)
(
j
dt
e
e
X
t
j
t
t
x(t
)
t
e
t
x
=
)
(
)
(
X
∞
→
t
0
)
(
=
t
x
（
1
）截取有限长序列
8
时当
=
t
00035
.
0
1
)
(
8
=
=
e
t
x
0
)
(
8
≈
>
t
t
x
即
8
0
=
∴
T
取信号长度
46
（
2
）确定
T
据取样定理，
m
f
T
2
1
≤
≥
T
2
1
Q
m
f
x
x
f
f
f
X
f
>
≈
,
0
)
(
,
使估算
∞
→
m
f
()
00497
.
0
201
1
32
2
1
1
)
(
2
=
=
+
=
π
f
X
则可取
.
32
=
x
f
512
64
8
64
1
64
32
0
=
×
=
=
=
=
≈
∴
T
T
N
T
f
f
s
m
，
，即
，则取
nT
e
n
x
=
)
(
47
[]
)
(
)
(
)
(
0
0
n
x
DFT
T
k
X
kF
X
=
=
则利用式
∑
=
=
1
0
2
)
(
N
n
N
n
jk
e
n
x
T
π
511
1
0
…
…
=
，
，
k
)
(
0
kF
X
可求出
)
(
0
kF
X
N/2
N
K
511
T
)
(
n
x
n
第三章离散傅里叶变换
(Discrete Fourier Transform
)
2
§
3-1
傅里叶变换的几种形式时域
x(t)
、
x(n)
与频域
X(j
)
、
X(e
j
ω
)
之间的变换关一、连续时间与连续频率的傅立叶变
)
(
),
(
j
X
t
x
a
a
∫
∞
∞
=
dt
e
t
x
j
X
t
j
a
a
)
(
)
(
=
∫
∞
∞
d
e
j
X
t
x
t
j
a
a
)
(
2
1
)
(
π
)
(
t
x
a
t
)
(
j
X
a
结论
：一非周期连续时间函数对应于一非周期连续频率函数
3
二、连续时间与离散频率的傅里叶表示（变换）
即周期性信号的傅里叶表示：
∑
∞
∞
=
=
m
t
jm
a
e
m
X
t
x
)
(
)
(
)
(
t
x
a
)
(
m
X
∫
=
2
2
)
(
1
)
(
T
T
t
jm
a
dt
e
t
x
T
m
X
)
(
t
x
a
t
)
(
m
X
T
π
2
=
m
4
T
π
2
=
相邻两谱线间隔为结论：周期性连续的时间函数对应于非周期的离散频率函数三、离散时间与连续频率的傅里叶变换 即：时域离散序列的傅里叶变换
∑
∞
∞
=
=
n
n
j
j
e
n
x
e
X
ω
ω
)
(
)
(
∫
∞
∞
=
ω
π
ω
ω
d
e
e
X
n
x
n
j
j
)
(
2
1
)
(
5
)
(
n
x
n
T
π
2
)
(
ω
j
e
X
ω
结论：非周期的离散时间函数对应于周期性连续频率函数
。
四、离散时间与离散频率的傅里叶变换对傅里叶变换，
t
与
f
是对称的因此在频域上取样将在时域上得到周期函数
6
)
(
~
k
X
N
π
2
k
....
)
(
~
n
x
T
周期离散
)
(
~
n
x
周期离散
)
(
~
k
X
即：周期性的离散时间函数对应于周期性离散频率函数 ---
离散傅里叶级数
DFS
7
§
3-2
离散傅里叶级数
(DFS)
一、定义已知
x(n) 0
≤
n
≤
N-1
有限长
,
则其傅里叶变换
）
周期为
π
ω
ω
2
(
)
(
)
(
1
0
∑
=
=
N
n
n
j
j
e
n
x
e
X
)
(
~
ω
j
e
X
记为：
∑
=
=
1
0
)
(
)
(
~
N
n
n
j
j
e
n
x
e
X
ω
ω
)
(
~
n
x
对频域取样，一周期内取样
N
点，将使时域
x(n)
周期化为
8
k
N
k
π
ω
2
=
ω被离散化：
正变换
DFS
e
n
x
e
X
k
X
N
n
kn
N
j
k
N
j
=
=
∴
∑
=
=
1
0
2
2
)
(
~
)
(
~
)
(
~
π
π
ω
ω
)
(
~
)
(
~
)
(
~
)
(
~
1
0
2
1
0
)
(
2
k
X
e
n
x
e
n
x
N
k
X
N
n
kn
N
j
N
n
n
N
k
N
j
=
=
=
+
∑
∑
=
=
+
π
π
显然
π
2
反变换：
kr
N
j
e
两边同乘并对一周期求和
∑∑
∑∑
∑
=
=
=
=
=
=
=
1
0
1
0
)
(
2
2
1
0
1
0
2
1
0
2
)
(
~
)
)
(
~
(
)
(
~
N
n
N
k
n
r
k
N
j
kr
N
j
N
k
N
n
kn
N
j
N
k
kr
N
j
e
n
x
e
e
n
x
e
k
X
π
π
π
π
9
正交原理）
而
(
0
)
(
sin
)
(
sin
11
)
(
)
(
)
(
2
)
(
2
1
0
)
(
2
≠
=
=
=
=
=
∑
n
r
n
r
N
n
r
N
e
n
r
e
ee
e
n
r
N
j
n
r
j
n
r
N
j
n
r
j
N
k
n
r
k
N
j
π
π
π
π
ππ
π
)
(
~
)
(
~
1
0
2
r
x
N
e
k
X
N
k
kr
N
j
=
∴
∑
=
π
nk
N
j
N
k
e
k
X
N
n
x
π
2
1
0
)
(
~
1
)
(
~
∑
=
=
∴
N
j
N
e
W
π
2
=
记
[]
[]
∑
∑
=
=
=
=
=
=
nk
N
N
n
nk
N
N
k
W
n
x
n
x
DFS
k
X
W
k
X
N
k
X
IDFS
n
x
1
0
1
0
)
(
~
)
(
~
)
(
~
)
(
~
1
)
(
~
)
(
~
则有
10
二、
的物理意义
)
(
~
k
X
{
1
0
)
(
~
else
0
)
(
≤
≤
=
N
n
n
x
n
x
∑
∑
=
=
=
=
1
0
1
0
)
(
~
)
(
)
(
N
n
n
N
n
n
z
n
x
z
n
x
z
X
k
N
j
k
N
e
z
W
z
z
X
z
X
k
X
π
2
)
(
)
(
)
(
~
=
=
=
=
即是在的一个周期所得序列的
Z
变换单位圆上等间隔取样得到的。每循环一次，得到的一个周期
)
(
~
k
X
)
(
~
n
x
)
(
~
k
X
[
]
Z
jI
m
N
π
2
[
]
Z
R
e
1
=
Z
11
)
(
~
)
(
~
)
(
~
2
1
3
n
x
b
n
x
a
n
x
+
=
)
(
~
)
(
~
)
(
~
2
1
3
k
X
b
k
X
a
k
X
+
=
三、
DFS
的性质
1
、线性：
[
]
)
(
~
)
(
~
k
X
W
m
n
x
DFS
mk
N
=
+
[]
nk
N
N
n
W
m
n
x
m
n
x
DFS
∑
=
+
=
+
1
0
)
(
~
)
(
~
2
、序列移位：
(1)
时域移位令
i=n+m
ik
N
m
N
m
i
mk
N
mk
N
ik
N
m
N
m
i
W
i
x
W
W
W
i
x
∑
∑
+
=
+
=
=
=
∴
1
1
)
(
~
)
(
~
上式
)
(
~
)
(
~
1
0
k
X
W
W
i
x
W
mk
N
ik
N
N
i
mk
N
=
=
=
∑
[
]
)
(
~
)
(
~
n
x
W
l
k
X
IDFS
l
N
n
=
+
(2)
频域移位
12
3
、周期卷积
（
1
）时域卷积两个周期信号（序列）的卷积，只限在一个周期内卷积。
)
(
~
)
(
~
1
1
k
X
n
x
→
)
(
~
)
(
~
2
2
k
X
n
x
→
[]
)
(
~
)
(
~
)
(
~
)
(
~
2
1
2
1
k
X
k
X
n
x
n
x
DFS
=
则，
∑
∑
=
=
=
=
1 0
1
2
1 0
2
1
2
1
)
(
~
)
(
~
)
(
~
)
(
~
)
(
~
)
(
~
N m
N m
m
n
x
m
x
m
n
x
m
x
n
x
n
x
而
13
[]
)
(
~
)
(
~
)
(
~
)
(
~
)
),
(
(
)
(
~
)
(
~
)
(
~
)
(
~
)
(
~
)
(
~
)
(
~
)
(
~
2
1
1
0
2
1
2
1
2
1
)
(
1
0
2
1 0
1
1
0
1 0
2
1
2
1
k
X
k
X
W
r
x
k
X
N
W
r
x
W
r
x
k
X
m
n
r
W
m
n
x
W
m
x
W
m
n
x
m
x
n
x
n
x
DFS
rk
N
N
r
rk
N
rk
N
m
N
m
r
k
m
n
N
N
n
mk
N
N m
N
n
nk
N
N m
=
=
=
=
=
=
∑
∑
∑
∑
∑∑
=
=
=
=
=
=
为周期均以
，则原式令证：
如下
)
(
~
),
(
~
2
1
n
x
n
x
3
=
N
12
0
1
..
.
...
14
周期卷积
01
2
m
)
(
~
1
m
x
)
(
~
)
(
~
2
1
n
x
n
x
...
.
...
.
n
-3
-2
-1
0
1
2
3
4
5
1
2
)
(
~
2
m
x
...
...
m
0
2
1
15
(2)
频域卷积定理
)
(
~
)
(
~
)
(
~
2
1
3
n
x
n
x
n
x
=
)
(
~
)
(
~
1
)
(
~
)
(
~
1
)
(
~
2
1
0
1
2
1
3
l
k
X
l
X
N
k
X
k
X
N
k
X
N
l
=
=
∑
=
)
(
~
)
(
~
)
(
~
1
)
(
~
1
)
(
~
)
(
~
1
)
(
~
1
)
(
~
2
1
)
(
1
0
2
1
0
1
1
0
1
0
2
1
2
1
0
3
3
n
x
n
x
W
l
k
X
N
W
l
X
N
W
l
k
X
l
X
N
W
k
X
N
n
x
l
k
n
N
N
k
nl
N
N
l
N
k
nk
N
N
l
N
k
nk
N
=
=
=
=
=
=
=
=
=
∑
∑
∑∑
∑
16
§
3
离散傅里叶变换
(DFT)
也称有限长序列的傅里叶级数。 即
DFT
是将有限长序列看成周期为
N
的时间序列的一个周期。
一、定义
:
1
0
≤
≤
N
n
设有限长序列
x(n)
∑
∞
∞
=
+
=
r
rN
n
x
n
x
)
(
)
(
~
则可把
x(n)
周期延拓
：
)
(
)
(
~
)
(
))
((
)
(
~
,
)
(
~
)
(
n
R
n
x
n
x
n
x
n
x
n
x
n
x
N
N
=
=
记为：
的主值序列为而
)
(
)
(
~
)
(
))
((
)
(
~
k
R
k
X
k
X
k
X
k
X
N
N
==
同理：
17
表示可得的关系
、
据
DFT
k
X
n
x
,
)
(
~
)
(
~
∑
∑
≤
≤
=
≤
≤
=
=
=
1
0
)
(
)
(
1
0
)
(
1
)
(
1
0
1
0
N
k
W
n
x
k
X
N-
n
W
k
X
N
n
x
kn
N
N
n
kn
N
N
k
二、
DFT
性质
1
、线性
)
(
)
(
2
1
n
x
n
x
、
[
]
)
(
)
(
1
1
n
x
DFT
k
X
=
[
]
)
(
)
(
2
2
n
x
DFT
k
X
=
N
列长
)
(
)
(
)
(
2
1
3
n
bx
n
ax
n
x
+
=
若
)
(
)
(
)
(
2
1
3
k
bX
k
aX
k
X
+
=
则
18
2
、
IDFT
的另一种表示方法：
∑
=
=
1
0
)
(
1
)
(
N
k
nk
N
W
k
X
N
n
x
[]
[]
=
=
=
∑
)
(
1
)
(
1
)
(
1
0
k
X
DFT
N
W
k
X
N
n
x
N
k
nk
N
取两次共轭
3
、对称定理：
[
]
)
(
)
(
))
((
)
(
k
N
Nx
k
R
k
Nx
n
X
DFT
N
N
=
=
则
)
(
)
(
k
X
n
x
∑
=
=
1
0
)
(
1
)
(
N
k
nk
N
W
k
X
N
n
x
Q
∑
=
=
∴
1
0
)
(
1
)
(
))
((
N
k
nk
N
N
N
W
k
X
N
n
R
n
x
19
交换
n,k
得：
[]
)
(
))
((
)
(
k
R
k
Nx
n
X
DFT
N
N
=
即
X(n)
的频谱与
x(n)
的形状在时间上互为倒置
)
(
)
(
k
X
n
x
4
、反转定理：
)
(
))
((
)
(
))
((
k
R
k
X
n
R
n
x
N
N
N
N
)
(
))
((
)
(
)
(
))
((
1
0
1 0
k
R
k
X
W
m
x
W
n
R
n
x
N
N
N
n
N m
mk
N
n
m
nk
N
N
N
=
=
∑∑
=
=
=
证明：
)
(
))
((
)
(
))
((
k
R
k
X
n
R
n
x
N
N
N
N
∴
20
5
、序列的总和
∑
∑
=
=
=
=
=
=
=
1
0
0
1
0
0
)
0
(
)
(
)
(
)
(
N
n
k
N
n
kn
N
k
X
n
x
W
n
x
k
X
∑
=
=
1
0
)
(
1
)
0
(
N
k
k
X
N
x
6
、序列的始值
7
、序列的循环移位（圆周移位）
x(n),n:0---N-1,
移位后仍在
[0
，
N-1]
取值将发生信息丢失右移一位
)
(
n
x
0
1
2
0 1 2 3
0
1 2
21
为避免发生信息丢失，移位时应先将周期延拓成再移位
，然后再取
[0
，
N-1]
上的值
)
(
n
x
N
n
x
n
x
))
((
)
(
~
=
)
(
)
(
~
n
R
m
n
x
N
+
∴
循环移位可表示成
)
(
~
n
x
)
1
(
~
n
x
)
(
)
1
(
~
n
R
n
x
N
3
=
N
n
0 1 2
….
……
-3 -2 -1 0 1 2 3 4 5
……
……
0 1 2
显然没有信息丢失，只不过从右端移出去的值又从左端移入 主值区间。仿佛是序列
x(n)
排列在一个
N
等分的圆周上，故称圆周移位
22
[
]
)
(
~
)
(
~
k
X
W
m
n
x
DFS
km
N
=
+
由
DFS
性质：
[]
)
(
)
(
))
((
)
(
))
((
k
X
W
k
R
k
X
W
n
R
m
n
x
DFT
km
N
N
N
km
N
N
N
=
=
+
知
(
)
线性移位注：
)
(
)
(
))
((
m
n
x
n
R
m
n
x
N
N
+
≠
+
[]
)
(
)
(
))
((
n
x
W
k
R
l
k
X
IDFT
nl
N
N
N
=
+
同理频域移位：
8
、圆周卷积
)
(
)
(
)
(
2
1
3
k
X
k
X
k
X
=
若
∑
∑
=
=
=
=
=
1 0
1
2
1 0
2
1
2
1
3
)
(
))
((
)
(
)
(
))
((
)
(
)
(
)
(
)
(
N
m
N
N
N m
N
N
n
R
m
n
x
m
x
n
R
m
n
x
m
x
n
x
n
x
n
x
则
23
证明：将
X
3
(k)
周期延拓
)
(
~
)
(
~
)
(
~
1
2
3
k
X
k
X
k
X
=
[
]
∑∑
=
=
=
=
=
∴
1 0
1 0
2
1
2
1
3
3
))
((
)
(
)
(
~
)
(
~
)
(
~
)
(
~
N m
N m
N
m
n
x
m
x
m
n
x
m
x
k
X
IDFS
n
x
∑
=
=
=
∴
1 0
2
1
3
3
)
(
))
((
)
(
)
(
)
(
~
)
(
N m
N
N
N
n
R
m
n
x
m
x
n
R
n
x
n
x
24
圆周卷积过程：
例：求下列两序列的
3
点圆周卷积
(N=3)
)
(
2
n
x
0
1
2
1
0
1
2
1
)
(
1
n
x
解
,(1)
先将
，
周期延拓，作出
)
(
2
n
x
)
(
~
2
m
x
)
(
1
n
x
)
(
~
1
m
x
)
(
~
1
m
x
...
(2)
作周期卷积得
)
(
~
3
n
x
..
.
01
2
3
)
(
~
2
m
x
01
2
1
...
...
25
)
(
)
(
~
)
3
(
3
3
n
x
n
x
主值序列得的一个周期取
即列长为
N
的两有限长序列的圆周卷积的结果也是一列长为
N
的有限长序列，而线性卷积的列长为
2N-1
。
0 1 2
)
(
3
n
x
3
9
、利用圆周卷积求线性卷积
:
例上例：
)
(
)
(
2
1
n
x
n
x
线卷列长为
5
（
2N-1
或
N+M-1)
因此可以将两个序列补零到
2N-1,
然后再作圆周卷积。
(1)
补零到
2N-1
点序列
,
并周期延拓
12
0
n
34
26
)
(
1
n
x
)
(
2
n
x
1
01
2
34
1
1
2
3
04
)
(
~
1
m
x
)
(
~
2
m
x
1
1
2
3
04
1
0
1234
(2)
作周期卷积
)
(
)
(
)
(
2
1
3
n
x
n
x
n
x
=
(3)
取主值序列，得：
)
(
~
3
n
x
12
0
n
34
...
...
12
0
n
34
)
(
)
(
)
(
)
(
2
1
2
1
n
x
n
x
n
x
n
x
=
此时
27
综上所述，由
DFT
求线卷过程。已知
x
1
(n)->N,x
2
(n)->M
<1>
将
x
1
(n),x
2
(n)
分别补零到列长为
L,L
≥
N+M-1
。
<2>
将补零后的
x
1
(n),x
2
(n)
以
L
为周期进行周期延拓，并作周期卷积 <3>
取周期卷积的主值序列，得圆周卷积
?
线卷
28
10
、分段卷积：
若
x(n)
很长，要先将
x(n)
分段，再进行
DFT
。设
h(n)
列长为
M
，分段方法有两种：重叠相加法和重叠保留法。
(1)
重叠相加法：
将
x(n)
分段，每段长为
N
点，则第
K
段
x
k
(n),
+
≤
≤
=
else
N
k
n
kN
n
x
n
x
k
0
1
)
1
(
)
(
)
(
∑
∞
∞
=
=
k
k
n
x
n
x
)
(
)
(
而
∑
∞
∞
=
=
=
∴
k
k
n
h
n
x
n
h
n
x
n
y
)
(
)
(
)
(
)
(
)
(
29
由于
x
k
(n)
与
h(n)
线卷之后列长为
N+M-1
即先要将
x
k
(n)
及
h(n)
均补零到
N+M-1,
因此每一段卷积的结果都多出
M-1
个非零点。
如下图所示：
0
12
3
4
5
6
)
(
m
x
k
)
(
m
h
-2
-1
0
-3
0123
456
)
(
)
(
n
h
n
x
k
30
显然前
N
个点卷积结果是正确的，而后
M-1
点卷积结果是不正确的。实际上还应将下一段的前
M-1
点卷积结果加到前一段卷积的后
M-1
点，即前后有
M-1
点重叠相加。
(2)
重叠保留法上面分段序列中的补零部分不是补零，而是保留原来的输入序列值
(
每段的后
M-1
点保留在下一段的前端
)
。
如图所示：
点
1
M
....
点新值
N
保留
{
31
因为每一段的前
M-1
点卷积值已在前一段求出，保留这
M-1
点是为了计算第
M
点卷积结果，所以前
M-1
点结果要舍去。然后把第
M
点以后的卷积输出接起来即是最终的输出。
---“
迭接舍去法
”
。
11
、圆周相关定理（循环相关）
)
(
)
(
)
(
2
1
3
k
X
k
X
k
X
=
若
[]
∑
=
+
=
=
1
0
2
*
1
3
3
)
(
))
((
)
(
)
(
)
(
N
l
N
N
n
R
n
l
x
l
x
k
X
IDFT
n
x
则
[]
nk
N
N k
W
k
X
k
X
N
k
X
IDFT
n
x
=
∑
=
=
)
(
)
(
1
)
(
)
(
2
1
0
1
3
3
证明：
nk
N
N m
mk
N
N
k
N
l
kl
N
W
W
m
x
W
l
x
N
=
=
=
=
∑
∑∑
1 0
2
1
0
1
0
1
)
(
)
(
1
=
=
=
=
=
=
=
=
∑
∑∑
∑
∑∑
k
l
n
m
N k
N
N
l
N m
nk
N
mk
N
N m
N k
lk
N
N
l
W
N
m
x
l
x
W
W
m
x
W
l
x
N
)
(
1
0
1
0
2
1 0
1
1 0
2
1
0
1
0
1
1
)
(
)
(
)
(
)
(
1
32
{
1 0
1
0
)
(
1
=
∑
=
N
k
l
n
m
k
N
W
N
已知：
时当时当
rN
l
n
m
rN
l
n
m
≠
=
rN
n
l
m
+
+
=
即
∑
=
+
=
∴
1
0
2
1
3
)
(
))
((
)
(
)
(
N
l
N
N
n
R
n
l
x
l
x
n
x
是实数，则设
)
(
1
l
x
)
(
))
((
)
(
)
(
1
0
2
1
3
n
R
n
l
x
l
x
n
x
N
N
l
N
+
=
∑
=
线性相关为
∑
∞
∞
=
+
=
m
m
n
x
m
x
n
x
)
(
)
(
)
(
2
1
3
而：
与卷积不同：不需要折叠运算，但移位相乘和相加二者完全相同。
33
能量守恒定理
12
、帕斯维尔定理：
∑∑
=
=
=
1
0
1
0
2
2
)
(
1
)
(
N
n
N
k
k
X
N
n
x
[
]
则若
)
(
)
(
n
x
DFT
k
X
=
在圆周相关定理中，取
x
2
(
l
)=x
1
(
l
)
，且
n=0
，则：
∑∑
=
=
=
1
0
0
1
0
)
(
)
(
1
)
(
)
(
N
l
N
N
k
W
k
X
k
X
N
l
x
l
x
∑
∑
=
=
=
∴
1
0
2
1
0
2
)
(
1
)
(
N
k
N
n
k
X
N
n
x
频域能量离散时域能量
34
13
、
DFT
的奇偶性和对称性：
<1>
周期性共轭对称和共轭反对称分量上一章讲过：任一序列可分解为一共轭对称与一共轭反对称两个分量之和
[] []
=
+
=
)
(
)
(
21
)
(
)
(
)
(
21
)
(
n
x
n
x
n
x
n
x
n
x
n
x
oe
)
(
)
(
)
(
n
x
n
x
n
x
o
e
+
=
由于
x
e
(n)
与
x
o
(n)
列长均为
2N-1
，一般
DFT
不用此定义，
而采用周期性的序列来分析
DFT
的对称性质。
即将
x(n)
分解成两个列长为
N
的有限长序列。
)
(
)
(
)
(
n
x
n
x
n
x
op
ep
+
=
35
即先将
x(n)
周期延拓其共轭对称与反对称
[] []
=
+
=
)
(
~
)
(
~
21
)
(
~
)
(
~
)
(
~
21
)
(
~
n
x
n
x
n
x
n
x
n
x
n
x
oe
取主值周期：
[]
[
]
)
(
)
(
21
)
(
))
((
))
((
21
)
(
n
N
x
n
x
n
R
n
x
n
x
n
x
N
N
N
ep
+
=
+
=
[]
[
]
)
(
)
(
21
)
(
))
((
))
((
21
)
(
n
N
x
n
x
n
R
n
x
n
x
n
x
N
N
N
op
=
=
)
(
~
)
(
~
)
(
~
n
x
n
x
n
x
o
e
+
=
Q
[
]
)
(
)
(
)
(
)
(
~
)
(
~
)
(
)
(
~
)
(
n
x
n
x
n
R
n
x
n
x
n
R
n
x
n
x
op
ep
N
e
e
N
+
=
+
=
=
∴
36
x
ep
(n)
和
x
op
(n)
分别称为列长为
N
的序列
x(n)
的周期性共轭对称分量和周期性共轭反对称分量 当
x
ep
(n)
和
x
op
(n)
为实序列时
---
分别称周期性偶分量和奇分量。
[
]
则：
已知
)
(
)
(
n
x
DFT
k
X
=
)
(
))
((
)
(
)
(
k
R
k
X
n
x
a
N
N
<2>
对称性质
)
(
)
(
))
((
)
(
k
X
n
R
n
x
b
N
N
[
]
)
(
)
(
Re
)
(
k
X
n
x
c
ep
[
]
)
(
)
(
)
(
k
X
n
x
jI
d
op
m
[
]
)
(
)
(
)
(
k
X
R
n
x
e
e
ep
[
]
)
(
)
(
)
(
k
X
jI
n
x
f
m
op
37
证明：
)
(
))
((
)
(
)
(
)
(
1
0
1
0
k
R
k
X
W
n
x
W
n
x
a
N
N
N
n
nk
N
N
n
nk
N
=
=
=
=
∑
∑
)
(
)
(
))
((
)
(
))
((
)
(
1
0
1
0
k
X
W
n
R
n
x
W
n
R
n
x
b
N
n
nk
N
N
N
N
n
kn
N
N
N
=
=
=
=
∑
∑
[]
[
]
[
]
)
(
)
(
))
((
)
(
21
)
(
)
(
21
)
(
Re
)
(
1
0
1
0
k
X
k
R
k
X
k
X
W
n
x
n
x
W
n
x
c
ep
N
N
N
n
kn
N
nk
N
N
n
=
+
=
+
=
=
=
∑
∑
[]
[
]
[
]
)
(
)
(
))
((
)
(
21
)
(
)
(
21
)
(
)
(
1
0
1
0
k
X
k
R
k
X
k
X
W
n
x
n
x
W
n
x
jI
d
op
N
N
N n
kn
N
nk
N
N
n
m
=
=
=
=
=
∑
∑
[
]
[
]
[]
)
(
Re
)
(
)
(
21
)
(
))
((
)
(
21
)
(
)
(
1
0
1
0
k
X
k
X
k
X
W
n
R
n
x
n
x
W
n
x
e
N
n
kn
N
N
N
nk
N
N
n
ep
=
+
=
+
=
=
=
∑
∑
[
]
[
]
[]
)
(
)
(
)
(
21
)
(
))
((
)
(
21
)
(
)
(
1
0
1
0
k
X
jI
k
X
k
X
W
n
R
n
x
n
x
W
n
x
f
m
N
n
kn
N
N
N
nk
N
N
n
op
=
=
=
=
=
∑
∑
38
若
x(n)
为实序列，则有：
[
]
[
]
)
(
))
((
Re
)
(
Re
)
1
(
k
R
k
X
k
X
N
N
=
[
]
[
]
)
(
))
((
)
(
)
2
(
k
R
k
X
I
k
X
I
N
N
m
m
=
)
(
))
((
)
(
)
3
(
k
R
k
X
k
X
N
N
=
[
]
[
]
)
(
))
((
arg
)
(
arg
)
4
(
k
R
k
X
k
X
N
N
=
)
(
)
(
n
x
n
x
=
∴
是实序列
)
(
n
x
Q
由前面性质
(a)
得
)
(
))
((
)
(
k
R
k
X
k
X
N
N
=
利用共轭的性质就可证得性质（
1
）
---
（
4
）
39
§
4
、频域取样一、取样：设
x(n)
为任意非周期序列，其
Z
变换为
X(z)
对
X(z)
在单位圆上进行等间隔取样。设
M
为取样点数，则：
∑
∞
∞
=
=
=
=
n
nk
M
W
z
W
n
x
z
X
k
X
k
M
)
(
)
(
)
(
M
j
M
e
W
π
2
=
式中问题：频率取样后，能否用
X(k)
恢复出
x(n)
？在什么条件下能恢复？
设
x’(n)
为频率取样后所得序列，则：
∑∑
∑
=
∞
∞
=
=
=
=
′
1
0
1
0
)
(
1
)
(
1
)
(
M
km
nk
M
mk
M
M
k
nk
M
W
W
m
x
M
W
k
X
M
n
x
∑∑
∞
∞
=
=
=
m
M
k
k
n
m
M
W
M
m
x
1
0
)
(
1
)
(
40
+
=
=
=
∑
=
else
rM
n
m
rM
n
m
W
M
M
k
k
n
m
M
0
)
(
1
1
1
0
)
(
Q
∑
∞
∞
=
+
=
′
∴
r
rM
n
x
n
x
)
(
)
(
是任意整数
r
Q
即
x’(n)
是原序列
x(n)
以
M
为周期的周期延拓序列
,
对列长为
N
的有限长序列
,
频率取样不失真的条件：
N
M
≥
∑
∞
∞
=
+
=
′
=
r
M
M
n
R
rM
n
x
n
R
n
x
n
x
)
(
)
(
)
(
)
(
)
(
此时
，
41
二、
X(z)
的内插：
由
X(k)--->X(z),
即
N
个
X(k)
如何表达整个
X(z)
函数？
∑
=
=
1
0
)
(
1
)
(
N
k
nk
N
W
k
X
N
n
x
n
N
n
N
k
nk
N
N
n
n
z
W
k
X
N
z
n
x
Z
X
=
=
=
∑∑
∑
=
=
1
0
1
0
1
0
)
(
1
)
(
)
(
(
)
∑
∑∑
=
=
=
=
=
1
0
1
1
0
1
0
1
1
1
)
(
1
)
(
1
N
k
k
N
N
kN
N
N
k
N
n
n
k
N
z
W
z
W
k
X
N
z
W
k
X
N
∑
=
=
∴
1
0
1
1
)
(
1
)
(
N
k
k
N
N
z
W
k
X
N
z
z
X
1
2
=
=
kN
N
j
kN
N
e
W
π
Q
即
X(z)
的内插公式
42
§
5
、利用
DFT
计算信号的频谱
∫
∞
∞
=
dt
e
t
x
X
t
j
)
(
)
(
非周期信号
x(t)
的近似频谱：
代入上式，则得即将小段的积分值再累加，
不变，则分别求出每一内设
。在长分为无限个小段，每段将
)
(
,
,
)
(
)
,
(
→
=
→∞
∞
∫
∑
∞
∞
∞
∞
=
X
nT
t
T
dt
t
x
T
T
n
T
e
nT
x
x
n
nT
j
≈
∑
∞
∞
=
)
(
)
(
若信号从
t=0
到
T
0
有值，则将
0---T
0
分为
N
小段，
即在时域取样
N
点，则：
∑
=
≈
1
0
)
(
)
(
N
n
nT
j
e
nT
x
T
X
43
为：
相邻频率取样点的间隔点，则段，也即取样频率范围分成将频率离散化
，将为周期的连续频谱，再即是一个以据时域取样，
N
N
T
T
X
s
s
π
π
ω
π
2
0
)
2
(
2
)
(
=
=
0
0
0
2
2
2
2
F
T
TN
N
T
π
π
π
π
=
=
=
=
NT
F
1
0
=
频率间隔
N
T
π
ω
2
0
0
=
=
数字化频率
T
0
代表非周期信号的时间长度。
F
0
,
0
表示非周期信号的频谱经离散化后样点之间的频率间隔离散化后的频率点及频谱：
44
NT
k
k
π
2
0
=
=
∑
=
≈
1
0
2
0
)
(
)
(
N
n
N
n
jk
e
n
x
T
k
X
π
[
]
)
(
)
(
0
n
x
DFT
T
kF
X
=
或
1
2
,
1
,
0
=
N
k
L
[]
)
(
1
)
(
0
kF
X
IDFT
T
n
x
=
而
45
例：利用
DFT
近似求出的幅度频率样值并与理论值进行比较。
)
(
)
(
t
u
e
t
x
t
=
2
1
1
)
(
+
=
∴
X
∫
∞
+
=
=
0
1
1
)
(
j
dt
e
e
X
t
j
t
t
x(t
)
t
e
t
x
=
)
(
)
(
X
∞
→
t
0
)
(
=
t
x
（
1
）截取有限长序列
8
时当
=
t
00035
.
0
1
)
(
8
=
=
e
t
x
0
)
(
8
≈
>
t
t
x
即
8
0
=
∴
T
取信号长度
46
（
2
）确定
T
据取样定理，
m
f
T
2
1
≤
≥
T
2
1
Q
m
f
x
x
f
f
f
X
f
>
≈
,
0
)
(
,
使估算
∞
→
m
f
()
00497
.
0
201
1
32
2
1
1
)
(
2
=
=
+
=
π
f
X
则可取
.
32
=
x
f
512
64
8
64
1
64
32
0
=
×
=
=
=
=
≈
∴
T
T
N
T
f
f
s
m
，
，即
，则取
nT
e
n
x
=
)
(
47
[]
)
(
)
(
)
(
0
0
n
x
DFT
T
k
X
kF
X
=
=
则利用式
∑
=
=
1
0
2
)
(
N
n
N
n
jk
e
n
x
T
π
511
1
0
…
…
=
，
，
k
)
(
0
kF
X
可求出
)
(
0
kF
X
N/2
N
K
511
T
)
(
n
x
n
