An Algorithm for Locating Short Circuits Among N Signal Paths Using K-Port Parallel Short Detector

To locate short circuits on a printed circuit board, a K-port parallel short detector can test K signal paths simultaneously. If the total number of signal paths N on a printed circuit board is larger than K, then we need to divide the testing process into multiple stages such that at most K signal paths are tested in each stage. In this paper, we design a parallel algorithm to locate all the short circuits among the N signal paths on a printed circuit board using a K-port parallel short detector where K<N. This algorithm consists of three main steps: (1) it partitions the set of signal paths {1, 2 • •, N} into disjoint sets Si’s such that Si contains at most K signal paths, and then it bisects Si, into two disjoint sets T2i_1 and T2i, (2) it locates all the short circuits in Sifor all i, and (3) it locates all the short circuits between Siand Sjfor all i ≠ j by testing T2i-1against t2j-1, t2i-1againstT2j, T2iagainst T2j-1, and t2iagainst T2j.