On fast algorithms for one-dimensional digital signal processing in finite integer and complex integer rings

Abstract

In this work, we present and analyze a number theoretic approach to computing one-dimensional cyclic convolution of sequences defined in finite integer and complex integer rings. A fundamental result of this work is that under the nonrestrictive condition, (N, M) = 1, the algorithms defined in finite integer and complex integer rings are as intensive computationally as the corresponding algorithms defined in rational and complex rational number systems only in the worst case. They simplify considerably for a large number of cases of importance in digital signal processing.