Cellular Automata for Efficient Image and Video Compression - Cellular Automata in Image Processing and Geometry - page 9

Fig. 1.6 Exemplification of binary synchronization using two identical CA with n = 31 cells
and rule ID=13474665135 (5 cells neighborhood). Although the initial states of both trans-
mitter (Tx-CA) and receiver (Rx-CA) are different by driving the Rx-CA with 1 single bit
from Tx-CA ensures that after a synchronization period T s the entire state of Rx-CA is iden-
tical to the state of Tx-CA.

Therefore, for any arbitrary cycle C j of length L j a scattering coefficient S j is defined
by averaging the Hamming distances between all consecutive binary vector states in

L j
k = 1

n
∑

1
nL j

that cycle: S j =

1 |

x i ( k ) − x i ( k − 1 ) | where k is the time index of consecu-

i =

− 2 S j − 1 is then defined such

tive states in the cycle j .A degree of chaos λ j = 1

that it becomes maximum if S j = 5 and zero for the extreme, non-chaotic cases

of both fixed points and period 2 cycles (with S j =

0 .

1 respectively). The
degree of chaos may be regarded as qualitatively similar to the Lyapunov exponent
used in continuous-state systems to characterize chaotic behaviours. In our case its
largest value is

0and S j =

1 indicates the highest degree of randomness in a finite-length
cycle of an automata network;
iii) Binary synchronization property: Unlike traditional chaos synchronization
[24] in the case of binary synchronization sending only 1 bit from the Tx automaton
allows the recovery of the entire state ( n bits) in a similar Rx automaton (as seen in
Fig. 1.6).
In this case the information needed to resynchronize the Rx is minimal and con-
sists of only 1 bit per clock cycle. Consequently it may be easily embedded and
recovered in various forms of modulation/demodulation. This property is not com-
mon to CA and it was first investigated for all elementary cellular automata (ECA)
in [18]. Within all 256 ECA we found that the binary synchronization property holds
only for the conservative rules ID=45 (and its 3 equivalents ID=75,89, and 101).
Further work [17] indicates that a precondition to achieve binary synchronization in
CA is the existence of an asymmetric cell (i.e. a cell that is sensitive to mirroring the
inputs from left to right with respect to the central cell). Also, in order to optimize
the dominant cycle length it was found [14] that a hybrid CA model with some of
the cells having inverted outputs has a better behavior and allows to design a cellular
automaton satisfying all 3 properties mentioned above.
Next, CA or automata systems fulfilling all the above three properties will be
mentioned as “good chaotic counters”. As seen in the next subsection, expanding
the neighborhood to 5 cells allows the identification of more CA rules holding the

λ j =