A graph representation for programmable logic arrays to facilitate testing and logic design

In this paper, we present a new graph model and an associated set of operations for representing programmable logic arrays (PLA's). The signal lines and devices of a PLA are represented as the edges and vertices of a directed graph, respectively. Through this graph model, most realistic PLA faults, including cross-point, stuck-at, break, and bridging faults, can be modeled and classified, and the maximal diagnosis resolution of a PLA can be determined. Moreover, the model can be easily transformed into a gate-level model. Hence, the work of automatic test-pattern generation for a PLA and for other random logic can be done simultaneously. We also show that this representation can be extended to some logic design techniques such as logic minimization, folding, and decomposition for PLA's. Thus, this graph model can unify the data structure and operations required in PLA design and test.