Fault tolerant cellular automata

摘要

Cellular automata have some useful characteristics because of the uniformity of the cellular structure. Here we use geometrical codings to design fault tolerant cellular automata which simulate given cellular automata. First, the concept of a group graph is introduced as a mathematical description of the cellular structure. Geometrical codings are then defined using its algebraic properties. Under the condition of K-separated misoperation, i.e., at each state transition at most one cell in any K-neighborhood of the cellular space can possibly misoperate, it is possible to design cellular automata which have detection capabity or correction capability. Some examples are also presented using the two-dimensional lattice and the hexagonal cellular space.