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

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

作　　者：张卉[1] 刘永刚[1] 阎跃鹏[1] 

机构地区：[1]中国科学院微电子研究所,北京100029

出　　处：《微电子学与计算机》2008年第11期43-46,共4页Microelectronics & Computer

摘　　要：针对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.

关 键 词：快速傅立叶变换 按时间抽取 混合基 实序列快速傅立叶变换 

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