知识2离散傅里叶变换及其快速算法

用Fourier变换来表示序列和线性时不变系统的频域特征，但是频谱jeX是ω的连续函书，用计算机处理和分析频谱是不方便的。那么就需要像时序信号那样，通过采集把连续信号变为离散信号，也对连续频谱采样而得到离散频谱，然后用数字电路或计算机进行处理和分析。有限长序列在应用中有重要的作用，通过它可以导出另一种Fourier变换表达式，即离散傅里叶变换(DFT)，此为解决频谱离散化的有效方法，同时DFT的高效算法——快速傅里叶变换FFT。周期序列一个周期为N的周期序列~x，对于所有的n，应该满足：为整数kkNnxx~~周期序列的周期N，一般使用最小周期作为周期。与连续时间周期函数相比，周期序列由于n及N均为整数，周期序列中应用最广泛的序列是：knNjknNeW2（2-1）ImRe10上图就是周期序列nNW（N=8），从n=0开始到8取完周期内的所有值。令k=1时，nNW就是一个周期序列。当n从0依次加1到N-1时，序列nNW取完周期内的所有值，这些值可以看成是Z平面上以原点为圆心的单位圆被N等分的交点的的坐标值。k为其他数值时，knNW的最小周期也许不是N，但是N一定是knNW的周期。knNW的性质很明显：周期性：knNW=nNkNW)(=)(NnkNW对称性：knNW=*knNW=nkNNW)(=)(nNkNW正交性：10n0,NkknNrrNnNW其他为整数或者10n0,NnknNrrNkNW其他为整数一个周期为N的周期序列nx~，在n=到n=+的范围内仅有N个序列值是独立的其中一个周期内的N个序列值足以表征整个序列的特征。而对于长度为N的有限长序列，只讨论n=0到N-1之间的N个序列值，其余皆为0。此二者在n=0到N-1单位内具有共同性。对于周期为n的周期序列nx~，定义n=0到N-1为主值区间，由主值区间N个序列值组成的有限长序列nx，称为nx~的主值序列。可以如下表示：nRnxnxN~（2-2）nRN为矩形序列，即：nNnnRN其他001上一过程称为取主值序列，有限长序列nx：nNnnxnx其他010如果以N为周期进行延拓，则有：rrNnxnx~（2-3）式2-2和2-3之间表明了周期序列和有限长序列之间的处理关系。即：周期序列可以去主值序列进行分析，然后对再周期延拓得到最后的处理结果。周期延拓的时候，延拓周期和有限长序列的长度不同的时候，序列可能会发生混叠。若nx为M长的有限长序列，即：nMnnxnx其他010（2-5）以N为周期进行延拓，得到周期序列：rNrNnxnx~再取nxN~的主值序列：nRnxnxNNN~（2-7）关于使（2-5）和（2-7）是否一致的问题：（1）当N=M时，nxN~和nxN是一致的，所以，周期延拓无混叠失真，主值序列和原序列一致相同。（2）当M/2=N=M时，此时会使得至少0~Nx不仅含有0x，还叠加有Nx。说明0Nx和0x是不一致的。因此，在M/2=N=M时会出现部分混叠失真，以下结论：110NnNMnxNMnnxnxN（3）当N=M/2时，nxN对nx是全混叠失真。所以，在数字信号处理中通常取N=M，以避免错误或者进一步的处理。周期序列不满足收敛条件，不能进行Z变换和Fourier变换分析。离散傅里叶级数（DFS）连续的周期函数和离散的周期函数都可用傅里叶级数表示，所以不论连续周期函数还是离散周期函数都可用傅里叶级数表示。经过推倒，周期为N的周期序列nxN~的傅里叶级数与周期为N的复指数序列knNW密切相关。nxN~有N个独立值，其离散傅里叶级数也只有N个独立分量。一个周期为N的周期序列nxN~的傅里叶级数的分析与综合对（正变换和反变换）可表示为：10~~~NnknNnxDFSWnxkX（2-9）和10~~~1NkknNkXIDFSWkXNnx（2-10）上两个式子是周期序列离散谱分析的数学方法，显然，离散傅里叶级数kX~在频域上是一个周期为N的周期序列。由于kX~、nx~以及knNW均是以N为周期的。因此，式中的n和k的值可以随机确定，只要取足N点即可。可表示为：1~~00NnnnknNWnxkX和1~~001NkkkknNWkXNnx离散傅里叶级数（DFS）的性质1.线性：kYbkXanybnxaDFS~~~~，其中a、b为任意常数。2.移位特性：kXWmnxDFSmkN~和nxWlkXIDFSnlN~3.周期卷积：若kYkXkF~~~，则有，kFIDFSnf~~mnymxNm~10~mnxmyNm~10~周期序列的卷积也可用下式表示：mnymxnfNmmm~100~~（2-18）式（2-18）说明对mx~只要取够一个周期的卷积即可，周期卷积与m的起点无关，而且周期序卷积的结果仍是一个周期序列。离散傅里叶变换（DFT）有限长序列nMnnxnx其他010的离散傅里叶变换对定义为：k01010其他NnknNNkWnxnxDFTkX和n010110其他NkknNNnWkXNkXIDFTnx上述两式均为非病态线性方程组，有唯一解。因此，长度为N的有限长序列nx的离散傅里叶变换kX仍然是一个N长的频域有限长序列，nx和kX由唯一对应的关系。把一个有限长序列nx看成是周期序列nx~的主值序列，就能利用周期序列的性质。nx~的相应的周期序列的离散傅里叶级数为kX~，它的主值序列即为nxDFTkX，即存在：nRkXIDFSnRnxnxNN~~kRnxDFSkRkXkXNN~~可见，离散傅里叶变换和离散傅里叶级数有着固有的内在的联系，理论上是成立的。同时长度为N的有限长序列nx可通过补0成为长度为M的有限长序列nxM，亦即：nMnNNnnxnxM其他补00,1010一般认为，nx补零并没有改变序列的本质，实际应用中也常常如此处理，但是kX的变换很大，此时的傅里叶变换应该为kXM：10MnknMMWnxkX而10NnknNWnxkX按照knNW的定义，显然knNW和knMW是不相同的。因此，一个有限长序列可以进行大于其序列的任意长度的任意点数的离散傅里叶变换，具体的点数可根据实际需要进行选定，但是由于频率点的变化，离散傅里叶变换的结果一般是不相同的。综上所述，nx的离散傅里叶变换与变换长度N的取值有关。离散傅里叶变换(DFT)的性质假设：nx与ny均为N点长的有限长序列，并有：nxDFTKXnyDFTkY1.线性性质：为常数、bakbYkaXnybnaxDFT2.圆周移位：一个有限长序列nx向左移动m位的圆周移位定义如下，nRmnxnfNN序列圆周移位m位以后的DFT如下，kXWnfDFTkFkmN3.卷积特性：若有kYkXkF，则kFIDFTnfkYkXIDFTnRkYkXIDFSN~~10NmNNNnRmnymx10NmNNnRmnymx（2-30）式（2-30）的卷积形式与上节的周期卷积过程相似，仅是最后取主值序列。mx限定在m=0到N-1之间，但mny是要圆周移位的，所以称为圆周卷积，式2-30可以写成：nxnynf或者nynxnf同理，频域的圆周卷积形式为：kYkXkRlkYlXNnynxDFTNlNN101kXkYkRlkXlYNnynxDFTNlNN1015.帕赛瓦尔定理：利用上述特性，可以证明：10*10*1NkNnkYkXNnynx当ny=nx时，则有：2102101NkNnkXNnx（2-36）式（2-36）的意义是：有限序列的能量=有限频谱的能量。有限长序列的线性卷积和圆周卷积有限长序列有两种卷积形式：线性卷积和圆周卷积，圆周卷积与DFT相对应，可以采用快速傅里叶变换算法(FFT)进行运算，求解速度极快。但实际问题中往往是解决线性卷积问题，例如信号通过线性系统，系统的输出信号ny是输入信号nx与单位取样响应nh的线性卷积：nhnxnf*，接下来用圆周卷积来实现线性卷积，设nx是长度为M点的有限长序列，ny是N点的有限长序列，则线性卷积：nynxnf*是一个长度为11MNL点的有限长序列，现将nx和ny均补0增长为L点的有限长序列，其中：NML,max，然后进行L点的圆周卷积：nynxnfc10LmLLnRmnymx通过公式可以证明nfc和nf的关系，通过计算得：rLcNRrLnfnf由上面的式子可以看出，nfc是nf以L为周期，进行周期延拓后在0到L-1的范围内所取得的主值序列，如果L=L1，则有，nfnfc上式表明，要使圆周卷积等于线性卷积而不产生混叠失真的充要条件是：L=M+N+1若LL12L，则在n=0到11LL范围内出现LL1个点的混叠失真，如下：110:11LnLLnfLLnnfnfc若随意选择L，当L2L时，圆周卷积和线性卷积的结果就会完全不一致，将产生全混叠失真。DFT、DTFT和Z变换如果一个有限长序列的nx，满足收敛条件时，则有，10NnnZnxZX（2-40）10NnnjjenxeX（2-41）DFT相应的形式为：10NnknNWnxkX（2-42）上式中的knNjknNeW2。式（2-40）是有限长序列nx的Z变换，是在Z平面内对nx的一些特性进行分析时的工具。当Z取单位圆的时候，亦即jeZ，则变为是（2-41），成为nx的频域特性分析，其中的ω不是一个固定值，而是一个参变量，可以连续取值。为了便于计算机进行处理，ω就需要离散化，简单的就是在ω=0到2π的范围内N等分，得到nx的DFT的形式，亦即（2-42）式，它们之间的关系可以如下表示：||2kNjWZeXZXkXkN（2-43）式（2-43）说明N点的有限长序列nx的离散傅里叶变换kX是它的Z变换在单位圆上N个等分点上（kNkWZ，k=0,1,2,3,...,N-1）的采样值，也是它的傅里叶变换jeX在0=ω=2π区间N个等分点上1,...,1,0,/2NkNkk的采样，这种关系意味着对于时间有限信号，可以像带限