Model-based diagnostic system with automated procedures for next test selection

<b>BACKGROUND OF THE INVENTION</b>

Field of Invention

The present invention pertains to the field of device testing. More particularly, this invention relates to a model-based diagnostic system that provides automated tools for selection of one or more next tests to apply to a device under test.

Art Background

A wide variety of systems including mechanical, electrical and chemical systems as well a combinations thereof are commonly tested under a variety of environments including manufacturing test environments and field support environments. These systems include electronic systems such as circuit boards-and full systems having a variety of circuit boards. These systems also include automobiles, satellite systems, and test equipment. Such a system while undergoing a test cycle may be referred to as a device under test (DUT).

Such a DUT typically includes a variety of components. Such components include, for example, integrated circuit devices, electrical components, battery systems, mechanical components, electrical buses, wiring components, and wiring harness and backplane components. Any one or more of such components may fail and cause a failure of the DUT.

Prior diagnostic systems for determining likely failed components in a DUT include model-based diagnostic systems. A model-based diagnostic system may be defined as a diagnostic system that renders conclusions about the state of the DUT using actual DUT responses from applied tests as an input to the diagnostic system. Such a diagnostic system is usually based upon computer generated models of the DUT and its components and the diagnostic process.

It is usually desirable to employ a model-based diagnostic system that is based upon a more manageable model of DUT characteristics. Such a model-based diagnostic system usually minimizes the amount of modeling information for a DUT that must be generated by a user before the system can be applied to the DUT. Such modeling usually speeds the process of adapting the diagnostic system to differing DUTs and increases confidence in the determinations rendered by the diagnostic system.

U.S. Patent Application Ser. No. 08/551,054 of Preist et. al. discloses a model-based diagnostic system, based on functional tests, in which the modeling burden is greatly reduced. The model disclosed in Preist et. al. employs a list of functional tests, a list of components exercised by each functional test along with the degree to which each component is exercised by each functional test, and (if available) the historical or a priori failure rate for individual components. Such model data may be rapidly and easily determined or estimated by test engineers, test programmers or others familiar with, but not necessarily expert on, the device under test. Typically, the models may be developed by test engineers in a few days to a few weeks depending on the complexity of the device under test.

The model-based diagnostic system of Preist et. al. is well-suited for a test environment that allows the automatic application of a sequence of tests to a device under test. Such a diagnostic system is particularly applicable when all available tests can be applied without a significant increase in time and cost. This situation is common in electronics manufacturing. For example, a printed circuit board can be attached to a fixture and a large number of tests can be applied before the device is removed from the fixture.

Other test environments, however, may be subject to time and/or cost constraints. For example, the application of diagnostic tests to an automobile or electronic device after sale is typically subject to time and cost constraints. Typically, only a few of the available tests can be performed economically in such a post-sale test environment. In such test environments, it is highly desirable to minimize the time required to diagnose a failure and to replace failed components. Therefore, it is highly desirable to be able to determine a next test to apply to a DUT based upon the results of earlier tests. The next test should be the best test from the point of view of eventually acheiving a correct diagnosis.

Prior model-based diagnostic systems which employ more manageable models usually do not provide automated tools for selecting a best next test. As a consequence, prior model-based diagnostic systems may impose excessive and expensive down time of the DUT during application of tests that are not necessarily the best next test to apply. Moreover, such prior systems usually do not provide tools for taking into account the economic costs associated with performing particular tests or replacing particular components of the device under test.

<b>SUMMARY OF THE INVENTION</b>

A model-based diagnostic system is disclosed which provides automated tools that enable a selection of one or more next tests to apply to a device under test from among the tests not yet applied based upon a manageable model of the device under test. In addition, the diagnostic system enables selection of components for replacement in response to indications of the costs associated with replacing components. The diagnostic system also enables selection of a next test to apply to the device under test in response to indications of the economic consequences of applying the tests.

Other features and advantages of the present invention will be apparent from the detailed description that follows.

<b>BRIEF DESCRIPTION OF THE DRAWINGS</b>

The present invention is described with respect to particular exemplary embodiments thereof and reference is accordingly made to the drawings in which: <ul id="ul0001" list-style="none"><li><b>Figure 1</b> illustrates a device under test coupled to a device tester which provides automated best next test selection using manageable model-based diagnosis;</li><li><b>Figure 2</b> illustrates a procedure for generating a set of statistical simulation data for the prediction table;</li><li><b>Figure 3</b> illustrates a process for generating patterns of component states that requires only a single pass through the list of components to generate a pattern of component states that contains at least one "BAD;<img file="EP0887733A2_D0001.tif" /></li><li><b>Figure 4</b> illustrates a procedure for selecting the best next test to apply to the device under test;</li><li><b>Figure 5</b> illustrates a procedure for determining the most likely bad component of the device under test;</li><li><b>Figure 6</b> illustrates an alternative embodiment of the procedure for determining the most likely bad component of the device under test which determines the probabilities of failure of the sets of components.</li></ul>

<b>DETAILED DESCRIPTION</b>

<b>Figure 1</b> illustrates a device under test 10 coupled to a device tester 12 which provides automated best next test selection using manageable model-based diagnosis. The device under test 10 includes a set of components 1-n. The device tester 12 implements a set of diagnostic tests 14 (test 1-m) the results of which when applied to the device under test 10 are stored in a test result table 16 (test results 1-m). At any time during a test cycle on the device under test 10, the test result table 16 indicates which of the tests 1-n have been applied and whether each applied test passed or failed.

The tester 12 implements a procedure 22 for selecting one or more best next tests from among the tests 1-m not yet applied to the device under test 10. The procedure 22 bases the best next test determinations upon a current state of the test result table 16 and the contents of a prediction table 30. The procedure 22 generates a next test table 26 that indicates which ones of the tests 1-m not yet applied to the device under test 10 are best next tests to be applied. The procedure 22 also enables selection of one or more best next tests using economic costs listed in a table 28 which are associated with performing each of the tests 1-m. The economic costs in the table 28 reflect the costs incurred by the system downtime required to run the tests 1-m and the costs of parts and labor needed to perform the necessary repairs.

The tester 12 includes a procedure 20 which enables a user to determine the most-likely bad component from among the components 1-n. The procedure 20 acts upon a current state of the test result table 16 and the contents of the prediction table 30. The procedure 20 generates a list 24 of the most likely bad components from among the components 1-n. The procedure 20 also enables selection of one or more of the components 1-n for replacement using economic costs associated with replacing each of the components 1-n. The economic costs of replacing components 1-n are stored in a table of economic costs 28. The economic costs in the table 28 reflect component costs and the costs incurred as a result of downtime of the device under test 10 while components are replaced.

The device under test 10 represents a variety of systems including mechanical, electrical and chemical systems as well a combinations thereof including circuit boards, full systems having a variety of circuit boards, automobiles, satellite systems, and test equipment. The device tester 12 includes the test mechanisms necessary for imparting a stimulus or multiple stimuli onto the device under test 10 and measuring a response to the stimulus. Such test mechanisms include electrical circuitry for generating electrical signals and measuring response electrical signals as well as mechanisms for generating mechanical or chemical stimulus and for measuring mechanical or chemical response depending upon the nature and function of the device under test 10. A stimulus imparted onto the device under test 10 may be electrical, mechanical, chemical, or a combination thereof, and the response for any of the imparted stimuli may be electrical, mechanical, chemical, or a combination thereof.

The tester 12 also includes a computer or equivalent mechanism for performing the procedures 20 and 22. The tester 12 includes a mechanism such as a graphical display for presenting to a user the results of automated best next test and most likely bad component determinations. The tester 12 may also transmit data indicating the next test to an element that operates in response to such data. The element could include another computer program, or could be an automated device such as an automated repair cell, for example. The procedures 20 and 22 may be embodied in application software for any one of a wide variety of available computer system platforms or may be embodied as diagnostic code that executes on a hardware computing platform designed specifically for the device tester 12. The application software or diagnostic code as well as the contents of the prediction table 30 and the table of economic costs 28 may be embedded within a persistent store in the device tester 12 or may be downloaded into memory within the device tester 12 via a variety of suitable communication mechanisms.

The components 1-n are each a separate well-defined replaceable component. Such replaceable components include, for example, integrated circuit devices, electrical components, battery systems, mechanical components, electrical buses, wiring components, and wiring harness and backplane components. Any one or more of such components may fail and cause a failure of the device under test 10.

For the purposes of the techniques disclosed herein, each of the components 1-n is either in a good state (GOOD) or a bad state (BAD). It is assumed that the components 1-n do not transition between the good and bad states during the course of a test cycle, i.e., intermittent failures of the components 1-n are not handled by the techniques disclosed herein.

Each of the tests 1-m acts on a subset of one or more of the components 1-n. The subsets of components acted upon or covered by a particular test 1-m may overlap with subsets covered by other of the tests 1-m. If a particular test 1-m fails, it is assumed that at least one of the components 1-n covered by that particular test is bad. Each test 1-m either passes or fails when applied to the device under test 10. If a particular test of the tests 1-m generates a finite number of test results then that particular test is treated as a number of tests, each with only two possible results, pass or fail.

Each test result 1-m includes an indication of whether the corresponding test 1-m passed (PASS) or failed (FAIL) and an indication of whether the corresponding test 1-m has been applied to the device under test 10 during a current test cycle. The subset of the tests 1-m that have been applied to the device under test 10 at a particular point in a test cycle are referred to as applied tests. The results of the applied tests are indicated in the current state of the test result table 16.

The prediction table 30 contains the numbers of occurrences of the test results for any probable test results and probable bad components jointly. In one embodiment, the prediction table 30 contains simulated experimental data generated by a statistical simulator 32. The statistical simulator 32 may be implemented on a separate computer system or may be implemented within the device tester 12. The use of a statistical or a Monte Carlo approach to produce the simulated experimental data in the prediction table 30 eliminates the need to produce real experimental data that would otherwise require years of collecting test results from real test systems and real world situations.

In an alternative embodiment, the prediction table 30 contains actual experimental data reflecting actual prior test results and component failures from historical records. In other embodiments, the prediction table 30 data may be based on a failure mode affects analysis.

Hereinafter, the term "random number" is meant to include the output of pseudo-random number generators as well as numbers chosen through some truly stochastic physical process.

The input to the statistical simulator 32 is a model of the capability of each the tests 1-m in locating bad components among the components 1-n. The model input to the statistical simulator 32 is given by the number of the component 1-n, the number of tests 1-m, and shared or joint coverages of the tests 1-m on the components 1-n, and for each component <i>i</i>, its statistical probability of failure, p(<i>i</i>). The coverage of test <i>j</i> on component <i>i</i> is referred to as cov(<i>i</i>,<i>j</i>). Each coverage cov(<i>i</i>,<i>j</i>) is a real number between 0 and 1, inclusive, and is a fraction of the functionality of component <i>i</i> that is checked by test <i>j</i>.

The joint coverages specify known dependencies among the tests 1-m. A joint coverage arises when two or more of the tests 1-m have some coverage that tests one of the components 1-n in the exactly the same way. An example of a joint coverage is when two or more of the tests 1-m performed by the device tester 12 use the same measurement subroutine with the same parameters.

A joint coverage k is specified by a list of the tests 1-m that use the joint coverage k and for each component <i>i</i> the amount of joint coverage k has on <i>i</i>. The amount of joint coverage k has on <i>i</i> is denoted as jcv(<i>i</i>,k) and is a number between 0 and 1 inclusive.

The prediction table 30 contains a set of entries each having a field for a frequency-of-occurrence value, a field for a test result pattern, and a field for a component state pattern. In one embodiment, each frequency-of-occurrence value indicates the number of times the corresponding patterns of component states and test results occurred during the course of the simulation performed by the statistical simulator 32. In an alternative embodiment, each frequency-of-occurrence value indicates the number of times the corresponding patterns of component states and test results actually occurred during the course of prior tests on similar systems. Each entry in the prediction table 30 corresponds to a unique pattern of test results and component states.

Table 1 shows example entries the prediction table 30 for an embodiment wherein n=3 and m=3. <tables id="tabl0001" num="0001"><table frame="all"><title>Table 1</title><tgroup cols="3" colsep="1" rowsep="0"><colspec colnum="1" colname="col1" colwidth="52.50mm" /><colspec colnum="2" colname="col2" colwidth="52.50mm" /><colspec colnum="3" colname="col3" colwidth="52.50mm" /><thead valign="top"><row rowsep="1"><entry namest="col1" nameend="col1" align="center">Test Results</entry><entry namest="col2" nameend="col2" align="center">Component States</entry><entry namest="col3" nameend="col3" align="center">Frequency-of-Occurrence</entry></row></thead><tbody valign="top"><row><entry namest="col1" nameend="col1" align="right">000</entry><entry namest="col2" nameend="col2" align="right">100</entry><entry namest="col3" nameend="col3" align="center">317</entry></row><row><entry namest="col1" nameend="col1" align="right">000</entry><entry namest="col2" nameend="col2" align="right">010</entry><entry namest="col3" nameend="col3" align="center">304</entry></row><row><entry namest="col1" nameend="col1" align="right">000</entry><entry namest="col2" nameend="col2" align="right">001</entry><entry namest="col3" nameend="col3" align="center">290</entry></row><row><entry namest="col1" nameend="col1" align="right">100</entry><entry namest="col2" nameend="col2" align="right">100</entry><entry namest="col3" nameend="col3" align="center">2664</entry></row><row><entry namest="col1" nameend="col1" align="right">100</entry><entry namest="col2" nameend="col2" align="right">110</entry><entry namest="col3" nameend="col3" align="center">3</entry></row><row><entry namest="col1" nameend="col1" align="right">100</entry><entry namest="col2" nameend="col2" align="right">101</entry><entry namest="col3" nameend="col3" align="center">1</entry></row><row><entry namest="col1" nameend="col1" align="right">100</entry><entry namest="col2" nameend="col2" align="right">001</entry><entry namest="col3" nameend="col3" align="center">33</entry></row><row><entry namest="col1" nameend="col1" align="right">110</entry><entry namest="col2" nameend="col2" align="right">100</entry><entry namest="col3" nameend="col3" align="center">336</entry></row><row><entry namest="col1" nameend="col1" align="right">110</entry><entry namest="col2" nameend="col2" align="right">110</entry><entry namest="col3" nameend="col3" align="center">24</entry></row><row><entry namest="col1" nameend="col1" align="right">110</entry><entry namest="col2" nameend="col2" align="right">011</entry><entry namest="col3" nameend="col3" align="center">1</entry></row><row><entry namest="col1" nameend="col1" align="right">111</entry><entry namest="col2" nameend="col2" align="right">110</entry><entry namest="col3" nameend="col3" align="center">3</entry></row><row><entry namest="col1" nameend="col1" align="right">111</entry><entry namest="col2" nameend="col2" align="right">101</entry><entry namest="col3" nameend="col3" align="center">3</entry></row><row><entry namest="col1" nameend="col1" align="right">111</entry><entry namest="col2" nameend="col2" align="right">011</entry><entry namest="col3" nameend="col3" align="center">1</entry></row><row><entry namest="col1" nameend="col1" align="right">101</entry><entry namest="col2" nameend="col2" align="right">101</entry><entry namest="col3" nameend="col3" align="center">18</entry></row><row><entry namest="col1" nameend="col1" align="right">101</entry><entry namest="col2" nameend="col2" align="right">011</entry><entry namest="col3" nameend="col3" align="center">1</entry></row><row><entry namest="col1" nameend="col1" align="right">101</entry><entry namest="col2" nameend="col2" align="right">001</entry><entry namest="col3" nameend="col3" align="center">300</entry></row><row><entry namest="col1" nameend="col1" align="right">010</entry><entry namest="col2" nameend="col2" align="right">100</entry><entry namest="col3" nameend="col3" align="center">40</entry></row><row><entry namest="col1" nameend="col1" align="right">010</entry><entry namest="col2" nameend="col2" align="right">110</entry><entry namest="col3" nameend="col3" align="center">5</entry></row><row><entry namest="col1" nameend="col1" align="right">010</entry><entry namest="col2" nameend="col2" align="right">010</entry><entry namest="col3" nameend="col3" align="center">2682</entry></row><row><entry namest="col1" nameend="col1" align="right">010</entry><entry namest="col2" nameend="col2" align="right">011</entry><entry namest="col3" nameend="col3" align="center">2</entry></row><row><entry namest="col1" nameend="col1" align="right">011</entry><entry namest="col2" nameend="col2" align="right">110</entry><entry namest="col3" nameend="col3" align="center">1</entry></row><row><entry namest="col1" nameend="col1" align="right">011</entry><entry namest="col2" nameend="col2" align="right">010</entry><entry namest="col3" nameend="col3" align="center">259</entry></row><row><entry namest="col1" nameend="col1" align="right">011</entry><entry namest="col2" nameend="col2" align="right">011</entry><entry namest="col3" nameend="col3" align="center">23</entry></row><row><entry namest="col1" nameend="col1" align="right">001</entry><entry namest="col2" nameend="col2" align="right">101</entry><entry namest="col3" nameend="col3" align="center">2</entry></row><row><entry namest="col1" nameend="col1" align="right">001</entry><entry namest="col2" nameend="col2" align="right">010</entry><entry namest="col3" nameend="col3" align="center">38</entry></row><row><entry namest="col1" nameend="col1" align="right">001</entry><entry namest="col2" nameend="col2" align="right">011</entry><entry namest="col3" nameend="col3" align="center">4</entry></row><row rowsep="1"><entry namest="col1" nameend="col1" align="right">001</entry><entry namest="col2" nameend="col2" align="right">001</entry><entry namest="col3" nameend="col3" align="center">2645</entry></row></tbody></tgroup></table></tables>

The component state, GOOD or BAD, for each component 1-n is represented by a single bit (0 or 1). Patterns of test results are indicated by a string of bits that represent the PASSED or FAILED results of the tests 1-m. Each test result is represented by a single bit (0 or 1) for each of the tests 1-m.

The values in the frequency-of-occurrence field indicate the number of times the corresponding pair of component state and test result patterns occurred during the course of the simulation performed by the statistical simulator 32 or during actual prior test runs. For example, the test result pattern 000 paired with the component failure pattern 100 occurred 317 times, while the test result pattern 000 paired with the component failure pattern 010 occurred 304 times during the simulation or the prior tests.

Each pattern of component states and each pattern of test results appears separately in the prediction table 30 more than once. Each pair of component states and test results appear together in the table 30 at most once. As a consequence, the test result and component failure fields together provide the key of the prediction table 30.

<b>Figure 2</b> illustrates the simulation performed by the statistical simulator 32. The simulation is set forth as steps 50 through 56, inclusive, which are repeatedly performed for a large predetermined number of times (T).

The statistical simulator 32 need only be run one time for a given model of the device under test 10, the components 1-n, and the tests 1-m. Thus, the work of diagnosis is divided into a preprocessing part which is done once only, and efficient decision procedures 20 and 22 that are performed for each device under test.

At step 50, a new pattern of component states is generated in which each state is initialized to "GOOD" and a new pattern of test results is generated in which each result is initialized to "PASS".

The pattern of component states generated at step 50 is modified by setting the component state for each component <i>i</i> to "BAD" with probability p(<i>i</i>). The a priori probability p(<i>i</i>) in one embodiment is an engineering estimate of the probability of failure of the component <i>i</i>. In another embodiment, the probabilities p(1)-p(n) provide a relative indication of the probabilities of failure among components 1-n.

It is assumed that no diagnosis will be performed unless at least one test has failed. It is also assumed that a test will fail only if at least one component is bad. Consequently, there is no reason to put an entry into the prediction table 30 unless its pattern of component states contains at least one "BAD".

Therefore, a random patterns of component states is generated at step 51 such that the random pattern of component states contains at least one "BAD" indication. In one embodiment, the state of each component <i>i</i> in the list of components is set to "BAD" with probability p(<i>i</i>). The resulting pattern of component states is then checked to determine whether it contains at least one "BAD." If the resulting pattern of component states does not contain at least one "BAD" then it is discarded and another pattern is generated. This process is repeated until a sufficient number of patterns of component states each containing at least one "BAD" has been generated. Since the probability p(<i>i</i>) that the state of a given component will be BAD is generally much closer to zero than to one, the process just described will typically generate many all-GOOD patterns of component states for each pattern of component states containing at least one "BAD." Consequently, the process just described does not make efficient use of available computer power or time.

<b>Figure 3</b> illustrates a process for generating patterns of component states that requires only a single pass through the list of components to generate a pattern of component states that contains at least one "BAD." The process operates in two phases which are shown as steps 51a-1 through 51a-5 and steps 51b-1 through 51b-6, respectively. The first phase steps through the list of components and assigns the state "BAD" to each component with an enhanced probability. The enhanced probability is computed both to guarantee that at least one BAD component state is generated in each pass through the list of components, and to guarantee that the overall probability of assigning the state "BAD" to component <i>i</i> remains p(<i>i</i>). The first phase ends once the state "BAD" has been assigned to one component, and the second phase begins. The second phase steps through the remainder of the component list, and assigns the state "BAD" to the component <i>i</i> with the original, un-enhanced probability p(<i>i</i>).

Step 51a-1 through 51a-5: For <i>k</i> = 1 to <i>n</i>; generate a uniformly-distributed random number <i>r</i> between 0 and 1. If <maths id="math0001" num=""><math display="inline"><mrow><mtext>r ≤ p(</mtext><mtext mathvariant="italic">k</mtext><mtext>)/(1- (1-p(</mtext><mtext mathvariant="italic">k</mtext><mtext>))*(1-p(</mtext><mtext mathvariant="italic">k</mtext><mtext>+1))*...*(1-p(</mtext><mtext mathvariant="italic">n</mtext><mtext>)))</mtext></mrow></math><img file="EP0887733A2_D0002.tif" /></maths>, then set the state of component <i>k</i> to "BAD," and go to step 51b-1.

Step 51b-1 through 51b-6: For <maths id="math0002" num=""><math display="inline"><mrow><mtext mathvariant="italic">l</mtext><mtext> = </mtext><mtext mathvariant="italic">k</mtext><mtext>+1</mtext></mrow></math><img file="EP0887733A2_D0003.tif" /></maths> to <i>n</i>; generate a uniformly distributed random number <i>r</i> between 0 and 1. If r ≤ p(<i>l</i>), then set the state of component <i>l</i> to "BAD."

Note that the value of <maths id="math0003" num=""><math display="inline"><mrow><mtext>p(</mtext><mtext mathvariant="italic">k</mtext><mtext>)/(1 -(1-p(</mtext><mtext mathvariant="italic">k</mtext><mtext>))*(1-p(</mtext><mtext mathvariant="italic">k</mtext><mtext>+1))* ... *(1-p(</mtext><mtext mathvariant="italic">n</mtext><mtext>)))</mtext></mrow></math><img file="EP0887733A2_D0004.tif" /></maths> for each possible value of <i>k</i> between 1 and <i>n</i> can be computed once for a particular device under test and can then be stored for rapid access when needed in step 51a.

At step 52, a pattern of test results is generated based upon test coverages. Assume an unsigned integer variable may contain values from 0 to 2^N-1, inclusive, for some machine-dependent integer N. Step 52 is performed according to the following steps for each component <i>j</i> to which state <img file="EP0887733A2_D0005.tif" />BAD<img file="EP0887733A2_D0001.tif" /> was assigned in step 51, for each test <i>i</i>: <ul id="ul0002" list-style="bullet"><li>Generate a uniformly distributed random number r in the range 2^N-1.</li><li>If (<maths id="math0004" num=""><math display="inline"><mrow><mtext>r + floor(cov(</mtext><mtext mathvariant="italic">i</mtext><mtext>,</mtext><mtext mathvariant="italic">j</mtext><mtext>)*(2^N-1))) mod 2^N &lt; r</mtext></mrow></math><img file="EP0887733A2_D0006.tif" /></maths>, where floor(x) is the greatest integer less than or equal to x, then set test result of test <i>i</i> to FAIL. (Note that the values floor(<maths id="math0005" num=""><math display="inline"><mrow><mtext>cov(</mtext><mtext mathvariant="italic">i</mtext><mtext>,</mtext><mtext mathvariant="italic">j</mtext><mtext>)*(2^N-1)</mtext></mrow></math><img file="EP0887733A2_D0007.tif" /></maths>) can be computed once, after the inputs are read but before the simulations are begun. Note that the modulo 2^N operation is the usual result of overflow in binary addition, and so it never needs to be computed).</li></ul>

At step 53, a pattern of test results based upon the joint coverages of the tests 1-m is generated. Step 53 is performed according to the following steps for each joint coverage <i>i</i>, for each component <i>j</i> to which the state <img file="EP0887733A2_D0005.tif" />BAD<img file="EP0887733A2_D0001.tif" /> was assigned in step 51: <ul id="ul0003" list-style="bullet"><li>Generate a uniformly distributed random unsigned integer r in the range 0 to 2^n-1 inclusive.</li><li>If <maths id="math0006" num=""><math display="inline"><mrow><mtext>(r + floor(jcv(</mtext><mtext mathvariant="italic">i</mtext><mtext>,</mtext><mtext mathvariant="italic">j</mtext><mtext>)*(2^n-1))) mod 2^n &lt; r</mtext></mrow></math><img file="EP0887733A2_D0008.tif" /></maths> then for each test k that uses joint coverage <i>i</i>, set the test result of test k to FAIL.</li></ul>

At step 54, it is determined whether there is an entry in the prediction table 30 for the pattern of test results and the pattern of component states generated in steps 50 through 53.

If there is such an entry, then the frequency-of-occurrence field for that entry in the prediction table 30 is incremented by 1 at step 55. If there is no such entry, then the entry is created and added to the prediction table 30 with the frequency-of-occurrence initialized to 1 at step 56.

<b>Figure 4</b> illustrates the procedure 22 for selecting one or more best next tests to perform on the device under test 10. The best next tests are the ones of the tests 1-m that will result in the least number of tests being performed before the procedure 20 generates a reliable answer for which of the components 1-n is most likely bad. The procedure 22 takes as inputs the prediction table 30 and the current test results indicated in the test result table 16.

The procedure 22 generates the next test table 26 which contains one row for each of the tests 1-m that has not yet been performed on the device under test 10. The next test table 26 contains two columns. The first column contains identifiers such as test numbers of the tests not yet performed. The second column contains the expected proportion of correct diagnoses that will result if the test in the first column is performed next and the result along with all previous test results on the device under test 10 is run through the procedure 20.

<b>Table 2</b> illustrates an example of the next test table 26 which can provide to a skilled technician a display of several next tests, the best next test along with several other good next tests. <tables id="tabl0002" num="0002"><table frame="all"><title>Table 2</title><tgroup cols="2" colsep="1" rowsep="1"><colspec colnum="1" colname="col1" colwidth="78.75mm" /><colspec colnum="2" colname="col2" colwidth="78.75mm" /><thead valign="top"><row><entry namest="col1" nameend="col1" align="center">Test:</entry><entry namest="col2" nameend="col2" align="center">Score:</entry></row></thead><tbody valign="top"><row><entry namest="col1" nameend="col1" align="left">T6</entry><entry namest="col2" nameend="col2" align="char" char=".">0.3</entry></row><row><entry namest="col1" nameend="col1" align="left">T1</entry><entry namest="col2" nameend="col2" align="char" char=".">0.25</entry></row><row rowsep="1"><entry namest="col1" nameend="col1" align="left">T12</entry><entry namest="col2" nameend="col2" align="char" char=".">0.05</entry></row></tbody></tgroup></table></tables>

The values in the second column of the next test table 26, under "Score" in Table 2, are the values L which are computed as set forth below. The values in L are sorted and the values are displayed, in one embodiment, in decreasing order beside the identifying names of the associated tests.

Each value in the second column of the next test table 26 is a measure of the <img file="EP0887733A2_D0005.tif" />goodness<img file="EP0887733A2_D0001.tif" /> of a next test. The best test may then be selected as the one whose performance leads to the highest probability of a correct diagnosis, i.e. the highest value in the second column. The values in the second column may be combined with corresponding indications of the economic costs associated with performing the tests 1-m which are contained in the table 28. The economic cost of a particular test may reflect, for example, the economic cost of downtime of the device under test 10 or other related devices which is incurred during application of the particular test. Any tests 1-m having equal or approximately equal values in the second column of the next test table 24 may be selected by the procedure 22 on the basis of which test has a lower economic cost as indicated by the contents of the table 28.

In some embodiments, graphical symbols, color codes, etc., may be used instead of numbers to represent the relative likelihood of the diagnoses and the relative goodness of the next tests.

The next test table 26 can be sorted by either column. In one embodiment, the next test table 26 is sorted by the second column, so that the best test appears in the first row. The Best Next Test is the test that has the highest value in the second column, because the choice of that test maximises the improvement in the rate of successful diagnosis.

Initially, an empty next test table 26 is created. Steps 72 through 76 are then performed for each test <i>j</i> that has not yet been performed as indicated by the current test results contained in the test result table 16.

At step 72, P(T_j=FAIL) is determined which is the probability that test <i>j</i> will fail given the current test results. P(T_j=FAIL) is determined according to the following steps: <ul id="ul0004" list-style="bullet"><li>Generate u which is a sum of the frequency-of-occurrence fields of all the entries of the prediction table 30 having test results that match the current test results indicated in the test result table 16.</li><li>Generate w which is a sum of the frequency-of-occurrence fields all of the entries of the prediction table 30 having test results that match the current test results and that have test <i>j</i> indicating FAIL.</li><li>Generate <maths id="math0007" num=""><math display="inline"><mrow><msub><mrow><mtext>P(T</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>=FAIL)= w / u</mtext></mrow></math><img file="EP0887733A2_D0009.tif" /></maths>.</li></ul>

At step 73, P(T_j=PASS) is determined which is the probability that test <i>j</i> will pass given the input previous test results. P(T_j=PASS) is given by the following equation:<maths id="math0008" num=""><math display="block"><mrow><msub><mrow><mtext>P(T</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext>=PASS)= 1 - P(T</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>=FAIL)</mtext></mrow></math><img file="EP0887733A2_D0010.tif" /></maths>

At step 74, L_FAIL is determined which is the proportion of diagnoses that will be correct if test <i>j</i> is applied next on the device under test 10 and fails. Step 74 is performed according to the following steps: <ul id="ul0005" list-style="bullet"><li>Set L_FAIL to 0.</li><li>Set the test result table 16 to indicate that test <i>j</i> is completed and failed.</li><li>For each component <i>i</i>, generate <maths id="math0009" num=""><math display="inline"><mrow><mtext>Pi = ν(Δ_i) / ν(Δ)</mtext></mrow></math><img file="EP0887733A2_D0011.tif" /></maths> and add max(Pi, 1-Pi) to L_FAIL; where ν(Δ) is the sum of the frequency-of-occurrence fields of all the entries in the prediction table 30 that match the pattern of passed and failed tests listed in the test result table 16 and where ν(Δ_i) which is the sum of the frequency-of-occurrence fields of the entries of the prediction table 30 that match the pattern of passed and failed tests listed in the test result table 16 and that indicate component <i>i</i> is BAD.</li><li>Generate L_FAIL = L_FAIL / n, where n is the number of components 1-n.</li><li>Remove test <i>j</i> from the list of completed tests in the test result table 16.</li></ul>

At step 75, L_PASS is determined which is the proportion of diagnoses that will be correct of test <i>j</i> is run next on the device under test 10 and passes. Step 75 is performed according to the following steps: <ul id="ul0006" list-style="bullet"><li>Set L_PASS to 0.</li><li>Set test <i>j</i> in the test result table 16 to indicate completed and passed.</li><li>For each component <i>i</i>, generate <maths id="math0010" num=""><math display="inline"><mrow><mtext>Pi = ν(Δ_i) / ν(Δ)</mtext></mrow></math><img file="EP0887733A2_D0012.tif" /></maths> and add max(Pi, 1-Pi) to L_PASS; where ν(Δ) is the sum of the frequency-of-occurrence fields of all the entries in the prediction table 30 having the pattern of test results contained in the test result table 16 and where ν(Δ_i) is the sum of the frequency-of-occurrence fields of the entries of the prediction table 30 that match the pattern in the test result table 16 and that indicate component <i>i</i> is BAD.</li><li>Generate L_PASS = L_PASS / n, where n is the number of components 1-n.</li><li>Remove test <i>j</i> from the list of completed tests in the test result table 16.</li></ul>

At step 76, L_j which is the expected proportion of correct diagnoses if test <i>j</i> is performed next on the device under test 10 is determined according to the following equation.<maths id="math0011" num=""><math display="block"><mrow><msub><mrow><mtext>L</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = P(T</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext>=FAIL) * L_FAIL + P(T</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>=PASS) * L_PASS</mtext></mrow></math><img file="EP0887733A2_D0013.tif" /></maths>

Thereafter, <i>j</i> and L_j are written to the next test table 26 as the entries for the first and second columns, respectively, of the next available row of the next test table 26.

Finally, if the next test table 26 is to be sorted by either output column, then the sorting step is performed. The highest expected proportion of correct diagnoses listed in the next test table 26 may be selected as the best next test or the expected proportions listed in the next test table 26 may be weighted by the economic costs associated with performing the tests.

<b>Figure 5</b> illustrates one embodiment of the procedure 20 which enables a user to determine the most likely bad component of the device under test 10. The procedure 20 generates the list 24 of one or more most likely bad components from among the components 1-n. The procedure 20 takes as inputs the prediction table 30 and a current state of the test result table 16 which indicates which of the tests 1-m have been applied to device under test 10 and whether the applied tests passed or failed. The procedure 20 generates the list 24 of bad components to minimize the average number of wrongly diagnosed components over a large number of devices under test.

At step 60, ν(Δ) is generated which is the sum of the frequency-of-occurrence fields of all the entries in the prediction table 30 having the pattern of passed and failed tests provided by the current state of the test result table 16 (the current test results).

Steps 62-68 are performed for each component <i>i</i> wherein <i>i</i> ranges from 1 to n, the number of components of the device under test 10.

At step 62, ν(Δ_i) is generated which is the sum of the frequency-of-occurrence fields of the entries of the prediction table 30 that match the current test results and that indicate component <i>i</i> is BAD.

If <maths id="math0012" num=""><math display="inline"><mrow><mtext>2*ν(Δ_i) &gt; ν(Δ)</mtext></mrow></math><img file="EP0887733A2_D0014.tif" /></maths> at step 64 then the list 24 is written to indicate that component <i>i</i> is GOOD at step 66. Otherwise, the list 24 is written to indicate that component <i>i</i> is BAD at step 68.

At the end of the procedure 20, the list 24 contains a GOOD or a BAD indication for each of the components 1-n wherein each BAD indication identifies the corresponding component as a likely bad component. The combination of the indications of likely bad components in the list 24 and the economic cost associated with replacing the likely bad components in the table 28 provides information that enables selection of which likely bad component to replace. For example, if the list 24 contains two or more likely bad components then the user or the procedure 20 itself selects the likely bad component in the list 24 having the lowest economic cost for replacement as indicated in the list 28.

In some embodiments of a model-based diagnostic system it is desirable to present a skilled technician with a list of several most likely bad components. <b>Table 3</b> illustrates such a presentation of several most likely bad components. <tables id="tabl0003" num="0003"><table frame="all"><title>Table 3</title><tgroup cols="2" colsep="1" rowsep="1"><colspec colnum="1" colname="col1" colwidth="78.75mm" /><colspec colnum="2" colname="col2" colwidth="78.75mm" /><thead valign="top"><row><entry namest="col1" nameend="col1" align="center">Components:</entry><entry namest="col2" nameend="col2" align="center">Probability:</entry></row></thead><tbody valign="top"><row><entry namest="col1" nameend="col1" align="left">U1</entry><entry namest="col2" nameend="col2" align="char" char=".">0.5</entry></row><row><entry namest="col1" nameend="col1" align="left">U2 and U7</entry><entry namest="col2" nameend="col2" align="char" char=".">0.4</entry></row><row rowsep="1"><entry namest="col1" nameend="col1" align="left">U3</entry><entry namest="col2" nameend="col2" align="char" char=".">0.1</entry></row></tbody></tgroup></table></tables>

Table 3 can be interpreted as "the probability of only Ul being bad is 0.5, the probability that U2 and U7 are *both* bad is 0.4, and the probability that only U3 is bad is 0.1."

<b>Figure 6</b> illustrates an alternative embodiment of the procedure 20 which determines the probabilities of failure of the sets of components which are presented in the list 24 in the format shown in Table 3. At step 100, the rows of the prediction table 30 whose patterns of test results match the current test results in the test result table 16 are extracted and a sum N is generated which is the sum of the frequency-of-occurrence fields of the rows extracted.

An empty list of most likely bad components 24 is initially created. The elements of the list 24 include a pair of fields. The first field is a pattern of BAD components. The second field is a number-of-times that the corresponding pattern occurs in the rows extracted at step 100.

Steps 110 and 120 are performed for each particular row of the prediction table 30 extracted at step 100 that matches the current test results in the test result table 16.

At step 110, if the pattern of BAD components for the particular extracted row appears in the list 24, then the frequency-of-occurrence field of the particular extracted row is added to the number-of-times for that pattern in the list 24.

At step 120, if the pattern of BAD components for the particular extracted row does not appear in the list 24, then a new element is added to the list 24. The pattern of BAD components field of the new element in the list 24 is set to the pattern of the particular extracted row of the prediction table 30. In addition, the number-of-times field if the new element in the list 24 is set to the frequency-of-occurrence field of the particular extracted row of the prediction table 30.

The list 24 is sorted by the number-of-times fields. Step 130 is performed for each particular row in the list 24. At step 130, the number-of-times for the particular row is replaced with the number-of-times divided by N.

After step 130, the list 24 contains patterns of BAD components along with their probability given the test results. Graphical symbols, color codes, etc., may be used instead of numbers to represent the relative probabilities of bad components.

The diagnostic techniques described herein are conducted so as to maximize a known objective function, namely the proportion of good diagnoses over a large number of devices under test. As a consequence, the results of the diagnosis are easier to interpret and verify experimentally than heuristics-based diagnosis. This in turn makes it easier to debug the component/test model that is input to the statistical simulator 32.

The procedure 22 chooses one or more best next tests to maximize the expected improvement in the rate of successful diagnosis. Again, this metric is easy to interpret and verify.

If information about the cost of tests and the cost of incorrect diagnoses are available, the procedure 20 and 22 are readily modified so that the most-likely bad diagnosis and best next test selection are chosen to minimize the expected cost of testing and of incorrect diagnosis.

The procedures 20 and 22 are well-suited to be embedded in the device tester 12 or downloadable applications for the device tester 12. The procedures 20 and 22 are compact and perform neither the exhaustive searches required by prior artificial intelligence techniques nor the extensive floating point computations required by prior statistical techniques.

The prediction table 30 need not be stored exactly as depicted in Table 1. There are various tree storage, indexing, hashing, and data compression techniques that may reduce the amount of memory required to store the prediction table 30 and/or speed access to the values stored in the prediction table 30. These techniques and the criteria for choosing among them based on their relative advantages in particular situations are well known to those skilled in the art of design of computer algorithms, data structures, and programs.

The foregoing detailed description of the present invention is provided for the purposes of illustration and is not intended to be exhaustive or to limit the invention to the precise embodiment disclosed. Accordingly, the scope of the present invention is defined by the appended claims.