DFT及其快速算法

•第1章离散时间信号、系统和z变换•第2章DFT及其快速算法•第3章数字滤波器设计•第4章离散随机信号的处理目录第2章DFT及其快速算法•2-1周期序列•2-2离散傅立叶级数•2-3离散傅立叶变换•2-4频率采样理论•2-5快速傅立叶变换•2-6离散傅立叶反变换（IDFT)的运算意义：频域内离散化---快速算法（FFT）--易于计算机实现2-1周期序列为整数，应满足对于所有的周期序列一个周期为mmNnxnxnx)(~)(~n),(~N定义：主值区间、主值序列为主值序列个样本为主值区间，义个样本值是独立的，定，有周期序列)(N)1(~0N)(~nxNnx1N0)(~nx……n主值区间主值序列)(nx)()(~)(nRnxnxN周期序列)(~nxrrNnxnx)()(~间的余数取（：)1,0)/())(())(()(~NNnnnxnxNN若n=mN+n1，称n与n1同余。周期延拓例：设x(n)如图所示，求，即N=44))((nx0312)(nxn4))((nxn0312312312123……–5–4–3–2–10123456……nNn))((Nnx))((…………032103210321…………3012301231200312)(nxn4))((nxn0312312312123混叠失真n0312312123)n(R)n(x~)n(x))n((x)n(x~,M)n(xNNNNN长度为设)n(x)n(xMNN时，2))n((x1NnNM)n(x1NMn0)n(x)n(x2NMNN时，1M补充：傅里叶变换的四种基本形式1．连续时间与连续频率—连续傅里叶变换)(txat0f)(fXa0f2dfefXtxftjaa2)(21)(dtetxfXftjaa2)()(2．离散时间与连续频率—序列傅里叶变换)(nTxan0)(nxTt1()()2jjnxnXeednnjjenxeX)()()(jeX0TT/22周期性4．离散时间与离散频率—离散傅里叶级数0)(~nx……nt…f0…)(~kX时域、频域都是周期性的3．连续时间与离散频率—傅里叶级数)(txpt01T……f0)(1kfX)(1kXktkfjpekfXtx121)()(dtetxTkfXTtkfjp110211)(1)(周期性第一个域离散函数ℱ第二个域周期函数连续函数非周期函数ℱ且易证：一个域中的周期函数的周期离散间隔另一个域中离散函数的)2(12-2.离散傅里叶级数（DFS）1．从序列傅里叶变换导出DFS)(jeX为的连续的周期的函数，周期为2。对)(jeX离散化，离散间隔N2，即令kNjeXkX2)()(~整数k频域的离散化时域的周期化将导致离散间隔N2周期点数122NNNkNjeXkX2)()(~210()NjknNnxne[()]DFSxn在deeXnxnjj)(21)(的表达式，)(~)(kXeXjkN2Nd210Nk)(~)(nxnx21012()()2NjknNkxnXkeN2101()NjknNkXkeN[()]IDFSXk∴DFS变换对10[()]()()NnkNnDFSxnxnWXk101[()]()()NnkNkIDFSXkXkWxnN1.线性2.移位)(~)](~[)(~)(~nxWlkXIDFSkXWmnxDFSnlNmkNknjknNNeW22-1周期序列性质：)()(NnkNnNkNknN周期性：共轭奇对称－共轭偶对称)()()()(**nxnxnxnx)()(*nNkNnkNNknNknN）＝（对称性：－nrrNnNWNkknN其他为整数正交性：,010是一个周期复序列因子：knjknNNeWDFT23．周期序列的周期卷积两个周期为N的周期序列进行卷积12()()xnxn（1）周期卷积102121)(~)(~)(~)(~Nmmnxmxnxnx两个N点的周期序列进行周期卷积，其结果仍为周期为N的周期序列。12()()mxmxnm（2）卷积定理)(~)(~)(~21nxnxny)(~)(~)(~21kXkXkYNNNDFSDFSDFSNNN12()()()ynxnxn121()()()YkXkXkNNNNDFSDFSDFSNNN例DFT……n)(~1nx211023……n)(~2nx11023mm)(~1mx)(~2mx……m11023)(~2mx04n)(~)(~21nxnx……m11023)1(~2mx152354……m11023)4(~2mx……102121)(~)(~)(~)(~Nmmnxmxnxnx周期均为N1．DFT的定义用计算机进行傅里叶变换运算时，要求（1）时、频域均为离散的；（2）时、频域的点数均为有限的。在离散傅里叶级数中，由于其时域及频域均为周期序列，在整个域中都存在非零的序列值。但同时可注意到，其时域与频域之间的映射关系在一个周期内便可以完全地反映出来。2-3.离散傅里叶变换（DFT）)(~kX1N主值序列)(nx主值序列)(kX1NDFT变换对DFS变换对0)(~nx……n…k0…)()]([kXnxDFT)(])([10kRWnxNNnnkN)()]([nxkXIDFT)(])(1[10nRWkXNNNknkNDFT变换对DFT是一种数学上的映射关系，反映了时域上的N点与频域上的N点之间的对应关系2jNNWe的关系与问的序列加长补零为长度为把点点例：)()(1100)()()()()()(kXkYrNnNNnnxnynyrNnxkXNnxN注意长度N)rk(X)k(Y2．DFT与DFS（1）DFT与DFS的关系时域频域DFTDFSx(n)—有限长序列(N)=)()(~nRnxN—周期序列)(~nx取主值区间X(k)—有限长序列(N)=)()(~kRkXN—周期序列)(~kX取主值区间)(~nx—周期序列(N)=Nnx))((—有限长序列x(n)的周期延拓)(~kX—周期序列(N)=NkX))((—有限长序列X(k)的周期延拓2.3.4DFT与Z变换（1）DFT与Z变换的关系对于有限长序列x(n)（0nN1）10)()(NnnznxzX10()[()]()NnkNNnXkxnWRk显然，)(zXkNjezzXkX2)()(在Z平面的单位圆上采样？4．例用封闭形式表示下列有限长序列的N点DFT[x(n)]（a）)1)(()(NMnRnxM（b）)()(0nRenxNnj解：（a）)(])([)(10kRWnRkXNNnnkNM)(][10kRWNMnnkN)(11kRWWNkNMkN)(sinsin)1(kRekNMkNNkMNj)(kXk0N2.3.2DFT的性质（1）线性时域)()()(213nbxnaxnx1N2NN},max{21NNNNNN频域)()()(213kbXkaXkX（2）圆周移位若)())(()(nRmnxnfNN，称f(n)为x(n)的m点圆周移位序列。步骤：ⅱ）移位m点；ⅲ）取主值序列。ⅰ）将x(n)以N为周期进行周期延拓；0312)(nxnn03123123124))((nx123n03121234))2((nx)())2((44nRnx根据同余算法n((2))Nn((2))()NNxnRn012323011032若)()]([kXnxDFT则)()]())(([kXWnRmnxDFTmkNNN且)()]())(([nxWkRlkXIDFTnlNNN(3).共轭对称性•定义其他，定义对，长度为互为、1100)()0()())(()(NDFT)()(NnnnNxxnRnNxnNxkXnxNN)()(~)(~)(NnNxnNxnxnx取主值右移周期延拓后，反转其他1100)()0()())(()(NkNkkNXXnRkNXkNXNNNnN13共轭对称性•复共轭序列的DFT10**)()]([NnnkNWnxnxDFT证明：*10)(NnnkNWnx)(*kX)()(**10)(kNXWnxNnkNnN？)0(X)N(X)n(R))kN((X)kN(X)n(xDFTNN***10NkNkN1共轭对称与共轭反对称61是实数时，为奇序列则称为共轭反对称序列序列满足是实数时，为偶序列则称为共轭对称序列序列满足为复序列，则如果)()(),()(1))()(),()(1))(nxnxnxnxnxnxnxnxnxoe)()(21)()()(21)()()()()(**nxnxnxnxnxnxnxnxnxnxoeoe和一个共轭反对称序列之轭对称序列和，总可以表示为一个共任意一个序列)()()()(**nxnxnxnxooee•圆周共轭偶（奇）对称序列)()()()(**nxnxnxnxooee)()(21)()()()(21)()(****nNxnxnNxnxnNxnxnNxnxopopepep)()(21)()()(21)(**nxnxnxnxnxnxoe)()()(nxnxnxopep)()(nNxnxepep)(arg)(argnNxnxepepN-1)n(xep*****)()(21)()()()(21)()(****kNXkXkNXkXkNXkXkNXkXopopepep频域：)()()(kXkXkXopep)(Re)(RekXkNXoo)(Im)(ImkXkNXooN-1)(kXop****•DFT的共轭特性)kN(X)nN(xDFT)k(X)nN(xDFT**)()()(21)()(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(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(F1N0mNN)n(R))mn((y)m(x)]k(F[IDFT)n(f圆周卷积—频域若则N)k(Y