A line in a combinational circuit is classified into three types: a primary output, an input of a gate, and a stem. More precisely, a stem is either non-reconvergent fan-out or reconvergent fan-out. We use the fault simulation method based on the topology analysis of a circuit. During the topological fault simulation, a fault at a non-reconvergent fan-out stem is detected by searching the fan-outs of the stem, while the fault at the reconvergent fan-out stem cannot be detected. For the fault detection at the reconvergent fan-out stem, it is necessary to propagate the fault until the detection is determined. It is desirable to reduce the number of gates to be activated in propagating fault for the detection of the reconvergent fan-out stem. In this thesis, we propose two efficient fault detection methods for different circumstances. One is a primary output oriented fault detection method which is useful when test patterns are incrementally given one by one. The other is a fault detection method which is useful when a lot of test patterns are deposited at once. Both of them especially concentrate on the effective fault detection of the reconvergent fan-out stem to reduce the number of gates to be activated. Faults are detected in sequence from the primary outputs to the primary inputs. In the first method, the fault detection is traced with respect to each primary output with a single test pattern. This method is called primary output oriented fault detection, which is the firstly proposed parallel scheme for the fault simulation. The fault detection with respect to each primary output is performed in parellel. The event driven tracing is used during the fault propagation. The fault at a reconvergent fan-out stem can be detected without propagating the fault through all the propagation region, because the fault detection is determined independently with respect to each primary output. The region where the fault should be propagated is dynamically changed during the fault simulation. A fault simulation method which this detection scheme has been applied to is proposed. Experiments on the several benchmark circuits show that our fault simulation method reduces the number of activated gates by half in average cases compared with the other to which the primary output oriented fault detection has not been applied. In the second method, parallel patterns are evaluated simultaneously. There exists a static region in which the fault propagation is sufficient to detect the fault of the reconvergent fan-out stem, although parallel patterns are evaluated. Moreover, we reuse the available prior fault propagations during the fault detection of the reconvergent fan-out stem. The availability of reusing is proven by analyzing the stem region in detail and extracting the commonly useful sub-regions. The region where the fault propagation is inevitable is reduced to the primary stem region. A fault simulation method including this detection scheme is proposed and experiments on the several benchmark circuits illustrate the good performance.
조합 회로에서 선의 종류는 다음의 세가지로 분류할 수 있다. 근본 출력과 게이트의 입력 그리고 줄기가 그것이다. 줄기는 좀 더 상세히 비재수렴 줄기와 재수렴 줄기로 나눌 수 있다. 이 논문에서는 회로의 연결망 분석에 의거한 고장 모의실험을 사용하였다. 이 고장 모의실험 중에 비재수렴 줄기의 고장은 그 줄기의 가지만을 살펴봄으로써 검출될 수 있다. 반면 재수렴 줄기에 관해서는 그렇지 않다. 이 재수렴 줄기에 소재한 고장을 검출해 내기 위해서는 검출이 확인 되기까지 근본 출력으로 고장을 전파해 보아야 한다. 재수렴 줄기의 고장 검출을 위한 고장 전파시에 활성되는 게이트의 수를 적게 하는 것이 바람직하다. 본 논문에서는 다른 상황에 적합한 두 가지 효율적인 고장 모의실험 방법을 제시하였다. 하나는 근본 출력에 향한 방법인데 이는 검사 신호가 하나씩 점진적으로 주어지는 경우에 유용한 방법이다. 다른 하나는 한꺼번에 많은 검사 신호가 주어지는 경우에 유용한 방법이다. 두 방법 모두 다 재수렴 줄기의 고장 검출을 위해 활성화 해야 하는 게이트의 수를 줄이고자 하는 데 역점을 두고 있다. 고장 검출은 근본 출력에서부터 근본 입력까지의 순o}�? 진행 된다. 첫 번째 방법에서는 한 개의 검사 신호로 각 근본 출력에 관해서 고장 검출을 추적한다. 이 방법을 근본 출력에 향한 고장 검출이라 한다. 이 방법은 고장 모의 실험에 처음으로 고안된 병렬화 방법이다. 고장 검출이 각 근본 출력에 대해 병렬로 추진된다. 사건 중심 추적이 고장 전파시에 이용된다. 고장 검출은 각 근본 출력에 대하여 독립적으로 결정되므로 모든 고장 전파 영역으로 고장 전파 없이도 재수렴 줄기의 고장이 검출 될 수 있다. 필요 불가결한 고장 전파 영역은 고장 모의실험 중에 동적으로 변할 수 있다. 이러한 검출 기법이 적용된 고장 모의실험 방법이 제안 되었다. 여러개의 벤치마크 회로에 실험을 해 보았다. 결과로 근본 출력에 향한 검출 방법을 채택하지 않은 고장 모의실험 방법에서 보다 약 절반 만큼 활성되는 게이트의 수가 절감 된다. 두 번째 방법에서는 병렬 검사 신호가 동시에 평가되게 된다. 비록 여러개의 병렬 검사 신호가 평가되어 사건 중심 추적이 어렵더라도 재수렴 줄기의 고장을 검출하기 위해 고장 전파되어야 할 고정된 영역이 있게 된다. 거기에 재수렴 줄기의 고장 검출의 확인을 위해 수행한 앞서의 유용한 고장 전파를 재 사용하게 된다. 이러한 재사용의 당위성은 줄기 영역의 자세한 분석과 함께 사용되는 유용한 부-영역의 추출에 의하여 증명된다. 결과로 고장 전파가 필요 불가결한 영역이 일차 줄기 영역으로 줄어들게 된다. 이러한 검출 기법이 적용된 고장 모의 실험 방법이 제안되었고, 여러 벤치마크 회로에 대한 실험에서 좋은 성능을 나타내었다.
