Browse Prior Art Database

Speedup of Minimization Programs

IP.com Disclosure Number: IPCOM000051232D
Original Publication Date: 1982-Aug-01
Included in the Prior Art Database: 2005-Feb-10
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Kurtzberg, JM: AUTHOR [+2]

Abstract

The problem of finding economical covers for PLAs (Programmable Logic Arrays) is important for LSI and VLSI (J. Paul Roth, Computer Logic, Testing and Verification, Computer Science Press, Rockville, Maryland, 1980.). Minimization procedures and their approximations are hampered by long running time and enormous storage requirements. A novel method of adaptation of the D-algorithm (J. Paul Roth, Computer Logic, Testing and Verification, Computer Science Press, Rockville, Maryland, 1980.) to this two-level minimization problem is described herein. An essential step in one of the best of the extant approximations, SHRINK, is that of COFACE, that of changing the coordinate of a cube in the extant cover from a 1 or 0 to an x.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 62% of the total text.

Page 1 of 1

Speedup of Minimization Programs

The problem of finding economical covers for PLAs (Programmable Logic Arrays) is important for LSI and VLSI (J. Paul Roth, Computer Logic, Testing and Verification, Computer Science Press, Rockville, Maryland, 1980.). Minimization procedures and their approximations are hampered by long running time and enormous storage requirements. A novel method of adaptation of the D- algorithm (J. Paul Roth, Computer Logic, Testing and Verification, Computer Science Press, Rockville, Maryland, 1980.) to this two-level minimization problem is described herein. An essential step in one of the best of the extant approximations, SHRINK, is that of COFACE, that of changing the coordinate of a cube in the extant cover from a 1 or 0 to an x. This amounts to tentatively deleting the corresponding variable from a given term, but it must be changed to ascertain whether or not this change is justifiable. In SHRINK, this is done by interfacing the new cube with each member of the OFF-array, which requires computation of the OFF-array, which may require excessive time and space.

The new method, described herein, is to treat the COFACE change, from a 0 or 1 to an x, as if it were a FAILURE and to invoke the D-algorithm to ascertain whether or not there is a TEST for this failure. If there is, then this change in the array has MODIFIED the function and it is an inadmissible change. If there is no test, then this attempted simplification of the function is a...