Reliable Crossing of Signals in Asynchronous Cellular Automata

The embedding of logic circuits into the cellular spaces is an essential approach for efficient computing on asynchronous cellular automata (ACAs), which usually depends critically on the design of signals. Such signals are required to propagate definitely in predefined directions, and cross other signals coming from orthogonal directions without blockage. Adachi et al. (2004) constructed signals in an ACA with von Neumann neighborhood, which takes 5 states per cell and 24 transition rules. Unfortunately, two signals colliding with each other at the crossing point of paths may occasionally cause deadlock, due to the lack of adequate rules to cope with such a situation. This paper presents a novel 5-state ACA with von Neumann neighborhood that uses 64 rules, which allows reliable propagation and crossing of signals at all times.