A Fully Parallel Reverse Converter

Authors: Mehdi Hosseinzadeh, Amir Sabbagh Molahosseini, Keivan Navi

Abstract:

The residue number system (RNS) is popular in high performance computation applications because of its carry-free nature. The challenges of RNS systems design lie in the moduli set selection and in the reverse conversion from residue representation to weighted representation. In this paper, we proposed a fully parallel reverse conversion algorithm for the moduli set {rn - 2, rn - 1, rn}, based on simple mathematical relationships. Also an efficient hardware realization of this algorithm is presented. Our proposed converter is very faster and results to hardware savings, compared to the other reverse converters.

Keywords: Reverse converter, residue to weighted converter, residue number system, multiple-valued logic, computer arithmetic.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1086069

References:

[1] M. A. Soderstrand and et al. Eds, Residue number system arithmetic: modern applications in digital signal processing, New York: IEEE Press, 1986.
[2] N. Szabo and R. Tanaka, Residue arithmetic and its applications to computer technology, New York: McGraw-Hill, 1967.
[3] B. Parhami, Computer arithmetic: algorithms and hardware designs, Oxford, 2001.
[4] T. Stouratitis and V. Paliouras, "Considering the alternatives in lowpower design," IEEE Circuits and Devices, pp. 23-29, 2001.
[5] R. Conway and J. Nelson, "Improved RNS FIR Filter Architectures," IEEE Transactions On Circuits and Systems II, Vol. 51, No. 1, pp. 26- 28, 2004.
[6] P. G. Fernandez, et al., "A RNS-Based Matrix-Vector-Multiply FCT Architecture for DCT Computation," Proc. of 43rd IEEE Midwest Symposium on Circuits and Systems, pp. 350-353, 2000.
[7] A. D. Re, A. Nannareli and M. Re, "A Tools for Arithmetic Generation of RTL-Level VHDL Description of RNS FIR Filters," IEEE Proceeding of the Design, Automation and Test in Europe Conference and Exhibition, pp. 686-687, 2004.
[8] W. L. Freking and K. K. Parhi, "Low-power FIR digital filters using residue arithmetic," Proc. Of 31st Asilomar Conference on Signals, Systems, and Computers, vol. 1, pp. 739-43, 1997.
[9] F. Taylor, "A Single Modulus ALU for Signal Processing," IEEE Transactions on Acoustics, Speech, Signal Processing, vol. 33, pp. 1302- 1315, 1985.
[10] S. Yen, S. Kim, S. Lim and S. Moon, "RSA Speedup with Chinese Remainder Theorem Immune against Hardware Fault Cryptanalysis," IEEE Transactions On Computers, Vol. XX, No. Y, pp. 461-472, 2003.
[11] J. Ramirez, et al., "Fast RNS FPL-Based Communications Receiver Design and Implementation," Proc. 12th Int-l Conf. Field Programmable Logic, pp. 472-481, 2002.
[12] B. Parhami , "RNS Representation with Redundant Residues," Proc. of the 35th Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA, pp. 1651-1655, 2001.
[13] E. Kinoshita and K. Lee, "A Residue Arithmetic Extension for Reliable Scientific Computation," IEEE Transactions . On Computers, Vol. 46, No. 2, pp. 129-138, 1997.
[14] V. Paliouras and T. Stouraitis, "Novel High-Radix Residue Number System Architectures," IEEE Transactions On Circuits and Systems-II: Analog and Digital Signal Processing, Vol. 47, No. 10, pp. 1059-1073, 2000.
[15] L. L. Yang, and L. Hanzo, "Redundant Residue Number System Based Error Correction Codes," Proc. of VTC'2001, Atlantic City, USA. pp. 1472-1476, 2001.
[16] Y. Wang, X. Song, M. Aboulhamid and H. Shen: "Adder based residue to binary numbers converters for (2n-1, 2n, 2n+1)," IEEE Trans. Signal Processing, Vol. 50, No. 7, pp. 1772-1779, 2002.
[17] M. A. Soderstrand and R. A. Escott, "VLSI implementation in multiplevalued logic of an FIR digital filter using residue number system arithmetic," IEEE Trans. Circuits Syst., vol. CAS -33, no. 1, pp. 5-25l , 1986.
[18] M. Abdallah and A. Skavantzos, "On MultiModuli Residue Number Systems With Moduli of Forms ra, rb-1, rc+1," IEEE Transactions Circuits System I: Regular Paper, Vol. 52, No. 7, pp. 1253-1266, 2005.
[19] M. Hosseinzadeh, K. Navi, S. Gorgin, "A New Moduli Set for Residue Number System: {rn-2, rn-1, rn}," IEEE International Conference on Electrical Engineering, 2007.
[20] E. Dubrova, "Multiple-Valued logic in VLSI: Challenges and opportunities," 34th IEEE International Symposium on Multiple-Valued Logic, 2004.
[21] E. Kinvi-Boh, M. Aline, O. Sentieys, and E. D. Olson, "MVL circuit design and characterization at the transistor level using SUS-LOC," in Proc. 33rd Int. Symp. Multiple-Valued Logic, May 16-19, pp. 105-110, 2003.
[22] A. Hiasat and H. S. Abdel-Aty-Zohdy, "Residue-to-binary arithmetic converter for the moduli set (2k, 2k-1, 2k-1-1)," IEEE Trans. Circuits Syst., vol. 45, pp. 204-208, 1998.
[23] W.Wang, M. N. S. Swamy, M. O. Ahmad, and Y.Wang, "A high-speed residue-to-binary converter and a scheme of its VLSI implementation," IEEE Trans. Circuits Syst. II, vol. 47, pp. 1576-1581, 2000.
[24] Y. Wang, X. Song, M. Aboulhamid and H. Shen: "Adder based residue to binary numbers converters for (2n-1, 2n, 2n+1)," IEEE Trans. Signal Processing, Vol. 50, No. 7, pp. 1772-1779, 2002.
[25] W.Wang, M. N. S. Swamy, M. O. Ahmad, and Y.Wang, "A high-speed residue-to-binary converter and a scheme of its VLSI implementation," IEEE Trans. Circuits Syst. II, vol. 47, pp. 1576-1581, 2000.
[26] S. L. Hurst, "Multiple-Valued Logic - Its status and its future," IEEE Transaction on Computers, pp. 1160-1179, 1984.
[27] A.F. Gonzalez, and P. Mazumdar, "Redundant Arithmetic, Algorithms and Implementations," Integration: The VLSI Journal, Vol. 30, No. 1, pp. 13-53, 2000.
[28] A. K. Jain, R. J. Bolton, and M. H. Abd-El-Barr, "CMOS multiplevalued logic designÔÇöPart I: Circuit implementation," IEEE Trans. Circuits Syst. I, Fundam. Theory Appl., vol. 40, no. 8, pp. 503-514, 1993.
[29] S. J. Piestrak, "Design of residue generators and multioperand modular adders using carry-save adders", IEEE Trans. Comput., vol. 423, no. 1, pp. 68-77, 1994.
[30] A. A. Hiasat, "VLSI implementation of New Arithmetic Residue to Binary Decoders," IEEE Trans. VLSI Systems, Vol.13, pp. 153-158, 2005.
[31] A. Hariri, K. Navi, R. Rastegar, "A Simplified Modulo (2n − 1) Squaring Scheme for Residue Number System," Proc. IEEE International Conference on Computer as a tool , 2005.
[32] S. Timarchi, K. Navi and M. Hosseinzadeh, "New Design of RNS Subtractor for modulo (2n + 1) ," Proc. 2th IEEE International Conference on Information & Communication Technologies: From Theory To Applications, 2006.
[33] M. Hosseinzadeh, K. Navi and S. Timarchi, "Design of Residue Number System Circuits in Current mode," Proc. 14th Iranian Conference of Electrical Engineering, 2006.
[34] A. Sabbagh, K. Navi, "An Improved Residue to Binary Converter for the RNS with Pairs of Conjugate Moduli," Proc. International Conference on Electrical Engineering and Informatics, Indonesia, 2007.
[35] M. Hosseinzadeh, K. Navi and S. Timarchi, "New Design of 4-3 Compressor," Proc. 11th International CSI Computer Conference of Iran, 2006.
[36] A. Hariri, K. Navi, R. Rastegar, "A new high dynamic range moduli set with efficient reverse converter," International Elsevier Journal of Computers and Mathematics with Applications, doi:10.1016/j.camwa.2007.04.028, 2007.