Abstract
The Chinese remainder theorem is a fundamental technique widely employed in digital signal processing for designing fast algorithms for computing convolutions. Classically, it has two versions. One is over a ring of integers and the second is over a ring of polynomials with coefficients defined over a field. In our previous papers, we developed an extension to this well-known theorem for the case of a ring of polynomials with coefficients defined over a finite ring of integers. The objective was to generalize number-theoretictransforms, which turn out to be a special case of this extension. This paper focuses on the extension of the Chinese remainder theorem for processing complex-valued integer sequences. Once again, the present work generalizes the complex-number-theoretic transforms. The impetus for this work is provided by the occurrence of complex integer sequences in digital signal processing and the desire to process them using exact arithmetic.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
C. M. Rader, Discrete Convolutions via Mersenne Tranforms,IEEE Trans. on Computers, vol. c-21, pp. 1269–1273, December 1972.
R. C. Agarwal and C.S. Burrus, Fast Convolution Using Fermat Number Tranforms with Applications to Digital Filtering,IEEE Trans. on ASSP, vol. ASSP-22, no. 2, pp. 87–97, April 1974.
R. C. Agarwal and C. S. Burrus, Number Theoretic Transforms to Implement Fast Digital Convolution,Proceedings IEEE, vol. 63, pp. 550–560, April 1975.
J. H. McClellan, Hardware Realization of a Fermat Number Transform,IEEE Trans. on ASSP, vol. ASSP-24, no. 3, pp. 216–225, June, 1976.
H. J. Nussbaumer,Fast Fourier Transform and Convolution Algorithms, second edition, Springer-Verlag, New York, 1982.
D. G. Myers,Digital Signal Processing — Efficient Convolution and Fourier Transform Techniques, Prentice-Hall, Englewood Cliffs, NJ, 1990.
J. H. McClellan and C. M. Rader,Number Theory in Digital Signal Processing, Prentice-Hall, Englewood Cliffs, NJ, 1979.
K.-Y. Lin, B. Krishna, and H. Krishna, Rings, Fields, the Chinese Remainder Theorem and an Extension, Part I: Theory,IEEE Trans. on Circuits and Systems, accepted for publication, to appear in 1994.
H. Krishna, K.-Y. Lin, and B. Krishna, Rings, Fields, the Chinese Remainder Theorem and an Extension, Part II: Applications to Digital Signal Processing,IEEE Trans. on Circuits and Systems, accepted for publication, to appear in 1994.
L.K. Hua,Introduction to Number Theory, Springer-Verlag, New York, 1982.
H. Krishna, B. Krishna, K.-Y. Lin, and J.-D. Sun,Computational Number Theory and Digital Signal Processing, Fast Algorithms and Error Control Techniques, CRC Press, 1994.
H. Krishna, On factorization of polynomials and direct sum properties in integer polynomial rings,Circuits, Systems, and Signal Processing, submitted.
H. Krishna, B. Krishna, C.C. Ko, and H. Liu, Fast algorithms for computing one and two dimensional convolution in integer polynomial rings,IEEE Trans. on Sig. Proc., submitted.
Author information
Authors and Affiliations
Additional information
This paper was completed in the fall of 1992 when H. Krishna was a visiting professor at the Department of Electrical Engineering, I.I.T. Delhi, N. Delhi, 110016, India.
Rights and permissions
About this article
Cite this article
Krishna, H., Lin, K.Y. & Krishna, B. The AICE-CRT and digital signal processing algorithms: The complex case. Circuits Systems and Signal Process 14, 69–85 (1995). https://doi.org/10.1007/BF01183749
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01183749