On the minimization of SOPs for bi-decomposable functions
Butler, Jon T.
MetadataShow full item record
A function f is AND bi-decomposable if it can be written as f (X1;X2) = h1(X1)h2(X2). In this case, a sum-ofproducts expression (SOP) for f is obtained from minimum SOPs (MSOP) for h1 and h2 by applying the law of distributivity. If the result is an MSOP, then the complexity of minimization is reduced. However, the application of the law of distributivity to MSOPs for h1 and h2 does not always produce an MSOP for f . We show an incompletely specified function of n(nô 1) variables that requires at most n products in an MSOP, while 2nô 1 products are required by minimizing the component functions separately. We introduce a new class of logic functions, called orthodox functions, where the application of the law of distributivity to MSOPs for component functions of f always produces an MSOP for f . We show that orthodox functions include all functions with three or fewer variables, all symmetric functions, all unate functions, many benchmark functions, and few random functions with many variables.
Asia and South Pacific Design Automation Conference (ASP-DAC'2001), Jan. 30-Feb. 2, 2001, Yokohama, Japan, pp.219-224.This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. As such, it is in the public domain, and under the provisions of Title 17, United States Code, Section 105, may not be copyrighted.
Showing items related by title, author, creator and subject.
Tirumalai, Parthasarathy; Butler, Jon T. (1991-02);We analyze the performance of various heuristic algorithms for minimizing realizations of multiple-valued functions by the newly developed CCD 191 and CMOS [W] programmable logic arrays. The functions realized by ...
Tirumalai, Parthasarathy; Butler, Jon T. (1988-05);We compare the performance of three heuristic algorithms [3,6,13] for the minimization of sum-of-products expressions realized by the newly developed multiplevalued programmable logic arrays . Heuristic methods are ...
Balut, Stephen John (Monterey, California. Naval Postgraduate School, 1973-03);Investigation theory treats discrete combinatorial optimization problems in which there are several objects passing through a region containing one or more investigators who are to investigate, according to some criteria, ...