Title :
Using Decision Trees to Derive the Complement of a Binary Function with Multiple-Valued Inputs
Author_Institution :
MITRE Corporation, Bedford, MA 01730, and the College of Computer Science, Northeastern University
Abstract :
An algorithm to minimize decision trees of Boolean functions with multiple-valued inputs is presented. The recursive algorithm is used to obtain a complement of a sum-of-products expression for a binary function with multiple-valued inputs. In the case where each input is p-valued, the algorithm produces at most pn−l products for n-variable functions, whereas Sasao´s algorithm produces pn/2 products. This upper bound on the number of products is the best possible.
Keywords :
Complement of logical expression; decision trees; disjunctive normal form; minimization of logical expressions; multiplevalued logic; products; Absorption; Boolean functions; Decision trees; Decoding; Logic circuits; Logic design; Minimization methods; Programmable logic arrays; Time sharing computer systems; Upper bound; Complement of logical expression; decision trees; disjunctive normal form; minimization of logical expressions; multiplevalued logic; products;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.1987.1676883
