1、时间抽选法时间抽选法DIT:Decimation-In-Time频率抽选法频率抽选法DIF:Decimation-In-Frequency7-2 按按时间抽取的FFT算法一、按时间抽取的算法原理二、按时间抽取的算法特点三、按时间抽取FFT算法的其他形式22022-8-12一、按时间抽取的算法原理设序列点数 N=2L，L 为整数。若不满足，则补零N为2的整数幂的FFT算法称基-2FFT算法。将序列x(n)按n的奇偶分成两组：3 12221xrx rxrxr0,1,.,/2 1rN2022-8-124 则则x(n)的的DFT:111000NNNnknknkNNNnnnXkx n Wx n Wx n
2、 Wn为偶数n为奇数/2 1/2 121200221NNrkrkNNrrxr WxrW /2 1/2 1221200NNrkrkkNNNrrx rWWxrW /2 1/2 11/22/200NNrkkrkNNNrrx r WWxr W 12kNXkW Xk,0,1,./2 1r kN2022-8-125 再利用周期性求再利用周期性求X(k)的后半部分的后半部分 121122,/222XkXkNNNXkXkXkXk是以为周期的/22NkNkkNNNNWWWW 又2022-8-1261212()()()()()()2kNkNX kX kW XkNX kX kW Xk0,1,.,/21kN 一个一个
3、“蝶形运算蝶形运算”包含包含1次乘法，次乘法，2次加法次加法2022-8-1272022-8-12复数乘法复数乘法复数加法复数加法一个一个N/2点点DFT(N/2)2N/2(N/2 1)两个两个N/2点点DFTN 2/2N(N/2 1)一个蝶形一个蝶形12N/2个蝶形个蝶形N/2N总计总计8分解后的运算量：分解后的运算量：运算量减少了近一半运算量减少了近一半22/2/2/2NNN2/2 1/2N NNN2022-8-12N/2仍为偶数，进一步分解：N/2 N/491314(2)()(21)()xlxlxlxl0,1,.,/41lN13/2413/24()()()()()()4kNkNXkXkW
4、XkNXkXkWXk0,1,.,14Nk 2022-8-12102/2kkNNWW统一系数：10同理同理：25/2625/26()()()()()()4kNkNXkXkWXkNXkXkWXk0,1,.,14Nk 其中：其中：552()()(2)XkDFT xlDFT xl662()()(21)XkDFT xlDFT xl0,1,.,/41lN这样逐级分解，直到这样逐级分解，直到2点点DFT11N=2xk=x0,x1 1 0002xWxX 1 0 1 12xWxX0 x 1 x0X-102W 1 X 1 002xWx2022-8-1212x0 x2x1x3X10X11X20X212点DFT2点D
5、FT111104W14W02W02WX 0X 1X 2X 31,0,241mmXWmXmXm1,0,2241mmXWmXmXm2022-8-12132022-8-12144点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7111108W18W28W38W3,2,1,0,4281mmXWmXmXm3,2,1,0,281mmXWmXmXm2022-8-12154点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6
6、X 7111108W18W28W38W8点基2时间抽取FFT算法流图2022-8-1216第一级第一级第二级第二级第三级第三级2022-8-12171.计算速度 当N=2L时，共有L级蝶形，每级N/2个蝶形，每个蝶形有1次复数乘法2次复数加法。2log22FNNmLN复数乘法复数乘法：2logFaNLNN复数加法复数加法：222()2()loglog2FFmDFTNNNmFFTNN比较比较DFT 2022-8-12182022-8-1219复乘次数NN 2NN2log22022-8-12例.如果一台通用计算机的速度为平均每次复乘 ，每次复加 ，用它来计算512点的 ，问直接计算需要多少时间，用
7、 运算需要多少时间。5 s0.5 s DFT x nFFT解：(1)直接利用 计算：复乘次数为 ，复加次数为 。DFT2N1N N 复乘所需时间 626215 105 105121.31072TNs 复加所需时间 6260.5 1010.5 10512512 10.130816TNNs所以直接利用DFT 计算所需时间：121.441536TTTs2022-8-1220复乘所需时间 612625 10log25125 10log 5120.011522NTNs 622620.5 10log0.5 10512log 5120.002304TNNs复加所需时间 所以用 FFT 计算所需时间 120.
8、013824TTTs(2)利用 计算：复乘次数为 ，复加次数为 。FFT2log2NN2logNN2022-8-1221222.倒序排列n0n1n200011011001101倒位序倒位序 自然序自然序0000000010041001010220101106301100114100101551010113611011177111222 1 02()nn nn0 122()nn nn2 102()()x nnn n n23倒序倒序k0k1k2xk2 k1k0 x000 x100 x0100101112 xk k0 xk2 k101x110 x001x101x011x111010101012022-8-1224 3.同址运算 在同一级蝶形运算中，两信号只参与一次运算。4.蝶距规律240NW142NNW02NW12NNW三、按时间抽取FFT算法的其它形式252022-8-12262022-8-12272022-8-12282022-8-12
