Browse Prior Art Database

Minimal Test Set Calculation

IP.com Disclosure Number: IPCOM000051880D
Original Publication Date: 1981-Mar-01
Included in the Prior Art Database: 2005-Feb-11
Document File: 6 page(s) / 85K

Publishing Venue

IBM

Related People

Roth, JP: AUTHOR [+2]

Abstract

The number of tests computed to detect any of a given set of failures i a logic design - chip, cardboard- in very large-scale integration (VLSI) constitutes a serious problem. As the size of the complexity of the logic increases, the number of tests for conventional test generators seems to grow exponentially. A method is described which, in a reasonable increase in computation, achieves a minimal set of tests to detect a given set of failures. The method is heuristic so that a minimum is not guaranteed, but it is minimal in that it contains no redundant tests; experiments indicate substantial reductions over previous methods.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 29% of the total text.

Page 1 of 6

Minimal Test Set Calculation

The number of tests computed to detect any of a given set of failures i a logic design - chip, cardboard- in very large-scale integration (VLSI) constitutes a serious problem. As the size of the complexity of the logic increases, the number of tests for conventional test generators seems to grow exponentially. A method is described which, in a reasonable increase in computation, achieves a minimal set of tests to detect a given set of failures. The method is heuristic so that a minimum is not guaranteed, but it is minimal in that it contains no redundant tests; experiments indicate substantial reductions over previous methods.

It is assumed that the logic design is of the LSSD (Level Sensitive Scan Design) format [1,2,3], so that from a test point of view, the logic may be assumed to be combinational so that it has no memory.

Let then L be an (acyclic) logic design and C=C(L) be a category of failures F for which a test-set is required. The steps of the method are as follows:

1. Pick a failure FO in C, on the basis of depth from the primary outputs POs; this criterion has been proven out to be excellent in the selection of a failure whose test covers a maximal set of other failures.

2. Compute a test cube tc in the D-algorithm for failure FO; tc specifies signals, 1 or 0 on some primary inputs PI while the remainder remains unspecified: to each is assigned the symbol x; this has the meaning that the xs may be assigned any value, 1 or 0, independently, and still a test T is obtained. For us the problem of minimal test-set generation depends upon how these unspecified inputs are assigned.

3. Let L be subdivided into pairwise disjoint portions in the following manner. If r is the number of primary inputs of L, start with r subdivisions, one for each PI. If subdivisions i and j feed a common block, merge these subdivisions. Proceed in this manner until one of the forming subdivisions reaches a size k, a parameter selected by the user of the program; the default choice would be the number of xs, measuring the indeterminancy, of tc. After this bound is reached, those subdivisions are split off and the procedure continued inductively until all circuits in L have been assigned a subdivision.

If natural subdivisions of L are known, such as functional subdivisions, then the subdivisions may be restricted to lie within these blocks.

4. Pick an untested failure Fl on the basis of depth, in each subdivision. Order the subdivisions, hence these failures, according to depth.

5. Restoring the test cube tc computed in 2, extend tc by invoking the D- algorithm again so that it covers - tests - F1 (as well as FO).

6. Use TESTDETECT [1,4] to ascertain all failures covered by the new tc.

7. Return to 4 and repeat until either tc is exhausted of its indeterminate xs or else all failures are covered.

1

Page 2 of 6

8. When step 7 has been completed, return to step 1 and select a new untested failure. Continue until a minimal...