Рис. 5. Структура генератора ПСП на основе КлА
Генераторы ПСП на основе клеточных автоматов.
Структура
генератора.
Структура генератора псевдослучайных последователь-
ностей (ПСП), основанного на использовании однородных двумерных
булевых КлА, приведена на рис. 5. В состав генератора входят два КлА
и регистр сдвига с линейной обратной связью (РСЛОС).
Размеры решетки одинаковы для обоих автоматов и составляют
37
×
11
ячеек; выбор простых чисел позволяет избежать возникновения
пространственных периодов. Окрестность каждой ячейки состоит из
ячеек, непосредственно смежных с ней, что соответствует локальной
функции связи от 8 аргументов. В качестве выхода КлА используются
заполнения ячеек подрешетки размера
32
×
8
, т.е. ячеек
m
(
x,y
)
, где
0
≤
x <
32
и
0
≤
y <
8
, что обеспечивает выработку каждым КлА
256 бит за один такт работы. Для каждого КлА используется своя
собственная равновесная локальная функция связи.
Выход РСЛОС на каждом такте работы прибавляется по модулю 2
к заполнениям ячеек КлА с координатами
(34
,
9)
. Лавинный эффект
позволяет утверждать, что период внутренних состояний КлА будет не
меньше периода выходной последовательности РСЛОС. Считаем, что
для практического применения генератора достаточно использовать
РСЛОС длиной 63, что обеспечивает период его выходной последова-
тельности
2
63
−
1
≈
9
,
2
∙
10
18
бит; период выходной последовательности
КлА при этом составляет не менее
32
∙
8
∙
(2
63
−
1)
≈
2
,
4
×
10
21
бит. Тем
не менее длина регистра может быть изменена при необходимости.
Выход генератора формируется посредством сложения по модулю
2 выходных последовательностей обоих КлА, что позволяет суще-
ственно улучшить статистические свойства выходной последователь-
ности генератора, увеличить ее период, а также затруднить восстано-
вление внутреннего состояния генератора по выходным значениям.
Аппаратная реализация и статистические свойства генерато-
ра.
Автором настоящей работы был разработан прототип аппарат-
ной реализации предложенного генератора на ПЛИС Altera Cyclone II
(EP2C35F672C6), структурная схема которого приведена на рис. 6. Вы-
ходная последовательность генератора подавалась напрямую на выво-
ды ПЛИС, а также записывалась для дальнейшего анализа во внутрен-
74 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2011. № 2
