A parallel algorithm for locating short circuits on printed circuit boards

To locate all the short circuits on a printed circuit board, S.C. Fang (1990) proposed an efficient algorithm that finds the shorted paths one by one and groups these shorted paths into equivalence classes. By properly grouping the signal paths and testing one group of signal paths against another group at a time, Fang showed that this algorithm has the worst-case complexity O( chi log/sub 2/ N), where N and chi are the numbers of signal paths and shorted paths, respectively. A parallel algorithm based on Fang's algorithm is proposed for locating all the short circuits on a printed circuit board. By using M current sources of different frequencies and M bandpass filters with different passbands, this algorithm tests M groups of signal paths against M respective groups simultaneously. It is shown that this algorithm has worst-case complexity O( chi log/sub M/ N) and a much smaller average complexity than Fang's algorithm.