按时间抽取的FFT算法.pptx

FFTFFT算法分类算法分类:时间抽选法时间抽选法DIT:Decimation-In-Time频率抽选法频率抽选法DIF:Decimation-In-Frequency7-2 7-2 按时间抽取的按时间抽取的FFT算法算法7-2 按按时间抽取的FFT算法一、按时间抽取的算法原理二、按时间抽取的算法特点三、按时间抽取FFT算法的其他形式22024/4/19 周五一、按时间抽取的算法原理设序列点数 N=2L，L 为整数。若不满足，则补零N为2的整数幂的FFT算法称基-2FFT算法。将序列x(n)按n的奇偶分成两组：32024/4/19 周五4则则x(n)的的DFT:2024/4/19 周五5再利用周期性求再利用周期性求X(k)的后半部分的后半部分2024/4/19 周五6一个一个“蝶形运算蝶形运算”包含包含1次乘法，次乘法，2次加法次加法2024/4/19 周五72024/4/19 周五复数乘法复数乘法复数加法复数加法一个一个N/2点点DFT(N/2)2N/2(N/2 1)两个两个N/2点点DFTN 2/2N(N/2 1)一个蝶形一个蝶形12N/2个蝶形个蝶形N/2N总计总计8分解后的运算量：分解后的运算量：运算量减少了近一半运算量减少了近一半2024/4/19 周五N/2仍为偶数，进一步分解：N/2 N/492024/4/19 周五1010同理同理：其中：其中：这样逐级分解，直到这样逐级分解，直到2点点DFT基2时间抽取FFT算法流图11N=2xk=x0,x12024/4/19 周五4点基2时间抽取FFT算法流图12x0 x2x1x3X10X11X20X212点DFT2点DFT-1-1-1-1X 0X 1X 2X 32024/4/19 周五132024/4/19 周五4点基2时间抽取FFT算法流图8点基2时间抽取FFT算法流图144点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-12024/4/19 周五154点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-18点基2时间抽取FFT算法流图2024/4/19 周五基基2时间抽取时间抽取FFT算法算法16第一级第一级第二级第二级第三级第三级2024/4/19 周五二、按时间抽取的算法特点171.计算速度 当N=2L时，共有L级蝶形，每级N/2个蝶形，每个蝶形有1次复数乘法2次复数加法。复数乘法复数乘法：复数加法复数加法：比较比较DFT 2024/4/19 周五182024/4/19 周五算法的计算复杂度算法的计算复杂度19复乘次数NN 22024/4/19 周五例.如果一台通用计算机的速度为平均每次复乘 ，每次复加 ，用它来计算512点的 ，问直接计算需要多少时间，用 运算需要多少时间。解：(1)直接利用 计算：复乘次数为 ，复加次数为 。复乘所需时间 复加所需时间 所以直接利用DFT 计算所需时间：2024/4/19 周五20复乘所需时间 复加所需时间 所以用 FFT 计算所需时间(2)利用 计算：复乘次数为 ，复加次数为 。2024/4/19 周五21222.倒序排列n0n1n200011011001101倒位序倒位序 自然序自然序00000000100410010102201011063011001141001015510101136110111771112223倒序倒序k0k1k2xk2 k1k0 x000 x100 x0100101112 xk k0 xk2 k101x110 x001x101x011x111010101012024/4/19 周五24 3.同址运算 在同一级蝶形运算中，两信号只参与一次运算。4.蝶距规律24三、按时间抽取FFT算法的其它形式252024/4/19 周五262024/4/19 周五272024/4/19 周五282024/4/19 周五