Fault tolerant cellular spaces

摘要

This paper treats the problem of designing a fault tolerant cellular space which simulates an arbitrary given cellular space in real time. A cellular space is called fault tolerant if it behaves normally even when its component cells misoperate.First such notions as simulation, misoperation, and K-separated misoperation are defined. Then a new multidimensional coding of configurations is introduced and explained using as typical example the two-dimensional space.The first main result is Theorem 1, which states that the introduced coding method is useful for correcting errors occurring at most once in every K=5×5 rectangle. The general theory is given in Section 6, where the second main result is given in the form of Theorem 8. It gives a necessary and sufficient condition for testing whether or not a given coding is adequate for error correction.