Error detection/correction and fault detection/recovery – Pulse or data error handling – Error/fault detection technique
Reexamination Certificate
1998-11-19
2001-10-09
Moise, Emmanuel L. (Department: 2734)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Error/fault detection technique
C714S025000, C714S824000
Reexamination Certificate
active
06301685
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an error propagation path extraction system, error propagation path extraction method, and a recording medium recording error propagation path extraction control program, particularly to an error propagation path extraction system for quickly obtaining a signal line in which a fault may propagate in a combinational logic circuit.
2. Description of the Related Art
In the case of a conventional error propagation path extraction system, there is a system for extracting a route in which an error may propagate in a circuit when an input/output logical state obtained by inputting a test pattern is different from a normal output expected for a normal circuit. As disclosed in the official gazette of Japanese Patent Application Laid-Open No. 8-146093, this system can be used as a part of a fault diagnosis system of a sequential circuit. In this case, a fault can be present in the combinational circuit or an error can be included in an input pattern.
As the above error propagation path extraction system, there is a inverse logical inference system using a back track system introducing Don't Care. This inverse logical inference system is a system for estimating the logical state of the input terminal of a combinational logic circuit from the logical state of the output terminal of the circuit.
When using the fault diagnosis system for the fault analysis of a 100K-gate-size sequential circuit, a combinational circuit to be extracted is estimated as a 10K-gate size and the capacity for estimating every input signal pattern of the same-size combinational circuit is necessary.
In this case, a back track system is a system for estimating the logical state of every signal line by repeating implication and decision, which is also referred to as a “branch-and-bound system.”
Because the back track system uses only a small number of memories, in which the number of data values is proportional to the number of gates, it has features that it is possible to easily estimate the number of memories used, the algorithm is simple, and parallel processing is easy. In the case of the back track system, however, when a circuit size increases, the decision frequency increases. Therefore, a lot of calculation time is required to obtain every input logical state.
By applying the back track system to inverse logical inference, it is possible to estimate the internal logical state of a logic circuit. The back track system is described in “M. Abramobvici, M. A. Breuer, and A. D. Friedman, Digital Systems Testing and Testable Design, IEEE Press, New York, pp. 186-196, 1990.”
The above error propagation path extraction system is a method for comparing the input estimated state obtained through inverse logical inference and the logical state in a combinational logic circuit obtained in the process of the inverse logical inference with a normal logical value previously obtained through logical simulation in a normal circuit, recognizing a signal line under a faulty state, and extracting an error propagation path. This method makes it possible to obtain every input logical state meeting an output logical state and every internal logical state of a circuit and extract an error propagation path by comparing the states with a normal logical value.
However, it is estimated that the decision frequency greatly increases and the calculation time increases in the case of a multiplier. Moreover, as a circuit increases in size, the number of input logical states becomes tremendous. If an error propagation path is extracted from these tremendous logical states, a route not influencing a fault output is also extracted. In this case, a route not influencing a fault output denotes a route not propagating a fault to a fault output even if the fault occurs on the route though a logical state does not coincide with a normal logical value.
Moreover, to obtain an input logical state meeting an output logical state, it is assumed that a combinational circuit is normal. Therefore, it is impossible to extract an error propagation path for a fault due to the inside of the combinational circuit.
An embodiment of the prior art is described below in detail by referring to the accompanying drawings. In
FIG. 10
, the embodiment of the prior art includes an input unit
1
such as a keyboard, a data processor
2
operated in accordance with program control, a memory
4
for storing information, and an output unit
5
such as a display or printer.
The memory
4
is provided with a logic-circuit-structure storage section
41
, a decision-state storage section
42
, and a logical-state storage section
43
. The logic-circuit-structure storage section
41
previously stores the structure of a logic circuit, that is, the type of gate, connective relation between gates, connective relation between gate and signal line, and connective relation between signal lines.
The decision-state storage section
42
stores a decision level showing the number of decisions performed and a decision level when the logical state of each signal line is estimated through implication. The logical-state storage section
43
stores the logical state of each signal line under processing and the logical state (normal logical value) of each signal line when a circuit is normal.
The data processor
2
is provided with an initialization section
21
, an X(Don't Care) state (hereafter referred to as X state) setting section
22
, a first implication section
23
, a logical contradiction judgment section
24
, a processing-completion judgment section
25
, a back-track section
26
, U(Unknown)-state (hereafter referred to as U state) retrieval section
27
, logical-value decision section
29
, and logical-value comparison section
30
.
The initialization section
21
sets the type of a logic circuit supplied from the input unit
1
and the logical state of an input/output terminal. The X-state setting section
22
refers to a logic circuit structure stored in the logic-circuit-structure storage section
41
and the logical state of each signal line stored in the logical-state storage section
43
, sets the initial logical state of each signal line whose logical state is not fixed to X state, and records the X state in the logical-state storage section
43
. In this case, the X state is a logical state representing to allow both logical states “0” and “1” when both logical states “0” and “1” of a signal line do not contradict the logical state of the entire logic circuit.
As shown in
FIG. 11
, the first implication section
23
includes an implication section
231
, logical contradiction detection section
232
, a first-implication-allowing-gate retrieval section
233
, and an implication-completion judgment section
234
.
The implication section
231
refers to a logic circuit structure stored in the logic-circuit-structure storage section
41
and the logical state of each signal line stored in the logical-state storage section
43
and estimates the logical state of an input/output line at an input/output line set by the initialization section
21
, a gate connected to a signal line decided by the logical-value decision section
29
, or a gate detected by the first implication-allowing-gate retrieval section
233
. Estimation of a logical state is performed by using “0,” “1,” and “X.”
When a new logical value is estimated, the implication section
231
records the logical value in the logical-state storage section
43
and moreover, records a decision level showing under what number of decisions the estimation is performed in the decision-state storage section
42
.
The logical-contradiction detection section
232
refers to a logic circuit structure stored in the logic-circuit-structure storage section
41
and the logical state of each signal line stored in the logical-state storage section
43
and detects a contradiction between a new logical state decided by the implication section
231
and a logical state having been decided by that point of time if any.
The first implication-
Moise Emmanuel L.
NEC Corporation
Young & Thompson
LandOfFree
Error propagation path extraction system, error propagation... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Error propagation path extraction system, error propagation..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Error propagation path extraction system, error propagation... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2595041