数字信号处理-课件 第5章 FFT快速傅氏变换.ppt

*5.6.3用FFT算线性卷积y(n)的步骤运算量：N/2log2N运算量：N/2log2N运算量：N/2log2N运算量：N总运算量？3N/2log2N+N*5.6.4运算量比值(K)1.L=M时，比值最大，即最节省运算量2.L=M=32时，比值为0.803.L=M=64时，比值为1.39什么条件下，K的取值最大？结论：L=M=64体现快速运算的临界点（值）*FFTh(n)IFFTy(n)FFTx(n)X(k)H(k)×Y(k)根据算法给出线性卷积计算流程图：*几点说明1.当M=L时,用圆周卷积计算线性卷积的速度快,点数越多,速度越快,N≥64时,速度增加明显.2.LM时,速度增加不太明显,为了增加速度,采用(1)重叠相加法(2)重叠保留法(从略).*本章总复习一.基本概念1.FFT、DIT、DIF、2.蝶形图、运算量、倒位序、节点距离、原位运算、变址运算3.线性卷积快速算法、重叠相加法等*二.基本原理1.DIT算法的基本原理与算法3.IFFT快速算法4.快速卷积算法2.DIF算法的基本原理与算法5.从DIT/DIF及快速卷积算法中得到启发，具有将其他算法实现快速运算的能力*三.基本公式1.DIT第一次分解公式：2.类推继续分解（公式与原理）前一半后一半*3.DIF第一次分解公式：-14.类推继续分解（公式与原理）*6.其它快速算法运算量的估计5.DIT/DIF复数乘法运算量：**********因此,N点的FFT的运算量为复乘:mF=（N/2）L=（N/2）log2N（复加:aF=NL=Nlog2N）DFT与FFT运算量之比较：N2/(N/2)log2N=2N/log2N因此，N越大，运算量节省更明显。*1.原位运算每级(列)都是由N/2个蝶形运算构成,即:-1WNr5.4.2DIF算法的特点*2.蝶形运算两节点的距离一般公式为2L-m=N/2m例如N=23=8：(1)m=1时的距离为8/2=4；(2)m=2时的距离为8/4=2;(3)m=3时的距离为8/8=1。*r的求法：k=(n2n1n0),左移m-1位,右边空出补零,得(r)2,亦即(r)2=(k)22m-1.例如,N=8:(1)m=1,k=2,k=(010)2左移0位,(r)2=(010)2=2;(2)m=2,k=1,k=(001)2左移1位,(r)2=(010)2=2;(3)m=2,k=0,k=(001)2左移1位,(r)2=(010)2=2.3.的计算由于DIF蝶形运算的两节点的距离为N/2m,所以蝶形运算可表为：*1.相同点(1)都要求序列长度满足条件N=2L(2)均需要L次分解，均包含L级运算(3)总运算量相同,均为（N/2)Log2N次复乘(4)编程时都可以进行原位运算；5.4.3DIF与DIT算法的比较比较如下:*2.不同点(1)如无特别说明，DIT算法的输入为倒位序,输出为自然顺序；DIF算法正好与DIT算法相反。但经过改进DIT算法也有输入为自然顺序,输出为倒位序的情况。*(2)蝶形运算不同用矩阵表示=11a.DIT先乘法运算，后求和运算*b.DIF用矩阵表示=11先求和运算，后乘法运算*(3)两种蝶形运算的关系互为转置（矩阵）；将流图的所有支路方向都反向,交换输入和输出，即可得到另一种蝶形。a.(DIT)11b.(DFT)11*5.4.4IFFT算法1.观察DFT和IDFT运算的差异