FAST ALGORITHMS FOR COMPUTING ONE-DIMENSIONAL AND 2-DIMENSIONAL CONVOLUTION IN INTEGER POLYNOMIAL-RINGS

In a recent work, the factorization properties of polynomials defined over finite integer polynomial rings were analyzed. These properties, along with other results pertaining to polymomial theory, led to the d irect sum property and the American-Indian-Chinese extension of the Ch inese remainder theorem over such integer rings. The objective of this paper is to describe algorithms for computing the one- and two-dimens ional convolution of data sequences defined over finite integer rings. For one-dimensional convolution, algorithms for computing acyclic and cyclic convolution are described. For two-dimensional convolution, on ly the cyclic case is analyzed. Computational and other relevant aspec ts associated with the structure of these algorithms are also studied.