Optimal interconnect diagnosis

摘要

Interconnect diagnosis is an important problem in very large scale integration (VLSI), multi-chip module (MCM) and printed circuit board (PCB) production. The problem is to detect and locate all the shorts among a given set of nets using the minimum number of tests. In this paper, we prove matching lower bounds for two non-adaptive diagnosis problems, and give an optimal algorithm for the adaptive diagnosis problem. Our results provide optimal solutions to several open problems in interconnect diagnosis.