A new formulation of yield enhancement problems for reconfigurable chips

The covering problem assigns redundant elements to replace defective elements so that the chip will function properly. A general model that can be used to represent the relationship between redundant elements and defective elements in a uniform way is presented. This model subsumes many of the models discussed in previous approaches. A complete characterization of the complexity of the covering problems in all the subcases of the model, most of which have not been studied before, is given. It is hoped that the formulation will also lead to new ways of designing reconfigurable chips.<>