Метод синтеза генераторов детерминированных тестов на сетях клеточных автоматов (СКА)
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?а структура одномерной линейной СКА, длинны n, с нулевыми граничными условиями.
Рисунок 1.4 - Одномерная n-клеточная СКА с нулевыми граничными условиями
Каждая ячейка СКА - КА, имеющий два состояния, структура которого представлена на рис.1.5.
Рисунок 1.5 - Структура КА
Ячейка состоит из двух основных блоков: элемента памяти на триггере типа D и комбинационной схемы, реализующей функцию возбуждения триггера F. Обозначим текущее состояние i-й ячейки СКА в момент времени t как , тогда последующее состояние определяется выражением:
где F - функция возбужден ил триггера, называемая правилом поведения клеточного автомата.
Правило может быть представлено и виде логической функции, либо таблицей истинности, либо как десятичный эквивалент двоичного числа (0.255), образуемого значениями функции и таблице истинности. В таблице 2.1 представлен пример численного значения правила
Таблица 1.1 - Пример вычисления численного значения правила
111110101100011010001000Правило 14410010000Правило 6501000001Степень 276543210
Правило 144 = 27 + 24
Правило 65 = 26 + 21
Аналогично вычисляется численное значение для любого правила.
Правило функционирования КА может быть записано в виде булевого выражения. Например, для правила 144, соответствующее выражение будет иметь вид:
где 'x' и '+' операции конъюнкции и дизъюнкции соответственно.
Определение 1. Диаграмма состояний КА.
Диаграмма состояний КА с двумя состояниями представляет собой вектор-столбец, состоящий из нулей и единиц. Обозначим состояние i-й ячейки в момент времени t - , тогда диаграмма состояний i-клетки за m-шагов может быть записана в виде:
где Т - оператор транспонирования матрицы
Определение 2. Диаграмма состояний ячейки СКА.
Диаграмма состояний ячейки, входящей в состав одномерной СКА записывается в виде матрицы, состоящей из трех столбцов (Хi-1, Xi, Xi+1). Хi - диаграмма на выходе интересующей ячейки, а Хi-1, Xi+1 - диаграммы на выходах левой и правой ячеек соответственно.
Определение 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.4 Моделирование физических процессов
Каждый клеточный автомат, это - некий мир, живущий по определённым законам. Жизнь его, как замкнутой системы, бесцельна. Время идет, он меняется, но сам по себе он не в силах понять, зачем это нужно и как долго это ещё будет продолжаться. Существование мира обретает смысл, к