第8章-DFT的有效计算：快速傅里叶变换算法.ppt

数字信号处理-8-,邬霞教授北京师范大学信息学院电子系wuxia,离散傅里叶变换(DFT)快速傅里叶变换(FFT),2,DFT是信号分析与处理中的一种重要变换。但直接计算DFT的计算量与变换区间长度N的平方成正比，当N较大时，计算量太大，直接用DFT算法进行谱分析和信号的实时处理是不切实际的。1965年发现了DFT的一种快速算法，使DFT的运算效率提高12个数量级，为数字信号处理技术应用于各种信号的实时处理创造了条件，推动了数字处理技术的发展。1984年，提出了分裂基快速算法，使运算效率进一步提高；,本讲提纲,DFT的复杂度问题DIT-FFT算法原理DIT-FFT运算规律DIF-FFT算法IDFT的高效算法实序列的FFT算法,3,本讲提纲,DFT的复杂度问题DIT-FFT算法原理DIT-FFT运算规律DIF-FFT算法IDFT的高效算法实序列的FFT算法,4,DFT的复杂度问题_,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,5,问题的提出,N点DFT变换：,IDFT变换：,1、DFT的定义式,包含运算：,DFT的复杂度问题_,6,问题的提出,2、DFT的运算量,通常和都是复数,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,DFT的复杂度问题_,7,问题的提出,DSP芯片没有复数运算，因此复数运算需转换成实数运算实现,可见，1次复数加法需要2次实数加法实现；1次复数乘法需要4次实数乘法和2次实数加法实现。,（3）对应实数的运算量,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,DFT的复杂度问题_,8,问题的提出,N点DFT的复数乘法次数举例,结论：当N很大时，其运算量很大，对实时性很强的信号处理来说，要求计算速度快。如何改进DFT的计算方法以大大减少运算次数？,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,DFT的复杂度问题_,9,问题的解决,3、减小运算量的途径,N点DFT的复数乘法次数等于N2。把N点的DFT分解成几个较短的DFT，可使乘法的次数大大减少。旋转因子的特殊性质：,周期性,对称性,可约性,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,DFT的复杂度问题_,10,问题的解决,3、减小运算量的途径,利用上述性质可大大减少DFT的计算量，用这种方法计算DFT称为快速傅里叶变换（FFT)。,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,本讲提纲,DFT的复杂度问题DIT-FFT算法原理DIT-FFT运算规律DIF-FFT算法IDFT的高效算法实序列的FFT算法,11,DIT-FFT算法原理,12,设序列x(n)的长度为N，且满足,为自然数,将序列x(n)按n为奇、偶数分为x1(n)、x2(n)两组序列；用2个N/2点DFT来完成一个N点DFT的计算。,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,注意：这里k的取值范围为0，1，N-1,DIT-FFT算法原理,13,(2)用N/2点X1(k)和X2(k)表示序列x(n)的N点DFTX(k),DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,注意：这里k的取值范围为0，1，N/2-1,DIT-FFT算法原理,14,其中X1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT，即：,将N点DFT分解为两个N/2点的DFT,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,DIT-FFT算法原理,15,完成一个蝶形运算需要一次复数乘和两次复数加法运算，经过一次分解后，共需要复数乘和复数加的次数为2(N/2)2+N/2和N2/2,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,DIT-FFT算法原理,16,蝶形运算符号,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,DIT-FFT算法原理,17,N=8点的基2DIT-FFT第一次分解图,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,DIT-FFT算法原理,18,(3)第二次分解：将x1(r)按r取奇、偶可分解成2个长度为N/4的子序列x3(l)=x1(2l)、x4(l)=x1(2l+1)，根据上面推导可得：X1(k)=X3(k)+WN/2kX4(k)，k=0,1,N/2-1,l=0,1,，N/4-1；,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,DIT-FFT算法原理,19,(3)第二次分解：,将x2(r)按r取奇、偶可分解成2个长N/4的子序列x5(l)=x2(2l)，l=0,1,，N/4-1x6(l)=x2(2l+1)；,同理:,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,DIT-FFT算法原理,20,N=8点的基2DIT-FFT第二次分解图,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,DIT-FFT算法原理,21,N=8点的基2DIT-FFT第三次分解图,(4)第三次分解：,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,DIT-FFT算法原理_,22,运算量分析与比较,1、直接DFT运算N点运算：复数乘次数：NN复数加次数：N(N-1)2、用DIT-FFT作N点运算：复数乘次数：MN/2=N/2log2N；复数加次数：2N/2M=Nlog2N可见FFT大大减少了运算次数，提高了运算速度。,整个运算流图中有M级蝶形，每一级运算流图中有N/2个蝶形，每个蝶形需一次复乘和两次复数加运算。,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,DIT-FFT算法原理_,23,运算量分析与比较,FFT算法与直接计算DFT所需乘法次数的比较曲线,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,DIT-FFT算法原理_,24,运算量分析与比较,【例】N=210=1024时，DIT-FFT的运算效率为当N=211=2048时，DIT-FFT的运算效率为,DFT的乘法次数DIT-FFT的乘法次数,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,本讲提纲,DFT的复杂度问题DIT-FFT算法原理DIT-FFT运算规律DIF-FFT算法IDFT的高效算法实序列的FFT算法,26,DIT-FFT运算规律,27,运算规律为了编程方便（1）原位计算（2）旋转因子的变化规律（3）输入序列的序号规律（4）编程思想及程序框图（5）DFT的矩阵运算实现（6）IFFT的运算原理,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,DIT-FFT运算规律_,28,原位计算,（1）原位计算观察每个蝶形的两个输入和两个输出蝶形的输出可存入原输入数据所占存储单元利用同一组存储单元存储输入、输出数据的方法，称为原位（址）计算。节约内存节省寻址的时间,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,DIT-FFT运算规律_,29,旋转因子变化规律,（2）旋转因子的变化规律,观察图不难发现，第L级共有2L-1个不同的旋转因子。,1,2,3,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,DIT-FFT运算规律_,30,旋转因子变化规律,（2）旋转因子的变化规律,N=23=8时的各级旋转因子表示如下:L=1时L=2时L=3时对N=2M的一般情况，第L级的旋转因子为,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,DIT-FFT运算规律_,31,旋转因子变化规律,（2）旋转因子的变化规律,由于所以这样，就可按上式确定第L级运算的旋转因子。,实际编程序时，L为最外层循环变量,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,DIT-FFT运算规律_,32,输入序列的序号规律,（3）输入序列的序号规律,DITFFT算法的输入序列的排序看起来似乎很乱，但仔细分析就会发现这种序列是很有规律的。由于N=2M，用M位二进制数(nM-1nM-2n1n0)表示序列的序号n。,04261537,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,DIT-FFT运算规律_,33,输入序列的序号规律,（3）输入序列的序号规律,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,DIT-FFT运算规律_,34,编程思想及程序框图,（4）编程思想及程序框图,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,整序流程图,DIT-FFT流程图,DIT-FFT运算规律_,37,DFT的矩阵运算实现,（5）DFT的矩阵运算实现,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,DIT-FFT运算规律_,38,IFFT的运算原理,（5）IFFT的运算原理,方法1：,方法2：,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,本讲提纲,DFT的复杂度问题DIT-FFT算法原理DIT-FFT运算规律DIF-FFT算法IDFT的高效算法实序列的FFT算法,39,DIF-FFT算法_,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,40,算法原理,DIF-FFT算法_,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,41,算法原理,DIF-FFT算法_,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,42,算法原理,DIF-FFT算法_,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,43,算法原理,DIF-FFT一次分解运算流图(N=8),频率抽取法蝶形运算单元,DIF-FFT算法_,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,44,算法原理,DIF-FFT二次分解运算流图(N=8),DIF-FFT算法_,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,45,算法原理,DIF-FFT运算流图(N=8),DIF-FFT算法_,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,46,算法特点,DIF-FFT算法_,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,47,算法原理,频率抽取FFT算法的输入是自然顺序，输出是倒位序的，因此运算完毕后，要通过变址计算将倒位序转换成自然位序，然后再输出。转换方法与时间抽取法相同。初看起来，DIF法与DIT法的区别是：DIF输入是自然顺序，输出是倒位序的，这与4-4的DIT法正好相反。但这不是实质性的区别，因为输入或输出数据是可以重排的。,DIF-FFT算法_,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,48,算法原理,DIF法与DIT法的根本区别是：DIF的基本蝶形与DIT的基本蝶形有所不同，DIF的复数乘法只出现在减法之后，DIT则是先作复乘后再作加减法。按照转置定理，即将流图的所有支路方向都反向，并且交换输入与输出，但节点变量值不交换，因而对每一种按时间抽取的FFT流图都存在一个按频率抽取的FFT流图，反之亦然。因此，实质上频率抽取法与时间抽取法是两种等价的FFT运算。,本讲提纲,DFT的复杂度问题DIT-FFT算法原理DIT-FFT运算规律DIF-FFT算法IDFT的高效算法实序列的FFT算法,49,IDFT的高效算法_,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,50,利用FFT流图计算IFFT,以上所讨论的FFT的运算方法同样可用于IDFT的运算，简称为IFFT，即快速傅里叶反变换。从IDFT的定义出发，可以导出下列两种利用FFT来计算IFFT的方法。,IDFT的高效算法_,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,51,利用FFT流图计算IFFT,IDFT的高效算法_,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,52,DIT-IFFT运算流图,利用FFT流图计算IFFT,IDFT的高效算法_,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,53,DIT-IFFT运算流图（防止溢出）,利用FFT流图计算IFFT,IDFT的高效算法_,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,54,直接调用FFT子程序的方法,IDFT的高效算法_,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,55,直接调用FFT子程序的方法,本讲提纲,DFT的复杂度问题DIT-FFT算法原理DIT-FFT运算规律DIF-FFT算法IDFT的高效算法实序列的FFT算法,56,实序列的FFT算法,DFT复杂度DIT-FFTDIT-FFT运算规律DIF-FFTIDFT实序列FFT,57,在实际中遇到的数据大多数情况下是实序列，而在前面介绍的FFT流图主要针对的是复序列，若直接按该流图处理实序列，则是将序列看成虚部为零的复序列，这就浪费许多运算时间和存储空间。,解决的方法主要有两个。方法1是用一个N点的FFT计算两个N点实序列的FFT，一个作为实