Patent US5526514A successfully refreshed from Google Patents.
US5526514A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for circuit verification and multi-level circuit optimization based on structural implications
Assignee: Individual
•
Filing: 1994-06-21
•
Granted: 1996-06-11
•
Expires: 2014-06-21
Abstract
Abstract A method for verifies that two integrated circuits are functionally equivalent by extracting equivalencies between internal nodes of the two circuits. Values are assigned to internal nodes in the first circuit and the effects of the assignments are determined in the rest of the first circuit and the second circuit. These effects, or implications, are analyzed to find internal equivalents between the first and second circuit. These steps are repeated with different values assigned to different nodes in the first circuit. The set of stored implications is used to determine if the two circuits are functionally equivalent. A method is also disclosed for using the equivalencies, or indirect implications determined above to remove redundancies from the second circuit using a set of predetermined transformations. Based on an indirect implication a particular transform is selected and applied to the second circuit. This transformation is intended to create redundancies elsewhere in the circuit that can be removed thus optimizing the second circuit.
Inventors
- 👤 Dhiraj Pradhan
- 👤 Wolfgang Kunz
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 14:26
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/32; G06F30/33; G06F30/3308
Claims Analysis
Total Claims: 8
Claim 1
Independent Claim
280 words
A method for verifying that a first logic circuit is equivalent to a second logic circuit, the first logic circuit having a first plurality of inputs and a first plurality of internal nodes and the second logic circuit having a second plurality of inputs and a second plurality of internal nodes, the method comprising the steps of: a) coupling the first plurality of inputs to the second plurality of inputs; b) assigning a first combination of signal values to a combination of at least one of the first plurality of internal nodes, such that the corresponding assignment creates an unjustified signal in said node; c) determining, through logic implications, signal values for the first plurality and second plurality of internal nodes not included in the combination of some or all the first plurality of internal nodes such that the signal values result in conditions which are consistent with the first combination of signal values in the the combination of at least one of the first plurality of internal nodes; d) extracting a resulting combination of signal values from a second combination of at least one of the second plurality of internal nodes corresponding to the first combination signal values; e) storing the resulting combination of signal values in an internal memory; f) repeating the steps of assigning, determining, extracting and storing for a different combination of at least one of the first plurality of internal nodes of the first and the second circuit to create a list of indirect implications; and g) using the list of indirect implications to verify that the first and second circuits are equivalent based on a set of pre-stored signal relationships in the internal memory.
Claim 2
Independent Claim
280 words
A method for verifying that a first logic circuit is equivalent to a second logic circuit, the first logic circuit having a first plurality of inputs and a first plurality of internal nodes and the second logic circuit having a second plurality of inputs and a second plurality of internal nodes, the method comprising the steps of: a) coupling the first plurality of inputs to the second plurality of inputs; b) assigning a first combination of signal values to a combination of at least one of the first plurality of internal nodes, such that the corresponding assignment creates an unjustified signal in said node; c) determining, through logic implications, signal values for the first plurality and second plurality of internal nodes not included in the combination of some or all the first plurality of internal nodes such that the signal values result in conditions which are consistent with the first combination of signal values in the the combination of at least one of the first plurality of internal nodes; d) extracting a resulting combination of signal values from a second combination of at least one of the second plurality of internal nodes corresponding to the first combination signal values; e) storing the resulting combination of signal values in an internal memory; f) repeating the steps of assigning, determining, extracting and storing for a different combination of at least one of the first plurality of internal nodes of the first and the second circuit to create a list of indirect implications; and g) using the list of indirect implications to verify that the first and second circuits are equivalent based on a set of pre-stored signal relationships in the internal memory.
Claim 3
Dependent Claim
30 words
The method of claim 1 and further comprising the step of: h) finding internal signals in the second circuit that are functionally equivalent to internal signals of the first circuit.
Claim 4
Dependent Claim
25 words
The method of claim 1, and further comprising prior to step (f) the step of establishing a user defined recursion level for the repeating step.
Claim 5
Independent Claim
106 words
A method for optimizing a circuit, comprising the steps of: storing predetermined circuit transformations for optimizing the circuit; making the circuit prime and irredundant; resetting all nodes of the circuit to pre-determined values; assigning a signal value to a node of the circuit such that the assignment creates an unjustified signal in said nodes; measuring the signal values of the other nodes in the circuit to derive an indirect implication for the node using recursive learning; modifying the circuit based on the indirect implication; and repeating the steps of assigning, measuring and modifying on the different nodes of the circuit so as to optimize the circuit.
Claim 6
Independent Claim
106 words
A method for optimizing a circuit, comprising the steps of: storing predetermined circuit transformations for optimizing the circuit; making the circuit prime and irredundant; resetting all nodes of the circuit to pre-determined values; assigning a signal value to a node of the circuit such that the assignment creates an unjustified signal in said nodes; measuring the signal values of the other nodes in the circuit to derive an indirect implication for the node using recursive learning; modifying the circuit based on the indirect implication; and repeating the steps of assigning, measuring and modifying on the different nodes of the circuit so as to optimize the circuit.
Claim 7
Dependent Claim
43 words
The method of claim 4, wherein said step of making the circuit prime and irredundant comprises the steps of: determining nodes of the circuit which are constant for all input values; and assigning a predetermined value to the node to isolate the node.
Claim 8
Dependent Claim
88 words
The method of claim 4, wherein said step of apply circuit transformations comprises the steps of: applying the transformation y'=y 1 +ƒ when the implication y=0 ƒ=1 is true; applying the transformation y'=y 0 +ƒ when the implication y=0 ƒ=0 is true; applying the transformation y'=ƒy 1 when the implication y=1 ƒ=1 is true; applying the transformation y'=ƒy 0 when the implication y=1 ƒ=0 is true; and wherein y,y 1 ,y 0 and f are logic functions and y' is a functionally equivalent transformation of the function y.
References Cited (Backward Citations)
US4942536A
Cited
US4803636A
Cited
US5175696A
Cited
US4816999A
Cited
US5159682A
Cited
US5018144A
Cited
US5243538A
Cited
US5243538B1
Cited
US5359539A
Cited
US5237513A
Cited
US5287289A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-06-11 | 1999-12-11 | 2000-06-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-06-11 | 2003-12-11 | 2004-06-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-06-11 | 2007-12-11 | 2008-06-11 | $7700.00 | Window Closed / Lapsed |