A New Efficient RNS Reverse Converter for the 4-Moduli Set
In this paper, we propose a new efficient reverse converter for the 4-moduli set {2n, 2n + 1, 2n− 1, 22n+1– 1} based on a modified Chinese Remainder Theorem and Mixed Radix Conversion. Additionally, the resulting architecture is further reduced to obtain a reverse converter that utilizes only carry save adders, a multiplexer and carry propagate adders. The proposed converter has an area cost of (12n + 2) FAs and (5n + 1) HAs with a delay of (9n + 6)tFA + tMUX. When compared with state of the art, our proposal demonstrates to be faster, at the expense of slightly more hardware resources. Further, the Area-Time square metric was computed which indicated that our proposed scheme outperforms the state of the art reverse converter.
[1] Szabo N.S. and Tanaka R.I. Residue Arithmetic and its Applications to
Computer Technology, McGraw Hill. New Tork, 1967.
[2] Shew M., Lin S., Chen C., and Yang S. An Efficient VLSI
Design for a Residue to Binar Converter for General Balance moduli
{2n − 3, 2n + 1, 2n − 1, 2n + 3}. IEEE Transactions on Circuits and
Systems -II Express Briefs, Vol. 51, No.3, March, 2004, pp. 152-155
[3] Parhami B. Computer Arithmetic: Algorithms and Hardware Designs.
Oxford University press, 2000.
[4] Wang W., Swamy M.N.S., Ahmad M.O. and Wang Y. A study of
the residue -to-binary converters for the three moduli sets. IEEE Trans.
Circuits Syst. I, Fundam. Theory Appl, Vol. 50, No. 2, Feb., 2003, pp.
235–243
[5] S. Lin, M. Sheu and C. Wang. Efficient VLSI Design of Residue-to-Binary
Converter for the moduli set. IEICE Trans Inf and Syst., Vol. E91-D, No.7,
pp. 2058-2060, , July, 2008.
[6] K.A. Gbolagade, G.R. Voicu, S.D. Cotofana. Memoryless RNS-to-Binary
Converters for the 2n+1 − 1, 2n, 2n − 1. IEEE International
Conference on Application Specific System, Architectures and Processors
(ASAP 2010) pp 301-304, Rennes, France. July, 2010.
[7] P.V.A. Mohan. RNS-to-Binary Converter for a New three moduli set
2n+1 − 1, 2n, 2n − 1. IEEE Transactions on Circuits and Systems
-II, Vol. 54, No.9, pp. 775-779. Sep, 2007.
[8] M. Hosseinzadeh, A.S. Molahosseini and K. Navi. A parallel
Implementation of the Reverse Converter for the moduli set
2n, 2n − 1, 2n−1 − 1. World Academy of Science, Engineering and
Technology, Vol. 55, pp. 494-498. 2009.
[9] P.V.A. Mohan, A.B. Premkumar. RNS-to-Binary Converters for
two Four moduli set 2n − 1, 2n, 2n + 1, 2n+1 − 1 and
2n − 1, 2n, 2n + 1, 2n+1 + 1. IEEE Transactions on Circuits
and Systems -I. Regular papers. Vol. 54, No.6, June, 2007.
[10] B. Cao, C. Chang and T Srikanthan. Adder Based Residue to Binary
Converters for a New Balanced 4-moduli set. Proceedings of the 3rd
International Symposium on Image and Signal Processing and Analysis.
pp. 820-825. 2003.
[11] B. Cao, C. Chang and T Srikanthan. An Efficient Reverse Converter
for the 4-moduli set 2n − 1, 2n, 2n + 1, 22n + 1 Based on the New
Chinese Remainder Theorem. IEEE Transactions on Circuits and Systems
-I. Fundamental Theory and Applications. Vol. 50, No.10. October, 2003.
[12] E.K. Bankas and K.A. Gbolagade. A Speed Efficient RNS-to-Binary
Converter for a the Moduli set {2n, 2n + 1, 2n − 1}. Journal of
Computing. Volume 4, Issue 5. pp. 83-88. May, 2012.
[13] Y. Wang. New Chinese Remaider Theorem. In proc. Asilomar
Conference, USA. pp. 165-171. Nov. 1998.
[14] A. S. Molahosseini, K. Navi and C. Dadkhah, O. Kavehei
and S. Timarcli . Efficient Reverse Converter Designs for
the New 4-Moduli sets 2n − 1, 2n, 2n + 1, 22n+1 − 1 and
2n − 1, 2n, 22n, 22n + 1 Based on New CRTs. IEEE Transactions
on Circuits and Systems -I. Vol. 57, No.4, 823 -835. April, 2010.
[15] A. S. Molahosseini, C. Dadkhah, and K. Navi. A new five-moduli set
for efficient hardware implementation of the reverse converter. IEICE
Electronic Express. Vol.6. pp. 1006-1012. July, 2009.
[16] K.A. Gbolagade, R. Chaves, L. Sousa, and S.D. Cotofana .
Residue-to-Binary Converters for the 22n+1 − 1, 22n, 2n Moduli set. 2nd IEEE International Conference on Adaptive Scienc−e a1nd
Technology. pp. 26 - 33, Accra, Ghana. December, 2009.
[17] K.A. Gbolagade, R. Chaves, L. Sousa, and S.D. Cotofana . An Improved
RNS Reverse Converter for the 22n+1 − 1, 2n, 2n − 1 Moduli set.
IEEE International Symposium on Circuits and Systems (ISCAS 2010).
pp. 2103 -2106, Paris, France. June, 2010.
[18] B. Cao, T. Srikanthan, C.H. Chang . Efficient reverse converters
for the four-moduli sets 2n − 1, 2n, 2n + 1, 2n+1 − 1, and
2n − 1, 2n, 2n + 1, 2n−1 − 1. IEEE Proc. Computers and Digital
Tech. vol. 152, no. 5, pp. 687-696. Sept. 2005.
[1] Szabo N.S. and Tanaka R.I. Residue Arithmetic and its Applications to
Computer Technology, McGraw Hill. New Tork, 1967.
[2] Shew M., Lin S., Chen C., and Yang S. An Efficient VLSI
Design for a Residue to Binar Converter for General Balance moduli
{2n − 3, 2n + 1, 2n − 1, 2n + 3}. IEEE Transactions on Circuits and
Systems -II Express Briefs, Vol. 51, No.3, March, 2004, pp. 152-155
[3] Parhami B. Computer Arithmetic: Algorithms and Hardware Designs.
Oxford University press, 2000.
[4] Wang W., Swamy M.N.S., Ahmad M.O. and Wang Y. A study of
the residue -to-binary converters for the three moduli sets. IEEE Trans.
Circuits Syst. I, Fundam. Theory Appl, Vol. 50, No. 2, Feb., 2003, pp.
235–243
[5] S. Lin, M. Sheu and C. Wang. Efficient VLSI Design of Residue-to-Binary
Converter for the moduli set. IEICE Trans Inf and Syst., Vol. E91-D, No.7,
pp. 2058-2060, , July, 2008.
[6] K.A. Gbolagade, G.R. Voicu, S.D. Cotofana. Memoryless RNS-to-Binary
Converters for the 2n+1 − 1, 2n, 2n − 1. IEEE International
Conference on Application Specific System, Architectures and Processors
(ASAP 2010) pp 301-304, Rennes, France. July, 2010.
[7] P.V.A. Mohan. RNS-to-Binary Converter for a New three moduli set
2n+1 − 1, 2n, 2n − 1. IEEE Transactions on Circuits and Systems
-II, Vol. 54, No.9, pp. 775-779. Sep, 2007.
[8] M. Hosseinzadeh, A.S. Molahosseini and K. Navi. A parallel
Implementation of the Reverse Converter for the moduli set
2n, 2n − 1, 2n−1 − 1. World Academy of Science, Engineering and
Technology, Vol. 55, pp. 494-498. 2009.
[9] P.V.A. Mohan, A.B. Premkumar. RNS-to-Binary Converters for
two Four moduli set 2n − 1, 2n, 2n + 1, 2n+1 − 1 and
2n − 1, 2n, 2n + 1, 2n+1 + 1. IEEE Transactions on Circuits
and Systems -I. Regular papers. Vol. 54, No.6, June, 2007.
[10] B. Cao, C. Chang and T Srikanthan. Adder Based Residue to Binary
Converters for a New Balanced 4-moduli set. Proceedings of the 3rd
International Symposium on Image and Signal Processing and Analysis.
pp. 820-825. 2003.
[11] B. Cao, C. Chang and T Srikanthan. An Efficient Reverse Converter
for the 4-moduli set 2n − 1, 2n, 2n + 1, 22n + 1 Based on the New
Chinese Remainder Theorem. IEEE Transactions on Circuits and Systems
-I. Fundamental Theory and Applications. Vol. 50, No.10. October, 2003.
[12] E.K. Bankas and K.A. Gbolagade. A Speed Efficient RNS-to-Binary
Converter for a the Moduli set {2n, 2n + 1, 2n − 1}. Journal of
Computing. Volume 4, Issue 5. pp. 83-88. May, 2012.
[13] Y. Wang. New Chinese Remaider Theorem. In proc. Asilomar
Conference, USA. pp. 165-171. Nov. 1998.
[14] A. S. Molahosseini, K. Navi and C. Dadkhah, O. Kavehei
and S. Timarcli . Efficient Reverse Converter Designs for
the New 4-Moduli sets 2n − 1, 2n, 2n + 1, 22n+1 − 1 and
2n − 1, 2n, 22n, 22n + 1 Based on New CRTs. IEEE Transactions
on Circuits and Systems -I. Vol. 57, No.4, 823 -835. April, 2010.
[15] A. S. Molahosseini, C. Dadkhah, and K. Navi. A new five-moduli set
for efficient hardware implementation of the reverse converter. IEICE
Electronic Express. Vol.6. pp. 1006-1012. July, 2009.
[16] K.A. Gbolagade, R. Chaves, L. Sousa, and S.D. Cotofana .
Residue-to-Binary Converters for the 22n+1 − 1, 22n, 2n Moduli set. 2nd IEEE International Conference on Adaptive Scienc−e a1nd
Technology. pp. 26 - 33, Accra, Ghana. December, 2009.
[17] K.A. Gbolagade, R. Chaves, L. Sousa, and S.D. Cotofana . An Improved
RNS Reverse Converter for the 22n+1 − 1, 2n, 2n − 1 Moduli set.
IEEE International Symposium on Circuits and Systems (ISCAS 2010).
pp. 2103 -2106, Paris, France. June, 2010.
[18] B. Cao, T. Srikanthan, C.H. Chang . Efficient reverse converters
for the four-moduli sets 2n − 1, 2n, 2n + 1, 2n+1 − 1, and
2n − 1, 2n, 2n + 1, 2n−1 − 1. IEEE Proc. Computers and Digital
Tech. vol. 152, no. 5, pp. 687-696. Sept. 2005.
@article{"International Journal of Information, Control and Computer Sciences:66741", author = "Edem K. Bankas and Kazeem A. Gbolagade", title = "A New Efficient RNS Reverse Converter for the 4-Moduli Set ", abstract = "In this paper, we propose a new efficient reverse converter for the 4-moduli set {2n, 2n + 1, 2n − 1, 22n+1 – 1} based on a modified Chinese Remainder Theorem and Mixed Radix Conversion. Additionally, the resulting architecture is further reduced to obtain a reverse converter that utilizes only carry save adders, a multiplexer and carry propagate adders. The proposed converter has an area cost of (12n + 2) FAs and (5n + 1) HAs with a delay of (9n + 6)tFA + tMUX. When compared with state of the art, our proposal demonstrates to be faster, at the expense of slightly more hardware resources. Further, the Area-Time square metric was computed which indicated that our proposed scheme outperforms the state of the art reverse converter.
", keywords = "Modified Chinese Remainder Theorem, Mixed Radix
Conversion, Reverse Converter, Carry Save Adder, Carry Propagate
Adder.", volume = "8", number = "2", pages = "348-5", }
