A signal path grouping algorithm for fast detection of short circuits on printed circuit boards

In a previous study, Leung (1993) proposed a parallel algorithm to locate all the short circuits on a printed circuit board. This algorithm divides the signal paths into multiple groups such that each group has a predetermined number of signal paths, and it tests M groups of signal paths against M respective groups simultaneously. In this paper, we show that the average number of tests required by Leung´s algorithm depends not only on the number of signal paths in each group but also on how the signal paths are grouped. The reason is that a signal path is more likely shorted to its neighboring paths, but it is less likely shorted to the faraway paths. We propose an algorithm, called a signal path grouping algorithm, to selectively group the signal paths. If this signal path grouping algorithm is used to complement Leung´s algorithm, the average number of tests required can be reduced