Reversible Logic Multipliers: Novel Low-cost Parity-Preserving Designs

Authors

School of Electrical and Computer Engineering, Babol Noshirvani University of Technology, Babol, Iran

Abstract

Reversible logic is one of the new paradigms for power optimization that can be used instead of the current circuits. Moreover, the fault-tolerance capability in the form of error detection or error correction is a vital aspect for current processing systems. In this paper, as the multiplication is an important operation in computing systems, some novel reversible multiplier designs are proposed with the parity-preserving property which will be useful for error detection. At first, two optimal signed serial multipliers are presented based on the Booth’s algorithm and its enhanced version called the K-algorithm, utilizing the new arrangements of reversible gates. Then, another low-cost serial multiplier is proposed based on the conventional Add & Shift method to be utilized in the applications in which unsigned numbers are used. Finally, a new signed parallel multiplier is proposed based on the Baugh-Wooley method that is useful for speed-critical applications. The comparative results showed that the proposed multipliers are much better than the existing designs regarding the main criterions used in reversible logic circuits including quantum cost, gate count, constant inputs, and garbage outputs.

Keywords


1. Landauer, R., "Irreversibility and heat generation in the computing process", IBM Journal of Research and Development, Vol. 5, No. 3, (1961), 183–191.

2. Bennet, C., "Logical reversibility of computation", IBM Journal of Research and Development, Vol. 17, No. 6, (1973), 525–532.

3. Toffoli, T., "Reversible Computing", Tech. memo MIT/LCS/TM-151, MIT Lab. for Computer Science, (1980).

4. Perkowski, M., Al-Rabadi, A., Kerntopf, P., Buller, A., Chrzanowska-Jeske, M., Mishchenko, A., et al., "A general decomposition for reversible logic", Proc. RM, (2001), 119–138.

5.  Zhou, R., Shi, Y., Wanga, H. and Cao, J., "Transistor realization of reversible ‘‘ZS’’ series gates and reversible array multiplier", Microelectronics Journal, Vol. 42, (2011), 305–315.

6. Pouraliakbar, E., Haghparast, M. and Navi, K., "Novel design of a fast reversible Wallace sign multiplier circuit in nanotechnology", Microelectronics Journal, Vol. 42, (2011), 973–981.

7. Moghadam, M. Z. and Navi, K., "Ultra-area-efficient reversible multiplier", Microelectronics Journal, Vol. 43, (2012), 377–385.

8. Babazadeh, S. and Haghparast, M., "Design of a nanometric fault tolerant reversible multiplier circuit", Journal of basic and applied scientific research, Vol. 2, No. 2, (2012), 1355–1361.

9. Qi, X. and Chen, F., "Design of fast fault tolerant reversible signed multiplier", International Journal of the Physical Sciences, Vol. 7, No. 17, (2012), 2506–2514.

10. Hatkar, A. P., Hatkar, A. A. and Narkhede, N. P., "ASIC Design of Reversible Multiplier Circuit", Proc. of Intl. Conf. on Electronic Systems, Signal Processing and Computing Technologies, (2014), 47–52.

11. Kotiyal, S., Thapliyal, H. and Ranganathan, N., "Circuit for Reversible Quantum Multiplier Based on Binary Tree Optimizing Ancilla and Garbage Bits", Proc. of 27th Intl. Conf. on VLSI Design (VLSID), (2014), 545–550.

12. Nagamani, A. N., Nikhil, R., Nagaraj, M. and Agrawal, V. K., "Reversible radix-4 booth multiplier for DSP applications", Intl. Conf. on Signal Processing and Communication (SPCOM), (2016), 1–5.

13. Gowthami, P. and Satyanarayana, R. V. S., "Design of an efficient multiplier using Vedic mathematics and reversible logic", IEEE Intl. Conf. onComputational Intelligence and Computing Research (ICCIC), (2016), 1–4.

 14. Bhardwaj, K. and Deshpande, M., "K-Algorithm: An Improved Booth’s Recoding for Optimal Fault-Tolerant Reversible Multiplier", 26th Intl. Conf. on VLSI Design, (2013), 362-367.

15. Baugh, C. R. and Wooley, B. A., "A two’s complement parallel array multiplication algorithm", IEEE Transactions Computers, Vol. 22, No. 12, (1973), 1045-1047.

16. Przigoda, N., Dueck, G., Wille, R. and Drechsler, R., "Fault detection in parity preserving reversible circuits", IEEE 46th Intl. Symp. onMultiple-Valued Logic (ISMVL), (2016), 44–49.

17. Gaur, H. M., Singh, A. K. and Ghanekar, U., "Testable Design of Reversible Circuits using Parity Preserving Gates", IEEE Design & Test, In Press, Publication date: 09 Nov. 2017.

18. Maslov, D. and Dueck, G. W., "Reversible cascades with minimal garbage", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 23, No. 11, (2004), 1497–1509.

19. Biswas, A. K., Hasan, M. M., Chowdhury, A. R. and Babu, H. M. H., "Efficient approaches for designing reversible Binary Coded Decimal adders", Microelectronics Journal, Vol. 39, (2008), 1693–1703.

20. Valinataj, M., Mirshekar, M. and Jazayeri, H., "Novel low-cost and fault-tolerant reversible logic adders", Computers and Electrical Engineering, Vol. 53, (2016), 56–72.

21. Parhami, B., "Fault-tolerant reversible circuits",40th Asilomar Conference on Signals, Systems and Computers (ACSSC), (2006), 1726–1729.

22. Fredkin, E. and Toffoli, T., "Conservative logic", International Journal of Theoretical Physics, Vol. 21, (1982), 219–253.

23. Hagparast, M. and Navi, K., "A Novel Fault Tolerant Reversible Gate for Nanotechnology Based System", American Journal of Applied Sciences, Vol. 5, No. 5, (2008), 519–523.

24. Islam, M. S., Rahman, M. M., Begum, Z. and Hafiz, M. Z., "Fault tolerant reversible logic synthesis: carry look-ahead and carry skip adders", Intl. Conf. on Advances in Computational Tools for Engineering Applications (ACTEA), (2009), 396–401.

25. Jamal, L., Rahman, M. M. and Babu, H. M. H., "An optimal design of a fault tolerant reversible multiplier", IEEE 26th Intl. SOC Conf. (SOCC), (2013), 37–42.

26. Zhou, R. G., Li, Y.-C. and Zhang, M.-Q., "Novel design for fault tolerant reversible binary coded decimal adders", International. Journal of Electronics, Vol. 101, No. 10, (2014), 1336–1356.

27. Mitra, S. K. and Chowdhury, A. R., "Minimum cost fault tolerant adder circuits in reversible logic synthesis", 25th IEEE Intl. Conf. VLSI Design (VLSID), (2012), 334–339.

28. Moallem, P. and Ehsanpour, M., “A novel design of reversible multiplier circuit”, International Journal of Engineering-Transactions C: Aspects, Vol. 26, No. 6, (2013), 577–586.

29. Madhulika, C., Nayak, V. S. P., Prasanth, C. and Praveen, T. H. S., "Design of systolic array multiplier circuit using reversible logic", IEEE Intl. Conf. onRecent Trends in Electronics Information & Communication Technology, (2017), 1670–1673.

30. Nagamani, A. N., Kumar, S. S. and Agrawal, V. K., "Design of garbage free reversible multiplier for low power applications", 4th Intl. Conf. on Power, Control & Embedded Systems, (2017), 1–4.

31. Zoka, S. and Gholami, M., “Two novel D-flip flops with level triggered reset in quantum dot cellular automata technology”, International Journal of Engineering-Transactions C: Aspects, Vol. 31, No. 3, (2018), 415–421.

32. Valinataj, M., “Novel parity-preserving reversible logic array multipliers”, Journal of Supercomputing, Vol. 73, No. 11, (2017), 4843–4867.

33. Eslami-Chalandar, F., Valinataj, M. and Jazayeri, H., “Design of error detecting serial multipliers in reversible logic”, Electronics Industries Quarterly (EIQ), Vol. 8, No. 1, (2017), 99–110.