Simulation of Non-uniform Cellular Automata by Classical Cellular Automata and Its Application in Embedded Systems
Supreeti Kamilya, Sukanta Das and Biplab K Sikdar
A uniform cellular automaton (CA) is a special case of non-uniform CA. This paper shows that for any non-uniform CA, there exists a uniform CA that simulates the dynamics of the non-uniform CA. A function (ψ) is defined that maps the rules and states of a non-uniform CA to the states of the proposed uniform CA. According to the construction of the function, the number of states of the uniform CA is greater than that of the non-uniform CA. It is shown that, a number of non-uniform cellular automata (CAs), formed using same set of local rules, can be simulated by a single uniform CA. Under this construction, the function ψ is a bijection. To reduce the number of states in the uniform CA, the function ψ is redefined later as a non-bijective function. However, there exists some uniform CAs which do not simulate any non-uniform CA by the given construction. As any non-uniform CA can be simulated by uniform CA, different applications that use different non-uniform CAs, can now be implemented in one system. This paper shows a brief overview of such an application. The proposed CA based design ensures hardware re-usability and cost effectiveness.
Keywords: Uniform cellular automata, non-uniform cellular automata, simulation, unified system