Computational Algorithms for Syndrome Based Single Error Correction in Residue Number Systems
Hari Krishna Garg *
Department of Electrical and Computer Engineering, National University of Singapore, Singapore.
*Author to whom correspondence should be addressed.
Abstract
Error control via residue number systems continues to attract researchers’ attention as evidenced by recent publications dealing with their applications in digital communications and computing. In this paper, we present syndrome based decoding algorithms and analyze their algebraic structure for single error correction in such systems. The mathematical framework is also extended to single error correction and simultaneous multiple error detection. We also bring residue number system product codes under the same framework. Specifically, all the algorithms are based on the computation of a single syndrome value. Computational aspects are also studied along with conditions for the validity of the syndrome based algorithmic approach being described here. Numerous examples are given to illustrate the structure, properties, and decoding procedures associated with the algorithms.
Keywords: Computer arithmetic, Chinese remainder theorem (CRT), residue number systems (RNS), error control, redundant residue number systems (RRNS), single error correction (SEC), multiple error detection (MED).