Browse Prior Art Database

Signal Probability Assisted Test Generation

IP.com Disclosure Number: IPCOM000119963D
Original Publication Date: 1991-Mar-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 3 page(s) / 117K

Publishing Venue

IBM

Related People

Savir, J: AUTHOR

Abstract

Disclosed is a method to accelerate the computation of test patterns by a test generator. This acceleration will reduce the cost associated with the generation of test patterns. The method can be embedded in DC test generation algorithms, AC test generation algorithms, and weighted random test pattern generation algorithms.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Signal Probability Assisted Test Generation

      Disclosed is a method to accelerate the computation of
test patterns by a test generator.  This acceleration will reduce the
cost associated with the generation of test patterns. The method can
be embedded in DC test generation algorithms, AC test generation
algorithms, and weighted random test pattern generation algorithms.

      Most test generation algorithms have two phases: the error
propagation phase and line justification phase.  The error
propagation phase is a forward trace from the site of the fault to a
primary output (PO) or latch.  During this phase, non-controlling
values are assigned to inputs of gates residing on the propagation
path.  This assignment facilitates the error propagation to the
intended PO or latch.

      The line justification phase is basically a backward trace from
the previously assigned values to the primary inputs (PIs) and
latches.  During this phase an attempt is made to "justify" the
previously assigned values by finding consistent input and latch
values that will impose the values required by the error propagation
phase.

      The error propagation phase is usually fast.  The line
justification phase is usually very time consuming due to the fact
that it involves a considerable number of a "one-to-many" mappings.
For example, in order to justify a 0 at an output of a three-input
AND gate, it is necessary to choose one of three different
assignments.  Many times a given choice ends up in inconsistencies
that require going back and making a different choice.  These "remade
decisions" slow down the algorithm and are the major cause for the
low performance of test generators.

      We define the signal probability of a line to be the
probability that a line will assume a value 1 as a result of a random
application of input vectors.  Consequently, the signal probability
of a line is also the fraction of all possible input vectors that
yield a value 1 at the desired line.  A signal probability of 0.9
means that 90% of the entire input space will impose a value 1 at the
given line, and only 10% will impose a value 0.  Thus, a line with
signal probability larger than 0.5 will "see" more 1s than 0s; and a
line with signal probability smaller than 0.5 will "see" more 0s than
1s.

      The basic idea of this disclosure is to make the choices in the
line justification phase based on the signal probability of the
lines.  Whenever a value 1 needs to be assigned to one of the inputs
of an OR gate, that input with the largest signal probability should
be chosen; and whenever a 0 needs to be assigned to an input of an
AND gate, that input with the smallest signal probability should be
chosen.  This strategy will have the best chance of justifying the
line values assumed during the error propagation phase without
inducing conflicts (at least,...