Testing for faults in combinational cellular logic arrays

Cellular logic arrays are beginning to take on an increasingly greater importance in digital technology, mainly because of their numerous advantages for the design, manufacture, and use in digital systems employing large-scale integrated semiconductor arrays. Particularly significant among these advantages is the feature of testability. One would naturally expect that the iterative structure and the short intercell connections of a cellular logic array would allow it to be tested from its edge terminals much more easily than a relatively disorganized interconnection of the same number of gates. In this paper we confirm this conjecture, and we describe procedures for deriving minimal (or near-minimal) schedules of test inputs, to be applied to a combinational cellular array in order to detect the presence of any single faulty cell. In addition, necessary and sufficient conditions are presented for some types of arrays of unilaterally connected, identical cells to be completely testable for single faults. For one-dimensional arrays, these conditions are based upon known results in sequential network theory. For two-dimensional arrays, a relationship to the "domino problem" (which is known to be insoluble) is described, but is shown to be largely avoidable and nonrestricting in the present case.