Browse Prior Art Database

Boolean Equivalence Check

IP.com Disclosure Number: IPCOM000050352D
Original Publication Date: 1982-Oct-01
Included in the Prior Art Database: 2005-Feb-10
Document File: 2 page(s) / 43K

Publishing Venue

IBM

Related People

Bahnsen, RJ: AUTHOR

Abstract

A Boolean analysis program can be provided to perform a Boolean comparison of two logic models. This comparison may be performed by adding a checking network to the output of the two models, as shown in Fig. 1. A counter example is given if there is some input pattern that will make either of the check outputs equal to 1. If there is no counter example, the models are equivalent.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 100% of the total text.

Page 1 of 2

Boolean Equivalence Check

A Boolean analysis program can be provided to perform a Boolean comparison of two logic models. This comparison may be performed by adding a checking network to the output of the two models, as shown in Fig. 1. A counter example is given if there is some input pattern that will make either of the check outputs equal to 1. If there is no counter example, the models are equivalent.

The time required to perform the Boolean comparison using Fig. 1 can be reduced by using the improved check network shown in Fig. 2 where the two check outputs of Fig. 1 are ORed to produce a single check output. A counter example is given if the output of the OR can be made 1 for some input pattern. If there is no counter example, the models are equivalent.

In case a counter example is found using Fig. 2, this counter example is imposed on the primary inputs as constant values to determine which of the check outputs of Fig. 1 produces a 1. This provides information as to whether the Model 1 output is 1 while the Model 2 output is 0, or vice-versa.

Because of the way a Boolean analysis program operates, the described technique should make such analysis programs run almost twice as fast as the original version for the case where there is no counter example (equivalent models). Since this case requires the longest run time, the saving is significant.

1

Page 2 of 2

2

[This page contains 4 pictures or other non-text objects]