Yield enhancement of field programmable logic arrays by inherent component redundancy

A complete technique that does not use any additional components for enhancing the yield of field-programmable logic arrays (FPLAs) is presented. In this approach, the inherent sparsity (absence of devices at crosspoints) of programmable logic arrays (PLAs) is utilized to mask certain types of manufacturing defects within the unprogrammed FPLAs, thus reclaiming chips which are otherwise discarded. Two categories of faults (called type 1 and type 2) are considered. Type-1 faults, which can be diagnosed a priori, are considered first. After diagnosing type 1 faults, the mask can be reconfigured around the faulty crosspoints. A streamlined bipartite matching algorithm is presented to enhance the speed of this reconfiguration. The uniqueness of the approach is that the programming of an FPLA is formulated as a graph theoretic problem for which a polynomial time solution exists. Type-2 faults in general cannot be diagnosed a priori. Therefore, a dynamic technique is presented for the repair of type-2 faults. Unused product lines of the FPLA are utilized for the repair. With a sufficient number of excess product lines, it is shown that a defective FPLA is guaranteed to be rendered usable. A probability measure for the usability of defective FPLA is obtained both with and without the implementation of this technique. Computer studies have shown that FPLAs with even a large number of defects can be successfully repaired, thereby increasing the yield