Matrix Based Synthesis of EXOR dominated Combinational Logic for Low Power

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.

Authors:

• Padmanabhan Balasubramanian
• C. Hari Narayanan

Keywords:

• AOI logic
• ESOP
• AND-OR-EXOR
• Incidencematrix
• Hamming distance.

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.