数字信号处理 离散傅里叶变换

x(n) IDFT [ X (k )] x1 (m) x2 ((n m)) N RN (n)
m0 N 1 m0
N 1
或 x(n) IDFT [ X (k )] x2 (m) x1 ((n m)) N RN (n) 上式所表示的运算称为x1(n)与x2(n)的循环卷积。 26
21
第7讲
离散傅里叶变换(DFT)
2 循环移位性质： (1) 序列的循环移位 设x(n)为有限长序列， 长度为N， 则x(n)的循环移位定义为 y(n)=x((n+m))NRN(N)
循环移位过程如下图所示:
22
第7讲
离散傅里叶变换(DFT)
循环移位过程示意图
23
第7讲
离散傅里叶变换(DFT)
(2) 时域循环移位定理： 设x(n) 是长度为N的有限长序列， y(n)为x(n)的循环移位， 即 y(n)=x((n+m))NRN(n) 则 Y(k)=DFT［y(n)］ WN km X (k ) 其中 X(k)=DFT［x(n)］, 0≤k≤N-1。
)
3π k 8
e (e -e ) π sin( k ) 2 , k 0,1..., 7 π sin( k ) 8
7
第7讲
离散傅里叶变换(DFT)
（2）设变换区间N=16 时，则：
kn kn X(k) = x(n)W16 = W16 n=0 n=0 15 3 k 1 -W164 = k 1 -W16
10
第7讲
离散傅里叶变换(DFT)
DFT与傅里叶变换和Z变换的关系
设序列x(n)的长度为M，其Z变换和
N(N≥M)点DFT分别为：
X ( z ) ZT[ x(n)] x(n) z

n 0 M 1 n 0

M 1
n
X (k ) DFT[ x(n)]N x(n)W
3
第7讲
离散傅里叶变换(DFT)
DFT的实质：有限长序列傅里叶变换的
有限点离散采样，即频域离散化。
DFT
有 多 种 快 速 算 法 (Fast Fourier Transform), 因此不仅在理论上有重要意 义, 在各种数字信号处理算法中亦起着核 心作用。从而使信号的实时处理和设备 的简化得以实现。
可写出 ~ (n) 的离散傅里叶级数表示式 x N 1 N 1 N 1 kn kn
n 0 n 0 n 0
kn X (k ) x(n)WN x((n)) N WN x(n)WN
1 N 1 1 N 1 x(n) X (k )WN kn X (k )WN kn N k 0 N k 0
14
第7讲
离散傅里叶变换(DFT)
实际上，任何周期为N的周期序列 x(n) 都可
以看做长度为N的有限长序列x(n)的周期延
拓序列，而x(n)则是 x(n)的一个周期，即
x(n)
m
x(n mN )

x(n) x(n) RN (n)
15
第7讲
离散傅里叶变换(DFT)
的长度时，将式
x(n)
m
x(n mN )
x((n)) N

用如右形式表示： (n) x
式中x((n)) N表示x(n)以N为周期的周期延拓序
列，((n))N表示模N对n求余，即如果 n=MN+n1 则 0≤n1≤N－1, M为整数 ((n))N=n1
17
第7讲
28
第7讲
离散傅里叶变换(DFT)
频域循环卷积定理： 如果 x(n)=x1(n)x2(n) 则 1
X (k ) DFT [ x(n)] 1 N N
X 1 (k ) X 2 (k )

l 0
N 1
X 1 (l ) X 2 ((k l )) N RN (k )
1 或X ( k ) X 2 ( k ) X 1 ( k ) N 1 N 1 X 2 (l ) X 1 ((k l )) N RN (k ) N l 0
x( L 1) x( L 2) x(0) x(1) x(0) x ( L 1) x(2) x(1) x (0) x( L 1) x( L 2) x( L 3) x (1) x (2) x (3) x (0)
DFT的隐含周期性
在DFT变换对中，x(n)与X(k)均为有限长序列，
kn 但由于 WN 的周期性，使DFT和IDFT式中的X(k)
隐含周期性，且周期均为N。对任意整数m，总有
k ( N WNk mN )， W
k , m为整数,N为自然数
N 1
在DFT式中，X（k)满足：
( kn (k mN ) X x(n)WNk mN ) n x(n)WN X (k ) n 0 n 0 N 1
=
1-e
-j
2π 4k 16
1-e e
-j
2π -j k 16

e
-j
π k 4
(e
j j
π k 4 π k 16
-e
-j -j
π k 4
)
3π k 16
e (e -e ) π sin( k ) 4 , k 0,1...,15 π sin( k) 16
8
-j
π k 16
π k 16
第7讲
离散傅里叶变换(DFT)
计算机只能处理有限长离散序列，因而
无法直接利用ZT与FT进行数值计算。
针对有限长序列,
还有一种更有用的数学 变 换 , 即 离 散 傅 里 叶 变 换 （ Discrete Fourier Transform），使数字信号处理 可以在频域采用数字运算的方法进行， 大大增加了数字信号处理的灵活性。
离散傅里叶变换(DFT)
N 例如， 8, x(n) x((n))8 , 则有 x(8) x((8)) x(0) 8
x(9) x((9))8 x(1)
所得结果符合下图所示的周期延拓规律。
18
第7讲
离散傅里叶变换(DFT)
~(n) x((n)) ，则 如果x(n)的长度为N，且 x N
第7讲
离散傅里叶变换(DFT)
循环卷积过程中， 要求对x2(m)循环反 转， 循环移位， 特别是两个N长的序列的
循环卷积长度仍为N。 显然与一般的线性
卷积不同， 故称之为循环卷积， 记为
x(n) x1 (n) x2 (n) x1 (m) x2 ((n m)) N RN (n)
m0 N 1

12
第7讲
离散傅里叶变换(DFT)
DFT的物理意义
DFT是 X(ejω)在区间［0, 2π］上的N点等 间隔采样。这就是DFT的物理意义。 DFT的变换区间长度N不同，表示对 X(ejω)在区间［0, 2π］上的采样间隔和采样
点数不同，所以DFT的变换结果不同。
13
第7讲
离散傅里叶变换(DFT)
一般称周期序列 ~ (n) 中从n=0到N－1 x 的第一个周期为 ~ (n) 的主值区间，而主 x 值区间上的序列称为 ~ (n) 的主值序列。 x ~ (n) 的上述关系可叙述为： (n) ~ 因此x(n)与 x x 是x(n)的周期延拓序列，x(n)是 ~ (n) 的主 x 值序列。
16
第7讲 离散傅里叶变换(DFT) 为了以后叙述简洁，当N大于等于序列x(n)
第7讲
离散傅里叶变换(DFT)
第3章 离散傅里叶变换(DFT)
1
第7讲
离散傅里叶变换(DFT)
本章作为全书的基础，主要学习: (1) DFT的定义； (2) DFT的物理意义； (3) DFT的基本性质以及频域采样； (4)DFT的应用举例等内容。
2
第7讲
离散傅里叶变换(DFT)
离散傅里叶变换定义
如果x1(n)和x2(n)是两个有限长序列， 长度分 别为N1和N2,且 y(n)=ax1(n)+bx2(n) 式中a、 b为常数， 即N=max［N1, N2］， 则y(n)的 N点DFT为 Y(k)=DFT[y(n)]=aX1(k)+bX2(k), 0≤k≤N-1 其中X1(k)和X2(k)分别为x1(n)和x2(n)的N点DFT。
kn N
k 0,1,, N 1
11
第7讲
离散傅里叶变换(DFT)
2π k N
比较上面二式可得关系式
X (k ) X ( z) ze
或
X (k ) X (e j ) |
j
k , N 1 0,1,
k 0,1,, N 1
2π k N
上二式表明序列x(n)的N点DFT是x(n)的 Z变换在单位圆上的N点等间隔采样。X(k) 为x(n)的傅里叶变换。
5
第7讲
离散傅里叶变换(DFT)
-j 2π N
对式中，WN = e ，N称为DFT变换 区间长度，N≥M。通常称上述二式为离散 傅里叶变换对。为了叙述简洁，常常用 DFT［x(n)］N和IDFT［X(k)］N分别表示 N点离散傅里叶变换和N点离散傅里叶逆 变换。
6
第Leabharlann Baidu讲
离散傅里叶变换(DFT)
【例】 x(n)=R4(n), 求x(n)的8点和16点DFT。
R4(n)的FT和DFT的幅度特性关系如下图所示:
X(n)的幅频 特性曲线 (FT曲线)
X(n)的8点 DFT曲线
X(n)的16点 DFT曲线
9
第7讲
离散傅里叶变换(DFT)
结论:
由此例可见，x(n)的离散傅里叶变换结果与 变换区间长度N的取值有关。在后面，对DFT 与Z变换和傅里叶变换的关系及DFT的物理意 义进行讨论后，上述问题就会得到解释。
24
第7讲
离散傅里叶变换(DFT)
（3）频域循环移位定理，如果 X(k)=DFT[x(n)], 0≤k≤N-1
Y(k)=X((k+l))NRN(k)
则
n y(n)=IDFT[Y(k)] WN l x(n)
25
第7讲 离散傅里叶变换(DFT) 3 循环卷积定理
有限长序列x1(n)和x2(n)， 长度分别为N1 和N2 ， N=max[N1, N2]。 x1(n)和x2(n)的N点 DFT分别为： X1(k)=DFT［x1(n)］ X2(k)=DFT［x2(n)］ 如果 X(k)=X1(k)·X2(k) 则
27
第7讲
离散傅里叶变换(DFT)
由于 X (k ) DFT [ x(n)]
X 1 (k ) X 2 (k ) X 2 (k ) X 1 (k )
所以 x (n ) IDFT [ X (k )] x1 (n ) x2 (n )
x2 (n ) x1 (n )
即循环卷积亦满足交换律。
式中
X (k ) X (k )R N (k )
19
即X(k)为 X (k ) 的主值序列。
第7讲
离散傅里叶变换(DFT)
因此可知，有限长序列x(n)的N点离散傅里叶变
换X(k)正好是x(n)的周期延拓序列x((n))N的离散傅里 ~ 叶级数系数 X (k ) 的主值序列，即 X (k ) X (k ) R (k ) 。
29
第7讲
离散傅里叶变换(DFT)
直接计算循环卷积较麻烦。计算机中
采用矩阵相乘或快速傅里叶变换（FFT）
的方法计算循环卷积。下面介绍用矩阵
计算循环卷积的公式。
30
第7讲
离散傅里叶变换(DFT)
当n = 0, 1, 2, „, L－1时，由x(n)形成的
序列为： {x(0), x(1), „, x(L－1)}。循环移位后 可得下面的矩阵：
4
第7讲
离散傅里叶变换(DFT)
DFT 的定义
设x(n)是一个长度为M的有限长序列， 则 定义x(n)的N点离散傅里叶变换为：
X(k) = DFT[x(n)] = x(n)W , k = 0, 1,... , N - 1
kn N n=0
N -1
X(k)的离散傅里叶逆变换为：
1 N -1 -kn x(n) = IDFT[X(k)] = X(k)WN , n = 0, 1, ..., N - 1 N n=0
N
后面要讨论的频域采样理论将会加深对这一关系的 理解。我们知道，周期延拓序列频谱完全由其离散 傅里叶级数系数 X (k ) 确定，因此，X(k)实质上是 x(n)的周期延拓序列x((n)) N的频谱特性，这就是N点
DFT的物理意义。
20
第7讲
离散傅里叶变换(DFT)
离散傅里叶变换的基本性质
1 线性性质
【解】（1）设变换区间N=8 时，则：
X(k) = x(n)W8kn = W8kn
n=0 n=0 7 3
1 -W8k 4 = 1 -W8k
π k 2 π k 8
=
1-e
-j
2π 4k 8
1-e e
-j
2π -j k 8

e
-j -j
π k 2 π k 8
(e
j j
-e
-j -j
π k 2 π k 8