A self-diagnosis algorithm for hypercube networks and its application to VLSI circuit testing

In this paper we introduce a self-diagnosis algorithm for hypercube-connected systems. The algorithm produces a diagnosis which is provably correct if the number of faulty units in the system is less than a thereshold T? asserted by the algorithm itself. Although the diagnosis may be incomplete, simulations show that the expected number of unidentified units is very small. The application of the diagnosis strategy to the manufacturing test of VLSI chips is also considered.