Rings, fields, the Chinese remainder theorem and an extension-Part II: applications to digital signal processing

Abstract

For pt. I, see ibid., vol. 41, no. 10, p. 641-55 (1994). In Part I of the research work, we introduced an extension to the well known Chinese remainder theorem for processing polynomials with coefficients defined over a finite integer ring. We term this extension as the American-Indian-Chinese extension of the Chinese remainder theorem. A systematic procedure for factorizing a monic polynomial into pairwise relatively prime monic factor polynomials over integer rings was presented. This factorization is based on the corresponding factor polynomials, monic and relatively prime, over the associated finite field containing prime number of elements. In this paper, we study the application of the theory developed in Part I to deriving computationally efficient algorithms for performing tasks having multilinear form. Especially, we focus on the cyclic and acyclic convolution as they are two of the most frequently occurring computationally intensive tasks in digital signal processing.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>