An Algorithm to Derive the Complement of a Binary Function with Multiple-Valued Inputs
- 1 February 1985
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-34 (2), 131-140
- https://doi.org/10.1109/tc.1985.1676549
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
This publication has 9 references indexed in Scilit:
- Input Variable Assignment and Output Phase Optimization of PLA'sIEEE Transactions on Computers, 1984
- Boolean Comparison of Hardware and FlowchartsIBM Journal of Research and Development, 1982
- Multiple-Valued Decomposition of Generalized Boolean Functions and the Complexity of Programmable Logic ArraysIEEE Transactions on Computers, 1981
- computer simplification of multi-valued switching functionsPublished by Elsevier ,1977
- MINI: A Heuristic Approach for Logic MinimizationIBM Journal of Research and Development, 1974
- On Complementation of Boolean FunctionsIEEE Transactions on Computers, 1972
- Analyzing Errors with the Boolean DifferenceIEEE Transactions on Computers, 1968
- The problem of simplifying logical expressionsThe Journal of Symbolic Logic, 1959
- Simplest normal truth functionsThe Journal of Symbolic Logic, 1955