Patent ID: 7246334

Claim:
A method of identifying state nodes in a sequential digital integrated circuit, the method comprising: a. providing a schematic of the circuit; b. defining a graph G=(V, E 1 , E 2 ), where V is a set of vertices, E 1 is a set of directed edges, and E 2 is a set of undirected edges, and wherein both a directed edge and an undirected edge can exist between a pair of vertices in the graph, the graph being constructed in accordance with the following rules: (i) for each node in the circuit, including input, output and inout nodes in the circuit, creating a vertex in the graph, ignoring power supply nodes and ground nodes; (ii) for every transistor in the circuit, adding a directed edge from the vertex representing the gate node of said transistor to the vertex representing the source node of said transistor if the source node is not a power supply node or a ground node, adding a directed edge from the vertex representing the gate node of said transistor to the vertex representing the drain node of said transistor if the drain node is not a power supply node or a ground node, and adding an undirected edge between the vertices representing the source node and the drain node of said transistor if neither said source node nor said drain node is a power supply node or a ground node; c. in the defined graph, identifying loops of vertices having the following properties: (i) the loop consists of at least two directed edges; (ii) vertices representing input nodes can not be part of the loop; (iii) there must exist at least one input such that all paths from the input to any node in the loop consist of at least one undirected edge; and (iv) nodes that are part of the loop but do not have any outgoing directed edge cannot be a state node; and (v) there exists at least one node in the loop from which all other nodes in the loop are reachable by a directed edges only.