快速傅里叶变换中计算倒序的新思路  

New Approach for Calculating Inversed Order Sequence in FFT

作　　者：刘大庆[1] 林浩然 陈树越[1] 

机构地区：[1]常州大学信息科学与工程学院,常州213164

出　　处：《电子与信息学报》2018年第3期758-762,共5页Journal of Electronics & Information Technology

基　　金：国家自然科学基金(51176016)~~

摘　　要：为了提高快速傅里叶变换的运算效率,减少运算时间,该文研究了FFT中倒序序列的计算。研究发现不同长度的倒序序列不相互独立,它们之间有深刻的联系,长度为N的倒序序列可以由长度为N/2的倒序序列生成。根据不同长度的倒序序列之间的相互关联性,给出了新的倒序序列的计算方法及相应的算法流程。通过计算仿真,验证了算法的正确性。该算法实现简单,而且运算效率高。与传统算法相比,新算法可将计算效率提高3个数量级。In order to improve the efficiency of Fast Fourier Transform（FFT） and reduce the computation time, an algorithm of inversed order sequence in FFT is studied. It is revealed that the inversed order sequences with different length N are not independent but have a deep connection, that is, the inversed order sequence with length N can be produced by the one with length N/2 according to a specific schedule. Based on the interconnectedness, a new approach for calculating the inversed order sequence with length N is proposed and the corresponding procedure flow is shown. The algorithm is simulated and the correctness of the algorithm is verified. The algorithm not only can be realized simply, but also has high efficiency. Compared with the traditional method, the new algorithm can improve the computing efficiency by three orders of magnitude.

关 键 词：数字信号处理 快速傅里叶变换 序列 倒序 

分 类 号：TN911.72[电子电信—通信与信息系统]