基于查找表的单基FFT原址倒序算法

Digit-reversal permutation algorithm based on look-up tables for in-place singleradix fast fourier transforms

单基快速Fourier变换(FFT)进行原址运算前需要对输入数据进行倒序,为了提高传统倒序算法的速度,在4个有关单基倒序定理的基础上,提出了基于查找表的单基快速Fourier变换原址倒序算法。该算法通过访问查找表,减少循环次数,简化倒序值的计算过程,从而提高速度。该算法所需查找表的规模不随点数增加而变大。仿真结果表明:该算法在计算基2倒序时,性能超过了现有算法,在计算非基2倒序时,比传统算法至少快80%,比现有的查找表算法最多慢15%。

Single-radix fast Fourier transforms （FFT） require digit-reversion before the ＂in-place＂ computations. For the sake of speed enhancement of conventional digit-reversion algorithms, we bring out four propositions, and propose a novel digit-reversion algorithm for single-radix FFT based on a look-up table. By accessing a look-up table, the algorithm reduces the number of cycles, simplifies the process computing the inverse value and enhances the speed. The table size is independent of the number of FFT points. Simulation results show that the performance of the proposed algorithm is significantly better than the others when the radix is 2 and the compution time is only 20% that of the conventional algorithm and at more 15% more than that of the existing algorithm based on look-up tables when the radix is greater than 2.