(4.9.1)--4.9按时间抽取的FFT与DFT运算量的比较.pdf

第四章 离散傅里叶变换及其快速算法4.6.5 按时间抽取的FFT与DFT运算量的比较由由以以上上按按时时间间抽抽取取法法FFT的的运运算算流流图图，可可以以看看出出，当当N=2M时时，共共有有M级级蝶蝶形形，每每级级都都由由N/2个个蝶蝶形形运运算算组组成成，每每个个蝶蝶形形有有一一次次复复乘乘、二二次次复复加加，因因而而每每级级运运算算都都需需N/2次次复复乘乘和和N次次复复加加，这这样样M级级运运算算总总共共需需要要复复乘乘数数 复复加加数数 2log22NFNNmM2logNFaNMN直直接接计计算算DFT复复数数乘乘法法次次数数是是N2，FFT复复数数乘乘法法次次数数是是，则则二二者者之之比比为为当当N=1024时时，这这一一比比值值为为204.8，即即直直接接计计算算DFT的的运运算算量量是是FFT运运算算量量的的204.8倍倍。当当点点数数N 越越大大时时，FFT的的优优点点更更为为明明显显。2222loglog2NNNNN4.6.5 按时间抽取的FFT与DFT运算量的比较例例4.5 如如果果计计算算机机的的速速度度为为平平均均每每次次复复数数乘乘需需要要510-6秒秒，每每次次复复数数加加需需要要10-6秒秒，用用来来计计算算N=1024点点DFT，求求分分别别利利用用DFT和和FFT计计算算各各需需要要多多少少时时间间？二二者者计计算算量量之之比比值值？解解:直直接接用用DFT的的复复数数乘乘运运算算次次数数为为N2次次=10241024次次，复复数数加加法法计计算算次次数数为为N(N-1)=10241023，所所以以直直接接计计算算所所需需时时间间为为T=510-610242+10-6102410236.29s。FFT计计算算所所需需时时间间为为DFT运运算算时时间间/FFT运运算算时时间间=6.29s/35.84ms=175.5倍倍。66226102461024225 10log10log210245 10log101024log235.84msNNNTN 4.6.5 按时间抽取的FFT与DFT运算量的比较按频域抽取FFT算法流图按频域抽取算法运算特点尽尽管管DIF与与DIT的的蝶蝶形形结结构构不不同同，但但其其运运算算量量相相同同，即即有有M 级级运运算算，每每级级运运算算需需N/2个个蝶蝶形形运运算算来来完完成成，总总共共需需要要 次次复复乘乘，次次复复加加。2log2NN2logNN与与时时间间抽抽取取法法不不同同的的是是，按按频频率率抽抽取取法法的的输输入入是是自自然然序序列列，而而输输出出是是倒倒位位序序。因因此此运运算算完完毕毕后后，要要通通过过变变址址计计算算将将倒倒位位序序转转换换成成自自然然序序列列，然然后后再再输输出出，转转换换方方法法与与时时间间抽抽取取法法相相同同。FFT的应用比比较较两两式式可可知知,只只要要D DF FT T的的每每个个系系数数 换换成成 ,最最后后再再乘乘以以常常数数1 1/N N就就可可以以得得到到I ID DF FT T的的快快速速算算法法-I IF FF FT T。用用FFT计计算算IDFT 1010()()()1()()()NnkNnNnkNkX kDFT x nx n Wx nIDFT X kX k WNnkNWnkNWFFT的的应应用用1*01010,1()()1()1()()1()nknkNNNnkNkNnkNkNnkNkWWA BABx nX k WNXk WNx nXk WNDFT XkN因因此此：先先将将X(k)取取共共轭轭，直直接接利利用用FFT程程序序计计算算DFT然然后后再再取取一一次次共共轭轭；最最后后再再乘乘1/N，即即得得x(n)。所所以以，FFT与与IFFT可可用用一一个个子子程程序序，这这在在使使用用通通用用计计算算机机时时比比较较方方便便。共共轭轭FFT共共轭轭乘乘1/N()X k*()Xk()x n线性卷积的FFTLnhLkYIFFTnyLkHkXkYLnxFFTkXLnhFFTkHNNnhnxLLLL222221mlogL)(log2;)()(.5)()()(.4log2)()(.3log2,)()(.2;12L)(),(.1总复数乘法的次数，不需要计算，数，第一步实际上通常是预先设计好的参因为复数乘法的次数，求；复数乘法的次数，求；复数乘法的次数，求复数乘法的次数，求点补零点，至少为将线线性性卷卷积积的的FFT线线性性卷卷积积的的FFT线线性性卷卷积积的的FFT2FFT121211212121log)1(log21,)1logNLLNNkNNNLNNLLLNk时，即两序列长度近似相等时当讨论：法计算的运算量比较直接计算和线性卷积的FFT线线性性卷卷积积的的FFT直直接接计计算算线线性性卷卷积积和和FFT法法运运算算量量比比较较 时速度提高极大当性就越大。越大，循环卷积的优越64N21 NN线性卷积的FFT线线性性卷卷积积的的FFT谢 谢Thanks