第4章 快速傅立叶变换问题的提出问题的提出解决问题的思路与方法解决问题的思路与方法 基基2 2时间抽取时间抽取FFTFFT算法算法基基2 2时间抽取时间抽取FFTFFT算法的计算复杂度算法的计算复杂度基基2 2时间抽取时间抽取FFTFFT算法流图规律算法流图规律基基2 2频率抽取频率抽取FFTFFT算法算法FFTFFT算法的实际应用算法的实际应用问题的提出问题的提出4点序列点序列2，3，3，2 DFT的计算复杂度的计算复杂度复数加法复数加法 N(N-1)复数乘法复数乘法 N 2如何提高DFT的运算效率?解决问题的思路解决问题的思路1. 将长序列DFT分解为短序列的DFT2. 利用旋转因子 的周期性、对称性、可约性。旋转因子 的性质1)周期性周期性2) 对称性对称性3)可约性可约性解决问题的方法解决问题的方法将时域序列逐次分解为一组子序列，利用旋转因子的特性，由子序列的DFT来实现整个序列的DFT。基基2时间抽取时间抽取(Decimation in time)FFT算法算法基基2频率抽取频率抽取(Decimation in frequency)FFT算算法法基2时间抽取FFT算法流图N=2xk=x0, x14点基2时间抽取FFT算法流图x0x2x1x3X10X11X20X212点DFT2点DFT-1-1-1-1X 0X 1X 2X 34点基2时间抽取FFT算法流图8点基2时间抽取FFT算法流图4点DFT4点DFTx0x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-14点DFT4点DFTx0x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-18点基2时间抽取FFT算法流图基基2 2时间抽取时间抽取FFTFFT算法算法第一级第一级第二级第二级第三级第三级算法的计算复杂度算法的计算复杂度复乘次数复乘次数NN 2基基2 2时间抽取时间抽取FFTFFT算法流图算法流图第一级第一级第二级第二级第三级第三级FFT算法流图旋转因子 规律第二级的蝶形系数为 ，蝶形节点的距离为2。第一级的蝶形系数均为 ，蝶形节点的距离为1。第三级的蝶形系数为 ，蝶形节点的距离为4。第M级 的蝶形系数为 ，蝶形节点的距离为N /2。倒序倒序k0k1k2xk2 k1k0x000x100x0100101112 xk k0xk2 k101x110x001x101x011x11101010101 基基2频率抽取频率抽取FFT算法算法3NW-1-12NW-1-11NW-1-10NW-1-1x0x4x1x5x2x6x3x74点点DFTX0X6X2X44点点DFTX1X3X5X7X0X6X4X2X1X5X3X70NW1NW2NW3NW-1-1-1-1-1-1-1-1x0x3x1x2x4x5x6x70NW2NW2点点DFT-1-1-1-12NW0NW-1-1-1-12点点DFT2点点DFT2点点DFT0NW1NW2NW3NW-1-1-1-1-1-1-1-1x0x3x1x2x4x5x6x70NW2NW2NW0NWX0X6X4X2X1X5X3X70NW0NW0NW0NW-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1FFT算法应用算法应用利用利用利用利用N N点复序列的点复序列的点复序列的点复序列的FFTFFT计算两个计算两个计算两个计算两个N N点实序列点实序列点实序列点实序列FFTFFT利用利用利用利用N N点复序列的点复序列的点复序列的点复序列的FFTFFT，计算计算计算计算2 2N N点序列的点序列的点序列的点序列的FFTFFT利用利用利用利用FFTFFT计算计算计算计算IFFTIFFT利用利用N点复序列的点复序列的FFT算法计算算法计算两个两个N点实序列点实序列FFTx1k, x2k是实序列，将其构成复序列yk=x1k+j x2kDFTx1k+j x2k=YR m+jYI m利用利用利用利用N N点复序列的点复序列的点复序列的点复序列的FFTFFT，计算计算计算计算2 2N N点序列的点序列的点序列的点序列的FFTFFTyk是一个长度为2N的序列问题：如何利用利用N点点FFT，计算计算4N点序列的点序列的FFT？利用利用FFT实现实现IFFT步骤：A) 将X m取共轭C) 对B)中结果取共轭并除以N