Library Aware Power Conscious Realization of Complementary Boolean Functions

Authors: Padmanabhan Balasubramanian, C. Ardil

Abstract:

In this paper, we consider the problem of logic simplification for a special class of logic functions, namely complementary Boolean functions (CBF), targeting low power implementation using static CMOS logic style. The functions are uniquely characterized by the presence of terms, where for a canonical binary 2-tuple, D(mj) ∪ D(mk) = { } and therefore, we have | D(mj) ∪ D(mk) | = 0 [19]. Similarly, D(Mj) ∪ D(Mk) = { } and hence | D(Mj) ∪ D(Mk) | = 0. Here, 'mk' and 'Mk' represent a minterm and maxterm respectively. We compare the circuits minimized with our proposed method with those corresponding to factored Reed-Muller (f-RM) form, factored Pseudo Kronecker Reed-Muller (f-PKRM) form, and factored Generalized Reed-Muller (f-GRM) form. We have opted for algebraic factorization of the Reed-Muller (RM) form and its different variants, using the factorization rules of [1], as it is simple and requires much less CPU execution time compared to Boolean factorization operations. This technique has enabled us to greatly reduce the literal count as well as the gate count needed for such RM realizations, which are generally prone to consuming more cells and subsequently more power consumption. However, this leads to a drawback in terms of the design-for-test attribute associated with the various RM forms. Though we still preserve the definition of those forms viz. realizing such functionality with only select types of logic gates (AND gate and XOR gate), the structural integrity of the logic levels is not preserved. This would consequently alter the testability properties of such circuits i.e. it may increase/decrease/maintain the same number of test input vectors needed for their exhaustive testability, subsequently affecting their generalized test vector computation. We do not consider the issue of design-for-testability here, but, instead focus on the power consumption of the final logic implementation, after realization with a conventional CMOS process technology (0.35 micron TSMC process). The quality of the resulting circuits evaluated on the basis of an established cost metric viz., power consumption, demonstrate average savings by 26.79% for the samples considered in this work, besides reduction in number of gates and input literals by 39.66% and 12.98% respectively, in comparison with other factored RM forms.

Keywords: Reed-Muller forms, Logic function, Hammingdistance, Algebraic factorization, Low power design.

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

References:

[1] U. Narayanan, and C.L. Liu, "Low power logic synthesis for XOR based circuits", Proc. of IEEE/ACM International Conf. on Computer Aided Design, pp. 570-574, 1997.
[2] Sasan Iman, and Massoud Pedram, Logic Synthesis for Low Power VLSI designs, Springer-Verlag Publishing, Berlin Heidelberg, 1998.
[3] P. Balasubramanian, R. Chinnadurai, and M.R. Lakshmi Narayana, "Minimization of Dynamic Power Consumption in Digital CMOS Circuits by Logic Level Optimization", WSEAS Trans. on Circuits and Systems, vol. 4(4), pp. 257-266, April 2005.
[4] J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, and A. Yakovlev, Logic synthesis of Asynchronous controllers and Interfaces, Springer Series in Advanced Microelectronics, Springer-Verlag, Berlin Heidelberg, 2002.
[5] K. Nguyen, M. Perkowski, and N. Goldstein, "Palmini-Fats Boolean minimizer for Personal Computers", Proc. of ACM/IEEE Design Automation Conference, pp. 615-621, 1987.
[6] S. Kahramanli, and S. Tosun, "A novel essential prime implicant identification method for exact direct cover logic minimization", Proc. of 2006 International Conference on Computer Design, pp. 10-16, 2006.
[7] Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, Mc-Graw Hill, New York, 1994.
[8] I.I. Zhegalkin, "O tekhnike vychisleniy predlozheniy v simvolicheskoy logike" (About a Technique of Computation of Expressions in Symbolic Logic), Mat. Sb., vol. 34, pp. 9-28, 1927.
[9] I.I. Zhegalkin, "Arifmetizatsiya simvolicheskoy logiki" (Arythmetization of Symbolic Logic), Mat. Sb., vol. 35, pp. 311-377, 1928.
[10] S.M. Reed, "A class of multiple-error-correcting codes and their decoding scheme", IRE Trans. on Information Theory, vol. PGIT-4, pp. 38-49, 1954.
[11] D.E. Muller, "Application of Boolean algebra to switching circuit design and to error detection", IRE Trans. On Electron. And Comp., vol. EC-3, pp. 6-12, 1954.
[12] D.H. Green, "Families of Reed-Muller Canonical forms", International Journal of Electronics, vol. 70(2), pp. 259-280, February 1991.
[13] T. Sasao, "An exact minimization of AND-EXOR expressions using BDDs", Proc. of IFIP WG 10.5 Workshop on Applications of the Reed- Muller Expansion in Circuit Design, pp. 91-98, 1993.
[14] U. Kalay, M. Perkowski, and D. Hall, "A minimal universal test set for self test of EXOR-Sum-of-Products circuits", IEEE Trans. on Computers, vol. 49(3), pp. 267-276, March 1999.
[15] C. Yang, M. Ciesielski, and V. Singhal, "BDS: A BDD-based logic optimization system", Proc. of 37th ACM/IEEE Design Automation Conference, pp. 92-97, 2000.
[16] A. Mishchenko, B. Steinbach, and M. Perkowski, "An algorithm for bidecomposition of logic functions", Proc. of 38th ACM/IEEE Design Automation Conference, pp. 103-108, 2001.
[17] T. Sasao, Logic Synthesis and Optimization, Kluwer Academic Publishers, Massachusetts (USA), 1993.
[18] S. Chattopadhyay, S. Roy, and P.P. Chaudhuri, "KGPMIN: An Efficient Multilevel Multioutput AND-OR-XOR Minimizer", IEEE Trans. on CAD of Integrated Circuits and Systems, vol. 16(3), pp. 257-265, March 1997.
[19] P. Balasubramanian, and C. Ardil, "Compact Binary Tree Representation of Logic Function with Enhanced Throughput", International Journal of Computer, Information, and Systems Science, and Engineering, vol. 1(2), pp. 90-96, 2007.
[20] B. Zeidman, "An Introduction to Application Specific Integrated Circuits", Tutorial: Proc. of Embedded Systems Conference, USA, 1999.
[21] Available: http://www.mentor.com
[22] C.-S. Ding, C.-Y. Tsui, and M. Pedram, "Gate-level Power Estimation using Tagged Probabilistic Simulation", IEEE Trans. on CAD of Integrated Circuits and Systems, vol. 17(11), pp. 1099-1107, November 1998.
[23] Christopher Umans, Tiziano Villa, and Alberto L. Sangiovanni Vincentelli, "Complexity of Two-Level Logic Minimization", IEEE Trans. On CAD of Integrated Circuits and Systems, vol. 25(7), pp. 1230- 1246, July 2006.
[24] A.P. Chandrakasan, and R.W. Broderson, "Minimizing power consumption in digital CMOS circuits", Proceedings of the IEEE, vol. 83(4), pp. 498-523, April 1995.
[25] S. Stergiou, and P. Papakonstantinou, "Exact minimization of ESOP expressions with less than eight product terms", Journal of Circuits, Systems and Computers, vol. 13(1), pp. 1-15, February 2004.