Library Aware Power Conscious Realization of Complementary Boolean Functions

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.

• Padmanabhan Balasubramanian
• C. Ardil

• Reed-Muller forms
• Logic function
• Hammingdistance
• Algebraic factorization
• Low power design.

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