Browse Prior Art Database

Redundancy Determination

IP.com Disclosure Number: IPCOM000047302D
Original Publication Date: 1983-Oct-01
Included in the Prior Art Database: 2005-Feb-07
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Roth, JP: AUTHOR

Abstract

In many minimization and approximate minimization procedures for programmed logic arrays -- more generally, 2-level logical realizations -- it is desired to ascertain whether or not a given cube, whether single- or multiple-output, is redundant with respect to a set of cubes, the totality defining some cubical function. The most efficient previous method known to me involved performing the sharp product of this set of cubes from the cube in question: the cube is redundant if and only if this product is empty. For cubes of large dimension this sharp product could be quite formidable in size and in time requirements for its execution. The method described here avoids such expansion and effects a determination economic in both time and space. The Method Let z be a cube [1].

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

Page 1 of 1

Redundancy Determination

In many minimization and approximate minimization procedures for programmed logic arrays -- more generally, 2-level logical realizations -- it is desired to ascertain whether or not a given cube, whether single- or multiple-output, is redundant with respect to a set of cubes, the totality defining some cubical function. The most efficient previous method known to me involved performing the sharp product of this set of cubes from the cube in question: the cube is redundant if and only if this product is empty. For cubes of large dimension this sharp product could be quite formidable in size and in time requirements for its execution. The method described here avoids such expansion and effects a determination economic in both time and space. The Method Let z be a cube [1]. Let C be a set of cubes which, together with z, defines some desired cubical function, mapping strings of bits of fixed length into strings of bits of (in general some other) fixed length. z is said to be "redundant" with respect to C if C covers all the vertices of z: this means that z may be deleted from the cover consisting of C and z with no change to the function defined by this cover; z is not necessary. STEP 1. Form z C, the assemblage of interfaces of each member of C with z. STEP 2. Call this assemblage E. Select any member, any cube, e of E. Perform the COFACE operation on each bound

coordinate of e with respect to E, using the adaptation of

the D-algorithm for...