按时间抽取的FFT算法.ppt

《按时间抽取的FFT算法.ppt》由会员分享，可在线阅读，更多相关《按时间抽取的FFT算法.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、FFTFFT算法分类算法分类:时间抽选法时间抽选法DIT:Decimation-In-Time频率抽选法频率抽选法DIF:Decimation-In-Frequency7-2 按按时间抽取的FFT算法一、按时间抽取的算法原理二、按时间抽取的算法特点三、按时间抽取FFT算法的其他形式22022/12/11一、按时间抽取的算法原理设序列点数 N=2L，L 为整数。若不满足，则补零N为2的整数幂的FFT算法称基-2FFT算法。将序列x(n)按n的奇偶分成两组：32022/12/114则则x(n)的的DFT:2022/12/115再利用周期性求再利用周期性求X(k)的后半部分的后半部分2022/12/

2、116一个一个“蝶形运算蝶形运算”包含包含1次乘法，次乘法，2次加法次加法2022/12/1172022/12/11复数乘法复数乘法复数加法复数加法一个一个N/2点点DFT(N/2)2N/2(N/2 1)两个两个N/2点点DFTN 2/2N(N/2 1)一个蝶形一个蝶形12N/2个蝶形个蝶形N/2N总计总计8分解后的运算量：分解后的运算量：运算量减少了近一半运算量减少了近一半2022/12/11N/2仍为偶数，进一步分解：N/2 N/492022/12/111010同理同理：其中：其中：这样逐级分解，直到这样逐级分解，直到2点点DFT11N=2xk=x0,x12022/12/1112x0 x2

3、x1x3X10X11X20X212点DFT2点DFT-1-1-1-1X 0X 1X 2X 32022/12/11132022/12/114点基2时间抽取FFT算法流图144点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-12022/12/11154点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-18点基2时间抽取FFT算法流图2022/12/1116第一级第一级第二级第

4、二级第三级第三级2022/12/11171.计算速度 当N=2L时，共有L级蝶形，每级N/2个蝶形，每个蝶形有1次复数乘法2次复数加法。复数乘法复数乘法：复数加法复数加法：比较比较DFT 2022/12/11182022/12/1119复乘次数NN 22022/12/11例.如果一台通用计算机的速度为平均每次复乘 ，每次复加 ，用它来计算512点的 ，问直接计算需要多少时间，用 运算需要多少时间。解：(1)直接利用 计算：复乘次数为 ，复加次数为 。复乘所需时间 复加所需时间 所以直接利用DFT 计算所需时间：2022/12/1120复乘所需时间 复加所需时间 所以用 FFT 计算所需时间(2

5、)利用 计算：复乘次数为 ，复加次数为 。2022/12/1121222.倒序排列n0n1n200011011001101倒位序倒位序 自然序自然序00000000100410010102201011063011001141001015510101136110111771112223倒序倒序k0k1k2xk2 k1k0 x000 x100 x0100101112 xk k0 xk2 k101x110 x001x101x011x111010101012022/12/1124 3.同址运算 在同一级蝶形运算中，两信号只参与一次运算。4.蝶距规律24三、按时间抽取FFT算法的其它形式252022/12/11262022/12/11272022/12/11282022/12/11