Implementation of Combinational Logic Circuits Using Nearest-Neighbor One-Dimensional Four-State Cellular Automata

Document Type : Research Paper


1 University of Tehran, College of Engineering, Faculty of Engineerng Science, Department of Algorithms and Computation

2 Department of Algorithms and Computation, College of Engineering, University of Tehran Tehran, 1417613131, Iran

3 Department of Electrical and Computer Engineering, Utah State University Logan, UT 84322-4120, USA


Cellular automata are simple mathematical idealizations of natural systems. They consist of a lattice of discrete identical sites, each site taking on a finite set of, say, integer values. Over the years, scientists have been trying to investigate the computational capabilities of cellular automata by limiting the dimension, neighborhood radius, and the number of states.
In this article, we represent a novel implementation of combinational logic circuits using nearest-neighbor one-dimensional four-state cellular automata (CA). The novelty behind the proposed model is the reduction of the required number of states and yet being able to implement combinational logic-circuits in the conventional CA fashion. This can open a new window to the computation using cellular automata.