A "well behaving" property is defined for each line (in general a bundle of wires) connecting two combinational logic cells. This property can be easily taken into account in the design process of the circuit. It is shown that all tree-structured circuits of combinational logic cells are easily testable for multiple faults if each line is "well behaving". The size of the test set increases only linearly as the number of cells increases. It is also shown that if no line is well-behaving then only the trivial (exhaustive) test set exists for the circuit, which increases exponentially as the number of cells increases. If there are well-behaving as well as non-well-behaving lines in the circuit, then the size of the test set increases exponentially with the sizes of the non-well-behaving subtrees and linearly with the number of such subtrees.

It is shown that any generalized counter of full-adder cells is testable for multiple faults with a test set of size proportional to the number of cells. Any number of cells can be faulty in any way, as long as the faults are permanent, the cells remain combinational, and no signal values other than 0 and 1 are generated.>

It is shown that one-dimensional, unilateral iterative logic arrays (ILAs) of combinational cells are C-testable for multiple sequential faults, provided the fault-free cell functions satisfy appropriate conditions. The test sequence is of length O((m/sup 2/n/sup 2/+mn/sup 3/)*K), where n (resp. m) is the number of signal values that can be applied to the horizontal (resp. vertical) cell input and K>

In this paper, a very simple model of parallel computation is considered, and the question of how restricting the flow of data to be one way compares with two-way flow is studied. It is shown that the one-way version is surprisingly very powerful in that it can solve problems that seemingly require two-way communication. Whether or not one-way communication is strictly weaker than two-way is an open problem, although the conjecture in this paper is in the positive. It is shown, however, that proving this conjecture is at least as hard as some well-known open problems in complexity theory.

We look at a very simple model of parallel computation and study the question of how restricting the flow of data to be one-way compares with two-way flow. A one-way linear iterative array (1LIA) is a finite one-dimensional array of identical finite-state machines (cells) in which information is allowed to move only in one direction- from left to right. For inputs of length n, the array uses n cells which are initially set to the quiescent state. The serial input, which is applied to the leftmost cell, is accepted if the rightmost cell ever enters an accepting state. We give results which show that 1LIA's are surprisingly very powerful in that they can accept languages which seemingly require two-way communication.

Two sets of conditions are derived that make one- dimensional bilateral arrays of combinational cells testable for single faulty cells. The test sequences are preset and, in the worst case, grow quadratically with the size of the array. Conditions for testability in linear time are also derived. The basic cell can operate at the bit or at the word level. An implementation of FIR filters using (systolic) one-dimensional bilateral arrays of cells, which can be considered combinational at the word level, is presented as an example. A straightforward generalization for the two- dimensional case is made; a systolic array used for matrix multiplication is presented as an example for this case.

The issue of testing two-dimensional iterative arrays with a constant number of test vectors independent of the array size (C-testability) is discussed in this paper. Sufficient conditions for C-testability are stated. It is shown that any two-dimensional array can be modified to become C-testable. An extension to systolic (synchronous) arrays is made. The approach simplifies testing systolic arrays by using one test vector to test many cells of the array in a periodic fashion. A two-dimensional array for matrix multiplication is used to illustrate the approach for systolic arrays.