离散傅里叶变换快速算法

离散傅里叶变换快速算法(FFT)快速傅里叶变换(FFT) 问题的提出 基2时间抽取FFT算法 基2频率抽取FFT算法 IFFT算法的实际应用 掌握基2时间抽取FFT算法的基本思想和方法 掌握基2频率抽取FFT算法的基本思想和方法 掌握实序列FFT计算，以及由N点序列FFT计算2N点序列FFT的方法 掌握利用FFT计算IDFT的过程，以及IFFT实现的原理快速傅里叶变换(FFT)重点：基2时间/频率抽取FFT算法的基本原理，FFT蝶形运算流图 难点：由短序列的DFT表达相应长序列的DFT的基本原理及方法快速傅里叶变换(FFT)乘法次数N加法次数N-1通常x[k]和WNkm都是复数，所以计算一个X[m]的值需要N次复数乘法运算和N-1次复数加法运算。所有的X[m]就要N2次复数乘法运算，N(N-1)次复数加法运算。当N很大时，运算量将是惊人的，如N=1024，则要完成1048576次(一百多万次)运算。1965年，库利(cooley)和图基(Tukey)首先在《机器计算傅里叶级数的一种算法》文章中提出FFT算法。N/2点DFTN/2点DFTX1[0]X1[1]X1[2]X1[3]X2[0]X2[1]X2[2]X2[3]X[0]X[4]X[1]X[5]X[2]X[6]X[3]X[7]N/2点DFTN/2点DFTX1[0]X1[1]X1[2]X1[3]X2[0]X2[1]X2[2]X2[3]+X[0]X[4]X[1]X[5]X[2]X[6]X[3]X[7]+++----N/2点DFTN/2点DFT将DFT长序列分解为短序列，降低运算次数。当N很大时，运算量减少了近一半 复数乘法 复数加法 1个点DFT 2个点DFT 1个蝶形 1 2 N/2个蝶形 N 总计 N点有限长序列的DFT N/2点有限长序列的DFT旋转因子的周期性旋转因子的对称性 旋转因子碟形运算*8点基2时间抽取FFT算法流图X1[0]X1[1]X1[2]X1[3]X2[0]X2[1]X2[2]X2[3]X[0]X[1]X[2]X[3]X[4]X[5]X[6]X[7]-1-1-1-12点DFT2点DFTX3[0]X3[1]x[0]x[4]x[2]x[6]X4[0]X4[1]112点DFT2点DFT11X5[0]X5[1]X6[0]X6[1]x[1]x[5]x[3]x[7]x[0]x[4]x[2]x[6]X3[0]X3[1]X4[0]X4[1]1111x[1]x[5]x[3]x[7]X5[0]X5[1]X6[0]X6[1]11118点基2时间抽取FFT算法流图第一级第二级第三级x[0]�x[4]�x[2]�x[6]�X[0]�X[2]�X[1]�X[3]�-1�-1�-1�-1�x[1]�x[5]�x[3]�x[7]�X[0]�X[2]�X[1]�X[3]�-1�-1�-1�-1�-1�-1�-1�-1�这种FFT算法,是在时间上对输入序列的次序是属于偶数还是属于奇数来进行分解的，所以称作按时间抽取的算法(DIT，DecimationinTime)。二、运算量当N=8=23时，由3级蝶形运算组成；每级由4个蝶形运算组成；共有12个蝶形运算；每个蝶形运算有1次复乘，2次复加；共有12次复乘，24次复加；*当N=2L时，共有L级蝶形，每级N/2个蝶形，每个蝶形有1次复数乘法2次复数加法。*复数乘法：复数加法：复数乘法次数与DFT比较：N点的FFT的运算量：1024点来说，比值为204.8*FFT算法特点第一级第二级第三级000001010011100101110111000100010110001101011111x[0]�x[4]�x[2]�x[6]�X[0]�X[2]�X[1]�X[3]�-1�-1�-1�-1�x[1]�x[5]�x[3]�x[7]�X[0]�X[2]�X[1]�X[3]�-1�-1�-1�-1�-1�-1�-1�-1�FFT算法特点 级数 碟形运算的数量:N/2第一级第二级第三级000001010011100101110111000100010110001101011111x[0]�x[4]�x[2]�x[6]�X[0]�X[2]�X[1]�X[3]�-1�-1�-1�-1�x[1]�x[5]�x[3]�x[7]�X[0]�X[2]�X[1]�X[3]�-1�-1�-1�-1�-1�-1�-1�-1�00000000自然顺序二进制k2k1k0倒位序二进制k0k1k2倒位顺序10011004201001023011110641000011510110156110011371111117倒位序规律由按时间抽选法FFT运算流图(书140页图3-6)可知，输出X[m]按正常顺序排列在存储单元，而输入x[k]是按顺序:*以N=8为例，说明如下:*x[0]x[1]x[2]x[3]x[4]x[5]x[6]x[7]x[0]x[4]x[2]x[6]x[1]x[5]x[3]x[7]变址处理方法存储单元自然顺序变址倒位序A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)*1.原位计算n表示第n级迭代，m，j表示数据所在的行数输入数据、中间运算结果和最后输出均用同一存储器* 级数 碟形运算的数量 序列倒序 序列原位 旋转因子分布例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]={1,-1,1,-1,2,1,1,2}的DFT。(书上作业3-5)解：根据基2时间抽取FFT算法原理，8点序列的DFTX[m]可由两个4点序列的DFTX1[m]和X2[m]表达。如果按照序列x[k]序号的奇偶分解为x1[k]和x2[k]，则存在其中x1[k]={1,1,2,1}，x2[k]={-1,-1,1,2}，X1[m]和X2[m]可通过4点的FFT来计算。例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]={1,-1,1,-1,2,1,1,2}的DFT。解：X1[m]={5,-1,1,-1},X2[m]={1,-2+3j,1,-2-3j}利用上述，可得序列x[k]的DFTX[m]为X[m]={6,-0.293+3.535j,1+j,-1.707+3.535j,4,-1.707-3.535j,1-j,-0.293-3.535j}-1�-1�-1�-j�1�2�1�1�5�-1�1�-1�3�-1�2�0�-1�快速傅里叶变换(FFT) 基2时间抽取FFT算法 与DFT的运算量对比 算法的特点在基-2FFT算法的流图中，当序列长度N=32时，一共有_________级蝶形运算，蝶形个数为________，共完成______次复数加法、_______次复数乘法。若直接完成DFT计算共需要_____次复数加法、______次复数乘法。若输入序列按自然顺序排列，序号为13的输出序列号(倒位序)是_____________。画出N=4基-2FFT时间抽取蝶形图。**本节课内容 按频率抽选的基-2FFT算法* FFT算法应用**3.2按频率抽取(DIF)的基-2FFT算法 —桑德-图基（Sand-Tukey）算法 基2时间抽取FFT算法输入序列x[k]按其顺序的偶、奇数分解为越来越短的序列。 基2频率抽取(DIF)FFT算法输出序列X[m](也是N点序列)按其顺序的偶、奇来分解为越来越短的序列。*常系数线性差分方程*一、算法原理设序列点数N=2L，L为整数。将X[m]按m的奇偶分组前，先将输入x[k]按k的顺序分成前后两半：***按m的奇偶将X[m]分成两部分：**则X[2r]和X[2r+1]分别是x1[k]和x2[k]的N/2点DFT，记为X1[m]和X2[m]，碟形运算为：令-1WNk**N/2点DFTN/2点DFT*3NW-12NW-11NW-10NW-1x[0]x[4]x[1]x[5]x[2]x[6]x[3]x[7]4点DFTX[0]X[6]X[2]X[4]4点DFTX[1]X[3]X[5]X[7]**N/2仍为偶数，进一步分解：N/2N/4*****X[0]X[6]X[4]X[2]X[1]X[5]X[3]X[7]0NW1NW2NW3NW-1-1-1-1x[0]x[3]x[1]x[2]x[4]x[5]x[6]x[7]0NW2NW2点DFT-1-12NW0NW-1-12点DFT2点DFT2点DFT*0NW1NW2NW3NW-1-1-1-1x[0]x[3]x[1]x[2]x[4]x[5]x[6]x[7]0NW2NW2NW0NWX[0]X[6]X[4]X[2]X[1]X[5]X[3]X[7]0NW0NW0NW0NW-1-1-1-1-1-1-1-1*已知有限长序列x[k]数值为{1,2,-1,3}，请按频率抽选的基-2FFT(快速傅里叶变换)运算过程求X[m]，并画出蝶形流程图解：x[0]x[1]x[2]x[3]X[0]X[2]X[1]X[3]x1[0]x1[1]x2[0]x2[1]-1-1-1-1**二、算法特点1.原位计算L级蝶形运算，每级N/2个蝶形。2.蝶形运算距离对N=2L点FFT，输入自然序，输出倒位序，两节点距离：2L-n=N/2n例如N=23=8：(1)n=1时的距离为8/2=4；(2)n=2时的距离为8/4=2;(3)n=3时的距离为8/8=1。*0NW1NW2NW3NW-1-1-1-1x[0]x[3]x[1]x[2]x[4]x[5]x[6]x[7]0NW2NW2NW0NWX[0]X[6]X[4]X[2]X[1]X[5]X[3]X[7]0NW0NW0NW0NW-1-1-1-1-1-1-1-1**二、算法特点3.运算量级数：log2N每级的蝶形数：N/2每蝶形：复乘1次，复加2次总运算量：复乘(N*log2N)/2次复加N*log2N次**(1)相同点(a).进行原位运算；(b).运算量相同，均为(N/2)Log2N次复乘，NLog2N次复加。3.DIF法与DIT法的异同**(2)不同点(a).DIT输入为倒位序，输出为自然顺序；DIF输入为自然顺序，输出为倒位序；*(b).蝶形运算不同DITDIF**(c)两种蝶形运算的关系互为转置(矩阵)；将算法流图的所有支路方向都反向，交换输入和输出，即可得到另一种蝶形。**8点序列DIT8点序列DIF*8点序列DIT8点序列DIF*FFT算法应用利用N点复序列的FFT，计算两个N点实序列FFT利用N点复序列的FFT，计算2N点序列的FFT利用FFT计算IFFT*利用N点复序列的FFT算法计算两个N点实序列FFT2个N点实序列：x[k],h[k]y[k]=x[k]+jh[k]目的：通过一次FFT求出X[m],H[m]构成复序列y*[k]=x[k]–jh[k]*利用N点复序列的FFT算法计算两个N点实序列FFT2个N点实序列：x[k],h[k]目的：通过一次FFT求出X[m],H[m]*利用N点复序列的FFT算法计算两个N点实序列FFT2个N点实序列：x[k],h[k]目的：通过一次FFT求出X[m],H[m]*利用N点复序列的FFT计算2N点序列的FFT*y[k]是一个长度为2N的序列*例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]={1,-1,1,-1,2,1,1,2}的DFT。解：根据基2时间抽取FFT算法原理，8点序列的DFTX[m]可由两个4点序列的DFTX1[m]和X2[m]表达。如果按照序列x[k]序号的奇偶分解为x1[k]和x2[k]，则存在其中x1[k]={1,1,2,1}x2[k]={-1,-1,1,2}**例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]={1,-1,1,-1,2,1,1,2}的DFT。如何求X1[m]和X2[m]可通过一次的y[m]的DFT来计算。y[m]=x1[k]+jx2[k]={1-j,1-j,2+j,1+2j}x1[k]={1,1,2,1}x2[k]={-1,-1,1,2}*Y*[(-m)4]={5-j,2+2j,1+j,-4+2j}Y[m]={5+j,-4-2j,1-j,2-2j}例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]={1,-1,1,-1,2,1,1,2}的DFT。*例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]={1,-1,1,-1,2,1,1,2}的DFT。X[m]={6,-0.293+3.535j,1+j,-1.707+3.535j,4,-1.707-3.535j,1-j,-0.293-3.535j}*利用FFT实现IFFT**IDFT的快速计算方法1.稍微变动FFT程序和参数可实现IFFT**DIF方法**2.不改(FFT)的程序直接实现IFFT**直接调用FFT子程序计算IFFT的方法：** 步骤：(1)将X[m]取共轭(3)对(2)中结果取共轭并除以N*解:pp1143-7见书64DFT的对称性已知复数序列y[k]=x1[k]+jx2[k],Y[m]求出X1[m]、X2[m](x1[k]、x2[k]是实数)3+4j,-10.4-0.6j,-5+4j,15.4-22.4j,17-2j,-21.6-17.4j,-3+2j,12.6+8.4j0.375+0.5j,-1.3-0.075j,-0.625+0.5j,1.925-2.8j,2.125-0.25j,-2.7-2.175j,-0.375+0.25j,1.575+1.05j求共轭/NX1[k]={0.375,-1.3,-0.625,1.925,2.125,-2.7,-0.375,1.575}X2[k]={0.5,-0.075,0.5,-2.8,-0.25,-2.175,0.25,1.05}0.375+0.5j,-1.3-0.075j,-0.625+0.5j,1.925-2.8j,2.125-0.25j,-2.7-2.175j,-0.375+0.25j,1.575+1.05jX1[k]={0.375,-1.3,-0.625,1.925,2.125,-2.7,-0.375,1.575}X2[k]={0.5,-0.075,0.5,-2.8,-0.25,-2.175,0.25,1.05}*本章小结 直接计算DFT所需要的复数乘法加法次数；采用基-2FFT所需要的复数乘法加法次数； FFT的基本思想(将长序列DFT分解为短序列的DFT)，利用旋转因子WNkm的周期性、对称性、可约性。 FFT的特点(蝶形运算、原位计算、倒位)**将时域序列逐次分解为一组子序列，利用旋转因子的特性，由子序列的DFT来实现整个序列的DFT。 基2时间抽取(Decimationintime)FFT算法 基2频率抽取(Decimationinfrequency)FFT算法**作业P1173-43-83-9***********常系数线性差分方程********************************