《二按时间抽选的基2FFT算法教学课件》由会员分享，可在线阅读，更多相关《二按时间抽选的基2FFT算法教学课件（24页珍藏版）》请在装配图网上搜索。
1、二、按时间抽选的基-2FFT算法1、算法原理设序列点数 N=2L，L 为整数。若不满足，则补零 12221xrx rxrxr0,1,.,/2 1rN将序列x(n)按n的奇偶分成两组：N为2的整数幂的FFT算法称基-2FFT算法。则x(n)的DFT:111000NNNnknknkNNNnnnX kx n Wx n Wx n 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
2、 kN再利用周期性求X(k)的后半部分1212()()()()()()2kNkNX kX kW XkNX kX kW Xk0,1,.,/21kN 121122,/222XkXkNNNXkXkXkXk是以为周期的/22NkNkkNNNNWWWW 又分解后的运算量：复数乘法复数加法一个N/2点DFT(N/2)2N/2(N/2 1)两个N/2点DFTN 2/2N(N/2 1)一个蝶形12N/2个蝶形N/2N总计22/2/2/2NNN2/2 1/2N NNN运算量减少了近一半1314(2)()(21)()xlx lxlx l0,1,.,/4 1lN13/2413/24()()()()()()4kNkN
3、X kXkWXkNX kXkWXk0,1,.,14Nk N/2仍为偶数，进一步分解：N/2 N/425/2625/26()()()()()()4kNkNXkXkWXkNXkXkWXk0,1,.,14Nk 同理：其中：552()()(2)XkDFT x lDFT xl662()()(21)XkDFT x lDFT xl0,1,.,/4 1lN2/2kkNNWW统一系数：这样逐级分解，直到2点DFT当N=8时，即分解到X3(k)，X4(k)，X5(k)，X6(k)，k=0,10003322301033223(0)(0)(1)(0)(4)(1)(0)(1)(0)(4)NNXxWW xxW xXxWW
4、 xxW x/4 1133/43/400()()()NlklkNNllXkx l Wx l W0,1k 0004422401044224(0)(0)(1)(2)(6)(1)(0)(1)(2)(6)NNXxWW xxW xXxWW xxW x/4 1144/44/400()()()NlklkNNllXkx l Wx l W0,1k 2、运算量当N=2L时，共有L级蝶形，每级N/2个蝶形，每个蝶形有1次复数乘法2次复数加法。2log22FNNmLN复数乘法：2logFaNLNN复数加法：222()2()loglog2FFmDFTNNNmFFTNN比较DFT 3、算法特点1）原位计算1111()()
5、()()()()rmmmNrmmmNXkXkXj WXjXkXj Wm表示第m级迭代，k，j表示数据所在的行数2）倒位序倒位序自然序0000000010041001010220101106301100114100101551010113611011177111n0n1n2000110110011012 102()()x nnn n n2 102()nn n n0 122()nn n n3）蝶形运算对N=2L点FFT，输入倒位序，输出自然序，第m级运算每个蝶形的两节点距离为 2m1第m级运算：1111111()()(2)(2)()(2)mrmmmNmmrmmmNXkXkXkWXkXkXkW 蝶形运算两节点的第一个节点为k值，表示成L位二进制数，左移L m位，把右边空出的位置补零，结果为r的二进制数。rNW 的确定2()2L mrk 4）存储单元输入序列x(n):N个存储单元rNW系数 ：N/2个存储单元4、DIT算法的其他形式流图输入倒位序输出自然序输入自然序输出倒位序输入输出均自然序相同几何形状 输入倒位序输出自然序 输入自然序输出倒位序
二按时间抽选的基2FFT算法教学课件
