第3章_FFT

3.1引言：1.DFT运算量的估计设x(n)为复序列，则计算每一X(k)需1010)(1)()()(NknkNNnnkNWkXNnxWnxkXN次复乘（N-1）次复加完成一次DFT计算需（k=0,1,2••••••N-1）若用实数乘法统计：复乘运算：(a+jb)(c+jd)=(ac-bd)+j(ad+bc)=[(a-b)d+a(c-d)]+j[(a-b)d+b(c+d)]完成一次DFT计算运算量为：2.提高DFT运算效率途径利用的性质：周期性、可约性、共轭对称性把长序列化解成短序列进行计算，通过叠代运算来减少DFT的运算量。N2次复乘N（N-1）次复加∝N2实乘：4N2实加：2N(N-1)+2N2=4N2-2NnkNW(3次实乘，5次实加)3.基（Radix）的定义：在FFT运算中最小DFT单元序列的长度称为基；4.FFT按分解方法不同可分为：Radix—2(N=2m)时间抽选(DIT)—DecimationInTime频率抽选(DIF)—DecimationInFrequency)1()0()1()0()1()0(1111)1()0()1()0()1,0()1()0()()(1202020222102xxxxxxxx•实质性乘法：指除去(±1),(±j)之外所需的乘法；例：3点DFT（用于Radix—3）)2(x)1(x)0(x)2(x)1(x)0(x)2(X)1(X)0(X13230323130303030343230323130303030313232313(ButterflyComputation))2,1,0()2()1()0()()(23303203kWxWxWxWnxkXkknnk)1(x)0(x)0(X1)1(X三点信号流图：x(0)X(0)x(1)X(1)x(2)X(2)13W23W23W43W5.高效算法标准：•乘、加次数最少；•算法结构的简单程度；（取指方便）•算法占用的存储量少；3。2时间抽选FFT算法(Radix2—DIT—FFT)—N=2m1.算法原理：时间抽选是把n序号按奇、偶分解例：N=8=23x(n)=（也称为信号的多相分解）0,2,4,6=x(2r)=e(r)E((k))N/21,3,5,7=x(2r+1)=f(r)F((k))N/2(0≤r≤N/2))k(FW)k(E)2Nk(X)k(FW)k(E)k(X))k((FW))k((EW)1r2(xW)r2(x)k(XkNkN2/NkN2/Nk)1r2(N12N0rrk2N12N0r(0≤k≤N-1)12Nk0其流图如教材图3.2.2•先做二个N/2点的DFT——需2×(N/2)2次乘法；•再做(N/2)个2点的DFT——勿需任何乘法；•级间需(N/2)个旋转因子(Twiddle—FactorFFTAlgorithm)；•经第一次分解后，总共需复乘次数：mc=2×(N/2)2+N/2=N/2(N+1)E(0)E(1)E(2)E(3)F(0)F(1)F(2)F(3)再次分解如图3.2.3完整的8点流图如3.2.4x0x1x2x32.Radix2—DIT—FFT算法特点:(1)分解级数：•FFT点数为：N=2m,则总共有m级；•每级共有（N/2）个蝶形运算xL-1(i)οοοοxL(i)xL-1(j)οοοοxL(j)xL(i)=xL-1(i)+xL-1(j)xL(j)=xL-1(i)－xL-1(j)－1rNWrNWrNW(2)运算量估计：•每个蝶形运算需：复乘次数1次；复加次数2次总共所需复乘和复加次数：如果考虑去除，则复乘次数可减至如果再去除，则复乘次数可减至•与直接计算相比较(图3.2.5))N(logN)2(logNNma)N(log2N)2(log2N2Nmm2m2c2m2c0NW)1N()N(log2Nm2c4NNW)2N23(Nlog2Nm2c﹡NlogN2Nlog2NNK222(3)原位运算（Inplace）利用同一存储单元存储蝶形输入、输出数据的方法；(4)序列的倒位序排列•目的：满足同址运算的要求；•表示方法：•实现：﹡表3.2.2变址处理：I≥J，不做处理I=J——不做交换；I≥J——已经交换完了，不再交换；IJ,进行交换；﹡软件编程实现：图3.2.8,虚框表示逆记数；21020122nn2n2nnn2n2n0≤ni≤1i=0,1,23.3N=8=2×2×2,Radix2—DIT—FFT的数学表示式及其对应的流图1。运算表示式及几点说明⑴设置变量及其维数；0≤n0≤10≤k0≤10≤n1≤10≤k1≤10≤n2≤10≤k2≤1⑵列写输入－输出n、k的表达式：⑶列出运算表示式，并对n分解（DIT），分别化简：01222102kk2k2knn2n2n互为倒序表示：)0k1k22k22)(2n1n20n22(8102n2102101n100nW)nn2n2(x)k(X)W)nn2n2(x()nn2n2(x002100122201221210012202kn210n10n10n01220)kk2k2(n8)kk2k2(n2810n10n10n)kk2k2(n280122001kn28W()W11kn48)kk2(n8012W()W22kn4810n10n0122121)kn2n2(x(01kn28W)W11kn2)kk2(n8012W()W22kn4801kn28W()kk2(n8012W(01kn28W)kk2(n8012W(10n012222)kk2n2(x)kk2(n8012W22kn2W)k(X)kk2k2(x01223说明：(1)n、k互为倒序排列（与要求的流图排序无关）；(2)FFT运算是一逐级叠代过程，每次求和消去一个ni代之以ki；(3)求和运算时，若DIT，则按n做分解；若DIF，则按k做分解，对表示式进行化简；(4)n表示式中的最高位，表示流图的第一级，不管nk如何表示，求和总是从n表示式中最高位开始；(5)同一表示式可以有多个流图与之对应；2.根据表示式画出相应的流图：输入倒序—输出正序形式)nnn(nnn2n2n2,1,02102000100010110001101011111)k,k,k(kkk2k2k012012200000101001110010111011101kn28W)kk2(n8012W3.组的概念：流图中的每一组有相同的结构和相同的分布结构包括：蝶形运算类型；运算结点的间距rNWL=1L=2L=3组的计算：第L级有：组，每组内有种蝶形，每个蝶形的间距；旋转因子的分布：例：设FFT的点数为N=256=28，输入为倒位序排列，问第L=5级，有几组蝶形，每组有几种蝶形，每个蝶形的间距是几点，旋转因子共有几个，具体值是什么？解：有23=8组蝶形，每组内有256/(8×2)=16种蝶形，每个蝶形的间距是16点，Lm21L21L2i2N2i22i2LmLmLmLL)12(1Li=(0,1,2,3…)76524334251607nn2n2n2n2n2n2n2n旋转因子分布：(0≤i≤15)具体蝶形运算形式：xL-1(i)οοοοxL(i)xL-1(j)οοοοxL(j)j=i+3.4Radix-2DIT—FFT的其他流图形式：其他流图形式的获取原则：保持各结点所连的支路及其传输系数不变，只是数据的提取和存放次序的不同。（见图3.4.13.4.2）i82562i256i32i2i2NLmW1L2)nnn(nnn2n2n2,1,02102)k,k,k(kkk2k2k012012200000101001110010111011101kn28W000100010110001101011111)kk2(n8012W输入正序—输出倒位序排列的流图：级间几何图形相同的DIT—FFT流图（图3.4.2）3。2频率抽选FFT算法(Radix2—DIF—FFT)—N=2m1.基本原理：DIF是把X(k)分解成短序列(对k分解)12N0nnr2NnN12N0nnr2N12N0nnkNk12N0nk)2Nn(N12N0nnkN1N2NnnkN12N0nnkNWW)]2Nn(x)n(x[)1r2(X1r2kW)]2Nn(x)n(x[)r2(Xr2kW])1)(2Nn(x)n(x[W)2Nn(xW)n(xW)n(xW)n(x)k(X逐次分解流图表示：nNWN=23=8点DIF—FFT完整流图：基本蝶形运算：xL-1(i)ooooxL(i)xL-1(j)ooooxL(j)－1rNWxL(i)=xL-1(i)+xL-1(j)xL(j)=[xL-1(i)－xL-1(j)]rNW2.N=8=2×2×2,Radix2—DIF—FFT的数学表示式及其对应的流图1)Radix2—DIF—FFT的数学表示式：⑴设置变量及其维数；0≤n0≤10≤k0≤10≤n1≤10≤k1≤10≤n2≤10≤k2≤1⑵列写输入－输出n、k的表达式：互为倒序表示：⑶列出运算表示式，并对k分解（DIF），分别化简：21020122kk2k2knn2n2n)kk2k2)(nn2n2(810n012210n10n21020122012W)nn2n2(x)k(X00011101000111012220120122201221012012202nk2nk28nk210n10n01221nk2nk28nk2)nn2(k8kn210n10n10n0122)nn2n2(k8)nn2n2(k2810n10n10n)nn2n2(k280122WW))W)nn2k2(x()W)(WW()W))(W)nn2n2(x()nn2n2(x)nn2(k8012W01nk28W01nk28W)kk2k2(xWW)nk2k2(x01223nk2nk2810n012220001001nk28W)nnn(nnn2n2n0,1,20122)k,k,k(kkk2k2k2102102=X(k)2)流图表示：00010001011000110101111100000101001110010111011101nk28W)nn2(k8012W3)DIT与DIF的关系：相同点：•分解级数都是m级；•乘法次数都是；•都是同址运算；•都有不同流图对应相同的表达式；区别：蝶形运算结构不同：DIT—FFTNlog2N2DIF—FFT由DIT—FFT碟形解出：xL-1(i)=（xL(i)+xL(j)）xL-1(j)=[xL-1(i)－xL-1(j)]若去除，并把改为，即为DIF蝶形流图，∴DIT和DIF在流图形式上互为转置关系。rNW2121rNWrNW214)用DIT与DIF的组合来过滤x(n)DIT—FFTDIF—IFFT×x(n)正y(n)正倒倒H(k)5)如何用DFT（FFT）模块做IFFT？3.6高组合数的FFT算法——旋转因子算法（混合基FFT，多基多进制算法）1。N为组合数时，DIT—FFT算法原理：N=N0N1N2…Nm-1=M0Nm-1物理概念见教材(p.139)M0设：0≤m0≤5，0≤n2≤2；0≤≤5，0≤k2≤2n=