Combinatorial group testing methods for the BIST diagnosis problem

We examine an abstract formulation of BIST diagnosis in digital logic systems. The BIST diagnosis problem has applications that include identification of erroneous test vectors, faulty scan cells, faulty modules, and faulty logic blocks in FPGAs. We develop an abstract model of this problem and show a fundamental correspondence to the well-established subject of combinatorial group testing (CGT) [Ding-Zhu Du et al., (1994)]. Armed with this new perspective, we show how to improve on a number of existing techniques in the VLSI diagnosis literature. In addition, we adapt and apply a number of CGT algorithms that are well-suited to the diagnosis problem in the digital realm. We also propose completely new methods and empirically evaluate the different algorithms. Our experiments show that results of the proposed algorithms outperform recent diagnosis techniques [J. Ghosh-Dastidar et al. (1999), (2000), J. Rajski et al. (1997)]. Finally, we point out future directions that can lead to new solutions for the BIST diagnosis problem.