(4.6.1)--4.6按时间抽取的基-2FFT算法.pdf
第四章 离散傅里叶变换及其快速算法4.6.2按时间抽取的基-2FFT算法 设设输输入入序序列列长长度度为为N=2M(M为为正正整整数数)，将将该该序序列列按按时时间间顺顺序序的的奇奇偶偶分分解解为为越越来来越越短短的的子子序序列列，称称为为基基2按按时时间间抽抽取取的的FFT算算法法。也也称称为为Coolkey-Tukey算算法法。其其中中基基数数2-N=2M，M为为整整数数.若若不不满满足足这这个个条条件件，可可以以加加零零补补长长,使使其其达达到到 N=2M。1.算算法法原原理理 设设一一序序列列x(n)的的长长度度为为L=9,应应加加零零补补长长为为N=24=16 应应补补7个个零零值值。0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 nx(n)4.6.2按时间抽取的基-2FFT算法设设序序列列点点数数 N=2M，M为为整整数数。若若不不满满足足，则则补补零零。1,1,0 ),()12(1,1,0 ),()2(DFT)()()(DFT)(2210NNNnknNrrhrxnrrgrxnnnxWnxkXnx为奇数时：为偶数时：，的奇偶分为两组作按将为：时时间间抽抽选选FFT算算法法，分分解解遵遵循循两两条条规规则则：时时间间上上进进行行奇奇偶偶分分解解；频频率率上上进进行行前前后后分分解解。4.6.2按时间抽取的基-2FFT算法)()()12()2()12()2()12()2()()()(21101010210210)12(102101022222222kXWkXWrxWWrxWrxWWrxWrxWrxWnxWnxkXkNrrkkNrrkrrkNkNrrkNrkrNrrkNNnnNnnkNnnkNNNNNNNNN奇数偶数1021012222)12()()2()(NNNNrrkrrkWrxkXWrxkX其中：4.6.2按时间抽取的基-2FFT算法rkNNkrNkNNkNWWWW2)2(2)2(,其中)()()2()2()2(1212,.1,0),()()(120DFT2DFT,2)(),(2)(),(212)2(1212121kXWkXNkXWNkXNkXNNkNkkXWkXkXNkNNNrxrxNkXkXkNNkNkN后半部分前半部分来计算点的可以用两个点的所以的长度也为，而的长度为4.6.2按时间抽取的基-2FFT算法蝶蝶形形运运算算问问题题：一一个个蝶蝶形形运运算算需需要要几几次次复复数数乘乘法法和和复复数数加加法法？)1,1,0()()()2()1,1,0()()()(221221NkNNkNkkXWkXNkXkkXWkXkX，1 1 11-1 1)()()(21kXWkXkXkN)()()2(21kXWkXkNXkN)(1kX)(2kXkNW蝶形运算-1 1)1()1()1(211XWXXN)1()1()12(211XWXNXN)1(1X)1(2XkNW-1 1)0()0()0(201XWXXN)0()0()2(201XWXNXN)0(1X)0(2X0NW-1 1)()()(21kXWkXkXkN)()()2(21kXWkXkNXkN)(1kX)(2kXkNW1次复乘,2次复加1次复乘,2次复加1次复乘,2次复加运算量分析(1 1)N N/2 2点点的的D DF FT T运运算算量量:复复乘乘次次数数:复复加加次次数数:(2 2)两两个个N N/2 2点点的的D DF FT T运运算算量量:复复乘乘次次数数:复复加加次次数数:(3 3)N N/2 2个个蝶蝶形形运运算算的的运运算算量量:复复乘乘次次数数:复复加加次次数数:复乘:复加:4)2(22NN)12(2NN22N)12(NN2NNN222)12(2NNNN22222NNN总总共共运运算算量量:但但是是,N N点点D DF FT T的的复复乘乘为为N N2 2 ;复复加加N N(N N-1 1);与与分分解解后后相相比比可可知知,计计算算工工作作点点差差不不多多减减少少 一一半半。运算量谢 谢Thanks
