《信号分析与处理》课程PPT教学课件（讲稿）第三章 离散信号傅立叶分析 3.3 离散傅立叶变换 3.4 快速傅立叶变换

3.3离散傅立叶 变换

3.3 离散傅立叶 变换

3.3离散傅里叶变换 DFT-Discrete Fourier Transform) 时间连续的周期信号>频率离散的傅立叶级数 时间连续的非周期信号→>频率连续的傅立叶变换 时间离散的周期序列》频率离散的周期级数 时间离散的非周期序列→>频率连续的周期变换 非周期序列称为是有限长度序列,分析有限长度 序列和周期序列之间的关系,推导离散傅立叶变换

3.3 离散傅里叶变换 (DFT-Discrete Fourier Transform) → → 时间连续的周期信号 频率离散的傅立叶级数 时间连续的非周期信号 频率连续的傅立叶变换 时间离散的周期序列 频率离散的周期级数 时间离散的非周期序列 → 频率连续的周期变换 → 非周期序列称为是有限长度序列,分析有限长度 序列和周期序列之间的关系,推导离散傅立叶变换

离散周期序列的傅里叶级数展开式 ∑ xn(n)e n= jk 2兀-n N k k=

离散周期序列的傅里叶级数展开式 N j N W e 2 − =  =  = k N j k n N k N x n c e 2 ( )  =  − = n N j k n k N N x n e N c 2 ( ) 1 nk N j kn N W e 2 − = nk N j kn N W e 2 = −  =  = n N kn k N n WN x N c ( ) 1  =  − = k N kn N k WN x (n) c

离散傅里叶变换定义式 由于周期序列只有有限个序列值有意义,所以离散傅里 叶级数也使用于有限长序列 如果把长度为N的有限长序列看成是周期为N周期序列 的一个周期,则可以利用离散傅立叶级数计算有限长序列 N-1 k ∑x(mn) n=0 k C k= 把有限长序列周期延拓,Ck也可以看成是X(k)主值序列 的周期研拓,由于DFS求和运算只限定在n=0-N-1和k=0-N-1, 所以完全适用于有限长序列的傅立叶变换对

离散傅里叶变换定义式  − = = 1 0 ( ) 1 N n kn k N n WN x N c  =  − = k N kn N k WN x (n) c 由于周期序列只有有限个序列值有意义,所以离散傅里 叶级数也使用于有限长序列. 如果把长度为N的有限长序列看成是周期为N周期序列 的一个周期,则可以利用离散傅立叶级数计算有限长序列 把有限长序列周期延拓, 也可以看成是X(k)主值序列 的周期研拓,由于DFS求和运算只限定在n=0-N-1和k=0-N-1, 所以完全适用于有限长序列的傅立叶变换对 k c

DFT的定义 2丌 X(k)=∑ (k=0,1,2…N-1) r(ne n=0 2丌 jk (n=0,1,2…N-1) x(n 1 x(ke X(k) x(n X￥(k)=DFT[x(n) x(n)=DFTIX (K) x(n)= X(kWN k

一 DFT的定义  − = − = 1 0 2 ( ) ( ) N n n N jk X k x n e  (k = 0,1, 2N −1)  − = = 1 0 2 ( ) 1 ( ) N k n N jk X k e N x n  (n = 0,1, 2N −1)  − = = 1 0 ( ) ( ) N n nk n WN X k x  − = − = 1 0 ( ) 1 ( ) N k nk WN X k N x n X(k) = DFT[x(n)] x(n) = IDFT[X(k)]

X(k k (k=0,1,2…N-1) =0 N-1 x(n)= ∑ X(k)w nk(n=0,1,2…N-1) X(0 0 0 x(0) (1)wow l×(N X(N-1wo W(N-1xl W(N-))x(N-1) X(0) X(1) N-1)[0w(8 W(N-1)→X(N-1

(k = 0,1, 2N −1) (n = 0,1, 2N −1)  − = = 1 0 ( ) ( ) N n nk n WN X k x  − = − = 1 0 ( ) 1 ( ) N k nk WN X k N x n              −              =             − −  −  −  − ( 1) (1) (0) ( 1) (1) (0) 0 ( 1) 1 ( 1) ( 1) 0 1 1 ( 1) 0 0 0 x N x x W W W W W W W W W X N X X N N N N                      −              =             − − −  − −  − − −  − ( 1) (1) (0) ( 1) (1) (0) 0 ( 1) 1 ( 1) ( 1) 0 1 1 ( 1) 0 0 0 X N X X W W W W W W W W W x N x x N N N N        

X(0) (0) X(1) W WIx(N-D X(N-1)|W0W(1)1…W(x)xx(N-1) 从矩阵可看出,计算一个N点DFT,无论是正变换 环视反变换,都需要N2x(n)次复数乘法和N(N-1)次加法 运算,如果一个中等长度序列N=210=1024,就需要100多 万次复数乘法,N更长时,所需计算时间更长

             −              =             − −  −  −  − ( 1) (1) (0) ( 1) (1) (0) 0 ( 1) 1 ( 1) ( 1) 0 1 1 ( 1) 0 0 0 x N x x W W W W W W W W W X N X X N N N N         从矩阵可看出，计算一个 N点DFT，无论是正变换 环视反变换，都需要N 2x(n)次复数乘法和N(N-1)次加法 运算，如果一个中等长度序列N=210=1024 ,就需要100多 万次复数乘法,N更长时,所需计算时间更长

X(k) x(n 1X(k)w ⅹ(n)和X(k)是有限长序列的离散傅立叶变换对,都 是长度为N的值,都有N个独立值,已知其中一个序列,就能 唯一确定另一序列 DFT和DTFT都是处理有限长序列的重要工具,他们 之间有什么关系?

x(n)和 X(k)是有限长序列的离散傅立叶变换对,都 是长度为N的值,都有N个独立值,已知其中一个序列,就能 唯一确定另一序列  − = = 1 0 ( ) ( ) N n nk n WN X k x  − = − = 1 0 ( ) 1 ( ) N k nk WN X k N x n DFT和DTFT 都是处理有限长序列的重要工具,他们 之间有什么关系?

二DTFT、DFS及DFT之间的关系 e Q=k X(e NC=N ∑ xn(n)e ∑x(n)e n= nE<M X(k=X(e/ 饭3n=NC0,1,2…N-1) Ⅹ(k)是连续DTFT的等间隔采样

二DTFT、DFS及DFT之间的关系 N k j k X e N c 2 ( ) 1 =  =   =  − =  − =  =         = = n N n N j k N n N n N j k k N N k j x n e x n e N X e Nc N    2 2 2 ( ) ( ) 1 ( ) ( ) ( ) ( 0,1, 2 1) = 2 = = − =  X k X e Nck k N N k j   X(k)是连续DTFT的等间隔采样

x() (e2) a DwS ● 1● 10 k〔2kx/N 图DFT和DF(a)有限长序列(m)(b)x(m)频谱 ()x(n)周期延拓x(m)(d)x(m)的DS系数

图DFT和DFS (a)有限长序列 (b) 频谱 (c) 周期延拓 (d) 的DFS系数 x(n) x(n) x(n) x (n) N x (n) N