第七讲 DFT——FFT

1、 第1章 离散时间信号、系统和z变换 第2章 DFT及其快速算法 第3章数字滤波器设计 第4章 离散随机信号的处理目 录第2章 DFT及其快速算法 2-1 周期序列 2-2 离散傅立叶级数 2-3 离散傅立叶变换 2-4 频率采样理论 2-5 快速傅立叶变换 2-6 离散傅立叶反变换（IDFT) 的运算意义：频域内离散化-快速算法（FFT）-易于计算机实现2-1 2-1 周期序列周期序列为整数，应满足对于所有的周期序列一个周期为mmNnxnxnx)()(n),(N定义：主值区间、主值序列为主值序列个样本为主值区间，义个样本值是独立的，定，有周期序列)(N) 1(0N)(nxNnx1N0)(nx

2、n主值区间主值序列)(nx)()()(nRnxnxN周期序列)(nxrrNnxnx)()(间的余数取（：) 1, 0)/()()()(NNnnnxnxNN若n=mN+n1 ，称n与n1同余。周期延拓 例：设x(n)如图所示，求，即N=44)(nx0312)(nxn4)(nxn03123123121 23 5 4 3 2 1 0 1 2 3 4 5 6 nNn)(Nnx)( 0 3 2 1 0 3 2 1 0 3 2 1 3 0 1 2 3 01 231 200312)(nxn4)(nxn03123123121 2 3混叠失真n03123121 2 3)n(R)n(x)n(x)n(x)n(x,M

3、)n( xNNNNN长度为设)n( x)n(xMNN时，2)n(x1NnNM)n( x1NMn0)n( x)n(x2NMNN时，1M 补充 ： 傅里叶变换的四种基本形式1连续时间与连续频率 连续傅里叶变换)(txat0f)( fXa0f2dfefXtxftjaa2)(21)(dtetxfXftjaa2)()(2离散时间与连续频率 序列傅里叶变换 )(nTxan0)(nxTt1( )()2jj nx nX eednnjjenxeX)()()(jeX0TT/22周期性4离散时间与离散频率 离散傅里叶级数0)(nxntf0)(kX时域、频域都是周期性的3连续时间与离散频率 傅里叶级数)(txpt01

4、Tf0)(1kfX)(1kXktkfjpekfXtx121)()(dtetxTkfXTtkfjp110211)(1)(周期性第一个域离散函数第二个域周期函数连续函数非周期函数且易证： 一个域中的周期函数的周期 离散间隔另一个域中离散函数的)2( 12-2. 离散傅里叶级数（离散傅里叶级数（DFS） 1从序列傅里叶变换导出 DFS )(jeX为 的连续的周期的函数，周期为2 。对 )(jeX离散化，离散间隔 N2，即令 kNjeXkX2)()(整数k频域的离散化 时域的周期化 将导致离散间隔 N2周期点数 122NNNkNjeXkX2)()(210( )Njk nNnx n e ( )DFS x

5、 n在 deeXnxnjj)(21)(的表达式， )()(kXeXjkN2Nd210Nk)()(nxnx21012( )( )2NjknNkx nX k eN2101( )NjknNkX k eN( )IDFS X kDFS 变换对 10 ( )( )( )NnkNnDFS x nx n WX k101( )( )( )NnkNkIDFS X kX k Wx nN1. 线性2. 移位)()()()(nxWlkXIDFSkXWmnxDFSnlNmkNknjknNNeW22-1 2-1 周期序列周期序列性质：)()(NnkNnNkNknNWWW周期性：共轭奇对称共轭偶对称)()()()(*nxnx

6、nxnx)()(*nNkNnkNNknNknNWWWW）（对称性：nrrNnNWNkknN其他为整数正交性：,010是一个周期复序列因子：knjknNNeWDFT23周期序列的周期卷积 两个周期为N 的周期序列进行卷积 12( )( )x nx n（1）周期卷积 102121)()()()(Nmmnxmxnxnx两个N 点的周期序列进行周期卷积，其结果仍为周期为N 的周期序列。 12( )()mx m x nm（2）卷积定理 )()()(21nxnxny)()()(21kXkXkYNNNDFSDFS DFSNNN12( )( )( )y nx nxn121( )( )( )Y kX kXkNN

7、NNDFSDFS DFSNNN例DFTn)(1nx211023n)(2nx11023mm)(1mx)(2mxm11023)(2mx 04n)()(21nxnxm1102 3)1 (2mx152 354m11023)4(2mx102121)()()()(Nmmnxmxnxnx周期均为N1 DFT 的定义 用计算机进行傅里叶变换运算时，要求 （1）时、频域均为离散的； （2）时、频域的点数均为有限的。 在离散傅里叶级数中，由于其时域及频域均为周期序列，在整个域中都存在非零的序列值。但同时可注意到，其时域与频域之间的映射关系在一个周期内便可以完全地反映出来。2-3. 离散傅里叶变换（离散傅里叶变换（

8、DFT）)(kX1N主值序列)(nx主值序列)(kX1NDFT变换对DFS变换对0)(nxnk0)()(kXnxDFT)()(10kRWnxNNnnkN)()(nxkXIDFT)()(110nRWkXNNNknkNDFT变换对 DFT是一种数学上的映射关系，反映了时域上的 N点与频域上的 N 点之间的对应关系2jNNWe的关系与问的序列加长补零为长度为把点点例：)()(1100)()()()()()(kXkYrNnNNnnxnynyrNnxkXNnxN注意长度N)rk(X)k(Y2 DFT与 DFS （1） DFT与DFS的关系 时域频域DFTDFSx(n)有限长序列(N) = )()(nRn

9、xN周期序列 )(nx取主值区间 X(k)有限长序列(N) = )()(kRkXN周期序列 )(kX取主值区间 )(nx周期序列(N) = Nnx)(有限长序列x(n)的周期延拓)(kX周期序列(N) = NkX)(有限长序列X(k)的周期延拓2.3.4 DFT与Z变换 （1） DFT与Z变换的关系 对于有限长序列x(n)（0nN1 ） 10)()(NnnznxzX10( )( )( )NnkNNnX kx n WRk显然， )(zXkNjezzXkX2)()(在Z平面的单位圆上采样 ？ 4例 用封闭形式表示下列有限长序列的N点DFTx(n) （a） )1)()(NMnRnxM（b） )()(

10、0nRenxNnj解： （a） )()()(10kRWnRkXNNnnkNM)(10kRWNMnnkN)(11kRWWNkNMkN)(sinsin)1(kRekNMkNNkMNj)(kXk0N2.3.2 DFT的性质 （1）线性 时域 )()()(213nbxnaxnx1N2NN,max21NNN NNN频域 )()()(213kbXkaXkX（2）圆周移位 若 )()()(nRmnxnfNN，称f(n)为x(n)的 m点圆周移位序列。步骤：）移位 m点； ）取主值序列。 ）将x(n)以N 为周期进行周期延拓；0312)(nxnn03123123124)(nx1 23n031212 34)2(

11、 nx)()2(44nRnx根据同余算法 n(2)Nn (2)( )NNx nRn0 1 2 32 3 0 11 0 3 2若 )()(kXnxDFT则 )()()(kXWnRmnxDFTmkNNN且 )()()(nxWkRlkXIDFTnlNNN(3). 共轭对称性 定义其他，定义对，长度为互为、1100)()0()()()(NDFT)()(NnnnNxxnRnNxnNxkXnxNN)()()()(NnNxnNxnxnx 取主值右移周期延拓后，反转其他1100)()0()()()(NkNkkNXXnRkNXkNXNNNnN13 共轭对称性 复共轭序列的DFT10*)()(NnnkNWnxnx

12、DFT证明：*10)(NnnkNWnx)(*kX)()(*10)(kNXWnxNnkNnN)0(X)N(X)n(R)kN(X)kN(X)n(xDFTNN*10NkNkN1共轭对称与共轭反对称61是实数时，为奇序列则称为共轭反对称序列序列满足是实数时，为偶序列则称为共轭对称序列序列满足为复序列，则如果)()(),()(1)()(),()(1)(nxnxnxnxnxnxnxnxnxoe)()(21)()()(21)()()()()(*nxnxnxnxnxnxnxnxnxnxoeoe和一个共轭反对称序列之轭对称序列和，总可以表示为一个共任意一个序列)()()()(*nxnxnxnxooee 圆周共轭

13、偶（奇）对称序列)()()()(*nxnxnxnxooee)()(21)()()()(21)()(*nNxnxnNxnxnNxnxnNxnxopopepep)()(21)()()(21)(*nxnxnxnxnxnxoe)()()(nxnxnxopep)()(nNxnxepep)(arg)(argnNxnxepep)()(21)()()()(21)()(*kNXkXkNXkXkNXkXkNXkXopopepep频域：)()()(kXkXkXopep)(Re)(RekXkNXoo)(Im)(ImkXkNXoo DFT的共轭特性)kN(X)nN( xDFT)k(X)nN(xDFT*)()()(21)

14、()(21)(kXkNXkXnxnxDFTnxDFTepr)()()(21)()(21)(kXkNXkXnxnxDFTnjxDFTopi)()()(kXkXkXopep)(Re)(kXnxDFTep)(Im)(kXjnxDFTop 共轭对称性实虚部讨论 若将有限长序列认为是分布在N等分圆周上，则共轭偶部 和 满足左半圆上和右半圆上的序列共轭对称；而共轭奇部 和 满足左半圆和右半圆上的序列共轭反对称。时域x(n)频域X(k)DFTx(n)圆周共轭偶部)(nxepx(n)圆周共轭奇部)(nxopx(n)实部)(nxrx(n)虚部)(njxiX(k)共轭偶部)(kXepX(k)共轭奇部)(kXopX

15、(k)实部)(kXrX(k)虚部)(kjXi)(nxe)(kXe)(nxo)(kXo（4）圆周卷积 周期卷积取主值序列 若 则 N)n(y)n(x)n(R)mn(y)mn(y)m(y)n(y)n(y)n(xNNNn 卷积与取主值序列右移反转周期延拓）（）（)k(Y)n(y),k(X)n(x)k(Y)k(X)k(F1N0mNN)n(R)mn(y)m( x)k(FIDFT)n( f圆周卷积 频域 若 则 N)k(Y)n(y),k(X)n(x)n( y)n( x)n(f1N0lNN)k(R)lk(Y)l (XN1)n( fIDFT)k(F1N0lNN)k(R)lk(X)l (YN1（5）. 帕赛瓦尔定律1