Image Processing Reference
In-Depth Information
The discrete-time dynamics of the hybrid cellular automata (HCA) is given by
the next equation, which applies synchronously to all
n
cells (a cell is identified by
an index
i
∈{
,
,..
}
1
2
n
):
Cell
x
i
−
1
(
ID
x
i
(
x
i
(
x
i
+
1
(
+
)=
↕
)
,
)
,
))
,
t
1
m
i
t
t
t
(1.1)
where the upper index “
T
” stands for the transmitting CA counter,
↕
is the log-
ical XOR operator and
Cell
(
u
1
,
u
2
,
u
3
,
ID
)
is a Boolean function with 3 binary
inputs (
u
1
u
2, and
u
3), also called the CA (local) rule. A periodic boundary con-
dition is assumed i.e. the leftmost cell (
i
,
=
1) is connected to the rightmost one
(
i
can be optimized [14] (so far
our programs perform optimization in reasonable time for
n
=
n
). The binary mask vector
m
=[
m
1
,
m
2
,..,
m
n
]
≤
29
)
to obtain a max-
2
n
imal cycle length (
r
=
L
/
ₒ
1
)
. The above equation (1.1) easily extends to larger
neighborhoods such as
m
5
by adding 2 additional inputs to the cell, located on
the rightmost and leftmost positions (
i-2
,and
i
=
2
). For any neighborhood the rela-
tionship between inputs and the output local CA rule can be characterized in two
different ways while conversion functions are available via [30] :
+
a) Truth-Table (TT) representation:
This is the most widely used representa-
tion. The rule is characterized by a binary vector
Y
=[
,
,...,
]
.Itsrepre-
sentation in decimal basis is called a rule identifier (ID). The output
y
k
is a binary
number assigned to the cell's output when its inputs ordered as a binary vector
[
y
N
−
1
y
N
−
2
y
0
u
n
,
are the binary representation of k;
b) Algebraic Normal Form (ANF):
This form is described by a binary vector
u
n
−
1
,..,
u
1
]
C
(using the method in [30] a unique conversion from Y to C and
vice-versa exists) such that its coefficients are multipliers of an algebraic represen-
tation on the GF2 exemplified next for the case of m
=[
c
0
,
c
1
,...
c
N
]
=
3 neighborhood:
y
=
c
0
↕
c
1
u
1
↕
c
2
u
2
↕
c
3
u
2
u
1
k
3
u
3
↕
c
4
u
3
↕
c
5
u
3
u
1
↕
c
6
u
3
u
2
↕
c
7
u
3
u
2
u
1
(1.2)
Note that in general (for any size
m
of the neighbourhood)
c
k
is the multiplier of
a product (logical AND) of all input variables in a binary vector
u
1
]
corresponding to 1 in the associated binary vector representing
k
. For example, in
the case of
m
[
u
n
,
u
n
−
1
,...,
101
2
only the inputs corresponding to 1 in the input
string
u
3
u
2
u
1
are selected to be multiplied resulting in the term
c
5
u
3
u
1
.
The most important results of our research in designing HCA that are good
chaotic counters are summarized in Figure 1.8:
i) First, we have
a number of HCA with 3 inputs
where the ANF represen-
tation of the rules is given by the formula:
y
=
3for
k
=
5
=
=
m
i
↕
u
a
↕
u
b
↕
u
c
u
b
where
a
,
b
,
c
are cell position indexes such that
a
h
where
h
is an integer. In all
these cases a computationally intensive program is run to find the best mask (the
one maximizing the dominant cycle length
L
−
b
=
b
−
c
=
)
. For instance the HCA with rule
ID
1347465135 has the best mask found so far 19801 (decimal representation of
mask vector
m
=
=[
m
1
,
m
2
,..,
m
n
])
leading to
L
=
N-1
=
131071
in the case of
n
=
17
cells (i.e. addressing an image of size 512
1024). The problem with all HCA in the
above category is that they are conservative (no transient and possible to optimize
×
Search WWH ::
Custom Search