Fault-tolerant schemes for some systolic systems. (English) Zbl 0656.68055

Fault-tolerant schemes for several types of systolic systems are proposed. By a fault-tolerant scheme for a certain type of systems, say undirectional rings, we mean an algorithm that converts any given system of this type into an equivalent fault-tolerant system of the same type. We consider a specific type of fault tolerance introduced by Kung and Lam. It is assumed that the faulty cells of a given system can be detected and “switched” so that each of them passes its inputs to its outputs in a specified order.
To specify the degree of fault tolerance we introduce the notion of fault tolerance with respect to a collection \(\Omega\) of subsets of the cells of a system. To be fault tolerant, the system must tolerate the failure of all the cells of any of the subset in \(\Omega\). We devise fault- tolerant schemes for trellis networks, one-way (unidirectional) cellular automata, one-way rings and two-way cellular automata and iterative arrays.


68Q80 Cellular automata (computational aspects)
Full Text: DOI


[1] Bucher W., RAIRO, Inf. Theoretique 18 pp 307– (1984)
[2] DOI: 10.1007/BF00264617 · Zbl 0534.68039
[3] DOI: 10.1016/0304-3975(85)90091-X · Zbl 0584.68068
[4] DOI: 10.1080/00207168408803410 · Zbl 0571.68041
[5] DOI: 10.1080/00207168408803421 · Zbl 0571.68042
[6] DOI: 10.1016/S0019-9958(80)90164-3 · Zbl 0442.68082
[7] DOI: 10.1016/S0022-0000(75)80066-3 · Zbl 0319.94030
[8] Hennie F. C., Iterative arrays of logical circuits (1961)
[9] DOI: 10.1137/0214033 · Zbl 0574.68044
[10] DOI: 10.1109/T-C.1974.223995 · Zbl 0285.68027
[11] Kung, H. T. and Lam, M. S. 1984. MIT Conf. on Advanced Research in VLSI. Fault-tolerant and two-level pipelining in VLSI systolic arrays. Jan1984.
[12] DOI: 10.1109/MC.1982.1653825 · Zbl 05331537
[13] DOI: 10.1016/S0022-0000(75)80065-1 · Zbl 0319.94029
[14] DOI: 10.1016/S0022-0000(72)80004-7 · Zbl 0268.68044
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.