Parallel Algorithms for Residue Scaling and Error Correction in Residue Arithmetic

Hao-Yung Lo, Ting-Wei Lin

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

DOI: 10.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.

Keywords

Chinese Remainder Theorem (CRT); Error Correction; Error Detection; Parallel Residue Scaling; Residue Number Systems (RNS); Target Race Distance (TRD); Target Residue-Digit Difference

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	R. W. Watson, “Error Detection and Correction and Other Residue-Interacting Operations in a Redundant Residue Number System,” University of California, Berkeley, 1965.
[2]	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
[3]	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
[4]	D. Mandelbaum, “Error Correction in Residue Arithmetic,” IEEE Transactions on Computers, Vol. C-21, No. 6, 1972, pp. 538-545.
[5]	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
[6]	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
[7]	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
[8]	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
[9]	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
[10]	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
[11]	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.
[12]	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
[13]	H. Y. Lo, “An Optimal Matched and Parallel MixedRadix Converter,” Journal of Information Science and Engineering, Vol. 10, 1994, pp. 411-421.
[14]	A. P. Shenoy and R. Kumaresan, “Fast Base Extension Using a Redundant Modus in RNS,” IEEE Transactions on Computers, Vol. 38, No. 2, 1989, pp. 152-161. http://dx.doi.org/10.1109/12.16508
[15]	E. D. Diclaudis, G. Orlandi and F, Piazza, “A Systolic Redundant Residue Arithmetic Error Correction Circuit,” IEEE Transactions on Computers, Vol. 42, No. 4, 1993, pp. 427-433. http://dx.doi.org/10.1109/12.214689
[16]	S. S. Wang and M. Y. Shau, “Single Residue Error correction Based on K-Term Mj-Projection,” IEEE Transactions on Computers, Vol. 44, No. 1, 1995, pp. 129-131. http://dx.doi.org/10.1109/12.368003
[17]	R. S. Katti, “A New Residue Arithmetic Error Correction Scheme,” IEEE Transactions on Computers, Vol. 45, No. 1, 1996, pp. 13-19. http://dx.doi.org/10.1109/12.481482