Analysis of bounded linear cellular automata based on a method of image charges

摘要

The temporal evolution of a class of one-dimensional cellular automata (CA) implementable in VLSI, is a problem of considerable complexity in the presence of the natural (null) boundary conditions. This paper provides an analytical solution to their evolution, based upon a method of image charges borrowed from electrostatics. Reductions in computational effort by factors of O(L2) for a single site value, or O(L) for the entire configuration of the CA, as compared to direct simulation, are obtainable by the present method of image charges. These results are expected to provide a basis for CA applications as highly parallel computational structures to be incorporated as functional blocks is novel VLSI architectures.