Volume:2, Issue: 5, 2008 Page No: 716 - 725

ISSN: 2517-9438

1320 Downloads

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.

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.