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.
[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.
[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.
@article{"International Journal of Electrical, Electronic and Communication Sciences:64928", author = "Mehdi Hosseinzadeh and Amir Sabbagh Molahosseini and Keivan Navi", title = "A Fully Parallel Reverse Converter ", 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.", volume = "1", number = "3", pages = "593-5", }
