Research ArticleOpen AccessGoogle Scholar indexed

Parallel Algorithms for Residue Scaling and Error Correction in Residue Arithmetic

¹ Department of Electrical Engineering, National Tsing Hua University, Hsinchu City, Chinese Taipei
² Department of Electrical Engineering, National Tsing Hua University, Hsinchu City, Chinese Taipei

Wireless Engineering and Technology·Volume 04 (2013)·Pages 198–213·Published 24 September 2013·DOI10.4236/wet.2013.44029

Abstract

In this paper, we present two new algorithms in residue number systems for scaling and error correction. The first algorithm is the Cyclic Property of Residue-Digit Difference (CPRDD). It is used to speed up the residue multiple error correction due to its parallel processes. The second is called the Target Race Distance (TRD). It is used to speed up residue scaling. Both of these two algorithms are used without the need for Mixed Radix Conversion (MRC) or Chinese Residue Theorem (CRT) techniques, which are time consuming and require hardware complexity. Furthermore, the residue scaling can be performed in parallel for any combination of moduli set members without using lookup tables.

KeywordsChinese Remainder Theorem (CRT)Error CorrectionError DetectionParallel Residue ScalingResidue Number Systems (RNS)Target Race Distance (TRD)Target Residue-Digit Difference

R. W. Watson, “Error Detection and Correction and Other Residue-Interacting Operations in a Redundant Residue Number System,” University of California, Berkeley, 1965.
R. W. Watson and C. W. Hastings, “Self-Checked Computation Using Residue Arithmetic,” Proceedings of the IEEE, Vol. 54, No. 12, 1966, pp. 1920-1931. http://dx.doi.org/10.1109/PROC.1966.5275
S. S. S. Yau and Y. C. Liu, “Error Correction in Redundant Residue Number Systems,” IEEE Transactions on Computers, Vol. C-22, No. 1, 1973, pp. 5-11. http://dx.doi.org/10.1109/T-C.1973.223594
D. Mandelbaum, “Error Correction in Residue Arithmetic,” IEEE Transactions on Computers, Vol. C-21, No. 6, 1972, pp. 538-545.
F. Barsi and P. Maestrini, “Error Correcting Properties of Redundant Residue Number Systems,” IEEE Transactions on Computers, Vol. 22, No. 3, 1973, pp. 307-315. http://dx.doi.org/10.1109/T-C.1973.223711
F. Barsi and P. Maestrini, “Error Detection and Correction by Product Codes in Residue Number Systems,” IEEE Transactions on Computers, Vol. 23, No, 9, 1974, pp. 915-924. http://dx.doi.org/10.1109/T-C.1974.224055
V. Ramachandran, “Single Residue Error Correction in Residue Number Systems,” IEEE Transactions on Computers, Vol. C-32, No. 5, 1983, pp. 504-507. http://dx.doi.org/10.1109/TC.1983.1676264
W. K. Lenkins and E. J. Altman, “Self-Checking Properties of Residue Number Error Checkers Based on Mixed Radix Conversion,” IEEE Transactions on Circuits and Systems, Vol. 35, No. 2, 1988, pp. 159-167. http://dx.doi.org/10.1109/31.1717
W. K. Lenkins, “Residue Number System Error Checking Using Expanded Projection,” Electronics Letters, Vol. 18, No. 21, 1982, pp. 927-928. http://dx.doi.org/10.1049/el:19820632
W. K. Lenkins, “The Design of Error Checkers for SelfChecking Residue Number Arithmetic,” IEEE Transactions on Computers, Vol. C-32, No. 4, 1983, pp. 388-396. http://dx.doi.org/10.1109/TC.1983.1676240
M. H. Etzel and W. K. Jenkins, “Redundant Residue Number Systems for Error Detection and Correction in Digital Filters,” IEEE Transactions on Acoustics Speech and Signal Processing, Vol. 28, No. 10, 1980, pp. 588-544.
C. C. Su and H. Y. Lo, “An Algorithm for Scaling and Single Residue Error Correction in Residue Number Systems,” IEEE Transactions on Computers, Vol. 39, No. 8, 1990, pp.1053-1064. http://dx.doi.org/10.1109/12.57044

Menu

Parallel Algorithms for Residue Scaling and Error Correction in Residue Arithmetic

Abstract

References (17)