Minimization of SOPs for bi-decomposable functions and non-orthodox/orthodox functions

Download
Author
Ulker, Birol
Date
2002-03Advisor
Butler, Jon T.
Second Reader
Loomis, Herschel H., Jr.
Metadata
Show full item recordAbstract
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 [1], 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.
Rights
Copyright is reserved by the copyright owner.Collections
Related items
Showing items related by title, author, creator and subject.
-
On the minimization of SOPs for bi-decomposable functions
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 ... -
An application of decomposition techniques to a decentralized force-level decision problem.
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 ... -
The development of the Book of Worship for United States Forces
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 ...