FFTFFT算法分类算法分类: :时间抽选法时间抽选法DIT: Decimation-In-Time频率抽选法频率抽选法DIF: Decimation-In-Frequency17-2 按按时间抽取的FFT算法一、按时间抽取的算法原理二、按时间抽取的算法特点三、按时间抽取FFT算法的其他形式2024/7/192一、按时间抽取的算法原理设序列点数 N = 2L，L 为整数。若不满足，则补零N为2的整数幂的FFT算法称基-2FFT算法。将序列x(n)按n的奇偶分成两组：2024/7/193则则x(n)的的DFT:2024/7/194再利用周期性求再利用周期性求X(k)的后半部分的后半部分2024/7/195一个一个“蝶形运算蝶形运算”包含包含1次乘法，次乘法，2次加法次加法2024/7/1962024/7/197复数乘法复数乘法复数加法复数加法一个一个N / 2点点DFT(N / 2)2N / 2 (N / 2 1)两个两个N / 2点点DFTN 2 / 2N (N / 2 1)一个蝶形一个蝶形12N / 2个蝶形个蝶形N / 2N总计总计分解后的运算量：分解后的运算量：运算量减少了近一半运算量减少了近一半2024/7/198N / 2仍为偶数，进一步分解：N / 2 N / 42024/7/19910同理同理：其中：其中：这样逐级分解，直到这样逐级分解，直到2点点DFTN=2xk=x0, x12024/7/1911x0x2x1x3X10X11X20X212点DFT2点DFT-1-1-1-1X 0X 1X 2X 32024/7/19124点基2时间抽取FFT算法流图2024/7/19134点DFT4点DFTx0x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-12024/7/19144点DFT4点DFTx0x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-18点基2时间抽取FFT算法流图2024/7/1915第一级第一级第二级第二级第三级第三级2024/7/19161.计算速度 当N = 2L时，共有L级蝶形，每级N / 2个蝶形，每个蝶形有1次复数乘法2次复数加法。复数乘法复数乘法：复数加法复数加法：比较比较DFT 2024/7/19172024/7/1918复乘次数NN 22024/7/1919例 .如果一台通用计算机的速度为平均每次复乘 ，每次复加 ，用它来计算512点的 ，问直接计算需要多少时间，用 运算需要多少时间。 解：(1)直接利用 计算： 复乘次数为 ，复加次数为 。 复乘所需时间 复加所需时间 所以直接利用DFT 计算所需时间： 2024/7/1920复乘所需时间 复加所需时间 所以用 FFT 计算所需时间 (2) 利用 计算： 复乘次数为 ，复加次数为 。 2024/7/1921222.倒序排列n0n1n200011011001101倒位序倒位序 自然序自然序0000000010041001010220101106301100114100101551010113611011177111倒序倒序k0k1k2xk2 k1k0x000x100x0100101112 xk k0xk2 k101x110x001x101x011x111010101012024/7/192324 3.同址运算 在同一级蝶形运算中，两信号只参与一次运算。 4.蝶距规律三、按时间抽取FFT算法的其它形式2024/7/19252024/7/19262024/7/19272024/7/1928