Fault spectrum analysis for fast spare allocation in reconfigurable arrays

Repairing a reconfigurable array by row and column replacement using SR rows and SC columns was shown to be an NP -complete problem. In order to reduce the search time, the authors propose to apply a three phase procedure. In the first phase, they suggest using a heuristic to find good, but not necessarily optimal, feasible cover for the faulty array. Only if the heuristic method fails to generate a feasible cover, the array is examined to find out whether it is repairable at all. If deemed economical, repairable chips will undergo an exhaustive analysis. This three phase strategy can considerably reduce the average time for repair analysis. Searching for a good heuristic to be applied in phase 1, the authors investigated the fault distribution pattern on the faulty array and considered the effect of a row or column replacement on this fault distribution. Accordingly, a k degree fault spectrum for a bipartite graph is defined and a maximum spectrum is introduced as a heuristic for selecting vertices. They prove that the vertices which are most likely to be included in the feasible cover will be selected by heuristic. Consequently, a fast method to generate a feasible cover is proposed and a suitable algorithm is developed