Failure analysis system, method for managing estimated logic status and information storage medium for programmed instruction of the method

[0002] This invention relates to a failure analysis for a semiconductor integrated circuit device and, more particularly, to a failure analysis system, a method for managing estimated logic status and an information storage medium for storing programmed instructions of the method.

[0003] A method for managing estimated logic status is available for a failure analysis system for a sequential circuit disclosed, by way of example, in Japanese Patent Publication of Unexamined Application No. 8-146093. In the following description, term “combinational circuit” expresses a combination of component circuits of an integrated circuit. The prior art failure analysis system backwardly traces a propagation path from a defective output toward an origin of trouble, and dynamically extracts combinational circuits possibly propagating the trouble. The prior art failure analysis system evaluates the extracted combinational circuits, and gives estimated logic status to the extracted combinational circuit. The logic status is given to not only signal lines but also all nodes in the extracted combinational circuit. Signal lines, gates and input/output nodes are examples of the node to be evaluated. The logic status is represented by more than two logic values, i.e., logic “0”, logic “1”, X which means “don't care”, Z which means high-impedance and U which means undefined. When the extracted combinational circuits are linked by using the logic status, the logical link is expected to guide the analyst to the origin of trouble.

[0004] An estimated linkage of logic status of each combinational circuit is managed by using the prior art method for managing estimated logic status. Pieces of status information representative of the logic status are registered, retrieved and selectively canceled, and are formed into a tree-like index structure. A large scale integration has a large number of combinational circuits, and more than one logic value is possibly given to each combinational circuit. For this reason, the tree-like index structure for the large scale integration is huge, and the relation between the pieces of status information is less clear to an analyst.

[0005] FIG. 1 illustrates a prior art failure analysis system for the estimated logic status. The prior art failure analysis system is broken down into an input-output unit 1, a data processing unit 2 and a memory unit 3. Input data is supplied from the outside through the input-output unit 1 to the data processing unit 2. The data processing unit 2 sequentially executes programmed instructions for a failure analysis, stores pieces of status information for a combinational circuit and a tree-like index structure representative of the logic status in the memory unit 3, and delivers data to be required through the input-output unit 1b.

[0006] The input-output unit 1 includes a data input unit 1aand a data output unit 1b. The input unit 1ais a keyboard and a data interface to a diagnostic system (not shown). The output unit 1bis a printer and a data interface to the diagnostic system. The memory unit 3 includes a memory 3afor data information representative of the logic status of combinational circuits and a memory 3bfor storing the tree-like index structure. Each of the pieces of status information represents the logic status at a node in a combinational circuit, and the logic status is labeled with an index. A logic value is given to the logic status, and the logic values are logic “1”, logic “0”, X which means “don't care”, Z which means high-impedance and U which means undefined. The node means a signal line, a gate, a gate terminal and an input/output terminal of a component circuit. On the other hand, the tree-like index structure is stored in the memory unit 3b. The tree-like index structure is built for each combinational circuit, and represents a linkage of logic status between the nodes.

[0007] The data processing unit 2 includes an instruction analyzer 2aconnected to a program memory (not shown), an index marker 2b, a condition analyzer 2cfor retrieving conditions and a condition analyzer 2dfor deleting conditions. The index marker 2b, the condition analyzer 2cand the condition analyzer 2dare respectively accompanied with a register 2e, a retriever 2fand a deleting means 2g.

[0008] The instruction analyzer 2aanalyzes an instruction supplied from the input unit 1a, and the data processing unit selectively branches the control to a data registration, a data retrieval and a data deletion. In other words, the control sequence is transferred from the instruction analyzer 2ato the index marker 2b, the retrieving conduction analyzer 2cor the condition analyzer 2d.

[0009] The index marker 2badds an index to the logic status given to a node or a group of nodes to be registered, and transfers the piece of status information representative of the logic status labeled with the index to the register 2e. The index is representative of both of a name of nodes in the combinational circuit and a relation between the nodes. If nodes are branched from a node, the nodes respectively have sub-indexes branched from an index given t o the node. A name is given to each node, and the name of node is also stored so as to make the linkage clear. The register 2eassorts the pieces of status information by the index, and stores the pieces of status information together with the names of the associated nodes. Moreover, the register 2ebuilds the pieces of status information into a tree-like index structure, and stores the tree-like index structure in the memory unit 3b. While the register 2eis building the pieces of status information into the tree-like index structure, the sub-indexes are located under the index. Thus, lower-level indexes are branched from an upper-level index, and all the indexes are built into the tree-like index structure.

[0010] The condition analyzer 2cdetermines search conditions for a data retrieving to be requested, and supplies the search conditions to the retriever 2f. The retriever 2fsearches the memory units 3a/3bfor a piece or pieces of status information satisfying the search conditions, and supplies the search result to the output unit 1b.

[0011] The condition analyzer 2ddetermines search conditions for a deletion of a piece of or pieces of status information from the contents of the memory units 3a/3b, and supplies the search conditions to the deleting means 2g. The deleting means 2gdeletes a piece of pieces of status information satisfying the search conditions from the contents of the memory units 3a/3b.

[0012] FIG. 2 illustrates the control sequence achieved by the prior art failure analysis system, and FIG. 3 illustrates a tree-like index structure built by the prior art failure analysis system. The tree-like index structure is finally achieved through repetition of the control sequence shown in FIG. 2. F1 to F16 are indicative of the names of nodes incorporated in a combinational circuit, and numeral “0” in a circle to numeral “15” in a circle are representative of the indexes each given to a group of nodes such as (F1, F2). FIG. 4 shows a logic path from the index “0” through the indexes “1” and “3” to the index “6” and the index “8” in the tree-like index structure, and FIG. 5 shows another logic path from the index “0” through the indexes “1” and “4” to the index “10” and the index “12” in the tree-like index structure. The logic paths are determined through the execution of the program sequence shown in FIG. 2.

[0013] The prior art control sequence is firstly described hereinbelow. Assuming now that a programmed instruction code is supplied from the input unit 1ato the instruction analyzer 2a, the instruction analyzer 2asequentially checks the instruction code at steps SP1/SP2/SP3, and transfers the control to the index marker 2b, the condition analyzer 2cand the condition analyzer 2d. In detail, the instruction analyzer 2afirstly checks the programmed instruction to see whether or not the programmed instruction requests the registration as by step SP1. If the answer at step SP1 is given affirmative, the instruction analyzer 2atransfers the control to the index marker 2b, and the index marker 2bstarts the registration as described hereinlater in detail.

[0014] On the other hand, if the answer at step SP1 is given negative, the instruction analyzer 2achecks the programmed instruction to see whether or not the programmed instruction re(quests the retrieval as by step SP2. If the answer at step SP2 is given affirmative, the instruction analyzer 2atransfers the control to the condition analyzer 2c, and the condition analyzer 2ccooperates with the retriever 2ffor the retrieval of data as described hereinlater.

[0015] On the other hand, if the answer at step SP2 is given negative, the instruction analyzer 2achecks the programmed instruction to see whether or not the programmed instruction requests a deletion. If the answer at step SP3 is given affirmative, the instruction analyzer 2atransfers the control to the condition analyzer 2c, and the condition analyzer 2dcooperates with the deleting means 2gfor deleting data as described hereinlater.

[0016] When the instruction analyzer 2adetermines the programmed instruction to request the registration, the index marker 2badds an index to the logic status for the purpose of data discrimination as by step SP4. A group of the names assigned the nodes and logic value assigned thereto are incorporated in a piece of status information representative of the logic status, and a single index is given to the logic status. It is assumed that an upper-level index had been known. The logic status was estimated for the lower-level index or the sub-index on the basis of the pieces of status information for the upper-level index. The piece of status information is supplied to the register 2etogether with the index, and the register 2estores the pieces of status information and the index in the memory unit 3aas by step SP5. If the index is a sub-index, the linkage between the index and the sub-index is also stored in the memory unit 3a.

[0017] If the instruction analyzer 2adetermines the given programmed instruction to request a data retrieval, the condition analyzer 2canalyzes given data, and determines conditions for a search as by step SP6. The search conditions are transferred from the condition analyzer 2cto the retriever 2f, and the retriever 2fsearches the memory units 3a/3bfor a piece of status information satisfying the search conditions as by step SP7. The result of the retrieval is output through the output unit 1bas by step SP8.

[0018] If the instruction analyzer 2adetermines the given programmed instruction to request a deletion, the condition analyzer 2danalyzes given data, and determines conditions for a search. The search conditions are transferred from the condition analyzer 2dto the deleting means 2g, and the deleting means 2gdeletes a piece of status information satisfying the search conditions together with the given index.

[0019] Description is hereinbelow made on part of the work of building the tree-like index structure with reference to FIGS. 4/5. Circuits 4a/4b/4c/4dform a combinational circuit (see FIG. 4), and circuits 4a/4b/4c/4eform another combinational circuit (see FIG. 5). Unexpected output signals are assumed to appear at the terminals F1 and F2. The terminal F1/F2 is hereinbelow referred to as “defective terminal”. Index “0” was assigned to the defective terminals F1/F2, and a piece of status information at the defective terminals F1/F2 and the index “0” have been already stored in the memory units 3a/3b.

[0020] A programmed instruction is representative of a request for the retrieval, and is supplied from the input unit 1ato the instruction analyzer 2aupon completion of step SP2. The instruction analyzer 2atransfers the programmed instruction to the condition analyzer 2c, and the condition analyzer 2cdetermines search conditions to be a defective terminals not estimated yet at step SP6. The retriever 2fsearches the memory units 3a/3bfor the piece of status information satisfying the search conditions at step SP7. The retriever 2ffinds the piece of status information representative of the terminals F1/F2 assigned index “0”. The retriever 2ftransfers the search result indicting the defective terminals F1/F2 to the output unit 1b, and the output unit 1boutputs a search report at step SP8.

[0021] The prior art failure analysis system selects the circuit 4aon the basis of the search report for the defective terminal F1/F2 assigned index “0”, and estimates the logic status of the circuit 4a. Then, two kinds of logic status are determined. One of them is representative of a failure propagation path from the terminal F3 to the terminals F1/F2, and the other is representative of another failure propagation path from the terminal F4 to the terminals F1/F2 (see FIG. 3).

[0022] The prior art failure analysis system instructs the data processing unit 2 to register pieces of status information representative of the two kinds of logic status. The instruction analyzer 2adetermines the given instruction to request a registration. The control is transferred to the index marker 2b. The index marker gives index “1” and index “2” to the pieces of status information (see FIG. 3) at step SP4. Index “1” and “2” are respectively assigned to the pieces of status information representative of the failure propagation path from the terminal F3 to the terminals F1/F2 and the logic status representative of the failure propagation path from the terminal F4 to the terminals F1/F2. Thereafter, the resister 2estores the pieces of status information, i.e., the names of nodes or terminals and the logic value given to one kind of logic status and the names of nodes or terminals and the logic value given to the other kind of logic status in the memory units 3a, and inserts indexes “1” and “2” in the tree-like index structure stored in the memory unit 3bas lower-level indexes branched from index “0” at step SP5.

[0023] Upon completion of the registration, the prior art failure analysis system returns to step SPO, and searches the memory units 3a/3bfor a terminal not estimated yet. The terminals F3/F4 are found, and the prior art failure analysis system repeats steps SP2, SP6, SP7 and SP8 for each of the terminals F3/F4.

[0024] The terminal F3 with index “1” relates to the circuit 4b, and the prior art failure analysis system extracts the circuit 4bfrom the combinational circuit. The prior art failure analysis system estimates the logic status of the circuit 4b. Two kinds of logic status are estimated. One of the two kinds-of logic status is representative of a failure propagation path from the terminal F3 to the terminals F5/F6 shown in FIG. 4, and the other kind of logic status is representative of a failure propagation path from the terminal F3 to the terminals F5/F7 shown in FIG. 5.

[0025] The prior art failure analysis system requests the data processing unit 2 to register the two kinds of logic status. The data processing unit 2 repeats the control sequence described hereinbefore, and stores the two kinds of logic status together with indexes “3” and “4”. Indexes “3” and “4” are inserted into the tree-like index structure as sub-indexes of index “1”.

[0026] The other terminal F4 has been assigned index “2”, and the prior art failure analysis system extracts a circuit from another combinational circuit, and estimates the logic status for the extracted circuit. Only one kind of logic status is obtained through the estimation, and is representative of a failure propagation path from the terminal F8 to the terminal F4 (see FIG. 3). The prior art failure analysis system instructs the data processing unit 2 to register the logic status for the extracted circuit. The data processing unit 2 repeats the above-described control sequence so as to store the logic status together with index “5” in the memory unit 3aand insert index “5” in the tree-like index structure in the memory unit 3bas a sub-index of index “2”.

[0027] Upon completion of the registration, the prior art failure analysis system instructs the condition analyzer 2cand the retriever 2fto search the memory 3 for terminals not estimated yet, and the retriever 2ffinds the terminals F5/F6 of index “3”, the terminals F5/F7 of index “4” and the terminal F8 of index “5”. The prior art failure analysis system repeats the above-described control sequence for each of the terminals F5/F6, F5/F7 and F8.

[0028] In this way, the prior art failure analysis system repeats the program sequence shown in FIG. 2 for terminals not estimated yet, and, finally, completes the tree-like index structure shown in FIG. 3. The indexes are hierarchically built up into the tree-like index structure, and the links represent the relation between the upper-level indexes and the lower-level indexes. The indexes are associated with the defective terminals as shown.

[0029] The linkage shown in FIG. 4 is indicative of the following estimation. The defective terminal F3 is estimated on the basis of the logic status labeled with index “1” which has been determined from the defective terminals F1/F2 labeled with index “0”. The defective terminals F5/F6 are estimated on the basis of the logic status labeled with “3” for the terminal F3, and the defective terminals F9 and F11 are estimated on the basis of the logic status labeled with “6” for the defective terminal F5 and the logic status labeled with “8” for the defective terminal F6.

[0030] Similarly, the linkage shown in FIG. 5 is indicative of the following estimation. The defective terminal F3 is estimated as similar to the linkage shown in FIG. 4, and the defective terminals F5/F7 are estimated on the basis of the logic status labeled with “4” for the terminal F3, and the defective terminals F9 and F13 are estimated on the basis of the logic status labeled with “10” for the defective terminal F5 and the logic status labeled with “12” for the defective terminal F7.

[0031] An analyst acquires a piece of knowledge from the tree-like index structure that the estimation proceeds from index “0” through index “1” to index “3”. In other words, the tree-like index structure teaches the analyst the heretical relation between upper-level indexes and lower-level indexes. However, the tree-like index structure does not teach a logical relation between the indexes such as the AND relation or the OR relation. When two kinds of logic status are concurrently realized, they are in the AND relation. On the other hand, if two kinds of logic status are never concurrently realized, they are in the OR relation. Focusing attention on indexes “3”, “6”, “7”, “8” and “9”, by way of example, the tree-like index structure teaches that the four kinds of logic status “6”, “7”, “8” and “9” are estimated from the kind of logic status “3”. It is unknown that what kind of logic relation is found between the four kinds of logic status “6”, “7”, “8” and “9”. Because the logic status is not linked with any one of the two circuits relating to the terminals F5/F6. If all the relations between the indexes are registered, the analyst is to register a large number of combinations between the indexes, and the registration consumes a large, amount of time and labor. Thus, the analyst encounters a first problem in the prior art failure analysis system in that the tree-like index structure can not express any logical relation between the indexes.

[0032] The second problem is that the prior art failure analysis system can not specify the inside of the circuit, because the prior art failure analysis system does not select AND relations from the linkage.

[0033] The third problem is that the prior art failure analysis consumes a long time. As shown in FIG. 3, indexes “6”/“10” and “7”/“11” are branched from index “3” and index “4”, respectively. However, both indexes “6” and “10” are given to the logic status for the defective terminal F9. Similarly, both indexes “7” and “11” are given to the logic status for the defective terminal F10. This means that the estimation is repeated for the terminals F9/F10. The repetition increases the amount of estimation, and prolongs the time period for the failure analysis.

[0034] It is therefore an important object of the present invention to provide a failure analysis system, which is free from the problems inherent in the prior art failure analysis system.

[0035] It is also an important object of the present invention to provide a method of managing estimated logic status available for the failure analysis system.

[0036] It is also an important object of the present invention to provide an information storage medium for storing programmed instructions of the method.

[0037] The present inventor contemplated the first to third problems, and noticed that the source of those problems was that the prior art failure analysis system could not determine the logical relation between the kinds of logic status labeled with different indexes.

[0038] In accordance with one aspect of the present invention, there is provided a failure analysis system for a sequential circuit containing plural circuits comprising an index marker receiving pieces of status information each representative of a failure propagation path in one of the plural component circuits, and selectively labeling the pieces of status information with indexes in such as manner one of the pieces of status information is labeled with an index serving as an upper level index with respect to other or others of the pieces of status information closer to candidates of an failure origin than the one of the pieces of status information, a group organizer checking the indexes to see whether or not one or ones of the indexes are branched from another of the indexes serving as the upper level index, and giving a tag to the one or ones of the indexes when the one or ones of the indexes are branched from the another of the indexes, thereby selectively giving tags to the indexes, and a logical relation analyzer checking the indexes and the tags to see whether more than one piece of status information is established in an AND relation or an OR relation.

[0039] In accordance with another aspect of the present invention, there is provided a method of managing estimated logic status for a sequential circuit containing plural component circuits comprising the steps of a) acquiring pieces of status information each representative of a degradation of a failure propagation path in one of the plural component circuits and selectively labeled with indexes to be built in a tree-like index structure so as to indicate a relation of the failure propagation paths from candidates of a failure origin in the sequential circuit to a signal output port of the sequential circuit, one of the indexes given to one of the propagation paths closer to the signal output port serving as an upper level index in the tree-like index structure with respect to other or others of the indexes given to other or others of the propagation paths closer to the candidates and connected to the one of the propagation paths, b) checking the tree-like index structure to see whether one of or ones of the indexes are branched from another of the indexes serving as the upper level index so as to give a tag to the one or ones of the indexes when the one or ones of the indexes are branched from the another of indexes, thereby selectively giving tags to an index or a group of indexes incorporated in the tree-like index structure, c) checking the indexes to see whether or not the tag is shared between more than one of the indexes, and d) determining a logical relation between the more than one of the indexes to be an OR relation when the tag is shared and an AND relation when the tag is not shared.

[0040] In accordance with yet another aspect of the present invention, there is provided a information storage medium for storing a sequence of programmed instruction for a method of managing estimated logic status for a sequential circuit containing Plural component circuits, and the method comprises the steps of a) acquiring pieces of status information each representative of a degradation of a failure propagation path in one of the plural component circuits and selectively labeled with indexes to be built in a tree-like index structure so as to indicate a relation of the failure propagation paths from candidates of a failure origin in the sequential circuit to a signal output port of the sequential circuit, one of the indexes given to one of the propagation paths closer to the signal output port serving as an upper level index in the tree-like index structure with respect to other or others of the indexes given to other or others of the propagation paths closer to the candidates and connected to the one of the propagation paths, b) checking the tree-like index structure to see whether one of or ones of the indexes are branched from another of the indexes serving as the upper level index so as to give a tag to the one or ones of the indexes when the one or ones of the indexes are branched from the another of indexes, thereby selectively giving tags to an index or a group of indexes incorporated in the tree-like index structure, c) checking the indexes to see whether or not the tag is shared between more than one of the indexes, and d) determining a logical relation between the more than one of the indexes to be an OR relation when the tag is shared and an AND relation when the tag is not shared.

[0041] The features and advantages of the failure analysis system, the method and the information storage medium for programmed instructions will be more clearly understood from the following description taken in conjunction with the accompanying drawings in which:

[0042] FIG. 1 is a block diagram showing the prior art failure analysis system;

[0043] FIG. 2 is a flow chart showing the program sequence of the prior art failure analysis system;

[0044] FIG. 3 is a view showing the tree-like index structure achieved through the prior art control sequence;

[0045] FIG. 4 is a view showing the part of the combinational circuit analyzed by the prior art failure analysis system;

[0046] FIG. 5 is a view showing the part of another combinational circuit analyzed by the prior art failure analysis system;

[0047] FIG. 6 is a block diagram showing the arrangement of components incorporated in a failure analysis system according to the present invention;

[0048] FIG. 7 is a flow chart showing a program sequence executed by the failure analysis system;

[0049] FIG. 8 is a flow chart showing a program sequence executed by a logical relation analyzer 31j;

[0050] FIG. 9 is a flow chart showing a program sequence executed by a failure path analyzer;

[0051] FIG. 10 is a view showing a tree-like index structure having index groups respectively labeled with tags;

[0052] FIG. 11 is a block diagram showing the arrangement of another failure analysis system according to the present invention;

[0053] FIG. 12 is a flow chart showing a failure analysis carried out by the failure analysis system;

[0054] FIG. 13 is a view showing a tree-like index structure having index groups respectively labeled with tags;

[0055] FIG. 14 is a view showing the part of a combinational circuit analyzed by the failure analysis system;

[0056] FIG. 15 is a view showing the part of another combinational circuit analyzed by the prior art failure analysis system; and

[0057] FIG. 16 is a block diagram showing yet another failure analysis system according to the present invention.

[0058] Referring to FIG. 6 of the drawings, a failure analysis system embodying the present invention largely comprises a data input-output facility 30, a data processing unit 31 and a data storage 32. An analyst instructs the failure analysis system to achieve a given task through the data input-output facility 30, and the data processing unit 31 executes programmed instructions for the given task. Pieces of status information, indexes and a tree-like index structure are stored in the memory 32, and the data processing unit 31 produces a report from the data information stored in the memory 32. The data processing unit 31 outputs the report through the input-output facility 30.

[0059] The input-output facility 30 includes an input unit 30aand an output unit 30b. The input unit 30ahas a keyboard and a data interface for a diagnostic system 33. An analyst gives instructions through the keyboard to the input unit 30a, and the diagnostic system 33 transfers pieces of status information to the data interface. On the other hand, the output unit 30bhas a display unit, a printer and a data interface to the diagnostic system 33. The analyst receives a search report and other results through the display and the printer, and a request for an estimation and related data are supplied from the output unit 30bto the diagnostic system 33.

[0060] The memory 32 has three memory units 32a, 32band 32c. Indexes and associated pieces of status data information are stored in the memory unit 32a, and a tree-like index structure is built up in the memory unit 32b. Each piece of status information has a logic value selected from logic “0”, logic “1”, X which means don't care, Z which means high impedance and U which means undefined. The logic value is given to all of the nodes in a combinational circuit or part of the nodes in the combinational circuit. A signal line, a gate, a gate electrode and input/output terminals are examples of the node. A name is given to each node, and is called as “node name” in the following description. Therefore, a piece of status information contains a node name and a logic value given thereto or node names and logic values respectively given thereto.

[0061] The memory unit 32cis assigned pieces of control data information each representative of a group of indexes assigned to pieces of status data information estimated in parallel to one another for a node of a combinational circuit.

[0062] The data processing unit 31 includes an instruction analyzer 31a, an index marker 31band condition analyzers 31c/31d. The instruction analyzer 31areceives the instruction, and interprets a request incorporated in the instruction. The instruction is representative of a registration, a data retrieval and a data elimination, and the control is branched to one of the index marker 31b, the condition analyzer 31cand the other condition analyzer 31ddepending upon the interpretation. The index marker 31blabels a piece of status information with an index. The condition analyzers 31cand 31ddetermine search conditions for a piece or pieces of status information and the indexes to be reported and search conditions for a piece or pieces of status information and the indexes to be deleted.

[0063] The data processing unit 31 further includes a group organizer 31e, a data retriever 31f, a data eliminator 31g, a register 31h, a logical relation analyzer 31jand a failure path analyzer 31k. The group organizer 31e, the logical relation analyzer 31jand the failure path analyzer 31kare newly incorporated in the failure analysis system according to the present invention.

[0064] The group organizer 31egives a tag to a piece or pieces of status information estimated in parallel to one another. In other words, if pieces of status information are labeled with a tag, the associated indexes are branched from a particular upper-level index.

[0065] Using the index as a unit, the register 31gregister 31gstores the pieces of status information in the memory unit 32a, and builds a tree-like index structure in the memory unit 32b. If pieces of status information are estimated on the basis of a piece of status information labeled with a particular index, the particular index and the indexes given to the pieces of status information are inserted into the tree-like index structure as an upper-level index and lower-level indexes to be branched from the upper-level index. The register 31gfurther stores the relation between the tags and the indexes. If pieces of status information belong to a particular group labeled with a tag, the indexes given to the pieces of status information are stored in the memory unit 32cunder the particular tag.

[0066] The data retriever 31freceives the search conditions from the condition analyzer 31c, and searches the memory units 32a/32b/32cfor a piece or pieces of status information, an index/indexes and/or a tag satisfying the search conditions. When the data retriever 31ffinds it or them, the data retriever 31ftransfers the piece or pieces of status information, the index/indexes and/or the tag to the output unit 30b, and the output unit 30bproduces a search report for these pieces of information.

[0067] The condition analyzer 31ddetermines search conditions for a piece or pieces of status information, an index/indexes and/or a tag to be eliminated from the contents of the memory units 32a/32b/32c. The search conditions are transferred from the condition analyzer 31dto the data eliminator 31g. The data eliminator 31I searches the memory units 32a/32b/32cfor a piece or pieces of status information, an index/indexes and/or a tag satisfying the search conditions. When the piece or pieces of status information, the index/indexes and/or the tag are found, they are eliminated from the contents of the memory units 32a/32b/32c.

[0068] The logical relation analyzer 31jchecks the tree-like index structure and the contents of the memory unit 32cto see what kind of logical relation is found. If it is impossible that two pieces of status information can concurrently take place, the two pieces of status information are in the AND relation. On the other hand, if the two pieces of status information can concurrently take place, they are in the OR relation.

[0069] The failure path analyzer 31kanalyzes the contents of the memory units 32a/32b/32cin order to find a failure propagation path in a given combinational circuit.

[0070] The failure analyzer according to the present invention behaves as follows. FIG. 7 illustrates a program sequence executed by the failure analysis system. When an instruction is transferred from the input unit 30ato the instruction analyzer 31a, the failure analysis system starts the program sequence at step SP30, and sequentially checks the instruction to see what job is to be requested as by steps SP31, SP32 and SP33. If the instruction requests the failure analysis system to newly register a piece of status information, the control is branched from step SP31 to step SP34. If the instruction requests the failure analysis system to search a particular piece or pieces of status information, the associated index/indexes and the tag, the control is branched from step SP32 to step SP35. If the instruction requests the failure analysis system to eliminate a particular piece or pieces of status information, the associated index/indexes and the tag from the memory units 32a/32b/32c, the control is branched from step SP32 to step SP36.

[0071] Assuming now that the job to be requested is a registration, the index marker 31badds an index to a piece of status information representative of logic status estimated by the diagnostic system 33 as by step SP34. The piece of status information contains plural logic values at respective nodes. If the estimation is carried out on the basis of logic status at a node labeled with an upper-level index, the upper-level index is known to the index marker 31b, and the index marker 31bdetermines the new index not to be conflict with the upper-level index.

[0072] Subsequently, the piece of status information labeled with the index is transferred to the group organizer 31e. The group organizer 31especifies other pieces of status information estimated in parallel to the piece of status information, and gives a tag to the pieces of status information estimated in parallel to one another as by step SP37. The tag is indicative of a group number assigned to those pieces of status information.

[0073] The piece of status information labeled with the index is transferred to the register 31gtogether with the tag, and the register 31gstores the piece of status information, the index and the tag in the memory units 32a/32b/32cas by step SP38. In the memory unit 32a, the index is used as unit, and the logic values at the related nodes and the node names are stored under the index. The index is linked with the upper-level index in order to build a tree-like index structure in the memory unit 32b. The tag is stored in the memory unit 32c, and is representative of the indexes given to the pieces of status information estimated in parallel to one another.

[0074] When the job to be requested is the data retrieval, the condition analyzer 31canalyzes the instruction, and determines search conditions for a piece or pieces of status information, an index/indexes and a tag/tags as by step SP35. If the search conditions represent determination of the logical relation, the search conditions are supplied from the condition analyzer 31cto the logic relation analyzer 31j. The logic relation analyzer 31jchecks the contents of the memory 32 to see what pieces of status information concern the AND relation and the OR relation as by step SP36, and supplies the search results to the output unit 30bas by step SP40.

[0075] If the search conditions represent estimation of a failure propagation path, the failure path analyzer 31kdetermines a linkage of the AND relation as by step SP41, and supplies the result to the output unit 30b.

[0076] On the other hand, if the search conditions do not represent the determination of logical relation nor the determination of a failure origin, the data retriever 31fsearches the memory 33 for a piece/pieces of status information, an index/indexes and/or a tag/tags satisfying the search conditions, and supplies the search result to the output unit 30bas by step SP42.

[0077] When the output unit 30breceives the search result or the analysis result, the output unit 30bproduces a report from the search result or the analysis report, and supplies the report to the analyst or the diagnostic system 33 as by step SP43.

[0078] When the instruction requests an elimination job, the condition analyzer 31ddetermines search conditions for a piece or pieces of status information, an index/indexes and/or a tag/tags to be eliminated as by step SP36, and the search conditions are supplied to the data eliminator 31g. The data eliminator 31gsearches the memory 33 for a piece or pieces of status information, an index/indexes and/or a tag/tags satisfying the search conditions, and eliminates the piece or pieces of status information, the index/indexes and/or the tag/tags from the contents of the memory 33 as by step SP44.

[0079] Subsequently, description is made on the determination of logical relation at step SP40 in detail with reference to FIG. 8. The logical relation analyzer 31freceives the search conditions from the condition analyzer 31c, and starts a program sequence shown in FIG. 8. The logical relation analyzer 31ffirstly sequentially fetches the indexes stored in the memory unit 32b, and determines lines of the indexes incorporated in the tree-like index structure as by step SP50. Subsequently, the logical relation analyzer 31fsequentially compares the lines of indexes with one another from the highest level indexes toward the lowest-level indexes, and repeatedly checks indexes of the lines to see whether there is inconsistency between the index of one of the lines and the index of another line as by step SP51.

[0080] If the logical relation analyzer 31jfinds the inconsistency between the indexes, the logical relation analyzer 31jfetches the tags respectively given to the inconsistent indexes as by step SP52, and, thereafter, proceeds to step SP53. The logical relation analyzer 31jcompares the tags to see whether or not the tags are consistent with one another as by step SP53. If the tags are inconsistent, the answer at step SP53 is given negative, and the logical relation analyzer 31jdetermines the associated pieces of status information to be in the AND relation as by step SP54. On the other hand, if the tags are consistent, the answer at step SP53 is given affirmative, and the logical relation analyzer 31jdetermines the associated pieces of status information to be in the OR relation as by step SP55.

[0081] Subsequently, description is made on the estimation of failure propagation path at step SP41 with reference to FIG. 8. When the search conditions are supplied from the condition analyzer 31cto the failure path analyzer 31k, the failure path analyzer 31kaccesses the memory unit 32c, and selects one index from each of the index groups respectively assigned the tags as by step SP60. Subsequently, the failure path analyzer 31kdeletes non-selected indexes and lower-level index or indexes linked with the non-selected indexes from the tree-like index structure as by step SP61. The non-eliminated indexes are in the AND relation.

[0082] The failure path analyzer 31kproceeds to step SP62, and connects the pieces of status information respectively labeled with the remaining indexes. Then, the failure path analyzer determines a candidate of the failure propagation path.

[0083] FIG. 10 illustrates a tree-like index structure stored in the memory unit 32b. Numerals “0”, “1”, “2”, “3”, “4”, “5”, “6”, “7”, “8”, “9”, “10”, “11”, “12”, “13”, “14” and “15” are the indexes, which are given to the pieces of status information associated with the nodes F1/F2, F3, F4, F5/F6, F5/F7, F8, F9, F10, F11, F12, F13, F14, F15 and F16, respectively. The tree-like index structure includes plural index groups, and the index groups are respectively labeled with the tags G1/G2/G3/G4/G5/G6/G7/G8. Description is hereinbelow made on the construction for the tree-like index structure and determination of a failure origin with concurrent reference to FIGS. 7, 8, 9, 10, 4 and 5.

[0084] Unexpected output signals are assumed to appear at the nodes F1/F2. The input unit 30atransfers an instruction for a data retrieval to the data processing unit 31, and the instruction analyzer 31ainterprets the instruction to be a request for the data retrieval, and the answer at step SP32 is given affirmative. Then, the condition analyzer 31cdetermines the search conditions to be a node or nodes not estimated yet at step SP35. The search conditions are supplied to the data retriever 31f, and the data retriever 31fsearches the memory 32 for a node or nodes not estimated yet. The nodes F1/F2 satisfy the search conditions. The data retriever 31ffinds the nodes F1/F2 labeled with index “0”, and informs the output unit 30bthat the nodes F1/F2 labeled with index “0” have not been analyzed yet at step SP43. The output unit 30balso informs the diagnostic system 33 that the nodes F1/F2 have not been analyzed yet.

[0085] The diagnostic system 33 identifies a circuit related to the nodes F1/F2 with the circuit A (see FIGS. 4 and 5), and estimates the logic status expressed by two pieces of status information. The two pieces of status information are indicative of two failure propagation paths, respectively. One of the failure propagation paths is from the node F3 to the nodes F1/F2, and the other failure propagation path is from the node F4 to the nodes F1/F2. Then, the diagnostic system 33 supplies an instruction representative of a data registration through the input unit 30ato the instruction analyzer 31a.

[0086] The instruction analyzer 31ainterprets the instruction, and determines that the diagnostic system 33 requests the data processing unit 31 to register the pieces of status information. The answer at step SP31 is given affirmative, and the index marker 31bgives new indexes “1” and “2” to the pieces of status information at step SP34. New index “1” is indicative of the failure propagation path from the node F3 to the nodes F1/F2, and other index “2” is indicative of the failure propagation path from the node F4 to the nodes F1/F2. Both indexes “1” and “2” are estimated from the circuit A, and the group organizer 31egives a tag G1 to the indexes “1” and “2” at step SP37.

[0087] The two pieces of status information, the indexes “1”/“2”, the upper-level index “0” and the tag G1 are transferred to the register 31g. Each of the pieces of status information contains the node names and the logic values at the nodes, and the register 31gstores the two pieces of status information under the indexes “1”/“2”, respectively. The register 31glinks the indexes “1”/“2” with the index “0”, and stores the indexes “1”/“2” as lower-level indexes of the index “0” in the memory unit 32b. Finally, the register 31gstores the tag G1 together with the indexes “1” and “2” in the memory unit 32c.

[0088] Upon completion of the registration, the diagnostic system 33 supplies an instruction for a data retrieval through the input unit 30ato the data processing unit 31, and the instruction analyzer 31ainterprets that the diagnostic system 33 requests a data retrieval. Then, the answer at step SP32 is given affirmative, and the condition analyzer 31cdetermines that the search conditions are a node or nodes not estimated yet at step SP35. The search conditions are supplied to the data retriever 31f.

[0089] The data retriever 31fsearches the memory 32 for a node or nodes not estimated yet at step SP42, and finds that the nodes F3/F4 satisfy the search conditions. The data retriever 31ftransfers the search result to the output unit 30b, and the output unit 30binforms that the node F3 labeled with the index “1” and the node F4 labeled with the index “2” have not been analyzed yet.

[0090] The diagnostic system 33 identifies circuit B and another circuit (not shown) to be related to the nodes F3/F4. The diagnostic system 33 estimates the logic status of the circuit B, and obtains two logic values. In other words, the diagnostic system 33 acquires two pieces of status information, one of which represents a failure propagation path from nodes F5/F6 to the node F3 (see FIG. 4), and the other of which represents another failure propagation path from the nodes F5/F7 to the node F3 (see FIG. 5).

[0091] The diagnostic system supplies an instruction through the input unit 30ato the data processing unit 31, and the instruction analyzer 31ainterprets that the diagnostic system 33 requests a data registration for the pieces of status information representative of the failure propagation paths from the nodes F5/F6 to the node F3 and the other failure propagation path from the nodes F5/F7 to the node F3. Then, the answer at step SP31 is given affirmative, and the index marker 31blabels the pieces of status information with index “3” and index “4”, respectively, at step SP34. The group organizer 31egives a tag G2 to the indexes “3” and “4” at step SP37. The register 31gstores the pieces of status information representative of the two failure propagation paths and the indexes “3” and “4” in the memory unit 32a, and connects the indexes “3” and “4” to the index “1”. The register 31gfurther stores the indexes “3” and “4” together with the tag G2 in the memory unit 32c.

[0092] The diagnostic system 33 further estimates the logic status of the other circuit (not shown), and acquires a piece of status information representative of a failure propagation path from the node F8 to the node F4. The piece of status information representative of the failure propagation path from the node F8 to the node F4 is labeled with index “5”, and the group organizer 31egives a tag G3 to the index “5”. The register 31gstores the piece of status information labeled with index “5” in the memory unit 32a, and connects the index “5” to the index “2”. The register 31gstores the tag G3 for the index “5” in the memory unit 32c.

[0093] Upon completion of the registration, the diagnostic system 33 supplies an instruction through the input unit 30ato the data processor 31, and the instruction analyzer 31ainterprets that the diagnostic system 33 requests a data retrieval for a node or nodes not estimated yet. The condition analyzer 31cdetermines the search conditions to be a node or nodes not estimated yet, and the data retriever 31fsearches the memory 32 for a node or nodes satisfying the search conditions. The data retriever 31ffinds that the nodes F5/F6 labeled with the index “3”, the nodes F5/F7 labeled with the index “4” and the node F8 labeled with the index “5” satisfy the search conditions.

[0094] The diagnostic system 33 repeats the estimation, and requests the data processing unit 31 to store pieces of status information representative of failure propagation paths from the nodes F9/F10/F11/F12 to the nodes F5/F6, pieces of status information representative of failure propagation paths from the nodes F9/F10/F13/F14 to the nodes F5/F7 and pieces of status information representative of failure propagation paths from the nodes F15/F16 to the node F8. The index marker 31bgives indexes “6”, “7”, “8” and “9” to the pieces of status information representative of the failure propagation paths from the nodes F9/F10/F11/F12 to the nodes F5/F6, respectively, indexes “10”, “11”, “12” and “13” to the pieces of status information representative of failure propagation paths from the nodes F9/F10/F13/F14 to the nodes F5/F7, respectively, and indexes “14” and “15” to the pieces of status information representative of failure propagation paths from the nodes F15/F16 to the node F8, respectively. The group organizer 31egives tags G4, G5, G6, G7 and G8 to the indexes “6”/“7”, the indexes “8”/“9”, the indexes “10”/“11”, the indexes “12”/“13” and the indexes “14”/“15”, respectively. The pieces of status information, the indexes and the tags are stored in the memory 32 as similar to those described hereinbefore, and the tree-like index structure is completed as shown in FIG. 10.

[0095] The indexes “1” to “15” are connected through solid lines, and the solid line represents the relation between an upper-level index and lower-level indexes. Therefore, the solid lines teach the direction of estimation. For example, the failure propagation paths shown in FIG. 4 are estimated as follows. The node F3 is determined from the logic value labeled with the index “1” which is estimated on the basis of the pieces of status information at the nodes F1/F2 labeled with the index “0”. The nodes F5/F6 are determined from the logic value labeled with the index “3” which is estimated on the basis of the piece of status information at the node F3, and the nodes F9 and F11 are respectively determined from the logic values labeled with the indexes “6” and “8” which are estimated on the basis of the pieces of status information at the nodes F5/F6.

[0096] Similarly, the failure propagation paths shown in FIG. 5 are estimated as follows. The node F3 is determined from the logic value labeled with the index “1” which is estimated on the basis of the pieces of status information at the nodes F1/F2 labeled with the index “0”. The nodes F5/F7 are determined from the logic value labeled with the index “4” which is estimated on the basis of the piece of status information at the node F3, and the nodes F9 and F13 are respectively determined from the logic values labeled with the indexes “10” and “12” which are estimated on the basis of the pieces of status information at the nodes F5/F7. Thus, the solid lines indicates the direction of estimation such as, for example, from the index “0” through the indexes “1” and “3” to the index “6”.

[0097] The tags G1, G2, G3, G4, G5, G6, G7 and G8 allow the logical relation analyzer 31fto make the logical relations between the pieces of status information clear. Assuming now that the logical relation analyzer 31janalyzes the logical relation between the piece of status information labeled with the index “6” and the piece of status information labeled with the index “8”, the logical relation analyzer 31jfirstly checks the tree-like index structure to see whether any lines of indexes are found between the highest level index “0” and the target indexes “6” and “8”. The logical relation analyzer 31jfinds that the indexes “0” and “6” are incorporated in the line of indexes through the indexes “1” and “3” and that the indexes “0” and “8” are incorporated in another line of indexes through the indexes “1” and “3” at step SP50. The two lines of indexes are consistent until the index “3”, and are branched from the index “3” to the indexes “6” and “8”. In other words, only the failure propagation path from the index “3” to the index “6” is different from the failure propagation path from the index “3” to the index “8”. Thus, the logical relation analyzer 31jdetermines the indexes “6” and “8” to be inconsistent with one another at step SP51.

[0098] When the inconsistent indexes are determined, the logical relation analyzer 31jchecks the memory unit 32cto see what tags are given to the inconsistent indexes “6” and “8”. The logical relation analyzer 31jfinds that the tags G4 and G5 are given to the indexes “6” and “8”, respectively, at step SP52.

[0099] The tag given to the index “6” is inconsistent with the tag given to the index “8”. Then, the answer at step SP53 is given negative, and the logical relation analyzer 31jdetermines the indexes “6” and “8” to be in the AND relation at step SP54.

[0100] Subsequently, the logical relation analyzer 31janalyzes the logical relation between the index “6” and the index “12”. The logical relation analyzer 31jdetermines the lines of indexes, and finds indexes branched from an index shared between the lines of indexes. The indexes “0” and “1” are shared between the lines of indexes, and the indexes “3” and “4” are branched from the index “1”. The tag G2 is given to both indexes “3” and “4”. Then, the answer at step SP53 is given affirmative, and the logical relation analyzer 31jdetermines the indexes “6” and “12” to be in the OR relation at step SP55. In this way, the logical relation is successively determined on the basis of the tree-like index structure and the tags given to the indexes.

[0101] The failure path analyzer 31kestimates a candidate of the failure propagation path as follows. First, the failure path analyzer 31kselect an index from each of the index groups (see step SP60 in FIG. 9). The indexes 1, 3, 5, 6, 8, 10, 12 and 14 are, by way of example, selected from the index groups G1, G2, G3, G4, G5, G6, G7 and G8, respectively, at step SP61. Subsequently, the failure path analyzer 31kdeletes the non-selected indexes and the lower-level indexes linked with the non-selected indexes from the tree-like index structure. Then, the indexes 0, 1, 3, 6 and 8 are left in the tree-like index structure. The indexes 0, 1, 3, 6 and 8 are indicative of a candidate of the failure propagation path.

[0102] Thus, the method of managing estimated logic status proceeds by extracting combinational circuits. A similar method is available for the extraction of a sequential circuit as one block.

[0103] As will be understood from the foregoing description, the failure analysis system according to the present invention includes the logical relation analyzer and the failure path analyzer, and those analyzers offers an analysis more useful than that of the prior art failure analysis system. The logic relation analyzer makes the logical relation between the pieces of status information clear, and the failure path analyzer selects candidates of a failure propagation path from the tree-like index structure.

[0104] Turning to FIG. 11 of the drawings, another failure analysis system embodying the present invention also comprises a data input-output facility 50, a data processing unit 51 and a data storage 52. The data input-output facility 50 and the data storage 52 are similar to the input-output facility 30 and the data storage 32, and, for this reason, units incorporated therein are labeled with the same references designating corresponding units of the first embodiment without detailed description.

[0105] The data processing unit 51 is partially different from the data processing unit 31. The units similar to those of the data processing unit 31 are labeled with the same references as the corresponding units of the data processing unit 31. The register 31gis replaced with a register 51a, and a searcher 51bis inserted between the group organizer 31eand the register 51a.

[0106] The searcher 51bchecks the pieces of status information to see whether any node has a logic value equal to another node categorized in the same group estimated in parallel. The register 51abehaves as similar to the register 31gexcept for the case where a piece of logic status is estimated in parallel to another piece of logic status. In detail, the register 51agroups pieces of status information by the index, and stores the pieces of status information in the data storage 52 under the index as similar to the register 31gas long as the pieces of status information were independently estimated. When a piece of status information represents a logic value at a node estimated in parallel to another node, the resister 51agives the node the upper-level index instead of an index assigned thereto by the index marker 31b. The other registration work is similar to that of the register 31g. The register 51aconnects lower-level indexes to an upper-level index, and builds up a tree-like index structure in the memory unit 32b. Moreover, the register 51astores tags representative of the index groups and the indexes selectively grouped under the tags in the memory unit 32c.

[0107] Description is hereinbelow made on the failure analysis with reference to FIG. 12. The program sequence shown in FIG. 7 is modified so that step SP38 is replaced with steps SP71/SP72. The other steps shown in FIG. 12 are similar to those of the program sequence shown in FIG. 7, and, for this reason, are labeled with the same references designating the corresponding steps without detailed description. The failure analysis system implementing the first embodiment repeats the estimation of logic status for a particular node under different indexes of a node group. The repetition is undesirable, and the failure analysis system shown in FIG. 11 avoids the repetition as follows.

[0108] Upon completion of step SP37, the searcher 51bsearches the data storage 52 for a node already given the logic value equal to that of the node presently processed in the same index group as by step SP71. If only one piece of status information is acquired through the estimation for a node, the node is registered under the upper-level index. If the searcher 51bcan not find the node with the same logic value, the register 51astores the pieces of status information, the index and the tag for the node presently processed as by step SP72. On the other hand, when the searcher 51bfinds the node, the register 51astores the upper-level index instead of the index given at step SP34 in the memory unit 32aat step SP72.

[0109] The above-described modification is detailed with reference to FIGS. 13, 14 and 15. Assuming now that unexpected output signals appear at nodes F1/F2, index “0” was given to the nodes F1/F2, and a piece of status information and index “0” have been already stored in the memory units 32a/32b.

[0110] The diagnostic system 33 requests the data processing unit 51 to look for a node or nodes not estimated yet. The instruction analyzer 31achecks the instruction supplied from the diagnostic system 33 to see whether the diagnostic system 33 requests the data processing unit 51 to register, retrieve or eliminate a piece/pieces of status information, index/indexes and/or tag/tags. The instruction analyzer 31adetermines that the diagnostic system 33 determines that the diagnostic system 33 requests a data retrieval at step SP32 (se FIG. 12), and the condition analyzer 31cdetermines the search conditions to be a node or nodes not estimated yet at step SP35. The data retriever 31fsearches the data storage 52 for a node or nodes satisfying the search conditions at step SP42. The data retriever 31ffinds the nodes F1/F2, and the output unit 30bsupplies a search report to the diagnostic system 33 at step SP43.

[0111] The diagnostic system 33 extracts a circuit 70afrom a sequential circuit 71 on the basis of the nodes F1/F2 labeled with index “0”, and estimates the logic status inside thereof. Two pieces of status information respectively are assumed to be estimated. One of the pieces of status information is representative of a failure propagation path from a node F3 to the nodes F1/F2 (see FIGS. 14 and 15), and the other piece of status information represents another failure propagation path from a node F4 to the nodes F1/F2 (see FIG. 13. Then, the diagnostic system 33 instructs the failure analysis system to register the pieces of status information.

[0112] The instruction analyzer 31adetermines that the diagnostic system 33 requests the data processing unit 51 to store the pieces of status information at step SP31. The index marker 31bgives indexes “1” and “2” to the two pieces of status information, respectively, at step SP34. The group organizer 31egives a tag G1 to the indexes “1” and “2”, because both pieces of status information have been determined on the basis of the logic status inside the circuit 70a.

[0113] Although the searcher 51btries to find a node with the logic value equal to either logic value in the index group G1, there is not any piece of status information, and the register 51astores the pieces of status information under the indexes “1” and “2” in the memory unit 32a, connects the indexes “1” and “2” to the upper-level index “0” in the memory unit 32b, and stores the indexes “1” and “2” together with the tag G1 in the memory unit 32cat step SP72.

[0114] Subsequently, the diagnostic system 33 instructs the failure analysis system to find a node or nodes not estimated yet, and the data retriever 31ffinds the nodes F3/F4. The diagnostic system 33 extracts a circuit 70bfrom the sequential circuit 71, and estimates the logic status inside the circuit 70b. The diagnostic system 33 acquires two pieces of status information through the estimation. One of the pieces of status information is representative of a failure propagation path from nodes F5/F6 to the node F3 (see FIG. 14), and the other piece of status information is representative of another failure propagation path from nodes F5/F7 to the node F3. Although the index marker 31btemporarily gives indexes “3” and “4” to the pieces of status information, the node F5 is shared between the indexes “3” and “4”, and the node F5 is stored under the upper-level index “1” as shown in FIG. 13. As a result, only the nodes F6 and F7 are stored under the indexes “3” and “4”, respectively, in the memory unit 32a. A tag G2 is given to the indexes “3” and “4”. The indexes “3” and “4” are added to the tree-like index structure as lower-level indexes under the upper-level index “1”, and the indexes “3” and “4” are stored under the tag G2 in the memory unit 32c.

[0115] The diagnostic system 33 further estimates the logic status inside the circuit 70bfor the node F4, and acquires a piece of status information representative of a failure propagation path from a node F8 to the node F4. Although the index marker 31blabels the piece of status information with index “5”, the logic value to be stored under the index “5” is registered under the upper-level index “2” as shown. The index “5” is inserted into the tree-like index structure as a lower-level index of the index “2”, and the index “5” is stored in the memory unit 32ctogether with a tag G3.

[0116] Subsequently, the diagnostic system 33 instructs the data processing unit 51 to find a node or nodes not estimated yet. The data retriever 31ffinds the node F5 labeled with the index “1”, the node F8 labeled with the index “2”, the node F6 labeled with the index “3” and the node F7 labeled with the index “4”. The search report is supplied from the output unit 30bto the diagnostic unit 33.

[0117] In this way, the failure analysis system cooperates with the diagnostic system 33, and builds the tree-like index structure shown in FIG. 13 in the memory unit 32b. The tree-like index structure shown in FIG. 13 is different from the tree-like index structure shown in FIG. 10 in that the nodes F5/F8 shared between different indexes “3” and “4” and solely registered under the upper-level index “2” are moved to the locations labeled with the upper-level indexes “1” and “2”. When the diagnostic system requests the failure analysis system to find a node or nodes not estimated yet, the data retriever 31fonce finds the node F6 and the node F7, and the diagnostic system 33 does not repeatedly estimate the logic status at the nodes F5. Thus, the failure analysis system reduces the load of the diagnostic system 33.

[0118] As shown in FIG. 14, the node F3 is determined on the basis of the piece of status information labeled with the index “1” estimated from the circuit 70arelating to the nodes F1/F2, the nodes F5/F6 are determined on the basis of the pieces of status information labeled with the index “3” estimated from the circuit 70brelating to the node F3, and the nodes F9/F11 are determined on the basis of pieces of status information estimated from circuits 70c/70dlabeled with the indexes “6” and “8” relating to the nodes F5/F6, respectively.

[0119] On the other hand, the failure propagation paths shown in FIG. 15 are determined as follows. The node F3 is determined on the basis of the piece of status information estimated from the circuit 70arelating to the nodes F1/F2, the nodes F5/F7 are determined on the basis of pieces of status information estimated from the circuit 70brelating to the node F3, and the nodes F9/F13 are determined on the basis of pieces of status information estimated from circuits 70c/70erelating to the nodes F5/F7, respectively.

[0120] If the searcher 51bis not incorporated in the failure analysis system, the diagnostic system 33 twice estimates the logic status inside the circuit 70c. The failure analysis system implementing the second embodiment specifies the node F5 stored under the index “1”, and the diagnostic system once estimates the logic status inside the circuit 70c. As a result, the analysis is speed up, and the tree-like index structure consumes memory area less than that consumed by the first embodiment. Of course, the failure analysis system achieves the advantages of the first embodiment.

[0121] FIG. 16 illustrates yet another failure analysis system embodying the present invention. The failure analysis system largely comprises a data input-output facility 80, a data processing unit 81, a data storage 82 and an information storage medium 83. The data input-output facility 80, the data processing unit 81 and the data storage 82 are similar to those of the first or second embodiment, and description is omitted for the sake of simplicity.

[0122] The information storage medium 83 is implemented by a magnetic disk, semiconductor memory devices or other kind of information storage medium. The information storage medium 83 stores the program sequence shown in FIG. 7 or 12, and the data processing unit 81 sequentially fetches the instruction codes of the program sequence. The analysis achieved through the program sequence is similar to that of the first or second embodiment, and no further description is incorporated hereinbelow for avoiding repetition.

[0123] As will be appreciated from the foregoing description, the failure analysis system according to the present invention determines the logical relation between the pieces of status information by using the tags given to the index group, and estimates the failure propagation path through each combinational circuit. The failure analysis system equipped with the searcher 51bprevents the diagnostic system from a multiple estimation carried out for a node stored under different indexes in the tree-like index structure, and reduces the load of the diagnostic system.

[0124] Although particular embodiments of the present invention have been shown and described, it will be apparent to those skilled in the art that various changes and modifications may be made without departing from the spirit and scope of the present invention.

[0125] The failure path analyzer selects an index from each index group in the first embodiment. The failure path analyzer may check the index from index “0” toward index “15” so as to select one index from each index group. For example, the failure path analyzer 31kdetermines that indexes “1” and “2” belong to the index group G1, and, then, selects index “1” from the index group G1. Similarly, the sub-indexes “3” and “4” of the index “1” belong to the index group G2, and the failure path analyzer 31kselects index “3”. The indexes “6” and “7” belong to the index group G4 branched from the selected index “3”, and the failure path analyzer 31kselects the index “6”. Subsequently, the failure path analyzer 31kfinds that the indexes “8” and “9” belong to the index group G5 also branched from the selected index “3”, and the failure path analyzer 31kselects the index “8”. As a result, the failure analyzer 31kdetermines candidates of the failure path shown in FIG. 4.