Formulation of a Test Pattern Measure That Counts Distinguished Fault-Pairs for Circuit Fault Diagnosis

Tsutomu INAMOTO  Yoshinobu HIGAMI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E103-A   No.12   pp.1456-1463
Publication Date: 2020/12/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.2020VLP0007
Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
Category: 
Keyword: 
LSI testing,  circuit fault diagnosis,  set cover problem,  greedy heuristic,  fault-pair,  

Full Text: PDF>>
Buy this Article




Summary: 
In this paper, we aim to develop technologies for the circuit fault diagnosis and propose a formulation of a measure of a test pattern for the circuit fault diagnosis. Given a faulty circuit, the fault diagnosis is to deduce locations of faults that had occurred in the circuit. The fault diagnosis is executed in software before the failure analysis by which engineers inspect physical defects, and helps to improve the manufacturing process which yielded faulty circuits. The heart of the fault diagnosis is to distinguish between candidate faults by using test patterns, which are applied to the circuit-under-diagnosis (CUD), and thus test patterns that can distinguish as many faults as possible need to be generated. This fact motivates us to consider the test pattern measure based on the number of fault-pairs that become distinguished by a test pattern. To the best of the authors' knowledge, that measure requires the computational time of complexity order O(NF2), where NF denotes the number of candidate faults. Since NF is generally large for real industrial circuits, the computational time of the measure is long even when a high-performance computer is used. The formulation proposed in this paper makes it possible to calculate the measure in the computational complexity of O(NF log NF), and thus that measure is useful for the test pattern selection in the fault diagnosis. In computational experiments, the effectiveness of the formulation is demonstrated as samples of computational times of the measure calculated by the traditional and the proposed formulae and thorough comparisons between several greedy heuristics which are based on the measure.