Apparatus and method for logic optimization by redundancy addition and removal
First Claim
1. 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.
6 Assignments
0 Petitions
Accused Products
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.
-
Citations
38 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
21. 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. - View Dependent Claims (22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35)
-
-
36. 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. - View Dependent Claims (37, 38)
-
Specification