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

Authors: Padmanabhan Balasubramanian, R. Chinnadurai

Abstract:

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

Keywords: Achilles' heel functions, AND-EXOR-Inverter logic, CMOS technology, low power design.

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

References:

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