ON THE TESTABILITY OF ITERATIVE LOGIC-ARRAYS

The problem of detecting single cellular faults in arbitrarily large one-dimensional, unilateral, combinational iterative logic array (= ILAs) is considered. Fault patterns ( = FPs) of the ILA's basic cell are introduced to characterize any cellular fault. Testability properties like (full, partial) testability, redundancy, test complexity of FPs are studied. Based on this analysis we prove that only two test complexity classes exist: the minimum size of a complete test set of an ILA is either constant - in this case the ILA is called C-testable - or linear in the length of the ILA. Furthermore, depending on the type of the FP that is considered new efficient algorithms for the determination of the test complexity and the construction of complete test sets are presented. In particular, we reduce the exponential worst case complexity of the construction given in (Friedman, 1973) to a polynomial worst case bound (measured in the size of the function table for the basic cell).