fft算法有很多的应用，尤其在信号测量和分析方面。由于该算法的计算量大，需要高速度的运算速度和一定容量的内存，一般采用dsp来做这方面的运算，但是随着现在单片机技术的发展，高速、大容量内存的单片机相继出现，在实际的数据测量和处理中有很大的用处，为了使问题方便表达，下面我们以基2，8点fft为例子加以说明。传统的基2变几何结构算法如下图表示，箭头上面的字代表了旋转因子中的k。图中输入的是按照码位颠倒的顺序来排放的，输出是自然顺序。

　　这种结构的特点是每个蝶形的输出数据仍然放在原来的输入数据存储单元内，于是只需要2n个存储单元(fft中的数据是复数形势，每一点需要两个单元存储)，但其缺点是不同级的同一位置蝶形的输入数据的寻址不固定，难以实现循环控制。
　　
　　对此结构进行进一步的变换，将第二级的输出不送回原处而是将其存储起来并按顺序存放，则第三级中间的两个蝶形跟着调换，并把输入按顺序排列，就变成了下图所示的固定结构的fft了。于是在蝶形变换的同时，其旋转因子也跟着做了调换。

　　从上面可以看出输出数据的顺序是不变的，因此每级几何结构是固定的，明显加快了fft的运算速度。

相关文章

• 上一篇： 神经网络在测控系统中的实现
• 下一篇： 滚筒式全自动洗衣机的程序控制器