混合基FFT算法运算量分析  

Computational complexity analysis on mixed-radix FFT

作　　者：程志鹏[1] 马琪[1] 竺红卫[2] 

机构地区：[1]杭州电子科技大学微电子CAD研究所,浙江杭州310018 [2]浙江大学超大规模集成电路设计研究所,浙江杭州310027

出　　处：《太赫兹科学与电子信息学报》2016年第6期-,共4页Journal of Terahertz Science and Electronic Information Technology

摘　　要：通过理论推导、定量分析和实验设计的研究方法分析了非2整数次幂点数N的混合基快速傅里叶变换(FFT)算法运算量大小与N分解因子的不同组合方式以及组合次序的关系。实验结果表明,在一定条件下,对于相同FFT点数N的混合基FFT的不同分解因子组合,其算法运算量与所有分解因子总和K的大小有关,但与因子的组合次序无关。最后提出了建立混合基FFT最小运算量的分解因子匹配库作为使用混合基FFT时的分解因子组合选择参考表的设想。为相关研究和实际应用的工程人员提供一定参考。Through the research method of theoretical derivation, quantitative analysis and design of experiment, the relationship among the computational complexity of the mixed-radix Fast Fourier Transform(FFT) algorithm in whichN is not the integer power of 2, different combinations and composite sequences ofN's decomposition factors are analyzed. The experimental result indicates, under certain conditions, for the mixed-radix FFT of the same FFT pointN, the computational complexity of the mixed-radix FFT algorithm relates to the size of the totalK ofN's decomposition factors, but has nothing to do with composite sequences ofN's decomposition factors. An idea is proposed to establish a matching library of the combinations ofN's decomposition factors for mixed-radix FFT, acting as a reference table for obtaining minimal computational complexity when using mixed-radix FFT. It can also provide reference for the related research and engineering personnel in the practical applications.

关 键 词：混合基快速傅里叶变换(FFT) 频谱扩散 分解因子 计算复杂度 

分 类 号：O174.22[理学—数学]