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

用Fourier变换来表示序列和线性时不变系统的频域特征，但是频谱XI向媒①的连续函书，用计算机处理和分析频谱是不方便的。那么就需要像时序信号那样，通过采集把连续信号变为离散信号，也对连续频谱采样而得到离散频谱，然后用数字电路或计算机进行处理和分析。有限长序列在应用中有重要的作用，通过它可以导出另一种Fourier变换表达式，即离散傅里叶变换(DFT)，此为解决频谱离散化的有效方法，同时DFT的高效算法一一，快速傅里叶变换FFT。周期序列•〜一个周期为N的周期序列x，对于所有的n，应该满足：X=x(n+kN北为整数)周期序列的周期N，一般使用最小周期作为周期。与连续时间周期函数相比，周期序列由于n及N均为整数，周期序列中应用最广泛的序列是：；2；2兀，一Wkn=e-JNkn(2-1)对称性:W-kn=N正交性:对称性:W-kn=N正交性:如Wkn二Nk=0(Wkn)=W(N-k)n=Wk(N-n)NNN=rN,r为整数)ten)或者如Wkn=Nn=0=rN,r为整数)他n)上图就是周期序列Wn(N=8)，从n=0开始到8取完周期内的所有值。N令k=1时，Wn就是一个周期序列。当n从0依次加1到N-1时，序列Wn取完周期内的所有值，这些值可以看成是Z平面上以原点为圆心的单位圆被N等分的交点的的坐标值。k为其他数值时，吟的最小周期也许不是N，但是N一定是WNn的周期。吟的性质很明显:周期性:Wkn=W(k-N)n=Wk(n-N)周期性:一个周期为N的周期序列X(n)，在n=-3到n=+s的范围内仅有N个序列值是独立的其中一个周期内的N个序列值足以表征整个序列的特征。而对于长度为N的有限长序列，

只讨论n=0到N-1之间的N个序列值，其余皆为0。此二者在n=0到N-1单位内具有共同性。对于周期为n的周期序列x(n)，定义n=0到N-1为主值区间，由主值区间N个序列值组成的有限长序列x(n)，称为Mn)的主值序列。可以如下表示：x(n)=x(n)R(n)(2-2)NRn(n)为矩形序列，即：/\1(0<n<N)

Rn=[o(其他n)上一过程称为取主值序列，有限长序列x(n)：/)fx(n)(<n<N-1)&=[o其他n)如果以N为周期进行延拓，则有：x(n)=方x(n+rN)(2-3)r=一8式2-2和2-3之间表明了周期序列和有限长序列之间的处理关系。即：周期序列可以去主值序列进行分析，然后对再周期延拓得到最后的处理结果。周期延拓的时候，延拓周期和有限长序列的长度不同的时候，序列可能会发生混叠。若x(n)为M长的有限长序列，即：/\fx(n)0<n<M-1)&="(其他〃)(2-5)以N为周期进行延拓，得到周期序列:x]n(n)=¥x(n+rN)r=一8再取xN^n)的主值序列:(n)(n)=xNn)Rn(n)(2-7)关于使(2-5)和(2-7)是否一致的问题:⑴当N>=M时，xCz)和x()是一致的，所以，周期延拓无混叠失真，主值序列和原序列一致相同。当M/2<=N<=M时，此时会使得至少xN(0)不仅含有x(0),还叠加有x(N)。说明Xn(0)和x(0)是不一致的。因此，在M/2<=N<=M时会出现部分混叠失真，以下结论：/)岸x(n)0<n<M-N-1)XN-]=x(n)M-N<n<N-1)当N<=M/2时，x(n)对x(n)是全混叠失真。N所以，在数字信号处理中通常取N=M，以避免错误或者进一步的处理。周期序列不满足收敛条件，不能进行Z变换和Fourier变换分析。离散傅里叶级数(DFS)连续的周期函数和离散的周期函数都可用傅里叶级数表示，所以不论连续周期函数还是离散周期函数都可用傅里叶级数表示。经过推倒，周期为N的周期序列XNO的傅里叶级数与周期为N的复指数序列吗〃密切相关。、(n)有n个独立值，其离散傅里叶级数也只有N个独立分量。一个周期为N的周期序列以(n)的傅里叶级数的分析与综合对(正变换和反变换)可表示为：(2-9)X(k)=祝X(n^kn=DFSX(n(2-9)n=0-(2-10)x(nT习又(kh=idfsx(k)(2-10)k=0-上两个式子是周期序列离散谱分析的数学方法，显然，离散傅里叶级数乂(k)在频域上是一个周期为N的周期序列。由于X(k)、XO以及Wkn均是以n为周期的。因此，式中的n和k的值可以随机确定，只要取足N点即可。可表示为：X(k)=宓-1x(n'>WknNn=n0和x(n)=—k0光1X(k)W-knNNk=k0离散傅里叶级数(DFS)的性质1.线性：DFSaX(n)+b§(n)=aX(k)+bY(k)，其中a、b为任意常数。移位特性：DFSX(n+m)1=WNmkX(k)和IDFSIX(k+1)l=Wnix(n)周期卷积：若F(k)=X(k)•Y(k)，则有，f(n)=IDFSF(k)=云X(m)•项(n-m)m=0=习y(m)•X(n-m)m=0周期序列的卷积也可用下式表示：f(n)=m%”1X(m)•y(n-m)(2-18)m=m0式(2-18)说明对X(m)只要取够一个周期的卷积即可，周期卷积与m的起点无关，而且周期序卷积的结果仍是一个周期序列。离散傅里叶变换(DFT)有限长序列/\[X(n)0<n<M-1)&=[。虹他n)的离散傅里叶变换对定义为：TOC\o"1-5"\h\zX(k)=DFT氐)]=FX(n如"<=)0(其他k)和f1K1/\/、/\r/\-i1%X(kW-kn(0<=n<=N-1)X(n)=IDFTX(k』=」Nn0(其他n)上述两式均为非病态线性方程组，有唯一解。因此，长度为N的有限长序列X(n)的离散傅里叶变换X(k)仍然是一个N长的频域有限长序列，X(n)和X(k)由唯一对应的关系。把一个有限长序列xJ)看成是周期序列X(n)的主值序列，就能利用周期序列的性质。X(n)的相应的周期序列的离散傅里叶级数为X(k)，它的主值序列即为X()=DFTL(n)]，

即存在:x(n)=出)R(n)=IDFSNX(k)气(n)\~「X(k)=X(k)RN(k即存在:x(n)=出)R(n)=IDFSNX(k)气(n)可见，离散傅里叶变换和离散傅里叶级数有着固有的内在的联系，理论上是成立的。同时长度为N的有限长序列x(n)可通过补0成为长度为M的有限长序列Xm(n)，亦即:，x(n)6<=n<=N-1)x^(n)=<0(N<=n<=M-1,补0)一般认为，x(n)补零并没有改变序列的本质，实际应用中也常常如此处理，但是乂(k)的变换很大，此时的傅里叶变换应该为X(k)：MX(k)=如x(n'^knMMn=0而X(k)彦x(nWknNn=0按照Wkn的定义，显然Wkn和WMn是不相同的。因此，一个有限长序列可以进行大于其序列的任意长度的任意点数的离散傅里叶变换，具体的点数可根据实际需要进行选定，但是由于频率点的变化，离散傅里叶变换的结果一般是不相同的。综上所述，x(n)的离散傅里叶变换与变换长度N的取值有关。离散傅里叶变换(DFT)的性质假设：x(n)与y(n)均为N点长的有限长序列，并有：X(K)=DFT(x(n))Y(k)=DFT(y(n))1.线性性质：DFT\ax(n)+b(y(n))]=aX(k)+bY(k"、b为常数)2.圆周移位：一个有限长序列x(n)向左移动m位的圆周移位定义如下，f(n)=x((n+m))R(n)序列圆周移位m位以后的DFT如下，F（k）=DFT（f（n^）=W-kmX（k）

'N3.卷积特性：若有F（k）=X（k）^（k）,则f（n）=IDFT（F（k^）=IDFT\x（k）Y（k^=IDFSR（n）N=£x（（m））-y（G-m））-R（n）NNNm=0—£x（m）--m））•R（n）（2-30）NNm=0式（2-30）的卷积形式与上节的周期卷积过程相似，仅是最后取主值序列。Jm）限定在m=0到N-1之间，但y（n-m）是要圆周移位的，所以称为圆周卷积，式2-30可以写成：f（n）=y（n）®x（n）或者/G）=x（n）®y（n）同理，频域的圆周卷积形式为：DFrL;G）yG）］=—Sx（/）r（Cl-/））R（k）=X（k）®Y（k）

NNN1=0DFtDcG）jG）］=—2yG）x（G-/））R（k）=Y（k）®X（k）

NNN1=05.帕赛瓦尔定理：利用上述特性，可以证明：^x（n）y（n）=l-^X（k¥（k）n=0k=0当y（n）=x（n）^i，则有:（2-36）n=0k=0式（2-36）的意义是：有限序列的能量=有限频谱的能量。有限长序列的线性卷积和圆周卷积有限长序列有两种卷积形式：线性卷积和圆周卷积，圆周卷积与DFT相对应，可以采用快速傅里叶变换算法(FFT)进行运算，求解速度极快。但实际问题中往往是解决线性卷积问题，例如信号通过线性系统，系统的输出信号yd)是输入信号尤J)与单位取样响应h(n)的线性卷积：fG)=x(n)*h(n)，接下来用圆周卷积来实现线性卷积，设x(n)是长度为M点的有限长序列，y(n)是N点的有限长序列，则线性卷积:f(n)=x(n)*y(n)是一个长度为L1=N+M-1点的有限长序列，现将x(n^y(n)均补0增长为L点的有限长序列，其中：L>maxM,N｝，然后进行L点的圆周卷积：f(n)=x(n)®y(n)c=如x(m)y((n-m))-R(n)m=0通过公式可以证明f(n)和fO的关系，通过计算得:cf(n)=Ef(n+rL).R(N)cLr=-s由上面的式子可以看出，f(n)是f(n)以L为周期，进行周期延拓后在0到L-1的范围c内所取得的主值序列，如果L>=L1，则有，f(n)=f(n)c上式表明，要使圆周卷积等于线性卷积而不产生混叠失真的充要条件是：L>=M+N+1若L<L1<2L，则在n=0到L1-L—1范围内出现匕-L个点的混叠失真，如下：()传f(n)0<n<L-L-1)fc:\=f(n)(L-L<n<L-1)iJi若随意选择L，当L>2L时，圆周卷积和线性卷积的结果就会完全不一致，将产生全混叠失真。DFT、DTFT和Z变换如果一个有限长序列的x(n)，满足收敛条件时，则有，X(Z)=^-1x(n)Z-n(2-40)n=0

XCj®)=云x(n)e-j®n(2-41)n=0DFTDFT相应的形式为:X(k)=云x(n^)Wkn(2-42)N

n=0A上式中的Wkn=e)N。N式(2-40)是有限长序列x(n)的Z变换，是在Z平面内对x(n)的一些特性进行分析时的工具。当Z取单位圆的时候，亦即z=ej®，则变为是(2-41)，成为x(n)的频域特性分亦即(2-42)式，它们之间的关系可以如下表示：(、X(k)=X(Z】=X1加)析，其中的3不是一个固定值，而是一个参变量，可以连续取值。为了便于计算机进行处理，亦即(2-42)式，它们之间的关系可以如下表示：(、X(k)=X(Z】=X1加)(2-43)TOC\o"1-5"\h\z一，2^,Z=W一o=kNN式(2-43)说明N点的有限长序列x(n)的离散傅里叶变换X(k)是它的Z变换在单位圆上N个等分点上(Z,=Wnk，k=0,1,2,3,...,N-1)的采样值，也是它的傅里叶变换X0<=3<=2兀区间N个等分点上虹=k(2k/N)k=0,1,...,N-1)的采样，这种关系意味着对于时间有限信号，可以像带限信号进行时域采集而不丢失任何信息一样，可以在频域上进行采样而不丢失任何信息，此正为傅里叶变换中时域和频域对偶关系的反映，有着十分重要的意义。DFT实现了频域的离散化，开辟了频域领域采用数字技术进行处理的领域。频率采样理论采用DFT后实现了频域的采样，同样可以采用频域采样的方法逼近任意一个频率特性，接下来，分析一下频率采样的可行性以及所带来的误差。一个任意序列x(n)，满足收敛条件，它的Z变换为：X(Z)=Ex(n)Z-nn=一8对X(Z)在单位圆上N个等分点上进行采样，有：X]v()=X(Z】=Ex(nW,，"n'n=-s对XN(k)进行IDFT，得到长度为N点的有限长序列XN。)，即：XN(n)=IDFTX(k))通过对上式进行运算，得到XN(n)与x(n)的关系如下所示：x(n)=切x(n+rN)-R(n)r=-s可见，Xn(n)是x(n)以N为周期进行周期延拓后所取的主值序列。和时域采样会造成频域周期延拓一样，频域采样同样会造成时域的周期延拓。如果x(n)是有限长序列，序列的长度为M，即：/\(x^i)^<=n<=M-1)&F他n)若N<M，则如先前所讨论的一样，会由于频率采样间隔过大，使得在一定的频率范围内的采样点不够多而造成x(n)在周期延拓时某些序列的序列的样本交叠在一起，产生混叠现象，因此，频域采样不失真条件为N>=M，即:x(n)=工x(n+rN)-R(n)=x(n)N>=M)r=-s这就是频域采样定理，此时XN(k)即为x(n)的N点离散傅里叶变换X(k)。当x(n)为无限长序列时，Xn(n)必然会产生存在混叠失真，只能随着采样点数N的增加，而逐渐逼近于x(n)。对于有限长序列x(n)，在满足频域采样定理的前提下，N点频域采样X(k)就足以不失真地代表序列的特性。因此，由N点采样值X(k)能够完全地表达整个X(Z)函数及频域特性XS。快速傅里叶变换(FFT)快速傅里叶变换(FFTFastFourierTransform)是快速计算DFT的有效算法。离散傅里叶变换实现了频域的离散化，在数字信号处理中有着重要的作用，包括分析信号的频谱、计算滤波器频域响应以及实现信号通过线性系统的卷积运算。DFT的运算特点一个有限长度为N的有限长序列x(n)的离散傅里叶变换为：X(k)=云x(n)•Wkn(0<k<N-1)Nn=0一般说来x(n)和W^n都是复数，按照一般定义来计算，计算一点X(k)值需要N次复数相乘运算，(N-1)次的复数相加运算。计算全部N点X(k)则需要N2次复数相乘运算和

N(N-1)次的复数相加运算。由于一个复数运算包含4个实数相乘和两个实数加法，所以，计算全部的X(k)需要4N2实数相乘运算和2N(N-1)次复数相加运算。由于DFT的运算量和N2成正比，所以将长序列的DFT分解成短序列的DFT计算，可是运算量得到明显的减少。快速傅里叶变换正是利用吗〃的特性，逐步将N点序列分解为较短的序列，计算短序列的DFT，然后再组合成原序列的DFT，使得运算量显著减少。FFT算法分为两类：时间抽取法和频域抽取法。时间抽取基-2FFT算法设序列长度N为2的整数幂次方(实际应用中常常如此选取)：N=2m，其中M为正整数，x(n)分为两组，偶数项为一组和奇数项为一组得到两个N/2点的子序列，即：x(r)=x(2r)1x(r)=x(2r+12相应的DFT运算也可以分成两组:X(k)=顼)•WknN

n=0TOC\o"1-5"\h\zN-1n-1r=0=乏x(2r)W2kr+Zx(2r+1)・W(2r+1)kr=0Nni=Ex(r).Wkr+WkEx(r).Wkr1N/2N2N/2r=0r=0=X(k))+WkX&))」R(k)(2-54)1N/2N2N/2Nr=0假定X(k)、X(k)分别是x(r)和x(r)的DFT，亦即:NX(k)=另x(rWkrr=0N-1X(k)=支x(r^krrke1。，N-1[]22N/2r=0<L2」7上两式的取值范围为0,N-1，式2-54的取值范围为hN-1］。由式子2-54可知，2

x&))、x&))分别为为主值序列的周期序列因此x(k)、x(k)应该周期性的重TOC\o"1-5"\h\z1N/22N/212复一次，所以式子2-54可以写成下面的形式：x()=x1()+WkX2(k)\o"CurrentDocument"Xfk+N)=x()—Wkx(/k=0,1,...,N-1\(2-57)"2)1N2"2),N-式中出现的负号是由于Wk+2=—Wk。NN式2-57的运算关系可用信号流图表示成蝶形运算的形式，左两路为输入，中间一个小圆点表示加减运算，右上支路为相加后的输出，右下支路为相减后的输出，箭头旁边的系数表示相乘的数。因流图形如蝴蝶，故称为蝶形运算。每个蝶形运算需要一次复数相乘，两次复数加法运算，如下图所示，还有8点DFT分解运算过程，为•入,席以伙、..蜘加澈:项-Hi)NilDF7—•柚)—•MS)—•.116)—<117)♦枷)♦♦X[2),H3|tottmUKMimAXMl化IB中)―址)DFT分解的旗帽(N・8)嵩;#篇忠夕也可以估算廉法运算虬每q-Hi)NilDF7—•柚)—•MS)—•.116)—<117)♦枷)♦♦X[2),H3|tottmUKMimAXMl化IB中)―址)DFT分解的旗帽(N・8)嵩;#篇忠夕也可以估算廉法运算虬每q1抽)一—™~山(|)M2)接下来估算一下乘法的运算量，每一个N/2点的DFT需要N2/4次复数相乘，两个N/2点DFT共需要N2/2次复数相乘，组合运算共需N/2个蝶形运算，需要N/2次复数相乘，因而共需要(N2/2)+(N/2)次复数相乘，N比较大时，可以近似认为等于N2/2，与直接计算相比节约一半的运算量。而共需要由于N/2=2m—1，如果大于2,可继续进行N/2点序列分解成两个N/4点的序列。如将气()分解为:%(l)=气(2l),(l)=气(2l+1i=0,1,...,n—1有:X](k)=X]](k)+Wk/2X12(k)X[k+史=X(k)-WkX(k)'k=0,1,...,N-1'1"4；11N/212<4J其中，气](k)=DFTk](l)],x12(k)=DFT{x2(l)L它们均为N/4点的DFT。这样序列长度又减为一半，对应于8点的前一个N/2点的DFT再分解为两个N/4点DFT流图。当然，%(r)也是如此，直到最后的两点的DFT为止。2点的DFT同样可用一个蝶形运算表示。例如，8点的第一个2点DFT由x(0)和X。)组成，就可以表示为：X11(0)=x(0)+W20-x(4)X11G)