清华大学：《信号与系统》课程教学资源（PPT课件讲稿）第九章 离散傅立叶变换及其快速算法 §9.4 离散傅立叶变换的性质 §9.5 DFT与Z变换的关系 §9.6 快速傅立叶变换（FFT）

89.4离散傅立叶变换的性质 线性 圆周位移、时移特性和频移特性 时域圆周卷积和频域圆周卷积定理 奇偶虚实性 相关特性 帕斯瓦尔定理 (只讲圆周卷积,其它类似拉氏变换 的性质)

1 §9.4 离散傅立叶变换的性质 • 线性 • 圆周位移、时移特性和频移特性 • 时域圆周卷积和频域圆周卷积定理 • 奇偶虚实性 • 相关特性 • 帕斯瓦尔定理 （只讲圆周卷积，其它类似拉氏变换 的性质）

圆周位移的概念 有限长序列 (n) x(1)0≤n≤N-1 周期延拓 x(4)N x((n N 线性位移 x((n-m ) x(07-m)x 加窗 x(7-m)G(m) 得到圆周位移序列 x(n-m)Gn(n) o m N-1 2 GN(n

2 圆周位移的概念 • 有限长序列 • 周期延拓 • 线性位移 • 加窗 • 得到圆周位移序列 x(n) n N x(( ))0  n  N −1 n m N x(( − )) x((n m)) G (n) − N N x(n) n N x(( )) n m N x(( − )) G (n) N x((n m)) G (n) − N N 0 N −1 n n n n m m

时移特性 若 DFTIx(n= X(k) y(n)=x((n-m)NGn(n) DFTIy(n)]=W mX(k) 时域序列的圆周位移的DFT为原来的 DFT乘以一个因子Wm

3 时移特性 • 若 • 则 • 时域序列的圆周位移的 为原来的 乘以一个因子 ( ) (( )) ( ) [ ( )] ( ) y n x n m G n DFT x n X k = − N N = DFT[y(n)] W X(k) mk = DFT DFT mk W

频移特性 若DFT[x(m)=X(k) y(k)=X((k-DNG(n) IDFTIY(k]=x(n)W 在Z域的频移l,则IDFT在时域x(n)乘以 个Wh

4 频移特性 • 若 • 则 • 在Z域的频移l，则IDFT在时域x(n)乘以 一个 ( ) (( )) ( ) [ ( )] ( ) Y k X k l G n DFT x n X k = − N N = ln IDFT Y k x n W − [ ( )] = ( ) ln W −

时域圆周卷积定理 若Y(k)=X(k)H(k) 则y(n)=x(n)h x(n)oh(n)=2x(m)(n-m) GN(ny m=0 定义为 圆周卷积 x(n)@h(n)=h(m)x(n-m)NG(n) x(n)和h(n)都 的 需是N点 x(n)h(n)(圆则点在 卷积

5 时域圆周卷积定理 • 若 • 则 Y(k) = X (k)H(k)  − =  = − =  1 0 ( ) ( ) ( ) (( )) ( ) ( ) ( ) ( ) N m N N x n h n x m h n m G n y n x n h n 定义为 圆周卷积  − =  = − 1 0 ( ) ( ) ( ) (( )) ( ) N m x n h n h m x n m N GN n x(n) N h(n) N点的 圆周卷积 x(n)和h(n)都 需是N点

频域圆周卷积定理 若y(an)=x(n)h(n) Y(k)=DFTLy(n) N-1 之XOH(k-1)G(k) =0 人、H(O)X(k-D)G(k) 6

6 频域圆周卷积定理 • 若 • 则 y(n) = x(n)h(n)   − = − = = − = − = 1 0 1 0 ( ) (( )) ( ) 1 ( ) (( )) ( ) 1 ( ) [ ( )] N l N N N l N N H l X k l G k N X l H k l G k N Y k DFT y n

89.5DFT与Z变换的关系 有限长序列的Z变换的抽样 X() ∑x(m)=”|平=∑x(n >x(nWmk=DFT[x(n)=X(k) X(=2)=X(k 2丌 2=e N x(n)的Z变换在 单位圆上均匀抽样 即为它的DFT Z平面

7 §9.5 DFT与Z变换的关系 有限长序列的Z变换的抽样 ( ) [ ( )] ( ) ( ) ( ) ( ) 1 0 1 0 1 0 2 2 2 2 x n W DFT x n X k X z x n z x n e n k N n W e j kn N n z e N n n z e N j N N k N k j N j = = = = =    − = = − − = = − = − = −     x(n)的Z变换在 单位圆上均匀抽样 即为它的DFT N 2 Z平面 X (z) 2 X (k) k N j z e = = 

89.6快速傅立叶变换(FT) W′因子的周期性和半周期性 0彡 N 0 W=1. W=Wu=1 N N WM=l r+mN三WN N NWN=[WN丁 2丌N w-e J/L (mN+×2 N 8

8 §9.6 快速傅立叶变换（FFT） • W r 因子的周期性和半周期性 r N r N m N N j j N r N r N r N r m N N m N N N N N N W W W e e W W W W W W W W W N N N N N = − = = = − = − = = = = = = + − − + + − 2 2 2 2 2 1, 1 [ ] 1, 1, 1 ( ) * 0 0  

基-2算法的FFT的基本思路 以N=22=4为例的DFT X(k)=∑x(7)W知 n=0 k=0X(O)=x(0W+x(1)+x(2)W4+x(30 k=1X(1)=x(0W0+2x(1)W4+x(2)W2+x(3)W43 k=2X(2)=x(0W+x(1)W2+x(2)W4+x(3)W k=3X(3)=x(0W4+x(1)W43+x(2)W4+x(34 X(O)WWw wi x(0) 4 (1W W W2 Wix( X(2)|W40W42W4W6 4/x(2) X(3) 0 w, ws w W3‖x(3) 4

9 基-2算法的FFT的基本思路 • 以 2 4 为例的DFT 2 N = =  − = = 4 1 0 4 ( ) ( ) n kn X k x n W 9 4 6 4 3 4 0 4 6 4 4 4 2 4 0 4 3 4 2 4 1 4 0 4 0 4 0 4 0 4 0 4 3 (3) (0) (1) (2) (3) 2 (2) (0) (1) (2) (3) 1 (1) (0) (1) (2) (3) 0 (0) (0) (1) (2) (3) k X x W x W x W x W k X x W x W x W x W k X x W x W x W x W k X x W x W x W x W = = + + + = = + + + = = + + + = = + + +                           =             (3) (2) (1) (0) (3) (2) (1) (0) 9 4 6 4 3 4 0 4 6 4 4 4 2 4 0 4 3 4 2 4 1 4 0 4 0 4 0 4 0 4 0 4 x x x x W W W W W W W W W W W W W W W W X X X X

W0=1 X(0)11111|x(0) X(1)1W4W2Wx(1) N X(2)1W421W4x(2) X(3) 6 9 4 WW4‖x(3) (mN+N )=-1「X(0)「1111x(0 X(1)1W4-1Wx(1) x(2)1-11-1x(2) X(3)[1W8-1W4x(3)

10                         =             (3) (2) (1) (0) 1 1 1 1 1 1 1 1 (3) (2) (1) (0) 9 4 6 4 3 4 6 4 2 4 3 4 2 4 1 4 x x x x W W W W W W W W X X X X 1 1 0 = = mN N N W W 1 ( ) 2 = − mN+N WN                         − − − − =             (3) (2) (1) (0) 1 1 1 1 1 1 1 1 1 1 1 1 (3) (2) (1) (0) 9 4 3 4 3 4 1 4 x x x x W W W W X X X X