按时间抽选的基2FFT算法(PPT 30页)

1、算法原理
设输入序列长度为N=2M(M为正整数，
将该序列按时间顺序的奇偶分解为越来越短的子序列，
称为基2按时间抽取的FFT算法。也称为Coolkey-Tukey算法。
其中基2表示：N=2M，M为整数.若不满足这个条件，
可以人为地加上若干零值（加零补长）使其达到N=2M。
先将x(n)按n的奇偶分为两组，作变量置换:
当n=偶数时，令n=2r;
当n=奇数时，令n=2r+1;
..............................