Method for generating test vectors for characterizing and verifying the operation of integrated circuits

• US 5,586,125 A
• Filed: 11/22/1994
• Issued: 12/17/1996
• Est. Priority Date: 02/26/1993
• Status: Expired due to Fees

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: William T. Warner
• Inventors: Warner, William T.
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): Palys, Joseph E.
• Application Number:
  US08/344,391
• Time in Patent Office: 756 Days
• Field of Search: 371/27, 371/23, 371/13, 371/15.1, 371/22.1, 395/183.08, 395/183.09, 395/183.11, 395/183.10, 395/183.13, 395/183.14, 395/183.1, 395/183.01
• US Class Current: 714/738
• CPC Class Codes: G01R 31/318371 Methodologies therefor, e.g. algorithms, procedures

Abstract

The present invention is a method for operating a data processing system to generate a sequence of test states containing a predetermined set of states and/or transitions for use in testing an integrated circuit or the like. The method minimizes the number of additional states and/or transitions contained in the test sequence while preserving any constraints on the sequence of transitions that may be applied to the circuit to be tested. The present invention operates by defining a graph containing the predetermined set of states and/or transitions. The states are the vertices of the graph and the transitions are edges of the graph. The graph is then augmented if needed with additional states and/or transitions. The additional states and/or transitions assure the existence of an Eulerian Path through the graph. The additional states assure that the graph is connected, and that each vertex in the graph, with the possible exception of two vertices, has the same number of inbound and outgoing transitions. The Eulerian Path is then traced to provide a sequence of states that includes the input list of states and/or transitions.

Claims

1. A method for generating an Eulerian sequence of test vectors for an integrated circuit, the method comprising the steps of:

(a) generating and storing a list of input states for which the circuit is designed to operate;

(b) generating and storing a list of transitions between said input states, wherein said states correspond to inputs to said integrated circuit, each of said transitions is a transition between two such states and said transitions conform to some constraint restricting the existence of transitions;

(c) defining a graph having vertices that correspond to states in said list of input states and edges that correspond to the transitions in said list of transitions, wherein each such transition is a transition for which a test is desired and wherein each vertex corresponds to an input state to which at least one such transition provides a connection;

(d) determining all sub-graphs of said graph;

(e) determining if said graph is connected, and if said graph is not connected adding at least one transition that meets said constraint and that connects a vertex in one of said sub-graphs with a vertex in another of said sub-graphs;

(f) determine if said graph is connected, and if said graph is still not connected, adding to said graph one or more nodes that correspond to input states having transitions that conform to said constraint condition such that said transitions connect one sub-graph to another sub-graph;

(g) determining if said graph is Eulerian, and if said graph is not Eulerian, adding additional edges corresponding to transitions from said input list of transitions and, if necessary, vertexes corresponding to states from said input list of states to cause said graph to be Eulerian, wherein said transitions conform to said constraint; and

(h) determining a single path through said graph such that each transition in said list of transitions is used precisely once in traversing said path, said Eulerian sequence of test vectors for said integrated circuit being determined by the sequence of vertices on said path and transferring said Eulerian Sequence of test vectors to a testing unit for testing said integrated circuit, wherein said testing unit is selected from a group consisting of a circuit simulator and a chip tester.

2. The method as defined in claim 1, wherein the vertices further comprise a first vertex with exactly one more inbound transition than outbound transition and a second vertex with exactly one more outbound transition than inbound transition.

3. The method as defined in claim 1, wherein said step (d) of determining all sub-graphs comprises the steps of:

(d.1) defining a set of sub-graphs such that each node in said graph is in a distinct subgraph; and

(d.2) for each sub-graph, identify all transitions which connect that subgraph with another subgraph, and for each such connecting transition, combine the sub-graphs into one subgraph.

4. The method as defined in claim 1, wherein said step (e) of adding transitions between vertexes of said sub-graphs, comprises the steps of:

(e.1) determining if said graph is connected by counting the number of subgraphs, and if said graph is not connected, select a first sub-graph, until there is only one sub-graph or until all sub-graphs have been traversed;

test each vertex in said first sub-graph for a transition that meets said constraint and that connects said vertex with a vertex in another sub-graph, if such a transition exists, said transition is added to said list of transitions, and said first sub-graph and said other sub-graph are combined into one sub-graph, if no such transition exists from said first sub-graph, select a new first sub-graph; and

(e.2) if said graph is still not connected, repeating step (e.1) until either said graph is connected or the number of sub-graphs cannot be further reduced by repeating step. (e.1).

5. The method as defined in claim 1, wherein said step (f) of adding nodes and transitions between subgraphs comprises:

(f.1) for each pair of sub-graphs define a new sub-graph that contains all the vertexes that may be reached by a transition that conforms to said constraint from a vertex in a first member of said pair of sub-graphs; and

(f.2) testing each vertex in said new sub-graph to determine if there exists a transition that conforms to said constraint and that connects such vertex in said new sub-graph with a vertex in a second member of said pair of sub-graphs, and if such a transition exists adding said vertex in said new sub-graph to said graph and adding, to said list of transitions, said transition from said vertex in said first member to said vertex in said new sub-graph and said transition from said vertex in said new sub-graph to said vertex in said second member.

6. A method for generating an Eulerian sequence of test inputs for a system, the method comprising the steps of:

(a) generating and storing a list of input states for which the system'"'"'s behavior is known, wherein each distinct input to said system is an input state;

(b) generating and storing a list of transitions between said input states, wherein each of said transitions is a transition between two such states and said transitions conform to some constraint restricting the existence of transitions, wherein said sequence of test inputs includes each transition in a desired set of transitions and only a minimum number of other transitions;

(c) defining a graph having vertices that correspond to states in said list of input states and edges that correspond to the transitions in said list of transitions, wherein each such transition is a transition in said desired set of transitions and wherein the vertices correspond to inputs to said system at opposite ends of such transitions;

(d) determining all subgraphs of said graph;

(e) determining if said graph is connected by counting the number of subgraphs, and if said graph is not connected, select a first sub-graph, until there is only one sub-graph or until all sub-graphs have been traversed;

test each vertex in said first sub-graph for a transition that meets said constraint and that connects said vertex with a vertex in another sub-graph, if such a transition exists, add said transition to said list of transitions, and combine said first sub-graph and said other sub-graph into one sub-graph;

(f) determine if said graph is connected by again counting the number of sub-graphs, and if said graph is still not connected, repeat step (e) until either said graph is connected or the number of sub-graphs cannot be further reduced by repeating step (e);

(h) determine if said graph is connected, and if said graph is still not connected, locate one or more vertexes that connect one sub-graph to another sub-graph by means of transitions that conform to said constraint condition;

(i) determining if said graph is Eulerian, and if said graph is not Eulerian, adding additional transitions from said input list of transitions and, if necessary, states from said input list of states to cause said graph to be Eulerian; and

(j) determining a single path through said graph such that each transition in said list of transitions is used precisely once in traversing said path, said Eulerian sequence of test inputs being determined by the sequence of vertices on said path and transferring said Eulerian Sequence of test vectors to a testing unit for testing said integrated circuit, wherein said testing unit is selected from a group consisting of a circuit simulator and a chip tester.

7. The method as defined in claim 6, wherein said system is an integrated circuit.

8. The method as defined in claim 6, where in said step (d) of determining all sub-graphs comprises the steps of:

(d.1) defining a set of sub-graphs such that each node in said graph is in a distinct subgraph; and

(d.2) for each subgraph, identify all transitions which connect that sub-graph with another subgraph, and for each such connecting transition, combine the subgraphs into one subgraph.