Основные разделы


Двумерный клеточный автомат

Определение 3. Диаграмма состояний СКА.

Диаграмма состояний СКА длины n может быть записана в виде совокупности из n триплет

Каждая совокупность из трех столбцов (Хi-1, Хi Хi+1) представляет диаграмму состояний i-й ячейки сети. Нужно заметить, что столбцы Х0 и Хn+1 - это столбцы, состоящие из нулей. Эти столбцы соответствуют нулевым граничным условиям.

Определение 4. Детерминизм правил КА.

В данной работе рассматриваются только детерминированные правила. Это значит, что любая пара идентичных состояний окрестности КА приводит его в одно и тоже последующее состояние.

Обозначим состояние окрестности i-й ячейки СКА на шаге t, как

(1.1)

Рассмотрим состояние i - ячейки СКА на шаге tj и tk, tj≠tk, если

(1.2)

Вышеприведенное выражение дает возможность определить, является ли двоичная последовательность, состоящая из трех столбцов, частью диаграммы состояний ячейки СКА.

Определение 5. Универсальная окрестность.

Запишем:

где F представляет правило функционирования КА, а - это состояние окрестности i-й ячейки СКА в момент времени t. Параметр r - это положительное целое число, характеризующее размер окрестности, а, следовательно, и диапазон правил КА [5].

Универсальная окрестность, , ячейки xi, в одномерной СКА длинны n, может быть представлена в следующем виде:

Таким образом, окрестность Фон Неймана является частным случаем универсальной окрестности.

На рис.1.6 показаны два варианта окрестности с г = 1 и г = 2. Как можно заметить, при r =1, на последующее состояние ячейки влияет три переменные, а при r =2 - пять.

Рисунок 1.6 - Универсальная окрестность с r=1 и r=2

Окрестность определяется диапазоном правил КА [6] в зависимости от параметра r следующим образом , где (2r+1) - количество соседних с рассматриваемой ячеек, участвующих в вычислении последующего.

Окрестность Фон Неймана, рассматриваемая в данной работе, позволяет использовать =256 правил. Этот класс КА называют "элементарный КА Вольфрама" [6].

Диаграмма состояний ячейки СКА с универсальной окрестностью состоит из совокупности (2г+1) столбцов (Хi-r,.,Xi,… Xi+r), где - диаграмма состояний КА. При этом столбцы (X-r+1, X-r+2,…, X0) и (Xn+1, Xn+2,…, Xn+r) обеспечивают заданные граничные условия.

Увеличение r > 1 и, следовательно, расширение окрестности влечет за собой ряд проблем, одна из которых состоит в кодировании правил, возможное число которых значительно возрастает, в этом случае правила рассматриваются в виде таблицы истинности и соответствующей логической функции. Кроме того, из-за такого расширения окрестности значительно усложняется проектирование СКА с заданными свойствами.

Определение 6. Детерминированность субпоследовательности.

Детерминированность для субпоследовательности S, состоящей из k строк, длины n, на основании (2.1) можно сформулировать следующим образом:

пусть - i-й элемент строки t, тогда субпоследовательность (СП) детерминирована, если

, выполняется (1.2) (1.3)

Перейти на страницу: 1 2 3 

Прочитайте еще и эти статьи:

Разработка системы голосового управления электромеханическими устройствами
В настоящее время вычислительная техника используется во многих областях человеческой деятельности, являясь удобным и многофункциональным инструментом для решения широкого круга задач. Однако, в настоящее время пользователи ЭВМ вын ...

Разработка цифрового комбинационного устройства - демультиплексора
Необходимо разработать цифровое комбинационное устройство демультиплексор из 1 в 4 в базисе ИЛИ-НЕ, НЕ, логическая функция которого указана ниже. Требуемые параметры устройства и базисных элементов представлены в таблице 1.1. Параметры, необ ...

© Copyright 2021 | www.techattribute.ru