On algorithms for digital signal processing of sequences (Q1922614)

The authors analyze the algebraic structure of fast algorithms for computing one- and two-dimensional convolutions of sequences defined over the fields of rational and complex rational numbers. The algorithms are based on factorization properties of polynomials and the direct sum property of modulo computation over such fields. Algorithms are described for cyclic as well as acyclic convolutions. It is shown that under certain nonrestrictive conditions, all the previously defined algorithms over the fields of rational and complex rational numbers are also valid over the rings of finite rings of finite integers. Examples are presented to illustrate the results.