A New Efficient RNS Reverse Converter for the 4-Moduli Set 

Authors: Edem K. Bankas, Kazeem A. Gbolagade

Abstract:

In this paper, we propose a new efficient reverse converter for the 4-moduli set {2ⁿ, 2ⁿ + 1, 2ⁿ − 1, 2²ⁿ⁺¹ – 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)t_FA + t_MUX. 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.

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

References:

[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.