2-D Reversible Cellular Automata with Nearest and Prolonged Next Nearest Neighborhoods under Periodic Boundary

Journal Name:

Publication Year:

Abstract (2. Language): 
In this paper, we study a 2-dimensional cellular automaton generated by a new local rule with the nearest neighborhoods and prolonged next nearest neighborhoods under periodic boundary condition over the ternary field (Z 3). We obtain the rule matrix of this cellular automaton and characterize this family by exploring some of their important characteristics. We get some recurrence equations which simplifies the computation of the rank of the rule matrix related to the 2-dimensional cellular automaton drastically. Next, we propose an algorithm to determine the rank of the rule matrix. Finally, we conclude by presenting an application to error correcting codes.



[1] H. Akın. On the directional entropy of Z2 -actions generated by additive cellular automata,
Applied Mathematics and Computation. 170 (1), 339-346. 2005.
[2] H. Akın. On the topological directional entropy, Journal of Computational and Applied
Mathematics. 225 (2), 459-466. 2009.
[3] H. Akın and I. Siap. On cellular automata over Galois rings, Information Processing
Letters. 103 (1), 24-27. 2007.
[4] G. Alvarez, L. H. Encinas, and A. Martin del Rey. A multisecret sharing scheme for color
images based on cellular automata, Information Sciences. 178, 4382-4395. 2008.
[5] S.R. Blackburn, S. Murphy, and K.G. Peterson. Comments on theory and applications of
cellular automata in cryptography, IEEE Transactions on Computers. 46, 637-638. 1997.
[6] P. Chattopdhyay, P. P. Choudhury, and K. Dihidar. Characterisation of a particular hybrid
transformation of two-dimensional cellular automata, Computers Mathematics with Applications.
38, 207-216. 1999.
[7] S.J. Cho, U.S. Choi, and S.H. Heo. Design of double error correcting codes based on
cellular automata, Journal of Applied Mathematics and Computing. 21, 545-553. 2006.
[8] D.R. Chowdhury, S. Basu, I.S. Gupta, and P.P. Chaudhuri. Design of CAECC-Cellular
Automata Based Error Correcting Code, IEEE Transactions on Computers. 43, 759-764.
[9] A. K. Das. Additive cellular automata: Theory and application as a built-in self-test
structure, PH.D. Thesis, I.I.T. Kharagpur, India. 1990.
[10] K. Dihidar and P. P. Choudhury. Matrix algebraic formulae concerning some exceptional
rules of two dimensional cellular automata, Information Sciences 165, 91-101. 2004.
[11] S. Inokuchi and T. Sato. On limit cycles and transient lengths of cellular automata with
threshold rules, Bulletin of Informatics and Cybernetics. 32 (1), 2360. 2000.
[12] A. R. Khan, P. P. Choudhury, K. Dihidar, S. Mitra, and P. Sarkar. VLSI architecture of a
cellular automata, Computers Mathematics with Applications. 33, 79-94. 1997.
[13] A. R. Khan, P. P. Choudhury, K. Dihidar, and R. Verma. Text compression using two dimensional
cellular automata, Computers Mathematics with Applications. 37, 115-127.
[14] S. Lipschutz. Theory and problems of linear algebra, Mc Graw Hill Inc. 1990.
[15] F.J. MacWilliams and N.J.A Sloane. The Theory Of Error Correcting Codes, North-
Holland Pub. Co., 1977.
[16] M. Mihaljevic, Y. Zheng, and H. Imai. A family of fast dedicated one-way hash functions
based on linear cellular automata over GF(q), IEICE Transactions on Fundamentals E82-
A, 40-47. 1999.
[17] K. Nishinar and D. Takahashi. Multi-value cellular automaton models and metastable
states in a congested phase, Journal of Physics A: Mathematical and General. 33, 7709-
7720. 2000.
[18] I. Siap, H. Akın, and F. Sah. Characterization of two dimensional cellular automata over
ternary fields, Journal of the Franklin Institute, 348, 1258-1275. 2011.
[19] I. Siap, H. Akın, and F. Sah. Garden of Eden configurations for 2-D cellular automaton
with rule 2460N, Information Science. 180 (18), 3562-3571. 20107
[20] I. Siap, H. Akın, and S. Uguz. Structure and reversibility of 2-dimensional hexagonal cellular
automata, Computers Mathematics with Applications, 62(11), 4161-4169. 2011.
[21] J. Von Neumann. The theory of self-reproducing automata, (Edited by A.W.Burks), Univ.
of Illinois Press, Urbana. 1966.
[22] S. Wolfram. Statistical mechanics of cellular automata, Reviews of Modern Physics.
55(3), 601-644. 1983.

Thank you for copying data from http://www.arastirmax.com