快速傅里叶变换(FFT)【精品ppt】 .ppt

第4章快速傅里叶变换(fft),4.1引言4.2基2fft算法4.3进一步减少运算量的措施4.4分裂基fft算法4.5离散哈特莱变换(dht),4.1引言,dft是信号分析与处理中的一种重要变换。因直接计算dft的计算量与变换区间长度n的平方成正比，当n较大时，计算量太大，所以在快速傅里叶变换(简称fft)出现以前，直接用dft算法进行谱分析和信号的实时处理是不切实际的。直到1965年发现了dft的一种快速算法以后，情况才发生了根本的变化。,4.2基2fft算法,4.2.1直接计算dft的特点及减少运算量的基本途径长度为n的有限长序列x(n)的dft为考虑x(n)为复数序列的一般情况，对某一个k值，直接按(4.2.1)式计算x(k)值需要n次复数乘法、(n-1)次复数加法。,(4.2.1),如前所述，n点dft的复乘次数等于n2。显然，把n点dft分解为几个较短的dft，可使乘法次数大大减少。另外，旋转因子wmn具有明显的周期性和对称性。其周期性表现为,(4.2.2),其对称性表现为,或者,4.2.2时域抽取法基2fft基本原理fft算法基本上分为两大类：时域抽取法fft(decimationintimefft,简称dit-fft)和频域抽取法fft(decimationinfrequencyfft,简称diffft)。下面先介绍diffft算法。设序列x(n)的长度为n，且满足,为自然数,按n的奇偶把x(n)分解为两个n/2点的子序列,则x(n)的dft为,由于,所以,其中x1(k)和x2(k)分别为x1(r)和x2(r)的n/2点dft，即,(4.2.5),(4.2.6),由于x1(k)和x2(k)均以n/2为周期，且，所以x(k)又可表示为,(4.2.7),(4.2.8),图4.2.1蝶形运算符号,图4.2.2n点dft的一次时域抽取分解图(n=8),与第一次分解相同，将x1(r)按奇偶分解成两个n/4长的子序列x3(l)和x4(l)，即,那么，x1(k)又可表示为,(4.2.9),式中,同理，由x3(k)和x4(k)的周期性和wmn/2的对称性wk+n/4n/2=-wkn/2最后得到：,(4.2.10),用同样的方法可计算出,(4.2.11),其中,图4.2.3n点dft的第二次时域抽取分解图(n=8),图4.2.4n点ditfft运算流图(n=8),4.2.3ditfft算法与直接计算dft运算量的比较每一级运算都需要n/2次复数乘和n次复数加(每个蝶形需要两次复数加法)。所以，m级运算总共需要的复数乘次数为,复数加次数为,例如，n=210=1024时,图4.2.5fft算法与直接计算dft所需乘法次数的比较曲线,4.2.4ditfft的运算规律及编程思想1.原位计算由图4.2.4可以看出，ditfft的运算过程很有规律。n=2m点的fft共进行m级运算，每级由n/2个蝶形运算组成。2.旋转因子的变化规律如上所述，n点ditfft运算流图中，每级都有n/2个蝶形。每个蝶形都要乘以因子wpn，称其为旋转因子，p称为旋转因子的指数。,观察图4.2.4不难发现，第l级共有2l-1个不同的旋转因子。n=23=8时的各级旋转因子表示如下：l=1时，wpn=wjn/4=wj2l，j=0l=2时，wpn=wjn/2=wj2l，j=0，1l=3时，wpn=wjn=wj2l，j=0，1，2，3对n=2m的一般情况，第l级的旋转因子为,(4.2.12),(4.2.13),3.蝶形运算规律设序列x(n)经时域抽选(倒序)后，存入数组x中。如果蝶形运算的两个输入数据相距b个点，应用原位计算，则蝶形运算可表示成如下形式：x(j)xl-1(j)+xl-1(j+b)wpnxl(j+b)xl-1(j)-xl-1(j+b)wpn式中p=j2m-l；j=0,1,，2l-1-1；l=1,2,，m,下标l表示第l级运算，xl(j)则表示第l级运算后数组元素x(j)的值。如果要用实数运算完成上述蝶形运算，可按下面的算法进行。设t=xl-1(j+b)wpn=tr+jtixl-1(j)=xr(j)+jxi(j)式中下标r表示取实部，i表示取虚部，,则,4.编程思想及程序框图,图4.2.6ditfft运算和程序框图,5.序列的倒序ditfft算法的输入序列的排序看起来似乎很乱，但仔细分析就会发现这种倒序是很有规律的。由于n=2m，所以顺序数可用m位二进制数(nm-1nm-2n1n0)表示。,图4.2.7形成倒序的树状图(n=23),表4.2.1顺序和倒序二进制数对照表,图4.2.8倒序规律,图4.2.9倒序程序框图,4.2.5频域抽取法fft(diffft)在基2快速算法中，频域抽取法fft也是一种常用的快速算法，简称diffft。设序列x(n)长度为n=2m，首先将x(n)前后对半分开，得到两个子序列，其dft可表示为如下形式：,偶数,奇数,将x(k)分解成偶数组与奇数组，当k取偶数(k=2r,r=0,1,n/2-1)时,(4.2.14),当k取奇数(k=2r+1,r=0,1,n/2-1)时,(4.2.15),将x1(n)和x2(n)分别代入(4.2.14)和(4.2.15)式，可得,(4.2.16),图4.2.10diffft蝶形运算流图符号,图4.2.11diffft一次分解运算流图(n=8),图4.2.12diffft二次分解运算流图(n=8),图4.2.13diffft运算流图(n=8),图4.2.14ditfft的一种变形运算流图,图4.2.15ditfft的一种变形运算流图,4.2.6idft的高效算法上述fft算法流图也可以用于离散傅里叶逆变换(inversediscretefouriertransform，简称idft)。比较dft和idft的运算公式：,图4.2.16ditifft运算流图,图4.2.17ditifft运算流图(防止溢出),如果希望直接调用fft子程序计算ifft，则可用下面的方法：由于,对上式两边同时取共轭，得,4.3进一步减少运算量的措施,4.3.1多类蝶形单元运算由ditfft运算流图已得出结论，n=2m点fft共需要mn/2次复数乘法。由(4.2.12)式，当l=1时，只有一种旋转因子w0n=1，所以，第一级不需要乘法运算。,综上所述，先除去第一、二两级后，所需复数乘法次数应是从l=3至l=m共减少复数乘法次数为,(4.3.1),(4.3.2),因此，ditfft的复乘次数降至,(4.3.3),从实数运算考虑，计算n=2m点ditfft所需实数乘法次数为,(4.3.4),4.3.2旋转因子的生成在fft运算中，旋转因子wmn=cos(2m/n)-jsin(2m/n)，求正弦和余弦函数值的计算量是很大的。,4.3.3实序列的fft算法设x(n)为n点实序列，取x(n)的偶数点和奇数点分别作为新构造序列y(n)的实部和虚部，即,对y(n)进行n/2点fft，输出y(k)，则,根据ditfft的思想及式(4.2.7)和(4.2.8)，可得到,由于x(n)为实序列，所以x(k)具有共轭对称性，x(k)的另外n/2点的值为,4.4分裂基fft算法,4.4.1分裂基fft算法原理当n=pq，且p=n/4，q=4时，n可表示为,并有,再将上式中的k表示为,可得,对k0=0，1,2,3,并用k表示k1，用n表示n0，可以写出,(4.4.1),(4.4.2),(4.4.3),令,则(4.4.2)式可写成如下更简明的形式：,(4.4.4),图4.4.1分裂基第一次分解l形流图,例如，n=16，第一次抽选分解时，由式(4.4.3)得x2(n)=x(n)+x(n+8),0n7x14(n)=x(n)-x(n+8)-jx(n+4)-x(n+12)wn16,0n3x24(n)=x(n)-x(n+8)+jx(n+4)-x(n+12)w3n16,0n3把上式代入式(4.4.4)，可得x(2k)=dftx2(n),0k7x(4k+1)=dftx14(n),0k3x(4k+3)=dftx24(n),0k3,图4.4.2分裂基fft算法l形排列示意图与结构示意图(a)分裂基fft算法l形排列示意图；(b)分裂基fft算法运算流图结构示意图,图4.4.316点分裂基第一次分解l形流图(图中省去箭头),第二次分解：先对图4.4.3中n/2点dft进行分解。令x1(l)=x(2l)，则有x1(2l)=dfty2(n),0l3x1(4l+1)=dfty14(n),0l1x1(4l+3)=dfty24(n),0l1,其中y2(n)=x2(n)+x2(n+4),0n3y14(n)=x2(n)-x2(n+4)-x2(n+2)x(n+6)wn8,n=0,1y24(n)=x2(n)-x2(n+4)+jx2(n+2)x2(n+6)w3n8,n=0,1,图4.4.4图4.4.4中n/2点dft的分解l形流图,图4.4.54点分裂基l形运算流图,图4.4.616点分裂基fft运算流图,4.4.2分裂基fft算法的运算量设第j级有lj个l形，j=1,2,m-1,m=log2n，则有l1=n/4。由图4.4.2(b)可见，第j-1列中的l形包含了第j列中的一部分结点的计算，即空白部分，所占结点数刚好等于第j-1列中所有l形对应结点的一半，所以第j列l形个数就减少lj-1/2个，即,由于每个l形有两次复(数)乘运算，所以全部复乘次数为,(4.4.5),4.5离散哈特莱变换(dht),4.5.1离散哈特莱变换定义设x(n),n=0,1,n-1，为一实序列，其dht定义为,式中，cas()=cos+sin。其逆变换(idht)为,(4.5.3),逆变换证明如下：,(4.5.4),将式(4.5.2)代入式(4.5.3)得,4.5.2dht与dft之间的关系为了便于比较，重写dft如下：,(4.5.5),(4.5.6),容易看出，dht的核函数dft的核函数的实部与虚部之和。,将xh(k)分解为奇对称分量xho(k)与偶对称分量xhe(k)之和,(4.5.7),(4.5.8),(4.5.9),由dht定义有,(4.5.10a),(4.5.10b),所以，x(n)的dft可表示为同理，x(n)的dht可表示为因此，已知x(n)的dht，则dft可用下式求得：,(4.5.11),(4.5.12),(4.5.13),4.5.3dht的主要优点(1)dht是实值变换，在对实信号或实数据进行谱分析时避免了复数运算，从而提高了运算效率，相应的硬件也更简单、更经济；(2)dht的正、反变换(除因子1/n外)具有相同的形式，因而，实现dht的硬件或软件既能进行dht，也能进行idht；(3)dht与dft间的关系简单，容易实现两种谱之间的相互转换。,4.5.4dht的性质1.线性性质,(4.5.14),2.x(n-n)的dht,(4.5.15),其中，当k=0时，xh(n-k)=xh(n)=xh(0)。,证明由dht定义,而,3.循环移位性质,(4.5.16),(4.5.17),证明由dht定义有,4.奇偶性奇对称序列和偶对称序列的dht仍然是奇对称序列或偶对称序列，即dht不改变序列的奇偶性。5.循环卷积定理,(4.5.18),(4.5.19),证明下面利用dft的循环卷积定理和dht与dft之间的关系来证明其中，x1(k)=dftx1(n),x2(k)=dftx2(n),根据dht与dft之间的关系，则有,将上面两式代入式(4.5.20)并整理后，得,所以式(4.5.18)成立。同理可证明式(4.5.19)亦成立。当x1(n)或x2(n)是偶对称序列时，则由dht的奇偶性有,(4.5.21),4.5.5dht的快速算法(fht)1.基2ditfht算法及运算流图仿照快速dft的分解方法，可通过时域抽取或频域抽取的方式实现快速dht。x(n)的n=2m点dht如下式：,对x(n)进行奇偶抽取,(4.5.22),(4.5.23),与dft的时域抽取分解比较，不是一个指数函数，所以处理要比w(2r+1)kn麻烦一些。根据三角公式有,(4.5.24),(4.5.25),令x0h(k)=dhtx0(n),x1h(k)=dhtx1(n)，并考虑dht的周期性，(4.5.25)式可写成,为了使以下推导中公式简明，记c(k)=cos(2/n)k，s(k)=sin(2/n)/k。将式(4.5.26)中的k分别取k，n/2+k,n/2-k和n-k四个值，并考虑x0h(k)和x1h(k)以n/2为周期，得到,(4.5.27),当k=0时，式(4.5.27)中有重复，可单独写成,(4.5.28),同理，在k=n/4时有,(4.5.29),图4.5.1基2dit-fht原理和哈特莱碟形,图4.5.24点dfht蝶形图,图4.5.316点基2ditfht流图,2.基