A signal path grouping algorithm for fast detection of shortcircuits 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