compiles/a4299af2063161b093a3327c9ea5f943/output.dvi


EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS

Vol. 6, No. 3, 2013, 315-334

ISSN 1307-5543 – www.ejpam.com

2-D Reversible Cellular Automata with Nearest and Prolonged

Next Nearest Neighborhoods under Periodic Boundary †

Irfan Siap1, Hasan Akin2, Selman Uguz3,∗

1 Department of Mathematics, Arts and Science Faculty, Yıldız Technical University, Istanbul, 34210,

Turkey
2 Department of Mathematics, Faculty of Education, Zirve University, Gaziantep, 27260, Turkey
3 Department of Mathematics, Arts and Science Faculty, Harran University, Sanliurfa, 63120,

Turkey

Abstract. 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 bound-

ary condition over the ternary field (Z3). 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.

2010 Mathematics Subject Classifications: 37B15; 15A04.

Key Words and Phrases: Cellular automata, Rule matrix, Matrix algebra, Periodic Boundary Condi-

tion, error correcting codes

1. Introduction

Cellular automata (CAs for brevity), introduced by Ulam and von Neumann [21] in the

early 1950’s, have been studied by many workers. Von Neumann [21] showed that a cellular

automaton (CA) can be universal. However, due to its complexity, von Neumann rules were

never implemented on a computer. In the beginning of the eighties, Stephen Wolfram [22]

has studied in much detail a family of simple one-dimensional (1-D) CAs rules and showed

that even these simplest rules are capable of emulating complex behavior.

†This paper was partially presented at 2nd WORLD CONFERENCE on INFORMATION TECHNOLOGY - WCIT-2011,

November 23-26, 2011 Antalya, Turkey.
∗Corresponding author.

Email addresses: irfansiap@hotmail.com (I. Siap), akinhasan25@gmail.com (H. Akin),

selmanuguz@gmail.com (S. Uguz)

http://www.ejpam.com 315 c© 2013 EJPAM All rights reserved.



I. Siap, H. Akin, S. Uguz / Eur. J. Pure Appl. Math, 6 (2013), 315-334 316

Due to various applications of CAs in many disciplines (e.g., mathematics, physics, com-

puter science, chemistry and so on) with different purposes (e.g., simulation of natural phe-

nomena, pseudo-random number generation, image processing, analysis of universal model

of computations, cryptography, coding theory, complexity), the study of CAs has received re-

markable attention in the last few years [1–3, 5, 9, 10, 12, 13]. The set of papers [1–3],

the entropies of 1-D CAs have been investigated. Most of the work for CAs is done for one

dimensional case [11]. Lately, two-dimensional (2-D) CA has found applications in traffic

modelling. For instance multi-value (including ternary) cellular automaton models for traffic

flow are proposed in [17]. CAs have found applications in Cryptography [5], recently multi

state CAs have also found applications on Cryptography [16] and especially two dimensional

CA has been proposed for multisecret sharing scheme for colored images [4]. The set of pa-

pers [6, 10, 12, 13, 18, 20] deals with the behavior of the linear 2-D CAs over binary fields

(Z2) by using matrix algebras setting. Das [9] has studied the characterization of 1-D CAs

by means of matrix algebra. Inokuchi et al. [11] have investigated the behaviors of 1-D CA

generated by the local rule 156. Khan et al. [12] developed an analytical tool to study all the

nearest neighborhood 2-D CA linear transformations. They proposed a new rule convention to

divide the 2-D linear CAs and tried to study the characterization of that 2-D CAs with different

rules.

In [18], we have characterized a 2-D finite CA by using matrix algebra built on Z3. Also,

we have analyzed some results about the rule numbers 2460N and 2460P. In [19], we have

obtained necessary and sufficient conditions for the existence of Garden of Eden configura-

tions for 2-D ternary CAs. Also by making use of the matrix representation of 2-D CAs, we

have provided an algorithm to obtain the number of Garden of Eden configurations for the

2-D CA defined by rule 2460N.

In present paper, we define the 2-D CAs generated by new local rules so called the nearest

neighborhoods and prolonged next nearest neighborhoods over the field Z3 under Periodic

Boundary Condition (briefly, PBC). We obtain recurrence equations to compute the rank of

the rule matrix related to this 2-D CA. We present an application to error correcting codes.

The rest of this paper is organized as follows. In Section 2 we give basic definitions and

notations. In Section 3 we obtain the rule matrix corresponding to a 2-D finite CA with PBC

generated by the local rule N PNN over the field Z3. In Section 4 we study the rank of the rule

matrix. In Section 5 we give some examples of the main theorem. We also give an algorithm

and apply it to a 2-D CA with larger order. In the last Section, we present an application to

error correcting codes and we conclude the paper.

2. Preliminaries

In this section, we introduce 2-D CAs over the field Z3 by using some local rules. We recall

the definition of a CA. We consider the 2-dimensional integer lattice Z2 and the configuration

space Ω = {0,1,2}Z
2

with elements

σ : Z2→ {0,1,2}.



I. Siap, H. Akin, S. Uguz / Eur. J. Pure Appl. Math, 6 (2013), 315-334 317

The value of σ at a point v ∈ Z2 will be denoted by σv. Let u1, . . . ,us ∈ Z
2 be a finite set of

distinct vectors and F : {0,1,2}s→ {0,1,2} be a function. A CA with local rule F is defined as

a pair (Ω, TF ), where the global transition map UF : Ω→ Ω is given by

(UFσ)v = F(σv+u1
, . . . ,σv+us

), v ∈ Z2.

The function F is called local rule. The space Ω is assumed to be equipped with a (metrizable)

Tychonoff topology; it is easily seen that the global transition map UF introduced above is

continuous in this topology.

The 2-D finite CA consists of m× n cells arranged in m rows and n columns, where each

cell takes one of the values of 0, 1 or 2. A configuration of the system is an assignment

of states to all the cells. Every configuration determines a next configuration via a linear

transition rule that is local in the sense that the state of a cell at time (t + 1) depends only on

the states of some of its neighbors at time t using modulo 3. For 2D CA nearest neighbors,

there are nine cells arranged in a 3×3 matrix centering that particular cell (see [6, 9, 10] for

the details). For 2-D CA there are some classic types of neighborhoods, but in this work only

we restrict ourselves to the nearest neighborhood and prolonged next nearest neighborhood

(briefly, NPNN). So, we can define the (t + 1)th state of the (i, j)th cell as follows;

x
(t+1)

(i, j)
=ax

(t)

(i−1, j)
+ bx

(t)

(i, j+1)
+ cx

(t)

(i+1, j)
+ d x

(t)

(i, j−1)
+ ex

(t)

(i−2, j)
+ f x

(t)

(i, j+2)

+ g x
(t)

(i+2, j)
+ hx

(t)

(i, j−2)
(mod 3), (1)

where a, b, c, d, e, f , g,h ∈ Z∗3 = {1,2}. The dependence will be restricted to the case of being

zero or nonzero, in other words if the coefficients in (1) equal to 1 or 2, then this case will

be assumed to be the same. This approach is adopted in this paper though these cases may

be further distinguished. The linear combination of the neighboring cells on which each cell

value is dependent is called the rule number of the 2-D CA over the field Z3.

Regarding the neighborhood of the extreme cells, there exist two approaches.

• A Periodic Boundary CA is the one which the extreme cells are adjacent to each other.

• A Null Boundary CA is the one which the extreme cells are connected to 0-state.

Let us define the 2-D CA generated by the local rule N PNN with PBC (briefly N PNN P). In

sequel, for simplicity we will assume that N PNN P ≡ R. The 2-D CA UR : Ω→ Ω

(UR x)
(t)

(i, j)
=ax

(t)

(i−1, j)
+ bx

(t)

(i, j+1)
+ cx

(t)

(i+1, j)
+ d x

(t)

(i, j−1)
+ ex

(t)

(i−2, j)
+ f x

(t)

(i, j+2)

+ g x
(t)

(i+2, j)
+ hx

(t)

(i, j−2)
(mod 3),

=x
(t+1)

(i, j)
. (2)

In this paper, we will only consider a 2-D finite CA generated by the rule N PNN with PBC. It is

well known that these CAs are discrete dynamical systems formed by a finite two-dimensional



I. Siap, H. Akin, S. Uguz / Eur. J. Pure Appl. Math, 6 (2013), 315-334 318

array m× n composed by identical objects called cells. Let Φ : Mm×n(Z3)→ Z
mn
3 . Φ takes the

t th state [X t] given by




x11 x12 · · · x1n

x21 x22 · · · x2n
...

... · · ·
...

xm1 xm2 · · · xmn



−→ (x11, x12, . . . , x1n, . . . , xm1, . . . , xmn)

T , (3)

where T is the transpose of the matrix. Therefore, the local rules will be assumed to act on

Z
mn
3 rather than Φ : Mm×n(Z3).

Suppose binary information matrix is [X t]m×n, of order m× n:

[X t]m×n =




x
(t)

11 . . . x
(t)

1n
...

. . .
...

x
(t)

m1 . . . x (t)mn




is called the configuration of the 2-D finite CA at time t.

From (3), we can define as follows;

(TR)mn×mn.




x
(t)

11
...

x
(t)

1n
...

x
(t)

m1
...

x (t)mn




=




x
(t+1)
11

...

x
(t+1)
1n

...

x
(t+1)
m1
...

x (t+1)
mn




.

where x
(t+1)

i, j
is defined as Eq. (1). i denotes the i th row of the information matrix [X t]m×n

and j denotes the j th column of the matrix [X t]m×n. The matrix (TR)mn×mn is called the rule

matrix with respect to the 2-D finite CAm×n with rule N PNN P (see [6] for details). We can

briefly show as

[TR]mn×mn




X T
1

X T
2

X T
3
...

X T
m




mn×1

=




Y T
1

Y T
2

Y T
3
...

Y T
m




mn×1

For example, for i = j = 3

x
(t+1)
33 = ax

(t)

23 + bx
(t)

34 + cx
(t)

43 + d x
(t)

32 + ex
(t)

13 + f x
(t)

35 + g x
(t)

53 + hx
(t)

31 (mod 3).



I.
S

ia
p
,

H
.

A
k
in

,
S

.
U

g
u

z
/

E
u

r.
J.

P
u

re
A

p
p
l.

M
a
th

,
6

(2
0

1
3

),
3

1
5

-3
3

4
3

1
9

Table 1: An information matrix of order 5× 5 with PBC.

x(i+1, j+1) x(i+1, j+2) x(i+1, j−2) x(i+1, j−1) x(i+1, j) x(i+1, j+1) x(i+1, j+2) x(i+1, j−2) x(i+1, j−1)

x(i+2, j+1) x(i+2, j+2) x(i+2, j−2) x(i+2, j−1) x(i+2, j) x(i+2, j+1) x(i+2, j+2) x(i+2, j−2) x(i+2, j−1)

x(i−2, j+1) x(i−2, j+2) x(i−2, j−2) x(i−2, j−1) x(i−2, j) x(i−2, j+1) x(i−2, j+2) x(i−2, j−2) x(i−2, j−1)

x(i−1, j+1) x(i−1, j+2) x(i−1, j−2) x(i−1, j−1) x(i−1, j) x(i−1, j+1) x(i−1, j+2) x(i−1, j−2) x(i−1, j−1)

x(i, j+1) x(i, j+2) x(i, j−2) x(i, j−1) x(i, j) x(i, j+1) x(i, j+2) x(i, j−2) x(i, j−1)

x(i+1, j+1) x(i+1, j+2) x(i+1, j−2) x(i+1, j−1) x(i+1, j) x(i+1, j+1) x(i+1, j+2) x(i+1, j−2) x(i+1, j−1)

x(i+2, j+1) x(i+2, j+2) x(i+2, j−2) x(i+2, j−1) x(i+2, j) x(i+2, j+1) x(i+2, j+2) x(i+2, j−2) x(i+2, j−1)

x(i−2, j+1) x(i−2, j+2) x(i−2, j−2) x(i−2, j−1) x(i−2, j) x(i−2, j+1) x(i−2, j+2) x(i−2, j−2) x(i−2, j−1)

x(i−1, j+1) x(i−1, j+2) x(i−1, j−2) x(i−1, j−1) x(i−1, j) x(i−1, j+1) x(i−1, j+2) x(i−1, j−2) x(i−1, j−1)



I. Siap, H. Akin, S. Uguz / Eur. J. Pure Appl. Math, 6 (2013), 315-334 320

The conventional method of defining a rule number for a linear rule in 2-D CA with PBC

can be explained in Table 1 where x(k,h) ∈ Z3 (k,h ≥ 3) and x(i, j) is i th row and j th column

entry of the information matrix [X t]5×5.

3. Rule Matrix of 2-D Finite CA with Rule N PNN P

In this section, we determine the rule matrix corresponding to a 2-D finite CA with PBC

generated by the local rule N PNN P over the field Z3. We want to obtain the transformation

Ψ such that Ψ operating on the current information matrix (state) [X ]m×n of dimension m×n

generates the next information matrix [Y ]m×n = [X
′]m×n.

Theorem 1. Let a, b, c, d, e, f , g,h ∈ Z∗3, m ≥ 5 and n ≥ 5. Then, the rule matrix of TR from

Z
mn
3 to Zmn

3 which takes the t th state [X t] (as identified in (3)) to the (t+1)- state [X t+1] = [Y ]

is given by:

(TR)mn×mn =




S cI g I 0 · · · · · · eI aI

aI S cI g I · · · · · · 0 eI

eI aI S cI g I · · · 0 0

0 eI aI S · · · · · · 0 0
...

...
...

...
...

...
...

...

0 · · · 0 eI aI S cI g I

g I · · · · · · 0 eI aI S cI

cI g I · · · · · · 0 eI aI S




mn×mn

(4)

where each submatrix is of order n× n, and

Sn×n =




0 b f 0 0 0 · · · h d

d 0 b f 0 0 · · · 0 h

h d 0 b f 0 · · · 0 0

0 h d 0 b f 0 · · · 0
...

...
...

...
...

...
...

...
...

f · · · · · · · · · 0 h d 0 b

b f · · · · · · · · · 0 h d 0




n×n

. (5)

Proof. In order to determine the rule matrix TR we need to determine the action of TR on

the bases vectors. First, we consider the linear transformation Ψ from m× n matrix space to

itself. Next, we relate the transformation Ψ with rule matrix TR. Let ei j denote the matrix of

size m× n where the (i, j) position is equal to one and the rest of the entries equal to zero. It

is well known that these vectors give the standard basis for this space (see [14]). Given ei j ,

the image of ei j which is Ψ(ei j) is related to the four nearest neighbors and four prolonged

next nearest neighbors. Ψ(ei j) equals to a linear combination of its eight neighbors in the

following way:

Ψ(ei j) = f ei, j−2+ bei, j−1+ dei, j+1+ hei, j+2+ gei−2, j + cei−1, j + aei+1, j + eei+2, j



I. Siap, H. Akin, S. Uguz / Eur. J. Pure Appl. Math, 6 (2013), 315-334 321

with a care on the bordering components of the matrix. Due to the neighboring relations that

govern the rule, especially observing the bordering relations as mentioned above, we obtain

the following:

Ψ(e1,1) = f e1,n−1+ be1,n+ de1,2+ he1,3+ gem−1,1+ cem,1+ ae2,1+ ee3,1,

Ψ(e1,2) = f e1,n+ be1,1+ de1,3+ he1,4+ gem−1,2+ cem,2+ ae2,2+ ee3,2,

Ψ(e1,l) = f e1,l−2+ be1,l−1+ de1,l+1+ hel, j+2+

gem−1,l + cem,l + ae2,l + ee3,l , 3≤ l ≤ n− 2

Ψ(e1,n−1) = f e1,n−3+ be1,n−2+ de1,n+ he1,1+ gem−1,n−1+ cem,n−1+ ae2,n−1+ ee3,n−1,

Ψ(e1,n) = f e1,n−2+ be1,n−1+ de1,1+ he1,2+ gem−1,n+ cem,n + ae2,n+ ee3,n.

Now, let us apply to Ψ the second row of information matrix

Ψ(e2,1) = f e2,n−1+ be2,n+ de2,2+ he2,3+ gem,1+ ce1,1+ ae3,1+ ee4,1,

Ψ(e2,2) = f e2,n+ be2,1+ de2,3+ he2,4+ gem,2+ ce1,2+ ae3,2+ ee4,2,

Ψ(e2,l) = f e2,l−2+ be2,l−1+ de2,l+1+ he2, j+2

+ gem,l + ce1,l + ae3,l + ee4,l , 3≤ l ≤ n− 2

Ψ(e2,n−1) = f e2,n−3+ be2,n−2+ de2,n+ he2,1+ gem,n−1+ ce1,n−1+ ae3,n−1+ ee4,n−1,

Ψ(e2,n) = f e2,n−2+ be2,n−1+ de2,1+ he2,2+ gem,n+ ce1,n+ ae3,n+ ee4,n.

For 2≤ k ≤ m− 1, we have

Ψ(ek,1) = f ek,n−1+ bek,1+ dek,2+ hek,3+ gek−2,1+ cek−1,1+ aek+1,1+ eek+2,1,

Ψ(ek,2) = f ek,n+ bek,n+ dek,3+ hek,4+ gek−2,2+ cek−1,2+ aek+1,2+ eek+2,2,

Ψ(ek,l) = f ek,l−2+ bek,l−1+ dek,l+1+ hek, j+2

+ gek−2,l + cek−1,l + aek+1,l + eek+2,l , 3≤ l ≤ n− 2

Ψ(ek,n−1) = f ek,n−3+ bek,n−2+ dek,n+ hek,1+ gek−2,n−1+ cek−1,n−1+ aek+1,n−1+ eek+2,n−1,

Ψ(ek,n) = f ek,n−2+ bek,n−1+ dek,1+ hek,2+ gek−2,n+ cek−1,n+ aek+1,n+ eek+2,n.

Ψ(em−1,1) = f em−1,n−1+ bem−1,n+ dem−1,2+ hem−1,3+ gem−3,1+ cem−2,1+ aem,1+ ee1,1,

Ψ(em−1,2) = f em−1,n+ bem−1,1+ dem−1,3+ hem−1,4+ gem−3,2+ cem−2,2+ aem,2+ ee1,2,

Ψ(em−1,l) = f em−1,l−2+ bem−1,l−1+ dem−1,l+1+ hem−1,l+2

+ gem−3,l + cem−2,l + aem,l + ee1,l , 3≤ l ≤ n− 2

Ψ(em−1,n−1) = f em−1,n−3+ bem−1,n−2+ dem−1,n+ hem−1,1+ gem−3,n−1+ cem−2,n−1+ aem,n−1+ ee1,n−1,

Ψ(em−1,n) = f em−1,n−2+ bem−1,n−1+ dem−1,1+ hem−1,2+ gem−3,n+ cem−2,n+ aem,n+ ee1,n.

Finally, we also have

Ψ(em,1) = f em,n−1+ bem,n+ dem,2+ hem,3+ gem−2,1+ cem−1,1+ ae1,1+ ee2,1,

Ψ(em,2) = f em,n+ bem,1+ dem,3+ hem,4+ gem−2,2+ cem−1,2+ ae1,2+ ee2,2,



I. Siap, H. Akin, S. Uguz / Eur. J. Pure Appl. Math, 6 (2013), 315-334 322

Ψ(em,l) = f em,l−2+ bem,l−1+ dem,l+1+ hem,l+2

+ gem−2,l + cem−1,l + ae1,l + ee2,l , 3≤ l ≤ n− 2

Ψ(em,n−1) = f em,n−3+ bem,n−2+ dem,n+ hem,1+ gem−2,n−1+ cem−1,n−1+ ae1,n−1+ ee2,n−1,

Ψ(em,n) = f em,n−2+ bem,n−1+ dem,1+ hem,2+ gem−2,n+ cem−1,n+ ae1,n+ ee2,n.

Now, let Ei be the column vector in Zmn
3 where all entries equal to zero expect the entry

positioned at i which equals to one. These vectors also give the standard basis of the space

Z
mn
3 . The transition from the matrix space basis to the standard basis of Zmn

3 is given by

Φ(ei j) = E(i−1)n+ j ,

where 1≤ i ≤ m and 1≤ j ≤ n.

In order to determine the columns of the rule matrix TR we maintain the following method:

Φ(Ψ(ei j)) =Φ( f ei, j−2+ bei, j−1+ dei, j+1+ hei, j+2+ gei−2, j + cei−1, j + aei+1, j + eei+2, j)

= f Φ(ei, j−2) + bΦ(ei, j−1) + dΦ(ei, j+1) + hΦ(ei, j+2)

+ gΦ(ei−2, j) + cΦ(ei−1, j) + aΦ(ei+1, j) + eΦ(ei+2, j)

= f E(i−1)n+ j−2+ bE(i−1)n+ j−1+ dE(i−1)n+ j+1+ hE(i−1)n+ j+2

+ gE(i−3)n+ j + cE(i−2)n+ j + aEin+ j) + eE(i+1)n+ j (6)

which gives the ((i− 1)n+ j)th column of the rule matrix TR. For instance,

dE2+ hE3+ f En−1+ bEn+ aEn+1+ eE2n+1+ gE(m−2)n+1+ cE(m−1)n+2

which gives the first column of the rule matrix TR. Further,

bE1+ dE3+ hE4+ f En+ aEn+2+ eE2n+2+ gE(m−2)n+2+ cE(m−1)n+2

which gives the second column of the rule matrix TR.

Similarly one can obtain the last column of the rule matrix as following:

aEn+ eE2n+ gE(m−2)n+ cE(m−1)n+ dE(m−1)n+1+ hE(m−1)n+2+ f Emn−2+ bEmn−1.

Inductively, we can similarly obtain the rest of the columns.

Example 1. If we take m = 5 and n = 5, then we get the representation matrix TR of order

25× 25. We consider a configuration of size 5× 5 with PBC.

Table 2: An information matrix of order 5× 5 with PBC.

x44 x45 x41 x42 x43 x44 x45 x41 x42

x54 x55 x51 x52 x53 x54 x55 x51 x52

x14 x15 x11 x12 x13 x14 x15 x11 x12

x24 x25 x21 x22 x23 x24 x25 x21 x22

x34 x35 x31 x32 x33 x34 x35 x31) x32

x44 x45 x41 x42 x43 x44 x45 x41 x42

x54 x55 x51 x52 x53 x54 x55 x51 x52

x14 x15 x11 x12 x13 x14 x15 x11 x12

x24 x25 x21 x22 x23 x24 x25 x21 x22



I. Siap, H. Akin, S. Uguz / Eur. J. Pure Appl. Math, 6 (2013), 315-334 323

Now, we apply the local rule in Eq. (1) to all cells of the first row of information matrix 5×5,

then we obtain the first block row of rule matrix TR and next apply the rule R to all the cells of

the second row of information matrix 5× 5, we obtain the second block row of rule matrix TR.

Similarly, we can obtain the other block rows of rule matrix TR.

From Theorem 1, one can get the matrix as following:

(TR)25×25 =




S cI5 g I5 eI5 aI5

aI5 S cI5 g I5 eI5

eI5 aI5 S Ic5 g I5

g I5 eI5 aI5 S cI5

cI5 g I5 eI5 aI5 S




,

where each submatrix is of order 5× 5, and S5×5 =




0 b f h d

d 0 b f h

h d 0 b f

f h d 0 b

b f h d 0




5×5

.

4. Characterization of 2-D Finite CA with Rule N PNN P

The dimension of the kernel of a map gives a clue to draw the state transition diagram

(see [6, 10, 12]). In order to determine dimension of the kernel of a 2-D CA, we need to

study the rank of the rule matrix
�

TR

�
mn×mn. The following theorem presents an algorithm

for computing the rank:

Let Ti denote the ith row and Ti[ j] denote the j the entry of the ith row of matrix T

respectively. By definition, we have

T1 =[S, cI , g I , 0, 0, . . . , 0, eI , aI] ∈ Mn×n(Z3)
m

T2 =[aI ,S, cI , g I , 0, 0, . . . , 0, eI] ∈ Mn×n(Z3)
m

T3 =[eI , aI ,S, cI , g I , 0, 0, . . . , 0] ∈ Mn×n(Z3)
m

T4 =[g I , 0, 0, 0, . . . , eI , aI ,S, cI] ∈ Mn×n(Z3)
m

T5 =[cI , g I , 0, 0, . . . , 0, eI , aI ,S] ∈ Mn×n(Z3)
m.

Define the σ map as follows:

σ :Mn×n(Z3)
m→ Mn×n(Z3)

m

σ([A1,A2,A3, . . . ,Am−1,Am]) = [0n,A1,A2,A3, . . . ,Am−1],

where 0n represents the zero square matrix of order n. Further, if A= [A1,A2,A3, . . . ,Am−1,Am],

then A[i] = Ai represents the ith entry of A. Further, B[A1,A2, . . . ,Am] = [BA1, BA2, . . . , BAm].

Theorem 2. Let the rule matrix (TR)mn×mn be given in Theorem 1 and m≥ 5. Assume that

T
(1)
1 =T1,



I. Siap, H. Akin, S. Uguz / Eur. J. Pure Appl. Math, 6 (2013), 315-334 324

T
(k+1)
1 =−

1

e
T
(k)

1 [k]σ
(k−1)(T3) + T

(k)

1 for 1≤ k ≤ m− 4,

T
(1)
2 =T2,

T
(k+1)
2 =−

1

e
T
(k)

2 [k]σ
(k−1)(T3) + T

(k)

2 for 1≤ k ≤ m− 4

T
(1)
4 =T4,

T
(k+1)
4 =−

1

e
T
(k)
4 [k]σ

(k−1)(T3) + T
(k)
4 for 1≤ k ≤ m− 4,

T
(1)
5 =T5,

T
(k+1)
5 =−

1

e
T
(k)
5 [k]σ

(k−1)(T3) + T
(k)
5 for 1≤ k ≤ m− 4.

If

B =




T
(m−3)
1 [m− 3] T

(m−3)
1 [m− 2] T

(m−3)
1 [m− 1] T

(m−3)
1 [m]

T
(m−3)
2 [m− 3] T

(m−3)
2 [m− 2] T

(m−3)
2 [m− 1] T

(m−3)
2 [m]

T
(m−3)
4 [m− 3] T

(m−3)
4 [m− 2] T

(m−3)
4 [m− 1] T

(m−3)
4 [m]

T
(m−3)
5 [m− 3] T

(m−3)
5 [m− 2] T

(m−3)
5 [m− 1] T

(m−3)
5 [m]




is a 4× 4 block matrix consisting of square sub matrices each of order n, then

rank((TR)mn×mn) = (m− 4) · n+ rank(B).

Proof. We apply induction on m. First, we observe that the submatrix consisting of all

rows except the first, the second and last two rows is in the upper triangular form and it has

a full rank which is (m − 4) · n. Now, if we multiply the third row T3 by −1

e
T
(1)
1 [1]T3[1]

and add this to T
(1)
1 [1], then the first entry of the new first row T

(2)
1 becomes zero. So we

replace the first row by T
(2)
1 = −1

e
T
(1)
1 [1]σ

(0)(T3) + T
(1)
1 . Next, if we multiply the fourth

row σ(1)(T3) by −1

e
T
(1)
1 [2]σ

(1)(T3)[2] and add it to T
(1)
1 [2] the second entry of the new first

row T
(3)
1 becomes zero. Inductively, after m − 4 steps, the only nonzero entries of T

(m−3)
1

are T
(m−3)
1 [m − 3], T

(m−3)
1 [m − 2], T

(m−3)
1 [m − 1] and T

(m−3)
1 [m]. Similarly, by applying

elementary row operations to the second row, the only non zero entries of the second row are

T
(m−3)
2 [m− 3], T

(m−3)
2 [m− 2], T

(m−3)
2 [m− 1] and T

(m−3)
2 [m] (see (7)). Same procedure is

applied to the last two rows. After applying the elementary row operations mentioned above,



I. Siap, H. Akin, S. Uguz / Eur. J. Pure Appl. Math, 6 (2013), 315-334 325

we get

T ′R =




0 0 0 0 · · · 0

0 0 0 0 · · · 0

0 0 0 0 · · · 0 B

0 0 0 0 · · · 0

eI aI S cI g I · · · 0 0 0 0

0 eI aI S · · · · · · 0 0 0 0
...

...
...

...
...

...
...

...

0 · · · 0 eI aI S cI g I 0 0

0 · · · · · · 0 eI aI S cI g I 0

0 0 · · · · · · 0 eI aI S cI g I




=

�
0 B

C D

�
. (7)

The left lower block of C in (7) has full rank (m− 4) · n. The rank of the matrix in (7)

equals to (m− 4) · n+ rank(B).

A straightforward corollary which gives a lower and an upper bound for the rank of the

rule matrix (TR)mn×mn is presented below.

Corollary 1. Let the rule matrix (TR)mn×mn be defined as in Theorem 1. Then,

(m− 4) · n≤ rank((TR)mn×mn)≤ m · n.

5. Examples

In this section, we give some applications of the main theorem. We also give an algorithm

and apply it to a 2-D CA with larger order.

Example 2. Let n = 5, m = 5 and a = 2, b = 2, c = 1, d = 1, f = 2,h = 1, e = 1, g = 2. Then

we get

(TR)25×25 =




S I5 2I5 I5 2I5

2I5 S I5 2I5 I5

I5 2I5 S I5 2I5

2I5 I5 2I5 S I5

I5 2I5 I5 2I5 S




,

S =




0 2 2 1 1

1 0 2 2 1

1 1 0 2 2

2 1 1 0 2

2 2 1 1 0




.



I. Siap, H. Akin, S. Uguz / Eur. J. Pure Appl. Math, 6 (2013), 315-334 326

Direct computation of the rank of (TR)25×25 gives 20. On the other hand, if we apply Theorem (2),

then we proceed in the following way:

T
(1)
1 =T1 = [S, I5, 2I5, I5, 2I5],

T
(2)
1 =−

1

e
T
(1)
1 [1]σ

(0)(T3) + T
(1)
1

=− S[I5, 2I5,S, I5, 2I5] + [S, I5, 2I5, I5, 2I5]

=[05,−2S + I5,−S2+ 2I5,−S + I5,−2S + 2I5],

T
(1)
2 =T2 = [2I5,S, I5, 2I5, I5],

T
(2)
2 =−

1

e
T
(1)
2 [1]σ

(0)(T3) + T
(1)
2

=− (2I5)[I5, 2I5,S, I5, 2I5] + [2I5,S, I5, 2I5, I5] = [05,S − I5,−2S + I5, 05, 05],

T
(1)
4 =T4 = [2I5, I5, 2I5,S, I5],

T
(2)
4 =−

1

e
T
(1)
4 [1]σ

(0)(T3) + T
(1)
4

=− 2I5[I5, 2I5,S, I5, 2I5] + [2I5, I5, 2I5,S, I5] = [05, 05,−2S + 2I5,S − 2I5, 05],

T
(1)
5 =T5 = [I5, 2I5, I5, 2I5,S],

T
(2)
5 =−

1

e
T
(1)
5 [1]σ

(0)(T3) + T
(1)
5

=− (I5)[I5, 2I5,S, I5, 2I5] + [I5, 2I5, I5, 2I5,S] = [05, 05,−S + I5, I5,S − 2I5],

Thus,

B =




T
(2)
1 [2] T

(2)
1 [3] T

(2)
1 [4] T

(2)
1 [5]

T
(2)
2 [2] T

(2)
2 [3] T

(2)
2 [4] T

(2)
2 [5]

T
(2)
4 [2] T

(2)
4 [3] T

(2)
4 [4] T

(2)
4 [5]

T
(2)
5 [2] T

(2)
5 [3] T

(2)
5 [4] T

(2)
5 [5]



=




−2S + I5 −S2+ 2I5 −S + I5 −2S + 2I5

S − I5 −2S + I5 05 05

05 −2S + 2I5 S − 2I5 05

05 −S + I5 I5 S − 2I5


 .

Hence, rank(B) = 15. Therefore, rank((TR)36×36) = (m−4)·n+rank(B) = (5−4)·5+15= 20.

As a result, the CA is irreversible.

Example 3. Let n = 6, m = 6 and a = 2, b = 2, c = 1, d = 1, f = 2,h = 1, e = 2, g = 1. Then

we have,

(TR)36×36 =




S I6 I6 06 2I6 2I6

2I6 S I6 I6 06 2I6

2I6 2I6 S I6 I6 06

06 2I6 2I6 S I6 I6

I6 06 2I6 2I6 S I6

I6 I6 06 2I6 2I6 S




,



I. Siap, H. Akin, S. Uguz / Eur. J. Pure Appl. Math, 6 (2013), 315-334 327

S =




0 2 2 0 1 1

1 0 2 2 0 1

1 1 0 2 2 0

0 1 1 0 2 2

2 0 1 1 0 2

2 2 0 1 1 0




.

Direct computation of the rank of (TR)36×36 gives 18. On the other hand, if we apply Theorem (2),

then we proceed in the following way:

T
(1)
1 =T1 = [S, I6, I6, 06, 2I6, 2I6],

T
(2)
1 =−

1

e
T
(1)
1 [1]σ

(0)(T3) + T
(1)
1

=− 2S[2I6, 2I6,S, I6, I6, 06] + [S, I6, I6, 06, 2I6, 2I6]

=[06,−S + I6,−2S2+ I6,−2S,−2S + 2I6, 2I6],

T
(3)
1 =−

1

e
T
(2)
1 [2]σ

(1)(T3) + T
(2)
1

=− 2(−S+ I6)[06, 2I6, 2I6,S, I6, I6] + [06,−S + I6,−2S2+ I6,−2S,−2S + 2I6, 2I6]

=[06, 06,−2S2+ S, 2S2− S, 06, 2S],

T
(1)
2 =T2 = [2I6,S, I6, I6, 06, 2I6],

T
(2)
2 =−

1

e
T
(1)
2 [1]σ

(0)(T3) + T
(1)
2

=− 2(2I6)[2I6, 2I6,S, I6, I6, 06] + [2I6,S, I6, I6, 06, 2I6]

=[06,S − 2I6,−S + I6, 06,−I6, 2I6],

T
(3)
2 =−

1

e
T
(2)
2 [2]σ

(1)(T3) + T
(2)
2

=− 2(S − 2I6)[06, 2I6, 2I6,S, I6, I6] + [06,S − 2I6,−S + I6, 06,−I6, 2I6]

=[06, 06,−2S,−2S2+ S,−2S,−2S],

T
(1)
4 =T4 = [I6, 06, 2I6, 2I6,S, I6],

T
(2)
4 =−

1

e
T
(1)
4 [1]σ

(0)(T3) + T
(1)
4

=− 2I6[2I6, 2I6,S, I6, I6, 06] + [I6, 06, 2I6, 2I6,S, I6]

=[06,−I6,−2S + 2I6, 06,S − 2I6, I6],

T
(3)
4 =−

1

e
T
(2)
4 [2]σ

(1)(T3) + T
(2)
4

=− 2(−I6)[06, 2I6, 2I6,S, I6, I6] + [06,−I6,−2S + 2I6, 06,S − 2I6, I6]

=[06, 06,−2S, 2S,S, 06],



I. Siap, H. Akin, S. Uguz / Eur. J. Pure Appl. Math, 6 (2013), 315-334 328

T
(1)
5 =T5 = [I6, I6, 06, 2I6, 2I6,S],

T
(2)
5 =−

1

e
T
(1)
5 [1]σ

(0)(T3) + T
(1)
5

=− 2(I6)[2I6, 2I6,S, I6, I6, 06] + [I6, I6, 06, 2I6, 2I6,S] = [06, 06,−2S, 06, 06,S],

T
(3)
5 =−

1

e
T
(2)
5 [2]σ

(1)(T3) + T
(2)
5

=− 2(06)[06, 2I6, 2I6,S, I6, I6] + [06, 06,−2S, 06, 06,S]

=[06, 06,−2S, 06, 06,S].

Thus we have

B =




T
(3)
1 [3] T

(3)
1 [4] T

(3)
1 [5] T

(3)
1 [6]

T
(3)
2 [3] T

(3)
2 [4] T

(3)
2 [5] T

(3)
2 [6]

T
(3)
4 [3] T

(3)
4 [4] T

(3)
4 [5] T

(3)
4 [6]

T
(3)
5 [3] T

(3)
5 [4] T

(3)
5 [5] T

(3)
5 [6]



=




−2S2+ S 2S2− S 06 2S

−2S −2S2+ S −2S −2S

−2S 2S S 06

−2S 06 06 S


 .

Hence, rank(B) = 6. Therefore, rank((TR)36×36) = (m− 4) · n+rank(B) = (6− 4) · 6+ 6= 18.

As a result, the CA is irreversible.

5.1. An Algorithm for Computing The Rank of (TR)mn×mn

Now we can summarize the method introduced above for computing the rank of the rule

matrix as follows:

Step 1. Determine respectively the first two rows T1 and T2 and the last two rows T4 and T5

which consists of block of matrices. Set T
(1)
1 = T1, T

(1)
2 = T2, T

(1)
4 = T4 and T

(1)
5 = T5.

Step 2. If m> n+1, compute the characteristic polynomial of S by applying Cayley-Hamilton

theorem [14].

Step 3. For 1≤ k ≤ m− 4, compute

T
(k+1)
1 =−

1

e
T
(k)

1 [k]σ
(k−1)(T3) + T

(k)

1 ,

T
(k+1)
2 =−

1

e
T
(k)

2 [k]σ
(k−1)(T3) + T

(k)

2 ,

T
(k+1)
4 =−

1

e
T
(k)
4 [k]σ

(k−1)(T3) + T
(k)
4 ,

T
(k+1)
5 =−

1

e
T
(k)
5 [k]σ

(k−1)(T3) + T
(k)
5 .

Hence, determine the matrices

T
(m−3)
1 [m−3], . . . , T

(m−3)
1 [m], T

(m−3)
2 [m−3], . . . , T

(m−3)
2 [m], T

(m−3)
4 [m−3], . . . , T

(m−3)
4 [m]

and T
(m−3)
5 [m− 3], . . . , T

(m−3)
5 [m].



I. Siap, H. Akin, S. Uguz / Eur. J. Pure Appl. Math, 6 (2013), 315-334 329

If m> n+1, in every iteration while computing T
(k)

i
(i = 1,2,4,5), since S is a matrix,

arithmetic can be carried out modulo the characteristic polynomial of S which saves

reasonable time.

Step 4. Compute the rank of

B =




T
(m−3)
1 [m− 3] T

(m−3)
1 [m− 2] T

(m−3)
1 [m− 1] T

(m−3)
1 [m]

T
(m−3)
2 [m− 3] T

(m−3)
2 [m− 2] T

(m−3)
2 [m− 1] T

(m−3)
2 [m]

T
(m−3)
4 [m− 3] T

(m−3)
4 [m− 2] T

(m−3)
4 [m− 1] T

(m−3)
4 [m]

T
(m−3)
5 [m− 3] T

(m−3)
5 [m− 2] T

(m−3)
5 [m− 1] T

(m−3)
5 [m]




Therefore, rank((TR)mn×mn) = (m− 4) · n+ rank(B).

Here we give an example that makes use of the algorithm introduced above.

Example 4. Let n = 6, m = 1000 and a = 2, b = 1, c = 1, d = 1, f = 2,h = 2, e = 2, g = 1.

Hence, the representation matrix of this two dimensional cellular automata is of size 6000×6000.

In order to compute its rank, we apply the algorithm:

Step 1. We determine respectively the first two rows T1 and T2 and the last two rows T4 and T5

which consists of block of matrices. Set T
(1)
1 = T1, T

(1)
2 = T2, T

(1)
4 = T4 and T

(1)
5 = T5.

Step 2. Since m> n+ 1, the characteristic polynomial of S charpol y(S) = S6+ S3. So, in each

computational step we apply the Cayley-Hamilton theorem [14] to reduce the algebra

dramatically.

Step 3. By applying the reduction formula we get the rows of matrix B which are given in the

next step.

Step 4. So

B =




2S + 2S2 2S2+ 1 2S2+ S3 S4+ S + 2S2+ 2

S3+ 2+ 2S2 2S + 2S2 S3+ 2S4+ 2S + 1 2S3+ S4+ S

2S3+ S4+ S S4+ S + 2S2+ 2 S4+ 2S + S2+ 2S5 2S3+ S4+ S + 1

S3+ 2S4+ 2S + 1 2S2+ S3 2S + S5+ 2S2+ 2 S4+ 2S + S2+ 2S5


 .

Therefore, rank(B) = 18 and

rank((TR)mn×mn) = (m− 4) · n+ rank(B) = (996) · 6+ 18= 5994.

P.S. In Example 3, running these four algorithms for m = 1000 and n = 6 took approxi-

mately 522 seconds in an ordinary computer (Intel Core DuoCPU, 1.6GHZ, 1GB RAM).

6. Bit Error Correcting-Detecting Code Based On Nonsingular Transition Matrix

2D Cellular Automata

One Dimensional Cellular Automata based bit error correcting codes (ECC) proposed by

Chaudhuri et al. [8] in 1994 (see [7]). They studied CA based ECC over binary fields. In this



I. Siap, H. Akin, S. Uguz / Eur. J. Pure Appl. Math, 6 (2013), 315-334 330

section, we extend CA based bit error correcting code (CA-ECC) over ternary fields. CA based

bit error correcting codes have two main advantages if compared to standard linear coding.

The first advantage is that if errors occur only in the information or in check bits, decoding is

very simple and fast. Even in the case where the errors are in both information part and check

part the decoding steps are less than the classical syndrome decoding method. The second

advantage is that the structure of cellular automata allows parallel computing which leads to

faster computations and simple hardware implementations.

Now, we present some basics of error correcting codes. Further and more detailed in-

formation on this topic can be found in [15]. It is well-known that V = Zn
3 is a Z3-vector

space.

Definition 1. A subspace C of V is called a linear code of length n. The matrix with rows

consisting of the basis of C is called a generator matrix of the code. The elements of C are called

codewords.

Error correcting codes are applied in digital media. An information is encoded in order to

be able to detect errors or even correct them. An information of length k is encoded to an n

tuple an regarded as an element (codeword) of C . After the transmission process if a linear

code can detect and correct one error then the code is called one error correcting code. The

number of nonzero entries of a vector v in V is called the Hamming weight of v. The smallest

nonzero weight among all codewords of a linear code C is called the minimum Hamming

weight of C . A linear code C of length n, dimension k and minimum Hamming weight d

is represented by [n, k, d]. For a detailed information the reader can refer to [15]. These

three parameters play an important role in error correcting codes. Especially the minimum

Hamming weight of a code is is very crucial.

Theorem 3. [15] If C is a linear code with minimum Hamming weight d, then C can correct up

to b d−1

2
c errors.

Let T be n×n nonsingular transition matrix of 2D-cellular automata with N PNN . Suppose

that there exists 1≤ k ≤ n, k ∈ Z+ such that G =
�

In|T
k
�

(In, n×n identity matrix) generates

a linear code that corrects at least one error.

6.1. Encoding

Let I =
�
i1, i2, . . . , in
�
∈ Zn

3 be information bits, where n is the rank of nonsingular tran-

sition matrix. Then CW =
�

I , T k [I]
�
=
�
i1, i2, . . . , in, cn+1, cn+2, . . . , c2n

�
is a code word

(C = T k [I] =
�
cn+1, cn+2, . . . , c2n

�
is the check bits).

Now, we give a decoding scheme for CA based single bit error correcting code which is an

extension from binary [8] to ternary case.

6.2. Decoding

Let CW ′ =
�

I ′, T k [I]
�
=
�

i′1, i′2, . . . , i′n, c′n+1, c′n+2, . . . , c′2n

�
be received word, then we com-

pute syndrome vector as follows:

S = 2T k
�

I ′
�
⊕ C ′.



I. Siap, H. Akin, S. Uguz / Eur. J. Pure Appl. Math, 6 (2013), 315-334 331

Case 1. Let all errors occur in the information bits, then the syndrome of the information part

is

Sn = 2T k
�

I ′
�
⊕ C ′ and T−k
�

Sn

�
is error vector of information part. In this case the

syndrome vector of check part Sc is all zero vector. Then, the error vector is

E =
�

T−k
�

Sn

�
,Sc

�
=
�

T−k
�

Sn

�
, 00 . . . 0
�

Case 2. Let all errors occur in the check part, then, the syndrome of check part (at the same

time error vector of check part) is

Sc = T k
�

I ′
�
⊕ 2C ′.In this case the syndrome vector of information part Sn is all zero

vector, then the error vector is

E =
�

T−k
�

Sn

�
,Sc

�
=
�

00 . . . 0, T k
�

I ′
�
⊕ 2C ′
�

.

Case 3. Both information and check parts are in error. Then, we take Sc all possible error

vectors and execute decoding Cases 1 and 2.

Now we give an example that illustrates the algorithm proposed above:

Example 5. Let us take the following transition matrix (TR)25×25 =




S I5 2I5 I5 2I5

2I5 S I5 2I5 I5

I5 2I5 S I5 2I5

2I5 I5 2I5 S I5

I5 2I5 I5 2I5 S




,

where S =




0 1 2 1 1

1 0 1 2 1

1 1 0 1 2

2 1 1 0 1

1 2 1 1 0




. For k = 2, G =
�

I25|(TR)
2
25×25

�
generates

C → [50,25,10]3− code, and d (C) = 10 then C can correct 4 errors.

Let I = 1111111111222222222222222 ∈ Z25
3 be a word. Then we generate check bits

C = (TR)
2
25×25 [I] = 1111100000000001111100000.

CW =
�

I , (TR)
2
25×25 [I]
�
= 11111111112222222222222221111100000000001111100000

∈ Z50
3 .

Case 1. Four errors occur in the information bits. Let the received word be

CW ′ =Ö00001111112222222222222221111100000000001111100000=
�

I ′|C ′
�

.

S =2T2
�

I ′
�
⊕ C ′

=2020011012112112212122021⊕ 1111100000000001111100000

=0101111012112110020222021.

S25 =S ⊕ Sc = 0101111012112110020222021.



I. Siap, H. Akin, S. Uguz / Eur. J. Pure Appl. Math, 6 (2013), 315-334 332

Ie =T−2
�

S25

�
= 1111000000000000000000000.

I =I ′⊕ Ie =Ö0000111111222222222222222⊕ 1111000000000000000000000

=1111111111222222222222222.

C =C ′ = 1111100000000001111100000

E =11110000000000000000000000000000000000000000000000.

Case 2. Four errors occur in the check part. Let the received word be

CW ′ =1111111111222222222222222Ö2222100000000001111100000=
�

I ′|C ′
�

.

S =T2
�

I ′
�
⊕ 2C ′ = 1111100000000001111100000⊕ 1111200000000002222200000

=2222000000000000000000000.

S25 =0000000000000000000000000

and

Sc =2222000000000000000000000.

Ie =T−2
�

S25

�
= 0000000000000000000000000.

Ce =Sc = 2222000000000000000000000.

C =C ′⊕ Ce =Ö2222100000000001111100000⊕ 2222000000000000000000000

=1111100000000001111100000.

E =00000000000000000000000002222000000000000000000000.

Case 3. Both information and check part are in error. Let the received word be

CW ′ =1111c001111222222222222222111110000c2200001111100000.

S =2T2
�

I ′
�
⊕ C ′ = 2 (1021002221101201102020122)⊕ 1111100002200001111100000

=0120101111102100012110211.

After first and second cycles fail to detect errors take Sc all possible error vectors in the

check part. Consider the case when

Sc =0000000001100000000000000.

S25 =S ⊕ Sc = 0120101112202100012110211.

Ie =T−2
�

S25

�
= 0000110000000000000000000.

I =I ′⊕ Ie = 1111c001111222222222222222⊕ 0000110000000000000000000

=1111111111222222222222222.

C =C ′⊕ Ce = 111110000c2200001111100000⊕ 0000000001100000000000000

=1111100000000001111100000.

E =00001100000000000000000000000000001100000000000000.



REFERENCES 333

In the Case-3, where errors occur in the both information and check part, firstly the check

part is corrected by classical syndrome decoding which require in total
∑3

i=0

�25

i

�
steps. Secondly

the information part is corrected by applying Case-1 which requires only one step. On the other

hand if the classical decoding method is used,
∑4

i=0

�50

i

�
steps are required. So as n is larger the

advantage of using CA becomes clearer.

7. Conclusion

2-D finite CA with the rule N PNN P has been defined on the field Z3. The rule matrix of

the 2-D finite CA has been obtained. Characterization of 2-D finite CA with the rule N PNN P

has been investigated. Properties of the 2-D finite CA over other fields (see [3]) remain to be

of great research interest. In this paper we focuss on algebraic representation for a novel 2-D

CA over ternary fields. We give some examples of the algorithms established here. Finally, we

present an application to error correcting codes and discuss the advantages of using CA. Some

other applications of this family of codes especially to cryptography, simulation of natural

phenomena, pseudo-random number generators, etc. is waiting to be explored.

ACKNOWLEDGEMENTS The work is supported by The Scientific and Technological Re-

search Council of Turkey (TUBITAK), project number: 110T713.

References

[1] H. Akın. On the directional entropy of Z2 -actions generated by additive cellular au-

tomata, 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 Ap-

plications. 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.



REFERENCES 334

[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.

1994.

[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 di-

mensional cellular automata, Computers Mathematics with Applications. 37, 115-127.

1999.

[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 cel-

lular 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.