【摘要】 本文从DFT的变换矩阵分解成矩阵Kronecker积形式出发,提出一种通用递归分解算法(GRFA)。采用不同的分解基,可导出常规FFT、MD-FFT、SR-FFT和RCFA等各种递归分解算法的矩阵Kronecker积表示式。从GRFA出发,论证了DFT(2~m)递归分解算法的最小实数乘法次数是(m-3)2~m+4。SR-FFT或RCFA算法是OFT(2~m)递归分解算法实数乘法次数最少的最佳算法。更多还原

【Abstract】 In this paper a general recursive factorization algorithm (GRFA) for computing DFT(2m) on the basis of Kronecker product expression of factorization of the matrix is presented. Using distinct factorization radices, we have derived Kronecker product expression of some recursive factorization algorithms such as conventional FFT, Nakayama MD-FFT,Martens RCFA, Duhamel-Hollmann SR-FFT etc. As a result, the paper demonstrates that the minimum number of real multiplications required for DFT (2m) using GRFA is equal to (m-3)2m+4. SR-FFT or RCFA is the optimal recursive factorization algorithm with minimum number of real multiplications to compute DFT(2m).更多还原