Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

This paper shows that divide-and-conquer derives a minimum sum-of-products expression (MSOP) of functions that have an AND bi-decomposition when at least one of the sub-functions is orthodox. This extends a previous result showing that divide-and-conquer derives the MSOP of the AND bi-decomposition of two orthodox functions. We show that divide-and-conquer does not always produce an MSOP when neither function is orthodox. However, our experimental results show that, in this case, it derives a near minimal SOP. At the same time, our approach significantly reduces the time needed to find an MSOP or near minimal SOP. Also, we extend our results to functions that have a tri-decomposition.

REFERENCES

• 1: Robert King Brayton , Alberto L. Sangiovanni-Vincentelli , Curtis T. McMullen , Gary D. Hachtel, Logic Minimization Algorithms for VLSI Synthesis, Kluwer Academic Publishers, Norwell, MA, 1984
• 2: Jon T. Butler, Analysis and Design of Fanout-Free Networks of Positive Symmetric Gates, Journal of the ACM (JACM), v.25 n.3, p.481-498, July 1978 [doi>10.1145/322077.322089]
• 3: John P. Hayes, The Fanout Structure of Switching Functions, Journal of the ACM (JACM), v.22 n.4, p.551-571, Oct. 1975 [doi>10.1145/321906.321918]
• 4: C. L Liu, Elements of discrete mathematics (McGraw-Hill computer science series), McGraw-Hill Pub. Co., 1977
• 5: R. S. Michalski and Z. Kulpa, "A system of programs for the synthesis of switching circuits using the method of disjoint stars," Proceedings of IFIP Congress, pp. 61--65, April 1971.
• 6: Alan Mishchenko , Tsutomu Sasao, Large-scale SOP minimization using decomposition and functional properties, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775872]
• 7: A. Odlyzko, "On covering a product of sets with products of subsets," Discrete Mathematics, pp. 373--380, 1973.
• 8: W. J. Paul, "Realizing Boolean functions on disjoint set of variables," Theoretical Computer Science 2, pp. 383--396, 1976.
• 9: R. L. Rudell and A. Sangiovanni-Vincentelli, "Multiple-valued minimization for PLA optimization," IEEE Trans. Computer-Aided Design, Vol. CAD-6, No. 5 pp. 727--749, September 1987.
• 10: Tsutomu Sasao, Switching Theory for Logic Synthesis, Kluwer Academic Publishers, Norwell, MA, 1999
• 11: Tsutomu Sasao , Jon T. Butler, On the minimization of SOPs for bi-decomposition functions, Proceedings of the 2001 conference on Asia South Pacific design automation, p.219-224, January 2001, Yokohama, Japan [doi>10.1145/370155.370327]
• 12: T. Sasao and M. Matsuura, "DECOMPOS: An integrated system for functional decomposition," 1998 International Workshop on Logic Synthesis, Lake Tahoe, pp. 471--477, June 1998.
• 13: Bernd Voigt , Ingo Wegener, A Remark on Minimal Polynomials of Boolean Functions, Proceedings of the 2nd Workshop on Computer Science Logic, p.372-383, October 03-07, 1988