两个最佳短卷积算法

Two optimum algorithms for short convolutions

借助卷积的模多项式表示式及中国剩余定理推导出计算16点和11点短卷积的最佳算法,其算术复杂性分别为M16=35,A16=159;M11=41,A11=137,是目前公布的运算量最小的算法。与已有的7种最佳短卷积算法一起,使可嵌套计算的卷积长度范围由48种扩展到120种,满足了实际应用的需要。

Theory and practical applications indicate that the short convolutions nested algorithm is the most effective method in computing the convolutions with the non-high composite length. Two optimum algorithms for 16-point and 11-point cyclic convolutions were derived based on the Chinese remainder theory and the modular polynomial representations of convolutions. The arithmetic complexity are M16= 35, A10= 159 and M11=41,A11= 137, respectively, which means two new algorithms involving the least operation. Along with the seven known optimum short convolution algorithms, the kinds of calculable length of convolutions are extended from 48 to 120, which meets the needs of practical applications.