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

为了提高快速傅里叶变换的运算效率，减少运算时间，该文研究了FFT中倒序序列的计算。研究发现不同长度的倒序序列不相互独立，它们之间有深刻的联系，长度为N的倒序序列可以由长度为N/2的倒序序列生成。根据不同长度的倒序序列之间的相互关联性，给出了新的倒序序列的计算方法及相应的算法流程。通过计算仿真，验证了算法的正确性。该算法实现简单，而且运算效率高。与传统算法相比，新算法可将计算效率提高3个数量级。

New Approach for Calculating Inversed Order Sequence in FFT

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.