Minimization of SOPs for bi-decomposable functions and non-orthodox/orthodox functions
Butler, Jon T.
Loomis, Herschel H., Jr.
MetadataShow full item record
A logical function f is AND bi-decomposable if it can be written as f x1, x2)= h1 (x1) h2(x2), where x1 and x2 are disjoint. Such functions are important because they can be efficiently implemented. Also many benchmark functions are AND bi-decomposable. Surprisingly, the minimal sum of products (MSOP) of f is not always obtainable by finding the MSOP of h1 and h2 and applying the law of distributivity. However, a special class of functions called orthodox functions, introduced by Sasao and Butler , do have this property. This thesis focuses on orthodox functions, and the remaining non-orthodox functions. It is shown how to build up orthodox functions from orthodox functions on fewer variables. An algorithm is presented for generating families of non-orthodox functions. A test program is developed to test the results of the proposed algorithm and also other programs are developed to conduct experiments with both orthodox and non-orthodox functions. Results are presented that represent the first steps toward completely characterizing bi-decomposable functions that can be efficiently implemented.
Approved for public release; distribution is unlimited.
Showing items related by title, author, creator and subject.
Sasao, Tsutomu; Butler, Jon T. (2001);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 ...
Hutchison, William Edwin (University of Maryland, 1967);An approach to a force level problem which incorporates inputs of cost, operational effectiveness and requirements into a decision procedure is suggested. The problem is then defined within the framework of a decomposable ...
Carr, Gary W. (1996-04);The Book of Worship for United States Forces has been used as the primary worship resource in military chapels, in the field, as well as aboard ships since 1974. It is a hybrid hymnal combining the faith traditions of ...