通过理论推导、定量分析和实验设计的研究方法分析了非 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 which N is not the integer power of 2, different combinations and composite sequences of N’s decomposition factors are analyzed. The experimental result indicates, under certain conditions, for the mixed-radix FFT of the same FFT point N, the computational complexity of the mixed-radix FFT algorithm relates to the size of the total K of N’s decomposition factors, but has nothing to do with composite sequences of N’s decomposition factors. An idea is proposed to establish a matching library of the combinations of N’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.