A sweeping line approach to interconnect testing

This paper presents a new structural approach for test generation and diagnosis of interconnects (such as wiring networks). The proposed technique is based on computational geometry by considering the physical adjacencies of the nets in the layout. This information is used by a sweeping line technique for generating the test vectors. A realistic fault model in which nets can be bridged only if they are physically adjacent, is proposed. The proposed approach generates a set of initial local vectors for testing all the nets at the inputs. A different set of local vectors is then, generated by sweeping the layout at every point where two nets may intersect. The set of local vectors is generally sparse. So, a compaction algorithm is proposed for generating the final set. The proposed approach has an execution time of O((p+k) log p) for generating the local tests, where p is the maximum number of segments in the nets and k is the number of possible intersection points. It is proved that the problem of generating the minimum number of test vectors by compaction is NP-complete, but simulation results show that the proposed heuristic criteria are very efficient for a practical application. The extension of the proposed approach to other fault models and to other routing schemes (as applicable to PCB and VLSI) is presented