Two-step algorithms for maximal diagnosis of wiring interconnects

We give two algorithms for maximal diagnosis of wiring networks without repair under a general fault model. Maximal diagnosis consists of identifying all diagnosable faults under the assumptions that each net can have multiple drivers and receivers and can be affected by any number of short and open faults. This process is equivalent to verifying all connections between inputs and outputs. Matrices represent the connections in fault-free and faulty networks. All algorithms discussed are adaptive and have their tests divided into two phases. Our first algorithm exploits a unique condition for verifying the connections; our second algorithm maps the connection verification problem to a bipartite graph. All algorithms use an independent test set for the first test phase. Simulation results show that the proposed algorithms outperform previous algorithms for maximal diagnosis, in terms of the number of tests. The total time complexity for computing the test sequences and analyzing the output response is polynomial.