小点数圆卷积算法设计

A Simple Small-N Circular Convolution Algorithm

给出一种新的乘法次数少的小点数圆卷积算法，以达到减小计算圆卷积乘法次数的目的．与传统算法相比，其特点是构造简单、运算功效好，计算中无需利用多项式运算及余数定理，Ｎ点圆卷积所需的乘法次数近似为Ｎ～２Ｎ．此方法可推广应用于大点数的圆卷积计算和大点数的快速傅里叶变换计算．

Stasinski discussed in 1986[4] and in 1992151 small-N circular convolution algorithms. In this paper, the author proposes a design of such algorithm believed to be simpler than that of Stasinski.Unlike Stasinski, the author's design does not require computation with polynomial nor the use of Chinese remainder theorem. An additional reason for the greater simplicity of the author,s design is believed to be that the author constructs a matrix with all column vectors correlated and with all row rectors correlated. Like Stasinski, the author's algorithm requires only approximately N-2N multiplications.