Power-Efficient AND-EXOR-INV Based Realization of Achilles' heel Logic Functions

This paper deals with a power-conscious ANDEXOR- Inverter type logic implementation for a complex class of Boolean functions, namely Achilles- heel functions. Different variants of the above function class have been considered viz. positive, negative and pure horn for analysis and simulation purposes. The proposed realization is compared with the decomposed implementation corresponding to an existing standard AND-EXOR logic minimizer; both result in Boolean networks with good testability attribute. It could be noted that an AND-OR-EXOR type logic network does not exist for the positive phase of this unique class of logic function. Experimental results report significant savings in all the power consumption components for designs based on standard cells pertaining to a 130nm UMC CMOS process The simulations have been extended to validate the savings across all three library corners (typical, best and worst case specifications).

• Padmanabhan Balasubramanian
• R. Chinnadurai

• Achilles' heel functions
• AND-EXOR-Inverter logic
• CMOS technology
• low power design.

[1] A.P. Chandrakasan, and R.W. Brodersen, "Minimizing power
consumption in digital CMOS circuits," Proceedings of the IEEE, vol.
83(4), pp. 498-523, April 1995.
[2] A.P. Chandrakasan, S. Sheng, and R.W. Brodersen, "Low-power CMOS
digital design," IEEE Journal of Solid-State Circuits, vol. 27(4), pp.
473-484, April 1992.
[3] V. Gurvich, "Criteria for repetition-freeness of functions in the algebra
of Logic," Soviet Math., vol. 43(3), pp. 721-726, 1991.
[4] M. Karchmer, N. Linial, I. Newman, M. Saks and A. Wigderson,
"Combinatorial characterization of read-once formulae," Discrete
Mathematics, vol. 114(1-3), pp. 275-282, April 1993.
[5] I. Newman, "On read-once Boolean functions," in Boolean function
complexity: Selected papers from LMS Symposium, pp. 24-34, 1990.
[6] J. Peer, and R. Pinter, "Minimal decomposition of Boolean functions
using non-repeating literal trees," Proc. IFIP International Workshop on
Logic and Architecture Synthesis, pp. 129-139, December 1995.
[7] N.H. Bshouty, T.R. Hancock, and L. Hellerstein, "Learning Boolean
read-once formulas with arbitrary symmetric and constant fan-in gates,"
Proc. 5th Annual ACM Conference on Computational Learning Theory,
pp. 1-15, 1992.
[8] P. Balasubramanian, and R.T. Naayagi, "Critical path delay and net
delay reduced tree structure for combinational logic circuits,"
International Journal of Electronics, Circuits and Systems, vol. 1(1), pp.
19-29, 2007.
[9] P.C. McGeer, J.V. Sanghavi, R.K. Brayton, and A.L. Sangiovanni-
Vincentelli, "Espresso-Signature: a new exact minimizer for logic
functions," IEEE Trans. on VLSI Systems, vol. 1(4), pp. 432-440,
December 1993.
[10] P. Srinivasa Rao, and J. Jacob, "A fast two-level logic minimizer," Proc.
11th International Conf. on VLSI Design, pp. 528-533, January 1998.
[11] N.N. Biswas, C. Srikanth, and J. Jacob, "Cubical CAMP for
minimization of Boolean functions," Proc. 9th International Conf. on
VLSI Design, pp. 264-269, January 1996.
[12] T. Sasao, and P. Besslich, "On the complexity of mod-2 sum PLA-s,"
IEEE Trans. on Computers, vol. 32(2), pp. 262-266, February 1990.
[13] T. Sasao, "EXMIN: A simplification algorithm for Exclusive-OR Sumof-
Products expressions for multiple-valued input two-valued output
functions," Proc. 20th International Symposium on Multiple-Valued
Logic, pp. 128-135, May 1990.
[14] N. Koda, and T. Sasao, "An upper bound on the number of products in
AND-EXOR minimum expressions," IEICE Trans. on Fundamentals,
vol. J75-D-I (3), pp. 135-142, March 1992.
[15] T. Sasao, Logic Synthesis and Optimization, Kluwer Academic
Publishers, Massachusetts, USA, 1993.
[16] 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.
[17] D. Brand, and T. Sasao, "Minimization of AND-EXOR expressions
using rewrite rules," IEEE Trans. on Computers, vol. 42(5), pp. 568-576,
May 1993.
[18] H. Fleisher, M. Travel, and J. Yeager, "Computer algorithm for
minimizing Reed-Muller canonical forms," IEEE Trans. on Computers,
vol. C-36(2), pp. 247-250, February 1987.
[19] Y. Ye, and K. Roy, "An XOR-based decomposition diagram and its
application in synthesis of AND-XOR networks," IEICE Trans. on
Fundamentals, vol. E80-A (10), pp. 1742-1748, October 1997.
[20] Tsutomu Sasao, "EXMIN2: A simplification algorithm for Exclusive-
OR-Sum-of-Products expressions for multiple-valued-input two-valuedoutput
functions," IEEE Trans. on CAD of Integrated Circuits and
Systems, vol. 12(5), pp. 621-632, May 1993.
[21] A. Mishchenko, and M. Perkowski, "Fast heuristic minimization of
Exclusive-Sums-of-Products", Proc. 5th International Reed-Muller
Workshop, pp. 242-250, 2001.
[22] S. Stergiou, and G. 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.
[23] P. Balasubramanian, and R. Arisaka, "A set theory based factoring
technique and its use for low power logic design," International Journal
of Electrical, Computer, and Systems Engineering, vol. 1(3), pp. 188-
198, 2007.
[24] Synopsys Inc., Available: http://www.synopsys.com
[25] T. Eiter, T. Ibaraki, and K. Makino, "Bidual Horn functions and
extensions, " Discrete Applied Math., vol. 96-97, pp. 55-88, Oct. 1999.
[26] A. Sarabi, "Design of testability properties of AND/XOR networks,"
Proc. IFIP Workshop on Applications of Reed-Muller Expansion in
Circuit Design, pp. 138-142, Germany, 1993.
[27] W. -Z. Shen, J.-Y. Lin, and F.-W. Wang, "Transistor reordering rules for
power reduction in CMOS gates," Proc. ASP-DAC, pp. 1-6, 1995.