An Algorithm for Optimal PLA Folding
- 1 April 1982
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 1 (2) , 63-77
- https://doi.org/10.1109/tcad.1982.1269996
Abstract
In this paper we present a graph-theoretic formulation of the optimal PLA folding problem. The class of admissible PLA foldings is defined. Necessary and sufficient conditions for obtaining the optimal folding are given. A subproblem of the optimal problem is shown to be NP-complete, and a heuristic algorithm is given which has proven to be effective on a number of test problems.Keywords
This publication has 6 references indexed in Scilit:
- A High Density Programmable Logic Array ChipIEEE Transactions on Computers, 1979
- The complexity of satisfiability problemsPublished by Association for Computing Machinery (ACM) ,1978
- An Introduction to Array LogicIBM Journal of Research and Development, 1975
- Array Logic MacrosIBM Journal of Research and Development, 1975
- MINI: A Heuristic Approach for Logic MinimizationIBM Journal of Research and Development, 1974
- Some Basic Techniques for Solving Sparse Systems of Linear EquationsPublished by Springer Nature ,1972