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

第三章离散傅里叶变换(DFT)及其快速算法(FFT)3.1离散傅里叶变换的定义及物理意义3.2DFT的主要性质3.3频域采样3.5DFT(FFT)应用举例3.4DFT的快速算法——快速傅里叶变换(FFT)3.1离散傅里叶变换的定义及物理意义模拟域FT、LT数字域FT、ZT数字域DFT时间域t:连续频率域Ω、s:连续时间域n:离散频率域k：离散频率域ω、z：连续返回离散傅立叶变换（DFT）实现了信号首次在频域表示的离散化，使得频域也能够用计算机进行处理。并且这种DFT变换可以有多种实用的快速算法。使信号处理在时、频域的处理和转换均可离散化和快速化。因而具有重要的理论意义和应用价值，是本课程学习的一大重点。本节主要介绍返回3.1.1DFT定义3.1.2DFT与ZT、FT、DFS的关系3.1.3DFT的矩阵表示3.1.1DFT定义设序列x(n)长度为M，定义x(n)的N点DFT为式中，N称为离散傅里叶变换区间长度，要求N≥M。为书写简单，令，因此通常将N点DFT表示为定义X(k)的N点离散傅里叶逆变换(IDFT)为1j02()DFT[()]()e,0,1,,1NnNNnkXkxnxnkN10()DFT[()](),0,1,,1NknNNnXkxnxnWkN2jeNNW101()IDFT[()](),0,1,,1NknNNkxnXkXkWnNN长度为N的离散序列返回回到本节例3.1：，分别计算x(n)的8点、16点DFT。解:x(n)的8点DFT为x(n)的16点DFT为8()()xnRn277j888008,0()()e0,1,2,3,4,5,6,7knknnnkXkRnWk2j8781616162j1601611e()11ekkknkknWXkWW7j16sin2e,0,1,2,,15sin16kkkk返回回到本节LT3x1是在频率区间上的等间隔采样()Xk()jXe返回回到本节程序运行结果024680246805101520024680102030400246802040608002468点数81632643.1.2DFT与ZT、FT、DFS的关系DFT有明确的物理意义，我们可以通过比较序列的DFT、FT、ZT，并将DFT与周期序列的DFS联系起来，得到DFT的物理意义。DFT和FT、ZT之间的关系假设序列的长度为M，N≥M将N点DFT和FT、ZT的定义重写如下101jj010()ZT[()]()(e)FT[()]()e()DFT[()](),0,1,,1MnnMnnMknNNnXzxnxnzXxnxnXkxnxnWkN返回回到本节比较前面三式，得到，k=0,1,2,…,N-1，k=0,1,2,…,N-1结论：(1)序列的N点DFT是序列傅里叶变换在频率区间[0，2]上的N点等间隔采样，采样间隔为2/N。(2)序列的N点DFT是序列的Z变换在单位圆上的N点等间隔采样，频率采样间隔为2/N。2je()()kNzXkXzj2()(e)kNXkX返回回到本节DFT与z变换2X(ejω)X(k)ok1N00ImjZReZ1234567(N-1)2Nk=0DFT与DTFT变换•序列x(n)的N点DFT是x(n)的Z变换在单位圆上的N点等间隔采样；•X(k)为x(n)的傅立叶变换在区间上的N点等间隔采样。这就是DFT的物理意义。[0,2]()jXe变量周期分辨率2N2f、ssf、NfskN返回回到本节DFT和DFS之间的关系：周期延拓取主值有限长序列周期序列主值区序列有限长序列周期序列主值区间序列()0,1,2,1xnnM()()NmxnxnmN0001nNnmNn0(())Nnn()()()NNNxnxnRn,()()NNMxnxn(())Nxn返回回到本节8()xn4()xn返回回到本节周期序列DFS:有限长序列的DFT:对比二者发现：是的主值区序列，条件N≥M1010()[()]()()NknNNNnMknNnXkDFSxnxnWxknW1010()[0()](()1)NknNnMknnXkDFTxnxnWNxnWk()Xk()Xk()()()()()NmXkXkmNXkXkRk返回回到本节()NxnnN0N2N()Xk02NNkN01N0nk)(nx)(kXDFSDFT2N返回回到本节DFT与DFS之间的关系:有限长序列x(n)的DFT变换X(k)，就是x(n)的周期延拓序列的DFS系数的主值序列()()()()(())()()()()(())NNNNNxnxnRnxnxnXkXkRkXkXkNM:()():()()DFTxnXkDFSxnXk)(~nx)(~kX返回回到本节DFS与FT之间的关系:•周期延拓序列的频谱特性由其傅里叶级数的系数确定，幅度相差一个常数因子。•DFT的是的主值区序列，所以x(n)的DFT表示的是周期序列的频谱特性。10()[()]()MknNNnXkDFSxnxnWk22()[()]()()jNkXeFTxnXkkNN()Xk()Xk2N()Xk)(~nx)(~nx返回回到本节3.1.3DFT的矩阵表示周期序列的DFS以及有限长序列x(n)的DFT如下可以发现它们右边的函数形式一样，但k的定义域不同，X(k)只是的主值区序列，或者说X(k)以N为周期进行周期延拓即是，用后面两式表示二者的关系：()Nxn101010()DFS[()]()()()DFT[()](),0,1,,1MknNNNnMknNnMknNNnXkxnxnWxnWkXkxnxnWkN-()Xk()Xk返回回到本节式(3.1.5)～(3.1.8)说明了DFT和DFS之间的关系。这些关系式成立的条件是N≥M，即DFT的变换区间N不能小于x(n)的长度M。如果该条件不满足，按照式(3.1.5)将x(n)进行延拓时，中将发生时域混叠，由式(3.1.8)得到的X(k)不再是x(n)的DFT，这时以上讲的DFS和DFT之间的关系不再成立。()()mXkXkmN()()()NXkXkRk(3.1.7)(3.1.8)()Nxn返回回到本节也可以表示成矩阵形式式中，X是N点DFT频域序列向量:x是时域序列向量:DN称为N点DFT矩阵，定义为10()DFT[()](),0,1,,1NknNNnXkxnxnWkNNXDxT[(0)(1)(2)(1)]XXXNXNXT[(0)(1)(2)(1)]xxxNxNx121242(1)12(1)(1)(1)1111111NNNNNNNNNNNNNNNND(3.1.12)返回回到本节也可以表示为矩阵形式:称为N点IDFT矩阵，定义为从式(3.1.12)和式(3.1.14)，我们可以发现101()IDFT[()](),0,1,,1NknNNkxnXkXkWnNN1NxDX1ND12(1)1242(1)(1)2(1)(1)(1)11111111NNNNNNNNNNNNNNNND(3.1.14)1*1NNNDD返回回到本节3.2DFT的主要性质与序列的FT类似，DFT也有许多重要的性质。其中一些性质本质上与FT的相应性质相同，但是某些其他性质稍微有些差别。返回线性性质DFT的隐含周期性循环移位性质复共轭序列的DFTDFT的共轭对称性循环卷积定理离散巴塞伐尔定理①线性性质设有限长序列的长度分别为，，a和b为常数。则式中，。12()()xnxn和12NN和12()()()xnaxnbxn12()()(),0,1,2,,1XkaXkbXkkN12≥max[,]NNN11()DFT[()],NXkxn22()DFT[()]NXkxn返回回到本节[0,2]②DFT的隐含周期性在第一节中，DFT和IDFT只定义了X(k)和x(n)在变换区间上的N个值。如果使DFT中k的取值域为[-∞，∞]，就会发现X(k)是以N为周期的，即X(k+mN)=X(k)称X(k)的这一特性为DFT的隐含周期性。物理意义：X(k)为在区间上的N点等间隔采样。以2π为周期，X(k)以N为周期。()jXe()jXe返回回到本节③循环移位性质⑴有限长序列的循环移位设序列x(n)的长度为M，对x(n)以N（N≥M）为周期进行周期延拓，得到定义x(n)的循环移位序列为上式表示将序列x(n)以N为周期进行周期延拓，再左移m个单位并取主值序列，就得到x(n)的循环移位序列y(n)。下图中(a)、(b)、(c)和(d)分别描述了x(n)、、和y(n)。图中M=6，N=8，m=2。()(())NNxnxn()()()(())()NNNNynxnmRnxnmRn()Nxn()Nxnm返回回到本节序列的循环移位过程示意图返回回到本节⑵循环移位性质设序列x(n)长度为M，x(n)的循环移位序列为，N≥M则④复共轭序列的DFT假设用表示x(n)的复共轭序列，长度为N，且，则，k=0,1,2,…,N-1式中，。同样：()(())()NNynxnmRn()DFT[()]()kmNNYkynWXk()xn()DFT[()]NXkxnDFT[()]()xnXNk()(0)XNX[()]()NDFTxNnXk返回回到本节⑤DFT的共轭对称性上一章介绍了序列FT的共轭对称性，DFT也有类似的共轭对称性质。但FT中的共轭对称是指对坐标原点的共轭对称，在DFT中指的是对变换区间的中心，即N/2点的共轭对称。⑴有限长共轭对称序列和共轭反对称序列假设有限长序列满足下式，n=0,1,2,…,N-1则称为共轭对称序列。假设有限长序列满足下式，n=0,1,2,…,N-1则称其为共轭反对称序列。ep()xn*epep()()xnxNnep()xnop()xn*opop()()xnxNn返回回到本节任一有限长序列x(n)都可以用它的共轭对称分量和共轭反对称分量之和表示，即将上式中的n用N-n代替，并两边取共轭，得到由上面两式得到和与原序列x(n)的关系为epop()()()xnxnxn***epopepop()()()()()xNnxNnxNnxnxnep()xnop()xn*ep1()[()()]2xnxnxNn*op1()[()()]2xnxnxNn返回回到本节⑵DFT的共轭对称性质假设序列x(n)长度为N，其N点DFT用X(k)表示。①将序列x(n)分成实部和虚部，相应x(n)的DFT分成共轭对称和共轭反对称两部分。即式中，，则riepop()()j()()()()xnxnxnXkXkXkri()Re[()]()Im[()]xnxnxnxn，epr()DFT[()]NXkxnopi()DFT[j()]NXkxn返回回到本节②将序列x(n)分成共轭对称和共轭反对称两部分，相应x(n)的DFT分成实部和虚部两部分，即式中，，，则epopri()()()()()j()xnxnxnXkXkXkr()Re[()]XkXk=i()Im[()]XkXkrep()DFT[()]NXkxniopj()DFT[()]NXkxn返回回到本节③实信号DFT的特点设x(n)是长度为N的实序列，其N点DFT用X(k)表示，我们从①的结论可知道X(k)具有共轭对称性质，即如果将X(k)写成极坐标形式，由共轭对称