蝶形算法PPT课件.ppt

<p>第4章 快速傅立叶变换问题的提出问题的提出解决问题的思路与方法解决问题的思路与方法 基基2 2时间抽取时间抽取FFTFFT算法算法基基2 2时间抽取时间抽取FFTFFT算法的计算复杂度算法的计算复杂度基基2 2时间抽取时间抽取FFTFFT算法流图规律算法流图规律基基2 2频率抽取频率抽取FFTFFT算法算法FFTFFT算法的实际应用算法的实际应用1 1问题的提出4点序列2，3，3，2 DFT的计算复杂度复数加法N(N-1)复数乘法N 2如何提高DFT的运算效率?2 2解决问题的思路1.将长序列DFT分解为短序列的DFT2.利用旋转因子 的周期性、对称性、可约性。3 3旋转因子 的性质1)周期性2)对称性3)可约性4 4解决问题的方法将时域序列逐次分解为一组子序列，利用旋转因子的特性，由子序列的DFT来实现整个序列的DFT。基2时间抽取(Decimation in time)FFT算法基2频率抽取(Decimation in frequency)FFT算法5 5基2时间抽取FFT算法流图N=2xk=x0,x16 64点基2时间抽取FFT算法流图x0 x2x1x3X10X11X20X212点DFT2点DFT-1-1-1-1X 0X 1X 2X 37 74点基2时间抽取FFT算法流图8 88点基2时间抽取FFT算法流图4点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-19 94点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-18点基2时间抽取FFT算法流图1010基2时间抽取FFT算法第一级第二级第三级1111算法的计算复杂度复乘次数复乘次数NN 212122024/3/12 2024/3/12 周二周二1313基2时间抽取FFT算法流图第一级第二级第三级1414FFT算法流图旋转因子 规律第二级的蝶形系数为 ，蝶形节点的距离为2。第一级的蝶形系数均为 ，蝶形节点的距离为1。第三级的蝶形系数为 ，蝶形节点的距离为4。第M级 的蝶形系数为 ，蝶形节点的距离为N/2。1515倒序k0k1k2xk2 k1k0 x000 x100 x0100101112 xk k0 xk2 k101x110 x001x101x011x111010101011616 基2频率抽取FFT算法17173NW-1-12NW-1-11NW-1-10NW-1-1x0 x4x1x5x2x6x3x74点点DFTX0X6X2X44点点DFTX1X3X5X71818X0X6X4X2X1X5X3X70NW1NW2NW3NW-1-1-1-1-1-1-1-1x0 x3x1x2x4x5x6x70NW2NW2点点DFT-1-1-1-12NW0NW-1-1-1-12点点DFT2点点DFT2点点DFT19190NW1NW2NW3NW-1-1-1-1x0 x3x1x2x4x5x6x70NW2NW2NW0NWX0X6X4X2X1X5X3X70NW0NW0NW0NW-1-1-1-1-1-1-1-12020FFT算法应用利用利用NN点复序列的点复序列的FFTFFT计算两个计算两个NN点实序列点实序列FFTFFT利用利用NN点复序列的点复序列的FFTFFT，计算，计算2 2NN点序列的点序列的FFTFFT利用利用FFTFFT计算计算IFFTIFFT2121利用N点复序列的FFT算法计算两个N点实序列FFTx1k,x2k是实序列，将其构成复序列yk=x1k+j x2kDFTx1k+j x2k=YR m+jYI m2222利用利用NN点复序列的点复序列的FFTFFT，计算，计算2 2NN点序列的点序列的FFTFFTyk是一个长度为2N的序列问题：如何利用N点FFT，计算4N点序列的FFT？2323利用FFT实现IFFT步骤：A)将X m取共轭C)对B)中结果取共轭并除以N24242024/3/12 2024/3/12 周二周二2525</p>