Design for complete testability and fault diagnosis of programmable logic arrays

Abstract

The primary objective of this thesis is the formulation of a systematic procedure for the conversion of a Programmable Logic Array (PLA) having untestable faults into a corresponding completely testable PLA. In a completely testable PLA, all the modeled crosspoint faults, bridging faults, and stuck faults will be testable. First, it is shown that PLA minimization may not eliminate all untestable crosspoint faults. Then, the use of control inputs for the design of crosspoint-irredundant PLAs—that is, PLAs in which untestable crosspoint faults are absent—is illustrated. A condition to be satisfied by such PLAs is derived in terms of covering row sets. The problem of minimizing the number of control inputs required is posed as a non-standard set covering problem. This problem is then converted into a familiar problem of covering a set using the minimum number of maximal compatibles in the set. A depth-first tree search technique, incorporating a simple lower bound to limit the search, is developed for obtaining a minimum cover. An upper bound on the number of control inputs required in a given case is also obtained. A crosspoint-irredundant PLA obtained by the above procedure is analyzed to identify:

All stuck faults and bridging faults that are untestable Those faults not guaranteed to be detected by a test set for all crosspoint faults

A completely testable PLA is obtained by including appropriate additional hardware to eliminate the untestable faults. Both AND-type and OR-type bridging faults are considered. It is also shown that a completely testable PLA is easily testable, in the sense that a test set for all crosspoint faults is sufficient to test all stuck faults and adjacent bridging faults.

Online Fault Location Algorithm Another objective of this thesis is the development of an online algorithm for the location of crosspoint faults in a PLA. The important feature of the algorithm is the determination of a fault set corresponding to the response of a PLA for a failed test input. An upper bound on the number of faults in this set is obtained. For the obviously small number of faults in this set, all the remaining tests are generated and a fault table is formed. An adaptive procedure, followed by a functional equivalence test, is carried out to locate the fault equivalence class.