Design for complete testability and fault diagnosis of programmable logic arrays

Abstract

This thesis presents a systematic procedure for converting a programmable logic array (PLA) with untestable faults into a completely testable PLA. In such a PLA, all modeled faults - including crosspoint faults, bridging faults, and stuck faults - are guaranteed to be testable. It is first demonstrated that PLA minimization alone does not eliminate all untestable crosspoint faults. The concept of control inputs is introduced to design crosspoint-irredundant PLAs, and a condition for their construction is derived using covering row sets. The problem of minimizing control inputs is formulated as a non-standard set covering problem and transformed into a familiar problem involving maximal compatibles. A depth-first tree search algorithm with a lower bound heuristic is developed to find a minimal cover, and an upper bound on control inputs is also established. The resulting PLA is analyzed to identify stuck and bridging faults that remain untestable or are not guaranteed to be detected by crosspoint fault test sets. Additional hardware is proposed to eliminate these faults, resulting in a completely testable PLA. Both AND-type and OR-type bridging faults are considered. It is shown that such a PLA is easily testable, as a test set for crosspoint faults suffices to detect all stuck and adjacent bridging faults. A secondary objective of the thesis is the development of an online algorithm for locating crosspoint faults in a PLA. The algorithm identifies a fault set based on the response to a failed test input and provides an upper bound on the number of faults in the set. An adaptive procedure followed by a functional equivalence test is used to locate the fault equivalence class.