论文部分内容阅读
本文从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)递归分解算法实数乘法次数最少的最佳算法。
In this paper, we decompose the transform matrix of DFT into the matrix Kronecker product form, and propose a general recursive decomposition algorithm (GRFA). Using different decomposition bases, a matrix Kronecker product representation of various recursive decomposition algorithms such as conventional FFT, MD-FFT, SR-FFT and RCFA can be derived. From GRFA, we prove that the minimum real number multiplication of DFT (2 ~ m) recursive decomposition algorithm is (m-3) 2 ~ m + 4. The SR-FFT or RCFA algorithm is the best algorithm for OFT (2 ~ m) recursive decomposition algorithm with the least real number of multiplications.