Browse Prior Art Database

Transform System for Boolean Comparison

IP.com Disclosure Number: IPCOM000099974D
Original Publication Date: 1990-Mar-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 3 page(s) / 100K

Publishing Venue

IBM

Related People

Bahnsen, RJ: AUTHOR [+3]

Abstract

Disclosed is a transform system for reducing the complexity of Boolean comparison problems by means of transforms that do not adversely affect the comparison results.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Transform System for Boolean Comparison

       Disclosed is a transform system for reducing the
complexity of Boolean comparison problems by means of transforms that
do not adversely affect the comparison results.

      Boolean comparison is a technique that compares two
combinational logic models to see if they perform the same function
[1].  For each primary output of one model it is desired to verify
that its Boolean function of the primary inputs is equivalent to that
of the corresponding primary output of the other model.

      In order to improve the efficiency of Boolean comparison,
transforms are applied to simplify the logic without altering the
result of the comparison.  A transform system patterned after the
Logic Synthesis System (LSS) [2] has been defined that permits the
user to run a sequence of transforms on a segment just prior to the
Boolean analysis for the equivalence check.  The purpose of the
transforms is to reduce the complexity of the segment so that the
equivalence check can be successfully performed.  The segment
transformation system includes the following items:
1.   An Application Program Interface (API) that permits transforms
to be written in a relatively easy manner.
2.   A set of predefined transforms for reducing the complexity of a
segment.
3.   A scenario file that specifies the sequence of transforms to be
used.

      While the transform system is similar to LSS, its purpose is
different.  The purpose of transforms for synthesis is to preserve
Boolean functions while optimizing the logic.  The purpose of
transforms for Boolean comparison is to preserve the
equivalence/nonequivalence result while reducing the complexity of
the logic.  Part (a) of the figure illustrates cones of logic driving
corresponding outputs Z1 of model 1 and Z2 of model 2.  Corresponding
inputs have been given the same names X1, ..., Xn in both models.  To
verify that the Boolean functions of Z1 and Z2 are the same, these
outputs can be Exclusive- ORed as shown in part (b) of the figure.
The Exclusive-OR output Zc will be identically 0 if the functions Z1
and Z2 are equal. Otherwise, the function Zc will not be identically
0.  Zc is said to be satisfiable if and only if Zc is not identically
0.  Thus, outputs Z1 and Z2 are n...