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

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.