Обеспечение информационной защиты беспроводных сенсорных сетей…
9
1.
Объединение (параллельное соединение) клеточных автоматов
1
2
...
l
K K K K
≡ ⊗ ⊗ ⊗
. Объединением клеточных автоматов будем
называть клеточный автомат, алфавит состояний которого и множе-
ство эволюций являются декартовым произведением состояний и
эволюций объединяемых клеточных автоматов:
1 2
...
l
E E E E
≡ × × ×
,
1 2
...
l
Q Q Q Q
≡ × × ×
. Операция обладает свойством коммутативности и
ассоциативности:
1
2
3
1
2
3
(
) (
)
K K K K K K
⊗ ⊗ = ⊗ ⊗
,
1
2
2
1
K K K K
⊗ = ⊗
.
2.
Композиция (последовательное соединение) клеточных авто-
матов
1
2
(...(
) ...)
l
K K K
K
≡
⊕ ⊕ ⊕
. При последовательном соединении
заключительная конфигурация одного автомата является начальной дру-
гого:
e E
∀ ∈
01
1 12
2
,..., ,
,...,
,...,
l
e c c c c c
τ
τ
τ
=
,
1
2
...
l
K K K
K
= ⊕ ⊕ ⊕
.
Данная операция не обладает свойством коммутативности и ассоциа-
тивности
1
2
3
1
2
3
(
) (
)
K K K K K K
⊕ ⊕ ≠ ⊕ ⊕
,
1
2
2
1
K K K K
⊕ ≠ ⊕
.
3.
Взятие проекции клеточного автомата
( )
i
K K
≡
. Существо
этой унарной операции определяется выражением
( )
( )
i
c K c K
τ
=
.
4.
Склейка клеточных автоматов
1 2
...
l
K K K K
≡ ⋅
⋅ ⋅
. Для данной
операции
1 2
...
l
Q Q Q Q
= × × ×
,
(
)
1 2
, ,...,
l
f
ϕ = ϕ ϕ ϕ
. Операция комму-
тативна и ассоциативна. Геометрическая интерпретация склейки
представлена на рис. 4.
5.
Расслоение клеточного автомата
1 2
...
l
K K K K
≡
o o o
. Эта
операция является обратной операции склейки.
В работе [7] исследуются свойства генератора псевдослучайных
последовательностей на базе одномерного КЛА с бинарным алфави-
том, реализующего локальную функцию вида
(
)
1
1
1
t
t
t
t
i
i
i
i
q q q q
+
−
+
= ⊕ ∨
.
Конфигурации такого КЛА образуют последовательность двоичных
случайных векторов.
Используя операции предложенной алгебры, можно получать
другие КЛА, генерирующие псевдослучайные векторы. Так, в ре-
зультате операции склейки двух КЛА, элементарные автоматы кото-
рых реализуют линейные преобразования над бинарным алфавитом
1
1
1
t
t
t
i
i
i
q q q
+
−
+
= ⊕
,
1
1
1
t
t
t
t
i
i
i
i
q q q q
+
−
+
= ⊕ ⊕
,
получают генератор псевдослучайных последовательностей, изо-
морфный генераторам последовательностей на регистрах сдвига с
линейными обратными связями.
