Title :
An Algorithm to Derive the Complement of a Binary Function with Multiple-Valued Inputs
Author_Institution :
Department of Electronic Engineering, Osaka University
Abstract :
A recursive algorithm to obtain a complement of a sum-of-products expression for a binary function with p-valued inputs is presented. It produces at most pn/2 products for n-variable functions, whereas a conventional elementary algorithm produces O(tn·n(1-t)/2) products where t = 2P -1. It is 10-20 times faster than the elementary one when p = 2 and n = 8. For large practical-problems, it produces many fewer products than the disjoint sharp algorithm used by MINI. Appplications of the algorithm to PLA minimization are also presented.
Keywords :
Complement of logical expression; logic design; minimization of logical expressions; multiple valued logic; prime implicants; programmable logic array; switching theory; Decoding; Input variables; Logic circuits; Logic design; Minimization methods; Multivalued logic; Programmable logic arrays; Time sharing computer systems; Complement of logical expression; logic design; minimization of logical expressions; multiple valued logic; prime implicants; programmable logic array; switching theory;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.1985.1676549
