快速傅立叶变换中的一种倒位序生成法  

AN ALGORITHM TO GENERATE REVERSE SEQUENCE IN FAST FOURIER TRANSFORM

作　　者：王芳[1] 张学锋[1] 程增会[1] 

机构地区：[1]安徽工业大学计算机学院,安徽马鞍山243002

出　　处：《计算机应用与软件》2011年第2期93-95,共3页Computer Applications and Software

基　　金：安徽省教育厅项目(2008jq1032)

摘　　要：快速傅立叶变换是离散傅立叶变换(DFT)的一种快速算法,它的出现使DFT的计算大大简化,运算时间可缩短一、二个数量级,从而使得离散傅立叶变换在信号分析与处理领域中得到了广泛的应用。在应用软件和硬件程序设计中要实现快速傅立叶变换算法,均涉及到序列的倒位序排列问题。针对该问题提出倒位序生成法,直接计算各自然顺序位置的倒位序数值,然后通过变址运算完成原数列的倒位序的排列。该方法对任何满足N=2M点的快速傅立叶变换,能很快实现其变换中序列的倒位序排列。该方法只涉及倒位序十进制数和顺序十进制数,不用对二进制数进行转换,简单易行,仿真实验结果证明算法可靠有效。Fast Fourier transform is a fast algorithm of discrete Fourier transform,its appearance greatly simplifies the calculation of DFT,and the computation time can be shortened by one or two orders of magnitude thereby.For the reason of that,the discrete Fourier transform has been widely used in signal analysis and processing fields.The issue of reverse sequence is involved in programming designs of both application software and hardware for achieving fast Fourier transform algorithm.In light of this,in the paper a generation algorithm for reverse sequence is proposed.It directly calculates the values of reverse ordinals in each natural sequential position,and then through the operation of addresses variation the ordering of reverse sequence of the primary sequence is achieved.For any FFT meets the point of N=2M,this algorithm can quickly realise the reverse sequence ordering of the transform.The method only involves the reverse sequence decimal numeral and ordinal decimal numeral,but does not need to transform the binary numeral,it is simple and easy to implement.Simulation results show that the algorithm is reliable and effective.

关 键 词：快速傅立叶变换 离散傅立叶变换 倒位序 倒位序生成法 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]