开始 送入x(n),M L=1,M P=2- k=J,N-1,2 (k)∈X(k)+X(k+B)W x(k+B)∈X(k)-X(k+B)W 结束 5、序列倒序 DIT-FFT算法的输出X(k)为自然顺序,但为了适应原位计算,其输入序列 不是按x(n)的自然顺序排序,这种经过M1次偶奇抽选后的排序称为序列x(n) 的倒序。因此,在运算之前应先对序列x(n)进行倒序 11 图4.2.7形成倒序的树状图(N=23)开 始 送入x(n)，M N＝ 2 M 倒 序 L＝ 1 , M Ｊ＝ 0 , B－ 1 P＝ 2 M －LJ k＝ J , N－1 , 2L p N p N X k B X k X k B W X k X k X k B W ( ) ( ) ( ) ( ) ( ) ( ) +  − +  + + 输 出 结 束 B 2 L－1 5、序列倒序 DIT-FFT 算法的输出 X k( ) 为自然顺序，但为了适应原位计算，其输入序列 不是按 x n( ) 的自然顺序排序，这种经过 M-1 次偶奇抽选后的排序称为序列 x n( ) 的倒序。因此，在运算之前应先对序列 x n( ) 进行倒序。 0 1 0 1 0 1 0 1 0 1 0 1 0 1 (n2 n1 n0 ) 2 000 0 4 2 6 1 5 3 7 100 010 110 001 101 011 111 图 4.2.7 形成倒序的树状图(N=23)