Minimization of SOPs for bi-decomposable functions and non-orthodox/orthodox functions
Loading...
Authors
Ulker, Birol
Subjects
Advisors
Butler, Jon T.
Date of Issue
2002-03
Date
Publisher
Monterey, Calif. Naval Postgraduate School
Language
Abstract
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.
Type
Thesis
Description
Series/Report No
Department
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
xviii, 125 p. : ill. ;
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
Copyright is reserved by the copyright owner.