—大点数圆卷积算法设计

给出一种新的大点数基２长度的圆卷积算法。以往在计算圆卷积时常采用余数定理和多项式乘积，它可以对某些小点数圆卷积设计最少乘法次数的算法，并且结合这些算法可以构成具有较少乘法次数的大点数圆卷积算法。文中圆卷积计算被视为矩阵向量积。通过建立圆卷积矩阵中行向量之间和列向量之间的相关性可以压缩圆卷积矩阵，使矩阵向量积的乘法次数大大减少。这个过程对于基２长度的圆卷积矩阵可以重复进行下去，因此能够得到快速有效的基２圆卷积算法。

Design of Large Point Circular Convolution Algorithm

A new large point radix2 circular convolution algorithm is proposed in this paper. Conventionally Chinese remainder theorem and polynomial product are used to compute circular convolution because not only they result in minimum multiplication circular convolution algorithm for small point but also they can construct large point circular convolution algorithm with number of multiplications as small as possible. However, the programming of this conventional algorithm is complicated in structure. In this paper, a circular convolution can be viewed as a matrixvector product. The matrix can be shrunk via establishing correlation between row vectors and column vectors of the matrix. Thus number of multiplications of the matrixvector product is greatly reduced. The shrinking process can be reiterated for radix2 circular convolution which is then computed rapidly and efficiently by proposed algorithm.