DFT和FFT

1第六章DFT和FFT2§1引言（数字信号的傅立叶分析）将信号展开成傅立叶级数（周期函数），从频谱的角度看，表现出了过去没有注意到的信号的各种特征。实际中如何进行？（一种是理论计算，一般较难）利用频谱分析仪（电路硬件）其由多个带通滤波器构成。每个滤波器只让单一的频率信号通过，再经整流即得到该频率信号的幅度。将各个频率及其幅度排列起来，即得到深入信号的频谱，见下图。3该频率的输出信号幅度带通4计算机技术的发展，提供了新手段。信号调理采样、A/D计算机数字计算平滑处理、相关处理、进行各种变换（包括傅立叶变换）、频谱观察等如何进行数字信号的傅立叶分析？传感器5§2周期序列的离散傅立叶级数展开前已讲过，周期为2π的函数f(t)的傅立叶级数展开式为2π0jktππjktkkjktkdtf(t)e2π1dtf(t)e2π1CeCf(t)用等间隔对f(t)采样的N个信号，构成一个序列。如下图表示1N210f,,f,f,f(6.1)(6.2)6…f0f1f2fN-10△t2△t(N-1)△tN△t1N210f,,f,f,f采样序列f(n)tf(t)f(t)描述f(0),f(△t)1N...,2,1,0,nfn,7设此数字信号的采样间隔为△t，N△t是此信号的基本周期，可将此信号看成是周期为N△t的周期函数，将其展开成傅立叶级数。我们已学过，周期为2π的函数f(t)的复傅立叶系数Ck可以由函数f(t)与ejkt的内积给出Ck=〈f(t),ejkt〉需要定义与函数f(t)傅立叶系数相当的系数。现在，以采样序列1N210f,,f,f,ff(n)f(t)描述8此系数定义为N维向量f(n)的傅立叶系数。为求出此傅立叶系数，需要给出相当于复函数ejkt的N维向量（记为ek(N)），再取这个向量与f(n)的内积，从而得到对应于离散数据的傅立叶系数。Ck=〈f(n),ek(N)〉那么，ek(N)究竟是一个什么样的向量呢？从定义可推出，其就是复函数ejkt以2π/N(记为△ω)为间隔采样而得到的复序列构成的N维向量，如图示。fn(N)与ek(N)都为N维向量9采样复函数ej3t而得到的复序列构成的8维向量e3(8)例如，若N=8,k=3,则e3(8)=｛ej3n△ω(n=0,1,2,…7)｝=｛1，ej3△ω,ej6△ω,ej9△ω,ej12△ω,ej15△ω,ej18△ω,ej21△ω｝ej3t10kNjkjkjjkkeeeee)1(32,,,,,1实际上，ek(k=0,1,2,···，N-1)构成的向量集合｛e0,e1,e2,···,eN-1｝在N维向量空间构成标准正交基底。因此，向量f(n)可在该标准正交底上展开为)(10NeCNkkkfnejktmnniNjNimiNjnmeeNee)/2(10)/2(1,要确定向量序列｛e0,e1,e2,···,eN-1｝构成标准正交基底，只要计算下式的内积(6.3)11即10)/2(1NnknNjnkefNC称之为信号数值序列f(n)=｛f0,f1,f2,···fN-1｝的离散傅立叶变换*（DiscreteFourierTransform，记之DFT）相应地式称为离散傅立叶反变换(InverseDFT)。10)/2(NkknNjkneCf(k=0,1,2,···，N-1)(n=0,1,2,···，N-1)其系数Ck可表示为f(n)和ek的内积。Ck=〈f(n),ek〉(6.4)(6.6)(6.5)1210)/2(1NnknNjnkefNC10)/2(NkknNjkneCf关于*的说明：严格地说，是周期数字序列f(n)的傅立叶级数展开式。而则是该傅立叶级数展开式的系数。就是周期数字序列f(n)的频谱。13实际应用中，都是通过数据采集系统，得到物理量的一个数据序列，而利用计算机进行傅立叶分析时总是将该数据序列作为一个周期，因此可看成周期数据序列，都可应用上述公式。比较上述DFT和IDFT的表达式，两者不同仅在于前面有无系数1/N及e的指数部分的符号的正与负，其余部分的形式都相同。因此，DFT和IDFT都可以用相同的计算机程序来处理。14即进行DFT时信号值序列是输入数据，进行IDFT时傅立叶系数是输入数据，对应于DFT或IDFT主要改变e的指数符号和计算结果用数据N除或不除即可。10)/2(NkknNjkneCf10)/2(1NnknNjnkefNC输入数据输入数据DFTIDFT15§3傅立叶级数展开式的性质离散周期序列展开式的系数具有与连续周期信号复指数展开式系数相似的性质。性质1若f(n)为周期序列，且周期为N,则Ck也是周期的。且周期为N,Ck±lN=Ck(l为整数)频谱的周期性证明：10))(/2(1NnnlNkNjnlNkefNCnljNnknNjneefN210)/2(1(6.7)16换句话说，由N个数据得到的有效傅立叶系数是C0,C1,C2,…CN-1，其它的系数是这些系数周期性地重复。例如：CN=C0，CN-1=C-1，CN+1=C1等。展开式系数Ck和复指数序列ejkn2π/N均以N为周期，它导致一个重要的概念：“离散周期序列只含有有限项(N项)分量”。因为l,n是整数e±j2lπn从而得Ck+N=Ck傅立叶系数的频谱是周期性的，其周期为N意味着17性质2若f(n)为实数序列，则Ck具有共轭对称性，即C-k=Ck*此式意义在于其振幅频率是对称的。即对于傅立叶变换振幅频率以k=N/2为中心左右对称频谱的对称性性质3Ck的模为k的偶函数，Ck的相位（幅角）为k的奇函数。(6.8)18§4快速傅立叶变换（FFT）DFT是使用计算机进行信号分析时无论如何必须掌握的重要技术。如果不能掌握DFT理论，就不能很好地理解傅立叶频谱的计算结果。但实际中除了为达到特殊要求外，人们在信号处理时都不使用DFT算法进行傅立叶分析。其原因：计算时间长，不实用。比如：用计算机采集系统对所采集的1024个数据进行DFT处理，大约需要进行100万次乘法和加法运算。因此，研究DFT变换的特性，利用三角函数周期性计算技巧，减少运算次数，得出快速的算法是必要的。19FFT的基本思想一般而言，一个计算公式定义的运算关系，如果没有某方面的特殊性，无论按照什么途径进行计算，其计算量不会相差甚远。而DFT定义式中的e–j(2π/N)kn具有一些特殊性质，利用这些性质可以将一个周期为N的DFT计算分解为两个周期为N/2的DFT计算。由于按照定义式计算DFT时，运算量约与N2成正比。因此，变成周期N/2的DFT计算后，当N较大时，运算量会大幅降低。更进一步，周期N/2的DFT计算又可以化为两个周期N/4的DFT计算，N/4点的DFT计算又可化为两个周期N/8的DFT计算…直至最后分为周期为2的DFT计算，这就是FFT提高算法效率的基本思想。201DFT的分析记复数w=e–j(2π/N)设取数据序列f(n)=｛f0,f1,f2,…fN-1｝，进行DFT变换（处理），其傅立叶系数1N0nnknkfwN1C假定N=8,有傅立叶系数)fwfwfwf(w81C77k22k11k00kk后面研究中将忽略1/8，Ck可理解为NCk21于是可有矩阵形式表达的傅立叶系数7654321049423528211470423630241812603530252015105028242016128402118151296301412108642076543210000000007654310ffffffff(6.9)22为进行矩阵计算，必须进行8×8=64次乘法运算和7×8=56次加法运算。对N个数据的序列的DFT计算，必须进行N2次乘法运算和N×(N-1)次加法运算。考察上式w矩阵中w的幂中包含的规律w8=w0w9=w1w10=w2w11=w3...任何幂超过8的元素，都与从w0到w7的某一个元素相等。23可表示为wn=wnmod8求余运算ImRe821-1w22w14w6j-jw=e–j(2π/8)w2w10w18w20w12w4w0w8w16w21w13w5w1w9w17w3w11w19w23w15w7同一点的w的指数相差824因此矩阵形式表达的傅立叶系数7654321049423528211470423630241812603530252015105028242016128402118151296301412108642076543210000000007654310ffffffff(6.9)25可变为7654321012345670246024603614725040404040527416306420642076543210000000007654310ffffffff(6.10)26仔细观察该矩阵，有何规律?如何利用这些规律得到高效的计算方法?FFT就是包含在表达式DFT的矩阵中的某些规律的巧妙地应用，高效地进行计算的一种方法。其原则是将矩阵中的元素巧妙地排列替换，以减少乘法运算的次数。因为乘法运算比加减法运算花掉的时间多，若能将全部计算中乘法计算的次数减少，则可有效地缩短计算时间。FFT减少了多少乘法运算呢？先看2四个数据的FFT算法27在信号数字序列为4个数据时，设输入信号（变换的输入）为｛f0,f1,f2,f3｝其DFT可表示为321096306420321000003210ffff(6.11))fwfwfwf(w4Ck22k11k00kk33k=0,1,2,328即有（将w的幂转换为数值）32103210111111111111ffffjjjjCCCC下面将对此矩阵的元素进行频繁地替换，但采用通常的矩阵表示方法不易看出元素的替换关系。因此这里特殊地定义一种矩阵表示方法。(6.12)w0=1w1=e-j(2π/4)=-jw2=e-2j(2π/4)=-1w3=e-3j(2π/4)=j29392613003624120033221100302010003210fcwfdwfdwfdwfcwfcwfcwfcwfbwfbwfbwfbwfawfawfawfawCCCC963064203210000032103210ffff等价于只用于本课定义(6.13)