Search

This paper studies chaotic behavior of 1-dimensional non-uniform cellular automata (CAs). The chaotic system is unpredictable in the long run. To understand the source of unpredictability, we add an information to a cell and check how it flows to its neighbors. That is, once the state of a cell is changed, the probability to which the change affects its neighbors, is calculated. The probabilistic value decides whether one cell communicates with another cell. Depending on the communication among cells, a binary relation over the set of cells is defined in this paper which is known as communication relation. It is shown that the relation should be an equivalence relation to make a cellular automaton (CA) chaotic. The equivalence relation among the cells form an equivalence class which is named as communication class. Another important property of a chaotic CA is transitivity of the CA. Transitivity of a CA does not allow disjoint subsets of a configuration space. Based on the communication class and transitivity property of a CA, we newly define the chaos in CA. Sometimes one cell may not be able to communicate with another cell due to blocking word. The presence of blocking word in a CA makes the CA non-transitive. This paper shows a method to find out such blocking words. Finally, a parametrization technique is developed in this work based on the transitivity, communication class and blocking words. Depending on the parameter value of a non-uniform CA, one can predict whether the behavior of the CA is chaotic.

This work reports a unification technique that can form a universal platform to emulate any cellular automata (CAs). The paper shows that a number of non-uniform CAs can be mapped into one uniform CA. To show the effectiveness of the unification method, three well known applications, such as pseudo random pattern generation, cryptography and pattern classification are chosen where three different CAs are used for the corresponding hardware implementations. Finally, the hardware is proposed to show that all these existing applications, that use different platforms, can now be implemented in a universal platform.

This work reports realization of close to accurate data migration in Chip Multiprocessors (CMPs). The periodic boundary cellular automata (PBCA) is introduced to accept the requests from processor cores competing for a data block and to perform accurate density classification of the requesting processors. The CA enables identification of populated region of requesting cores and thereby points to the area of migration. The design is enriched to favor the processor cores in isolation and to decide on the area of migration to avoid performance loss of such processors.

This paper presents a study of chaos in one-dimensional cellular automata (CAs). The communication of information from one part of the system to another has been taken into consideration in this study. This communication is formalized as a binary relation over the set of cells. It is shown that this relation is an equivalence relation and all the cells form a single equivalence class when the cellular automaton (CA) is chaotic. However, the communication between two cells is sometimes blocked in some CAs by a subconfiguration which appears in between the cells during evolution. This blocking of communication by a subconfiguration has been analyzed in this paper with the help of de Bruijn graph. We identify two types of blocking — full and partial. Finally a parameter has been developed for the CAs. We show that the proposed parameter performs better than the existing parameters.