Multiple-Valued Minimization for PLA Optimization
- 1 September 1987
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 6 (5) , 727-750
- https://doi.org/10.1109/tcad.1987.1270318
Abstract
This paper describes both a heuristic algorithm, Espresso-MV, and an exact algorithm, Espresso-EXACT, for minimization of multiple-valued input, binary-valued output logic functions. Minimization of these functions is an important step in the optimization of programmable logic arrays (PLA's). In particular, the problems of two-level multiple-output minimization, minimization of PLA's with input decoders and solutions to the input encoding problem rely on efficient solutions to the multiple-valued minimization problem. Results are presented for a large class of PLA's taken from actual chip designs. These results show that the heuristic algorithm Espresso-MV comes very close to producing optimum solutions for most of the examples. Also, results from a chip design in progress at Berkeley show how important multiple-valued minimization can be for PLA optimization.Keywords
This publication has 14 references indexed in Scilit:
- Optimal State Assignment for Finite State MachinesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1985
- An Algorithm to Derive the Complement of a Binary Function with Multiple-Valued InputsIEEE Transactions on Computers, 1985
- Input Variable Assignment and Output Phase Optimization of PLA'sIEEE Transactions on Computers, 1984
- Logic Minimization Algorithms for VLSI SynthesisPublished by Springer Nature ,1984
- Multiple Constrained Folding of Programmable Logic Arrays: Theory and ApplicationsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1983
- An Algorithm for Optimal PLA FoldingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1982
- Multiple-Valued Decomposition of Generalized Boolean Functions and the Complexity of Programmable Logic ArraysIEEE Transactions on Computers, 1981
- Hardware Implementation of a Small System in Programmable Logic ArraysIBM Journal of Research and Development, 1975
- Computer Minimization of Multivalued Switching FunctionsIEEE Transactions on Computers, 1972
- A Way to Simplify Truth FunctionsThe American Mathematical Monthly, 1955