US5587919A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus and method for logic optimization by redundancy addition and removal
Assignee: Nokia of America Corp
•
Filing: 1994-04-22
•
Granted: 1996-12-24
•
Expires: 2014-04-22
Abstract
Abstract A method is disclosed for optimizing a digital logic network through the iterative addition and removal of redundant connections. Redundancy testing is performed on connections absolutely dominated by the node of the network being optimized to find redundant connections and connections that can be added to the network which would create more redundant connections elsewhere in the network which may under appropriate conditions be removed to simplify the network. Application of the redundancy addition and removal network optimization technique to selected connections in a network improves the cost efficiency of network optimization because a network is optimized by the consideration of a reduced number of candidate connections for addition.
Inventors
- 👤 Kwang-Ting Cheng
- 👤 Luis Entrena
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 23:03
CPC Classifications
G; G01; G01R; G01R31/00; G01R31/28; G01R31/317; G01R31/3181; G01R31/3183; G01R31/318342; G06; G06F; G06F30/00; G06F30/30; G06F30/32; G06F30/327
Claims Analysis
Total Claims: 41
Claim 1
Independent Claim
129 words
A method of efficiently optimizing a digital logic network through the iterative addition and removal of redundant connections previously identified as candidate connections comprising the steps of: selecting a target node for optimization; analyzing the digital logic network to determine if connections to the target node are absolutely dominated by said target node, by determining if each of said connections must pass through the target node before reaching any primary output of the digital logic network; performing redundancy testing on each fault corresponding to each connection previously determined to be absolutely dominated; removing from the digital logic network each said fault found redundant; identifying each candidate connection for addition suggested by an assignment value implicated during redundancy testing; and adding to the network each said candidate connection found redundant.
Claim 2
Independent Claim
129 words
A method of efficiently optimizing a digital logic network through the iterative addition and removal of redundant connections previously identified as candidate connections comprising the steps of: selecting a target node for optimization; analyzing the digital logic network to determine if connections to the target node are absolutely dominated by said target node, by determining if each of said connections must pass through the target node before reaching any primary output of the digital logic network; performing redundancy testing on each fault corresponding to each connection previously determined to be absolutely dominated; removing from the digital logic network each said fault found redundant; identifying each candidate connection for addition suggested by an assignment value implicated during redundancy testing; and adding to the network each said candidate connection found redundant.
Claim 3
Dependent Claim
21 words
The method of claim 1, further comprising the step of removing from the network a connection made redundant by said addition.
Claim 4
Dependent Claim
34 words
The method of claim 1, further comprising the step of computing the cost of each node of the network and selecting a node of the network having the highest cost as the target node.
Claim 5
Dependent Claim
35 words
The method of claim 3, wherein each said candidate connection is identified based on an assignment value implicated at a node outside the fanout cone and not in the input tree of said target node.
Claim 6
Dependent Claim
29 words
The method of claim 3, wherein each said candidate connection is identified based on an assignment value implicated at a node outside the fanout cone of the target node.
Claim 7
Dependent Claim
34 words
The method of claim 2, further comprising the step of computing the cost of each node of the network and selecting a node of the network having the highest cost as the target node.
Claim 8
Dependent Claim
35 words
The method of claim 6, wherein each said candidate connection is identified based on an assignment value implicated at a node outside the fanout cone and not in the input tree of said target node.
Claim 9
Dependent Claim
49 words
The method of claim 7, further comprising the step of creating for said target node an optimization table comprising at least one said suggested candidate connection for addition and at least one said connection made redundant by the addition to the network of said at least one candidate connection.
Claim 10
Dependent Claim
29 words
The method of claim 8, wherein each said fault and any said candidate connection for said target node, respectively, is a row and a column of said optimization table.
Claim 11
Dependent Claim
28 words
The method of claim 9, further comprising the step of marking a row in said optimization table in any column suggested by the fault corresponding to said row.
Claim 12
Dependent Claim
38 words
The method of claim 10, further comprising the step of selecting each candidate connection in descending order for redundancy testing according to which candidate connection not previously tested for redundancy makes the highest cost marked fault become redundant.
Claim 13
Dependent Claim
38 words
The method of claim 10, further comprising the step of selecting each candidate connection in descending order for redundancy testing according to which candidate connection not previously tested for redundancy has the highest sum cost of marked faults.
Claim 14
Dependent Claim
38 words
The method of claim 11, further comprising the step of selecting the candidate connection having the highest sum cost of marked faults for redundancy testing where the highest cost marked fault makes more than one candidate connection redundant.
Claim 15
Dependent Claim
29 words
The method of claim 6, wherein each said candidate connection is identified based on an assignment value implicated at a node outside the fanout cone of the target node.
Claim 16
Dependent Claim
49 words
The method of claim 14, further comprising the step of creating for said target node an optimization table comprising at least one said suggested candidate connection for addition and at least one said connection made redundant by the addition to the network of said at least one candidate connection.
Claim 17
Dependent Claim
29 words
The method of claim 15, wherein each said fault and any said candidate connection for said target node, respectively, is a row and a column of said optimization table.
Claim 18
Dependent Claim
28 words
The method of claim 16, further comprising the step of marking a row in said optimization table in any column suggested by the fault corresponding to said row.
Claim 19
Dependent Claim
38 words
The method of claim 17, further comprising the step of selecting each candidate connection in descending order for redundancy testing according to which candidate connection not previously tested for redundancy makes the highest cost marked fault become redundant.
Claim 20
Dependent Claim
38 words
The method of claim 17, further comprising the step of selecting each candidate connection in descending order for redundancy testing according to which candidate connection not previously tested for redundancy has the highest sum cost of marked faults.
Claim 21
Dependent Claim
38 words
The method of claim 18, further comprising the step of selecting the candidate connection having the highest sum cost of marked faults for redundancy testing where the highest cost marked fault makes more than one candidate connection redundant.
Claim 22
Independent Claim
163 words
A method of efficiently optimizing a digital logic network through the iterative addition and removal of redundant connections previously identified as candidate connections comprising the steps of: selecting in cost descending order a node of the network not previously selected as a target node for optimization, and in succession for each said target node selected, analyzing the digital logic network to determine if connections to each said target node selected are absolutely dominated by each said target node, by determining if each of said connections must pass through each said target node before reaching any primary output of the digital logic network; performing redundancy testing on each fault corresponding to each connection previously determined to be absolutely dominated by assigning values to the nodes of the network; removing each said fault found redundant from the network and identifying each candidate connection for addition suggested by an assignment value implicated during redundancy testing; and adding to the network each said candidate connection found redundant.
Claim 23
Independent Claim
163 words
A method of efficiently optimizing a digital logic network through the iterative addition and removal of redundant connections previously identified as candidate connections comprising the steps of: selecting in cost descending order a node of the network not previously selected as a target node for optimization, and in succession for each said target node selected, analyzing the digital logic network to determine if connections to each said target node selected are absolutely dominated by each said target node, by determining if each of said connections must pass through each said target node before reaching any primary output of the digital logic network; performing redundancy testing on each fault corresponding to each connection previously determined to be absolutely dominated by assigning values to the nodes of the network; removing each said fault found redundant from the network and identifying each candidate connection for addition suggested by an assignment value implicated during redundancy testing; and adding to the network each said candidate connection found redundant.
Claim 24
Dependent Claim
21 words
The method of claim 21, further comprising the step of removing from the network a connection made redundant by said addition.
Claim 25
Dependent Claim
35 words
The method of claim 22, wherein each said candidate connection is identified based on an assignment value implicated at a node outside the fanout cone and not in the input tree of said target node.
Claim 26
Dependent Claim
18 words
The method of claim 21, wherein optimization of the network continues until the network cannot be further optimized.
Claim 27
Dependent Claim
23 words
The method of claim 24, wherein optimization of the network ceases before a determination is made that the network cannot be further optimized.
Claim 28
Dependent Claim
49 words
The method of claim 23, further comprising the step of creating for said target node an optimization table comprising at least one said suggested candidate connection for addition and at least one said connection made redundant by the addition to the network of said at least one candidate connection.
Claim 29
Dependent Claim
29 words
The method of claim 26, wherein each said fault and any said candidate connection for said target node, respectively, is a row and a column of said optimization table.
Claim 30
Dependent Claim
28 words
The method of claim 27, further comprising the step of marking a row in said optimization table in any column suggested by the fault corresponding to said row.
Claim 31
Dependent Claim
38 words
The method of claim 28, further comprising the step of selecting each candidate connection in descending order for redundancy testing according to which candidate connection not previously tested for redundancy makes the highest cost marked fault become redundant.
Claim 32
Dependent Claim
38 words
The method of claim 28, further comprising the step of selecting each candidate connection in descending order for redundancy testing according to which candidate connection not previously tested for redundancy has the highest sum cost of marked faults.
Claim 33
Dependent Claim
38 words
The method of claim 29, further comprising the step of selecting the candidate connection having the highest sum cost of marked faults for redundancy testing where the highest cost marked fault makes more than one candidate connection redundant.
Claim 34
Dependent Claim
55 words
The method of claim 31, wherein, where any connection made redundant by the addition of a candidate connection to a particular target node has been removed from the network, redundancy testing of said particular target node continues from the step of identifying each fault corresponding to each connection absolutely dominated by said particular target node.
Claim 35
Independent Claim
67 words
The method of claims 32, wherein a candidate connection found redundant is not added to the network and the only one connection made redundant by addition of said redundant candidate connection is not removed from the network where the number of fanouts of the node corresponding to said one redundant connection is greater than the number of fanouts of the node corresponding to said redundant candidate connection.
Claim 36
Dependent Claim
18 words
The method of claim 33, wherein optimization of the network continues until the network cannot be further optimized.
Claim 37
Dependent Claim
23 words
The method of claim 34, wherein optimization of the network ceases before a determination is made that the network cannot be further optimized.
Claim 38
Independent Claim
152 words
An apparatus for efficiently optimizing a digital logic network through the iterative addition and removal of redundant connections previously identified as candidate connections comprising; a means for selecting a target node for optimization; a means for analyzing the digital logic network to determine if connections to said target node are absolutely dominated by said target node, by determining if each of said connections must pass through said target node before reaching and primary output of the digital logic network; a means for performing redundancy testing on each fault corresponding to each connection previously determined to be absolutely dominated by assigning mandatory values to the nodes of the network; a means for removing each said fault found redundant from the network; a means for identifying each candidate connection for addition suggested by a mandatory value assigned during redundancy testing; and a means for adding any said candidate connection found redundant to the network.
Claim 39
Independent Claim
152 words
An apparatus for efficiently optimizing a digital logic network through the iterative addition and removal of redundant connections previously identified as candidate connections comprising; a means for selecting a target node for optimization; a means for analyzing the digital logic network to determine if connections to said target node are absolutely dominated by said target node, by determining if each of said connections must pass through said target node before reaching and primary output of the digital logic network; a means for performing redundancy testing on each fault corresponding to each connection previously determined to be absolutely dominated by assigning mandatory values to the nodes of the network; a means for removing each said fault found redundant from the network; a means for identifying each candidate connection for addition suggested by a mandatory value assigned during redundancy testing; and a means for adding any said candidate connection found redundant to the network.
Claim 40
Dependent Claim
21 words
The apparatus of claim 36, further comprising a means for removing from the network any connection made redundant by said addition.
Claim 41
Dependent Claim
18 words
The apparatus of claim 37, further comprising a means for determining whether to continue optimization of the network.
References Cited (Backward Citations)
US4703435A
Cited
US4882690A
Cited
US5257201A
Cited
US4816999A
Cited
US5029102A
Cited
US5146583A
Cited
US5003487A
Cited
US5159682A
Cited
US5461574A
Cited
US5243538A
Cited
US5243538B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-12-24 | 2000-06-24 | 2000-12-24 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-12-24 | 2004-06-24 | 2004-12-24 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-12-24 | 2008-06-24 | 2008-12-24 | $7700.00 | Window Closed / Lapsed |