Matrix Based Synthesis of EXOR dominated Combinational Logic for Low Power

Authors: Padmanabhan Balasubramanian, C. Hari Narayanan

Abstract:

This paper discusses a new, systematic approach to the synthesis of a NP-hard class of non-regenerative Boolean networks, described by FON[FOFF]={mi}[{Mi}], where for every mj[Mj]∈{mi}[{Mi}], there exists another mk[Mk]∈{mi}[{Mi}], such that their Hamming distance HD(mj, mk)=HD(Mj, Mk)=O(n), (where 'n' represents the number of distinct primary inputs). The method automatically ensures exact minimization for certain important selfdual functions with 2n-1 points in its one-set. The elements meant for grouping are determined from a newly proposed weighted incidence matrix. Then the binary value corresponding to the candidate pair is correlated with the proposed binary value matrix to enable direct synthesis. We recommend algebraic factorization operations as a post processing step to enable reduction in literal count. The algorithm can be implemented in any high level language and achieves best cost optimization for the problem dealt with, irrespective of the number of inputs. For other cases, the method is iterated to subsequently reduce it to a problem of O(n-1), O(n-2),.... and then solved. In addition, it leads to optimal results for problems exhibiting higher degree of adjacency, with a different interpretation of the heuristic, and the results are comparable with other methods. In terms of literal cost, at the technology independent stage, the circuits synthesized using our algorithm enabled net savings over AOI (AND-OR-Invert) logic, AND-EXOR logic (EXOR Sum-of- Products or ESOP forms) and AND-OR-EXOR logic by 45.57%, 41.78% and 41.78% respectively for the various problems. Circuit level simulations were performed for a wide variety of case studies at 3.3V and 2.5V supply to validate the performance of the proposed method and the quality of the resulting synthesized circuits at two different voltage corners. Power estimation was carried out for a 0.35micron TSMC CMOS process technology. In comparison with AOI logic, the proposed method enabled mean savings in power by 42.46%. With respect to AND-EXOR logic, the proposed method yielded power savings to the tune of 31.88%, while in comparison with AND-OR-EXOR level networks; average power savings of 33.23% was obtained.

Keywords: AOI logic, ESOP, AND-OR-EXOR, Incidencematrix, Hamming distance.

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

References:

[1] A.P. Chandrakasan, and R.W. Brodersen, "Minimizing power consumption in digital CMOS circuits," Proc. of the IEEE, vol. 83(4), April 1995, pp. 498-523.
[2] Christopher Umans, et. al., "Complexity of two-level logic minimization," IEEE Trans. on CAD of Integrated Circuits and Systems, vol. 25(7), July 2006, pp. 1230-1246.
[3] C. -S. Ding, et al., "Gate-level power estimation using tagged probabilistic simulation," IEEE Trans. on CAD of Integrated Circuits and Systems, vol. 17(11), November 1998, pp. 1099-1107.
[4] Sasan Iman, and Massoud Pedram. Logic Synthesis for Low Power VLSI Designs. New York: Springer Publishing, 1998.
[5] Dieter Jungnickel. Graphs, Networks and Algorithms. New York: Springer-Verlag, 2nd Edition, 2005.
[6] Tsutomu Sasao. Switching Theory for Logic Synthesis. Kluwer Academic Publishers, 1999.
[7] 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), March 1999, pp. 267-276.
[8] H. Rahaman, et al., "Testing of stuck-open faults in generalized Reed- Muller and EXOR sum-of-products CMOS circuits," IEE Proc. on Computers and Digital Techniques, vol.151(1), January 2004, pp. 83-91.
[9] 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), May 1993, pp. 621-632.
[10] N. Song, and M. Perkowski, "Minimization of Exclusive Sum of Products Expressions for Multi-Output Multiple-Valued Input, Incompletely Specified Functions", IEEE Trans. on CAD of integrated Circuits and Systems, vol. 15(4), April 1996, pp. 385-395.
[11] Alan Mishchenko, and Marek Perkowski, "Fast heuristic minimization of Exclusive-Sums-of-Products", Proc. of 5th International Reed-Muller Workshop, 2001, pp. 242-250.
[12] Stergios Stergiou, and George Papakonstantinou, "Exact minimization of ESOP expressions with less than eight product terms," Journal of Circuits, Systems and Computers, vol. 13(1), February 2004, pp. 1-15.
[13] D. Debnath, and T. Sasao, "A heuristic algorithm to design AND-OREXOR three-level networks", Proc. of ASP-DAC, 1998, pp. 69-74.
[14] E.V. Dubrova, D.M. Miller, and J.C. Muzio, "AOXMIN-MV: a heuristic algorithm for AND-OR-XOR minimization," Proc. of 4th International Reed-Muller Workshop, 1999, pp. 37-53.
[15] Giovanni De Micheli, Synthesis and optimization of digital circuits. New York: McGraw Hill, 1st Edition, 1994.
[16] M.A. Harrison, Introduction to Switching and Automata Theory. Mc-Graw Hill, 1965.
[17] E.V. Dubrova, D.M. Miller, and J.C. Muzio, "Upper bound on number of products in AND-OR-XOR expansion of logic functions," IET Journal of Electronics Letters, vol. 31(7), March 1995, pp. 541-542.