Fault covers in reconfigurable PLAs
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 166-173
- https://doi.org/10.1109/ftcs.1990.89352
Abstract
Three kinds of faults are considered: stuck-at faults, bridging faults, and crosspoint faults. A new way of repairing bridging faults is introduced. It is shown that the problem of finding a minimum cover is NP-complete but that a special case of this problem can be formulated as a 2-SAT problem, which can be solved in polynomial time. The problem of finding a feasible cover for RPLAs (reconfigurable programmable logic arrays) with bridging faults alone is shown to be NP-complete. A necessary and sufficient condition on the number of spares for the existence of a feasible cover and an algorithm for finding a minimum feasible cover are presented.<>Keywords
This publication has 16 references indexed in Scilit:
- Location and identification for single and multiple faults in testable redundant PLAs for yield enhancementPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Minimum fault coverage in reconfigurable arraysPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- On yield consideration for the design of redundant programmable logic arraysIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1988
- On the design of a redundant programmable logic array (RPLA)IEEE Journal of Solid-State Circuits, 1987
- Implementing a Built-In Self-Test PLA DesignIEEE Design & Test of Computers, 1985
- Design and Application of Self-Testing Comparators Implemented with MOS PLA'sIEEE Transactions on Computers, 1984
- A Design of Programmable Logic Arrays with Universal TestsIEEE Transactions on Computers, 1981
- Multiple Fault Detection in Programmable Logic ArraysIEEE Transactions on Computers, 1980
- On the Complexity of Timetable and Multicommodity Flow ProblemsSIAM Journal on Computing, 1976
- A Computing Procedure for Quantification TheoryJournal of the ACM, 1960