Minimum fault coverage in reconfigurable arrays

Abstract

The authors discuss the case in which the redundant elements are arranged in the form of spare rows and spare columns for a rectangular array. Redundant RAMs are examples of such case. A covering is set of rows and columns that are to be replaced by spare rows and spare columns so that all defective elements are replaced. The authors introduce the notion of a critical set, which is a maximum set of rows and columns that must be included in any minimum covering. They show that for a given pattern of defective elements the corresponding critical set is unique. They also present a polynomial-time algorithm for finding the critical set and demonstrate how the concept of critical sets can be used to solve a number of fault-coverage problems.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>