УДК 004.421.5
Б. М. C у х и н и н
О НЕКОТОРЫХ СВОЙСТВАХ
КЛЕТОЧНЫХ АВТОМАТОВ
И ИХ ПРИМЕНЕНИИ В СТРУКТУРЕ
ГЕНЕРАТОРОВ ПСЕВДОСЛУЧАЙНЫХ
ПОСЛЕДОВАТЕЛЬНОСТЕЙ
Исследованы свойства однородных двумерных булевых клеточных
автоматов, а также разработан новый генератор псевдослучай-
ных последовательностей, основанный на использовании этих ав-
томатов. Выходные последовательности таких генераторов име-
ют хорошие статистические свойства, а аппаратная реализация
предложенных алгоритмов на типовых ПЛИС обладает очень вы-
соким быстродействием — до 25 Гбит/с на частоте 100 МГц.
E-mail:
Ключевые слова
:
клеточные автоматы, генераторы псевдослучайных
последовательностей, лавинный эффект.
Клеточным автоматом (КлА) называется модель с дискретным вре-
менем, состоящая из множества ячеек памяти, упорядоченных в пери-
одическую
n
-мерную решетку [1]. Заполнения ячеек являются элемен-
тами некоторого конечного множества. Для каждой ячейки выбирает-
ся ее окрестность, которая используется для определения заполнения
ячейки на следующем такте работы по некоторому заранее заданному
правилу.
Для классических КлА выполняются свойства однородности и ло-
кальности [2]. Однородность означает, что все ячейки КлА являются
неразличимыми по своим свойствам; кроме того, для решения пробле-
мы краевых клеток противоположные края решетки отождествляются,
т.е. двумерная решетка закручивается в тор. В соответствии со свой-
ством локальности в окрестность каждой ячейки входят только ячейки,
удаленные от нее на расстояние не более заданного.
Обширные исследования одномерных КлА были проведены Стефа-
ном Вольфрамом [3–5]; исследования же КлА размерности 3 и более
ограниченны в силу сложности их реализации. В настоящей работе
будем рассматривать двумерные булевы КлА с прямоугольными ячей-
ками. В таких автоматах заполнения ячеек памяти содержат двоичные
значения. Использование двоичного множества
{
0; 1
}
и прямоугольная
форма ячеек облегчают реализацию КлА и их применение в вычисли-
тельной технике. В качестве правила, определяющего новые заполне-
ния ячеек на следующем такте работы, используется булева функция,
аргументами которой являются заполнения ячеек, входящих в окрест-
ность данной. Такую функцию будем называть локальной функцией
68 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2011. № 2
