Abstract
Cellular Automata (CA) are a promising architecture for computers with nanometerscale sized components, because their regular structure potentially allows chemical manufacturing techniques based on self-organization . With the increase in integration density, however, comes a decrease in the reliability of the components from which such computers will be built. This paper employs techniques borrowed from error-correcting coding theory to construct CA with improved reliability. We will construct an asynchronous CA of which in the best case half of the bits storing a cell's state information may be corrupted without affecting the CA's operations, provided errors are evenly distributed over a cell's bits (no burst errors allowed), and certain bits in neighboring cells are not corrupted. Even if on the average a quarter of the bits in the cellular space are erroneous, the CA can recover from it, again assuming no burst errors occur. Under the same condition, the corruption of all of a cell's bits can be detected.