一种按时间抽取的混合基实序列高效FFT算法

An Efficient Mixed-Radix DIT 2N Real-Valued FFT Algorithm

针对2N点实序列FFT的实现,分析了FFT运算的基本原理,并在基本原理的基础上介绍了一种按时间抽取的混合基FFT算法.此算法采用"包装"算法和基2-基4混合算法结合的方法进行运算.通过复杂度分析,显示了此算法与传统的单一基2或基4的FFT相比,大大减少了计算过程中所需的实加法的个数;当点数大于1024时,所需实乘法的个数也有所减少.这是一种实序列FFT的高效低复杂度算法.

To the question of the realization that the 2N real-valued inputs FFT（RFFT）, the basic theory of FFT algorithm is analyzed, and on base of it, this paper introduces a mixed-radix DIT FFT algorithm. The mixed-radix DIT FFT algorithm is realized by using packaging algorithm and radix-2 FFT mixed with radix-4 FFT. Analyzing the computational complexity of algorithm, it indicates that this efficient algorithm has the advantage of fewer real additions than the con- vention radix-2 or radix-4 FFT algorithm for RFFT. In addition, the number of real multiplication is reduced too when 2N 〉 1024. This is an RFFT algorithm which is efficient and has lower computational complexity.