基二FFT的原理和算法

 以前在博客上放的基二FFT源程序，可读性是比较差的，现在已经改过程序，从新发上去了。这几天仔细的研究了一下基二FFT算法，受益非浅。现在简单的分析一下基二算法的原理。在VISIO里画了程序框图，呵呵。可是不知道怎么传上来，最后还是存为BMP格式的，传了上来。希望对大家有所帮助。源程序见我的另一篇文章《基二FFT的C语言实现》

    当N太大时，直接进行DFT运算，运算量会很大，这就对计算机的性能提出了很高的要求。但是利用周期性可以大大的降低运算量。利用周期性，可将N点DFT分解为两个N/2点的DFT。同理可以对x(n)进行继续分解，依次类推经过M-1次分解，最后将N点DFT分解成N/2个2点的DFT。N点DFT的一次时域分解图如图1

根据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变换。同一级中，每个蝶形的两个输入数据只对本蝶形有用，而且每个蝶形的输入、输出数据节点又同在一条水平线上，所以输出数据可以立即存入原输入数据所占用的存储单元。，这种方法可称为原址计算，可节省大量的存储单元。FFT算法的程序框图如图2

FFT算法的输出X(K)为自然顺序，但为了适应原位计算，其输入序列不是按x(n)的自然顺序排序，这种经过M-1次奇偶抽选后的排序为序列的倒序。因此，在运算之前应先对序列x(n)进行倒序。倒序的规律就是把顺序数的二进制位倒置，即可得到倒序值。倒序数是在M位二进制数最高位加一，逢2向右进位。对于 ，M位二进制数最高位的权值为N/2，且从左到右二进制位的权值依次为你N/4，N/8，···，2，1。因此，最高位加一相当于十进制运算J+N/2。（J表示当前倒序数的十进制数值）。倒序的程序框图如图3

 详细的解释请参考西安电子科学技术大学出版的《数字信号处理》

 

 

转自:http://zq2007.blog.hexun.com/4170886_d.html