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

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

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

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 convention 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.