Minimal covering problem and PLA minimization |
| |
Authors: | Ming Huei Young Saburo Muroga |
| |
Affiliation: | (1) Silicon Compiler Inc., 2045 Hamilton Ave., 95125 San Jose, California;(2) Department of Computer Science, University of Illinois, 61801 Urbana, Illinois |
| |
Abstract: | Solving the minimal covering problem by an implicit enumeration method is discussed. The implicit enumeration method in this paper is a modification of the Quine-McCluskey method tailored to computer processing and also its extension, utilizing some new properties of the minimal covering problem for speedup. A heuristic algorithm is also presented to solve large-scale problems. Its application to the minimization of programmable logic arrays (i.e., PLAs) is shown as an example. Computational experiences are presented to confirm the improvements by the implicit enumeration method discussed.This work was supported in part by the National Science Foundation under Grants Nos. MCS77-09744 and MCS81-08505 and also by the Department of Computer Science.M.-H. Young was with the Department of Computer Science, University of Illinois, Urbana, Illinois. |
| |
Keywords: | Minimal covering problem implicit enumeration method Quine-McCluskey method logic minimization programmable logic arrays minimal sum heuristic minimization |
本文献已被 SpringerLink 等数据库收录! |
|