Browse Prior Art Database

Test Generation Using an Efficient Weight Generator

IP.com Disclosure Number: IPCOM000036436D
Original Publication Date: 1989-Sep-01
Included in the Prior Art Database: 2005-Jan-29
Document File: 6 page(s) / 77K

Publishing Venue

IBM

Related People

Dennis, SF: AUTHOR [+4]

Abstract

A technique is described whereby a weight generator provides an efficient method of test generation, as used in the analysis of large combinational computer logic designs. The technique is efficient because it identifies a subset of remaining faults, which are likely to require similar weights, rather than attempting to generate optimal sets of weights for all the remaining faults. The technique is fast, since weights are generated, for the faults in the selected subset, by generating approximate test patterns.

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 24% of the total text.

Page 1 of 6

Test Generation Using an Efficient Weight Generator

A technique is described whereby a weight generator provides an efficient method of test generation, as used in the analysis of large combinational computer logic designs. The technique is efficient because it identifies a subset of remaining faults, which are likely to require similar weights, rather than attempting to generate optimal sets of weights for all the remaining faults. The technique is fast, since weights are generated, for the faults in the selected subset, by generating approximate test patterns.

Typically, generating tests for large combinational logic designs requires intensive computer processing analysis. In prior art, one technique [1] randomly searched the input space. However, the random search can be made more efficient by using weighted random patterns, such as sets of values on the primary inputs that are equal to a logic one with a probability that may differ from
0.5 2,3,4,5, whereby in some of the previously weighted random test generation algorithms, the weights were chosen so as to optimize the test generation process for all the remaining faults. However, conflicting requirements for different faults can diminish the effectiveness of the weighted random search, particularly when weights are constructed for all the remaining faults. In this case, they are likely to be close to 0.5.

Also in the prior art 5, certain subsets of the remaining faults, with weights optimized for each subset, were shown to be more efficient than attempting to cover all remaining faults with one set of weights. Weights were constructed by first generating tests for individual faults. Faults were then grouped into subsets by approximately subsuming tests for various faults. Finally, the ones and zeros in the subsumed pattern were translated into weights in a fixed fashion. For example, ones could be translated to a probability of 15/16 of getting a one, and zeros could be translated to a probability of 15/16 of getting a zero. Each set of weights was used to generate weighted random patterns and to fault simulate these patterns against all remaining faults, until the set of weights lost its effectiveness in exposing more faults.

The advantage of implementing the prior-art approach 5 was that test patterns were found for all testable faults, because of the use of an exact test generator. However, efficiency became a problem, since the use of a test generator to construct the weights required that tests be derived for many faults, thereby degrading the performance of the weight generator. The concept described herein implements a new method for identifying suitable subsets and provides a new technique for constructing the weights for the faults in the chosen subset. The technique uses an "approximate" test generator whereby an algorithm generates patterns that satisfy some of the requirements for an exact test, but not necessarily all the requirements.

The actual weighted rando...