离散傅里叶变换(DFT)及其快速算法(FFT)

第三章 离散傅里叶变换(DFT) 及其快速算法(FFT)

3.1 离散傅里叶变换的定义及物理意义 3.2 DFT的主要性质

3.3 频域采样 3.4 DFT的快速算法——快速傅里叶变换(FFT) 3.5 DFT(FFT)应用举例

3.1 离散傅里叶变换的定义及物理意义模拟域 时间域t:连续

FT、LT

频率域 Ω、s:连续

时间域n:离散

数字域 FT、ZT 数字域

频率域ω、z:连续

DFT

频率域k:离散返回

离散傅立叶变换(DFT)实现了信号首次在频域 表示的离散化，使得频域也能够用计算机进行处理。 并且这种DFT变换可以有多种实用的快速算法。使信 号处理在时、频域的处理和转换均可离散化和快速 化。因而具有重要的理论意义和应用价值，是本课程 学习的一大重点。 本节主要介绍

3.1.1 DFT定义 3.1.2 DFT与ZT、FT、DFS的关系 3.1.3 DFT的矩阵表示返回

回到本节

3.1.1 DFT定义设序列x(n)长度为M,定义x(n)的N点DFT为X (k ) DFT[ x(n)]N

x(n)en 0

N 1

j

2 kn N

,

k 0, 1, , N 1

式中，N称为离散傅里叶变换区间长度，要求N ≥ M。为 2 j 书写简单，令 WN e N ,因此通常将N点DFT表示为X (k ) DFT[ x(n)]N

n 0

N 1

k x(n)WN n ,

k 0, 1, , N 1

定义X(k)的N点离散傅里叶逆变换(IDFT)为1 x(n) IDFT[ X (k )]N N

X (k )Wk 0

N 1

k n N

, n 0, 1, , N 1

长度为 N的离 散序列

返回

回到本节

LT3x1例3.1: x(n) R8 (n),分别计算x(n)的8点、16点DFT。 解: x(n)的8点DFT为X (k ) 2 kn 8

R (n)W8 n 0

7

kn 8

en 0

7

j

k 0 8, 0, k 1, 2, 3, 4, 5, 6, 7 j 2 8k 16

x(n)的16点DFT为

k 1 W168 1 e k X (k ) W16 n k 2 j k 1 W16 n 0 1 e 16 7 sin k j k 2 e 16 , k 0,1, 2, ,15 sin k 16

7

返回

回到本节

X (k ) 是 X (e j ) 在频率区间上的等间隔采样

返回

程序运行结果8 6 4 2 0 8 6 4 2 0

点数8 160 5 10 15 20

0

2

4

6

8

8 6 4 2 0

8 6 4 2 0

32 64

0

10

20

30

40

0

20

40

60

80

回到本节

3.1.2 DFT与ZT、FT、DFS的关系DFT有明确的物理意义，我们可以通过比较序列的DFT、FT、 ZT,并将DFT与周期序列的DFS联系起来，得到DFT的物理意 义。 DFT和FT、ZT之间的关系 假设序列的长度为M,N≥M 将N点DFT和FT、ZT的定义重写如下X ( z ) ZT[ x(n)] X (e ) FT[ x(n)] X (k ) DFT[ x(n)]N j

n 0 n 0

M 1

x ( n) z n x(n)e j n k 0,1, , N 1返回

M 1

n 0

M 1 kn x(n)WN ,

回到本节

比较前面三式，得到

X (k ) X ( z )X (k ) X (e j )

z e

j

2 k N

,k=0, 1, 2, …, N-1 ,k=0, 1, 2, …, N-1

2 k N

结论： (1)序列的N点DFT是序列傅里叶变换在

频率区间[0,2 ] 上的N点等间隔采样，采样间隔为2 /N。 (2)序列的N点DFT是序列的Z变换在单位圆上的N点等间隔 采样，频率采样间隔为2 /N。返回

序列x(n)的N点DFT是 x(n)的Z变换在单位圆上的N点等 间隔采样； X (e j ) 在区间 [0, 2 ] 上的N X(k)为x(n)的傅立叶变换 点等间隔采样。这就是DFT的物理意义。

j Im Z 2 3 4 5 6 X(ejω) 12 N

X(k)

k=0 Re Z

0 0

o

2 N 1

7 (N-1)

k

DFT与z变换

DFT与DTFT变换

回到本节

变量

周期

、f

2

分辨率 2 N

s 、f s

fs N

k

N

返回

回到本节

DFT和DFS之间的关系：周期延拓 取主值

有限长序列 有限长序列

周期序列

主值区序列

x(n)

n 0,1, 2, M 1

周期序列 xN ( n)

m

x ( n mN ) x((n)) N

0 n0 N 1 n mN n0 ((n)) N n0

xN (n) xN (n) RN (n)主值区间序列N M , xN ( n) x ( n)返回

回到本节

x8 (n)

x4 (n)

返回

回到本节

周期序列DFS: X ( k ) DFS [ xN ( n)] M 1

xn 0

N 1

N

kn ( n)WN

n 0

kn x ( n)WN

k N 1 n 0

有限长序列的DFT:

X (k ) DFT [ x(n)]N x(n)W kn x(n)W knn 0 M 1

0 k N 1

对比二者发现： X (k ) 是 X (k ) 的主值区序列，条件N≥M X (k ) m

X (k mN )

X (k ) X (k ) RN (k )返回

回到本节

xN ( n)

N

n0

DFS

X (k )

N

2N

N 2

0x (n)0

N 2

N

k

nDFT

N

X (k )0N 1

k返回