根据DFT的基二分解方法,可以发现在第L(L表示从左到右的运算级数,L=1,2,3…M)级中,每个蝶形的两个输入数据相距B=2^(L-1)个点,同一旋转因子对应着间隔为2^L点的2^(M-L)个蝶形。从输入端开始,逐级进行,共进行M级运算。在进行L级运算时,依次求出个2^(L-1)不同的旋转因子,每求出一个旋转因子,就计算完它对应的所有的2^(M-L)个蝶形。因此我们可以用三重循环程序实现FFT变换。同一级中,每个蝶形的两个输入数据只对本蝶形有用,而且每个蝶形的输入、输出数据节点又同在一条水平线上,所以输出数据可以立即存入原输入数据所占用的存储单元。这种方法可称为原址计算,可节省大量的存储单元。下面为算法流程图: 开始输入x(n),NN=2^M倒序L=1,MB=2^(L-1)J=0,B-1P=J*2^(M-1)k=J,N-1,2^LX(k)=X(k)+X(k+B)WX(k+B)=X(k)-X(k+B)W输出结果结束 FFT算法的输出X(K)为自然顺序,但为了适应原位计算,其输入序列不是按x(n)的自然顺序排序,这种经过M-1次奇偶抽选后的排序为序列的倒序。因此,在运算之前应先对序列x(n)进行倒序。倒序的规律就是把顺序数的二进制位倒置,即可得到倒序值。倒序数是在M位二进制数最高位加一,逢2向右进位。对于M位二进制数最高位的权值为N/2,且从左到右二进制位的权值依次为你N/4,N/8,···,2,1。因此,最高位加一相当于十进制运算J+N/2。(J表示当前倒序数的十进制数值) 本文来源:https://www.wddqw.com/doc/d57ee22f5b0102020740be1e650e52ea5518ce9a.html