For signed–digit number systems, the proof of correctness of some reverse conversion algorithms remain ingrained in their developmental methods. As far as the remaining reverse conversion algorithms are concerned, either of no formal proof is given or different verification techniques are followed. Consequently at some points of time even some faulty algorithms were proposed through recognized platforms and sought to be projected as breakthroughs. In this paper, it is shown that a majority of available reverse conversion algorithms may be directly verified in generic form in a concise manner, merely using an ordinary mathematical induction technique, guided by the fundamental rules of typical reverse conversion. In addition to that, as evident from the case study which is presented in this paper, both the verification process and outcomes of reverse conversion, using the former class of algorithms, may be easily used to scrutinize the other more complex reverse conversion algorithms. Thus a unified framework for verifying reverse conversion algorithms for signed – digit number systems might have been obtained.

Reverse Conversion Algorithms, Signed – Digit Number Systems, Verification of Correctness, Unified Framework

[1] M. S. Chakraborty, “Reverse Conversion Schemes for Signed - Digit Number Systems: A survey”, Journal of Institute of Engineers (India): Series B, Vol. 97, pp. 589-593, 2016.
[2] I. Koren, “Computer Arithmetic Algorithms”, CRC Press, Oxford, 2001.
[3] M. S. Chakraborty, S. K. Sao, A. C. Mondal, “Equivalence of Reverse Conversion of Binary Signed-Digit Number System and Two’s - Complement to Canonical Signed-Digit Recording”, In the Proceedings of the 2018 IEEE International Conference on Recent Advancements in Information Technology, IIT/ ISM, Dhanbad, India, pp. 662 – 666, 2018.
[4] M. S. Chakraborty and A. C. Mondal, “Reverse conversion of signed - digit number systems: transforming radix - complement output”, Indonesian Journal of Electrical Engineering and Computer Science, Vol. 4, pp. 665 – 669, 2016.
[5] M. S. Chakraborty, A. C. Mondal, S. K. Sao, “Towards Relating Some Methods of Signed – Digit Arithmetic”, In the Proceedings of the 2018 International Conference on Mathematics, St. Thomas College, Thrissur, India, pp. 47 – 54, 2018.
[6] R. K. Barik, M. Pradhan, R. Panda, “Efficient conversion technique from redundant binary to non redundant binary representation”, Journal of Circuits, Systems and Computers, Vol. 26, pp. 1750135-1-1750135-18, 2017.
[7] S. S. Tripathy, R. K. Barik, M. Pradhan, “An Improved Conversion Circuit for Redundant Binary to Conventional Binary Representation”, In the Proceedings of the 2017 International Conference on Computational Intelligence, Communications and Business Analytics (CICBA), Kolkara, India, pp. 363-371, 2017.
[8] S. K. Sahoo, A. Gupta, A. R. Asati, C. Shekhar, “A novel redundant binary number to natural binary number converter”, Journal of Signal Processing Systems, Vol. 59, pp. 297-307, 2010.
[9] G. Wang and M. P. Tull, "A new Redundant Binary Number to two`s complement Number Converter", In the Proceedings of the 2004 IEEE Region 5 Conference, Norman, USA, pp. 141 – 143, 2004.
[10] G. A. Ruiz, "4bit CLA-based conversion from redundant to binary representation for CMOS simple and multi-output implementations", Electronics Letters, Vol. 35, No. 4, pp. 281-283, 1999.
[11] S. Yen, C. Laih, C. Chen and J. Lee, "An Efficient Redundant - Binary Number to Binary Number Converter", IEEE Journal of Solid-State Circuits, Vol. 27, No. 1, pp. 109-112, 1992.
[12] T. Stouraitis, C. Chen, “Fast Digit - Parallel Conversion of Signed Digit into Conventional Representations”, Electronics Letters, Vol. 27, No. 11, pp. 964 – 965, 1991.
[13] Y. He, C.-H. Chang, “A power-delay efficient hybrid carry-lookahead/ carry-select based redundant binary to two’s-complement converter”, IEEE Transactions on Circuits and Systems - I, Regular Papers, Vol. 55, pp. 336-346, 2008.
[14] S.-H. Shieh, C-W Wu, “Asymmetric High-Radix Signed-Digit Number Systems for Carry-Free Addition”, Journal of Information Science and Engineering, Vol.19, pp. 1015-1039, 2003.
[15] I. Choo and R. G. Deshmukh, “A novel conversion scheme from a redundant binary number to two’s complement binary number for parallel architectures”, In the Proceedings of the 2001 IEEE SoutheastCon, Clemson, USA, pp. 196 – 207, 2001.
[16] S. Veeramachaneni, M. K. Krishna, L. Avinash, S. Reddy, M. B. Srinivas, “High - speed redundant binary to binary converter using prefix networks”, in the Proceedings of the 2007 IEEE International Symposium on Circuits and Systems, Hyderabad, India, pp. 3271 – 3274, 2007.
[17] Y. Kim, B.-.S. Song, J. Grosspietsch and S. F. Gilling, "A carry-free 54×54 b multiplier using equivalent bit conversion algorithm", IEEE journal of Solid-State Circuits, Vol. 36, No. 10, pp. 1538-1544, 2001.
[18] H. R. Srinivas, K. K. Parhi, “High – Speed VLSI Arithmetic Processor Architectures using Hybrid Number Representation”, Journal of VLSI Signal Processing, Vol. 4, Issue 2 – 3, pp. 177 – 198, 1992.
[19] V. Charoensiri, A. Surarerks, “On-the-fly Conversion from Signed-Digit Number System into Complement Representation”, In the Proceedings of the 2006 IEEE International Symposium on Communications and Information Technologies, Bangkok, Thailand, pp. 1056-1061, 2006.
[20] H. R. Srinivas and K. K. Parhi, "A Fast VLSI Adder Architecture", IEEE Journal of Solid-State Circuits, Vol. 27, No. 5, pp. 761-767, 1992.
[21] W. Rülling, "A Remark on Carry - Free Binary Multiplication", IEEE Journal of Solid - State Circuits, Vol. 38, No. 1, pp. 159-160, 2003.
[22] M. S. Chakraborty, T. Ghosh, A. C. Mondal, “Towards a General Proof for the Correctness of Various Reverse Conversion Algorithms for Binary Signed – Digit Number System”, Orally Presented in International Seminar on Quality of Teaching – Learning in Higher Education in India: Concerns and Challenges, organized by the Education Department, Bankura University, Bankura, WB, India, 2018.
[23] M. S. Chakraborty, “Reverse conversion of signed - digit number system: Fast transformation sign – magnitude output”, International Journal of Computer Sciences and Enginering, Vol. 6, Issue 5, pp. 454 – 457, 2018.