Автоматные сети и реализация автоматных функций

2.3. Пример  реализации механизма сетей Петри

Одним из подходов, используемых при внедрении сетей Петри в программирование, является отождествление переходов с операторами программы, а позиций – с их готовностью к выполнению. Здесь возникает соблазн пренебречь длительностью простых операций и представить программу в виде одноуровневой сети, формально содержащей только простые переходы.

Однако при разработке параллельной программы в этом случае необходимо учитывать тот факт, что вследствие того, что срабатывания простых переходов последовательны, т.е. не могут перекрывать друг друга по  времени, организованная таким образом программа не может быть параллельной. Поэтому при реализации параллельных программ рассматриваются иерархические сети с составными переходами.

ГЛАВА 3.РЕАЛИЗАЦИЯ АВТОМАТНЫХ ФУНКЦИЙ

3.1. Схемы из  функциональных элементов и элементов задержки.

Будем реализовывать  автоматные функции из множества PE, где E= {0,1}, при помощи функциональных элементов дизъюнкции, конъюнкции и отрицания и элемента единичной задержки (рис 1) .

Рис. 1.

Отметим, что функциональные элементы можно рассматривать как частный случай автоматов, а точнее, как автоматы с одним состоянием. Такие автоматы называются автоматами без памяти.

В частности канонические уравнения для автоматов, соответствующих элементам дизъюнкции, конъюнкции и отрицания, имеют следующий вид:

y(t)=x1(t)∨x2(t);

q(t+1)=q(t);

q(1)=0,

y(t)=x1(t)&x2(t);

q(t+1)=q(t);

q(1)=0,

 

y(t)=x(t);

q(t+1)=q(t);

q(1)=0.

Будем обозначать автоматные функции из PE, которые вычисляются этими автоматами через f∨(x1,x2), f&(x1,x2) и f−(x) соответственно. Канонические уравнения элемента единичной задержки имеют вид:

y(t)=q(t);

q(t+1)=x(t);

q(1)=0

соответствующая автоматная функция обозначается через f(x).

Пусть f(x1, . . . ,xn) - произвольная автоматная функция из PE, а Vq0 = (A,B,Q,F,G) - инициальный автомат, вычисляющий функцию f , где A = En = {0,1}n, B = {0,1}, Q = {q1, . . . ,qλ},q0 ∈Q, F : {0,1} nЧQ→{0,1}, G : {0,1}n ЧQ→Q. Канонические уравнения этого автомата имеют вид:

y(t)=F(x1(t), . . . ,xn(t),q(t));

q(t+1)=G(x1(t), . . . ,xn(t),q(t));

q(1)=q0.

Положим j =] log2λ[. Занумеруем состояния q1, . . . ,qλ наборами из 0 и 1 длины j, причем начальному состоянию q0 сопоставим набор (0, . . . ,0). Рассмотрим теперь новые функции, определенные на наборах из нулей и единиц:

y(t)=F1(x1(t), . . . ,xn(t),q1(t), . . . ,ql(t));

(q1(t+1), . . . ,ql(t+1))=G˜1(x1(t), . . . ,xn(t),q1(t), . . . ,ql(t));

(q1(1), . . . ,ql(1))=(0, . . . ,0),

где функция F1 и компоненты G¹₁, . . . ,G¹j вектор функции G˜¹ =

(G¹₁, . . . ,G¹j ) определены на некотором подмножестве множества E^n+j всех наборов из нулей и единиц длины ^n+j и принимают значения из {0,1}, т. е. являются частичными булевыми функциями. В покомпонентной записи эти уравнения имеют следующий вид:

y(t)=F(x1(t), . . . ,xn(t),q1(t), . . . ,qj(t));

q2(t+1)=C¹₁ (x1(t),. . . . ,xn(t),q1(t),. . . . qj(t));

ql(t+1))=G¹lj (x1(t), . . . ,xn(t),q1(t), . . . ,qj(t));

q1.(.1.)=0;

qj(1)=0.

Доопределим функции F1,G¹₁, . . . ,G¹j до всюду определенных булевых функций F2,G2₁, . . . ,G2_j соответственно. Положим G˜2 =(G2₁, . . . ,G2j ).

Таким образом, мы построили  инициальный автомат Vq˜20 =({0,1}n,{0,1},{0,1}j,F2,G˜2) с n входами, входным алфавитом {0,1}n, выходным алфавитом {0,1}, алфавитом состояний {0,1}j ,функцией выходов F2 : {0,1}nЧ{0,1}l →{0,1}, вектор-функцией G˜2 : {0,1}nЧ{0,1}l → {0,1}j и начальным состоянием переходов q˜0 =(0, . . . ,0). Легко видеть, что этот автомат вычисляет функцию f(x1, . . . ,xn).⁶

Построим схему S из функциональных элементов в базисе {∨,&, } с n + l входами, которым приписаны символы x1, . . . ,xn,q1, . . . ,qj , и 1 + j выходами y,z1, . . . ,zj ; при этом на выходе y реализуется функция F2(x1, . . . ,xn,q1, . . . ,qj), а на выходах z1, . . . ,zj - функции G²₁(x1, . . . ,xn,q1, . . . ,qj), . . . ,G²j (x1, . . . ,xn,q1, . . . ,qj) соответственно (рис. 2) .

Рис.2.

Преобразуем схему S следующим образом. Возьмем j элементов единичной задержки. Присоединим вход i-го элемента задержки к выходу zi , а выход - ко входу qi схемы S, i =1, . . . , l . Кроме того символы x1, . . . ,xn заменим на x1(t), . . . ,xn(t) соответственно а символы функциональных элементов ∨,&, - на символы f&, f∨ и f− соответственно. В результате получим "схему" S1 из автоматных элементов в базисе {f&,f∨,f−,f} (рис. 3, приложение 3) .

Отметим что при этом мы вышли за рамки данного ранее определения схемы из автоматных элементов, поскольку в S1 возникли ориентированные циклы. Однако их наличие в "схеме" S1не приводит к противоречиям при ее функционировании, поскольку все эти циклы проходят через элементы задержки.

Операция построения в схемах ориентированных циклов, проходящих через элементы задержки, называется операцией обратной связи.

Индукцией по t нетрудно показать, что если в момент времени t подавать на входы схемыS1 значения x1(t), . . . ,xn(t) из {0,1}, то на ее выходе будет выдаваться значение y(t) из {0,1}, которое вычисляется в соответствии с каноническими уравнениями автомата Vq˜20. Тем самым схема S1 реализует автоматную функцию f(x1, . . . ,xn).

3.2.Использование  автоматной функции качестве  криптографического преобразования

Доступной информацией является класс криптоалгоритмов (конечно-автоматные функции); описание автоматной функции является секретным.

Конечный автомат –  это имеющее вход и выход устройство, которое в каждый момент времени находится в одном из своих состояний. Конечный автомат осуществляет преобразование информации в дискретные моменты времени 0, 1, 2, …, t, … На вход автомата поступает последовательность символов входного алфавита X = {x₁, x₂, …, x_n}; эту последовательность называют входным словом.⁷

Функционирование конечного  автомата осуществляется в соответствии с системой из ns команд, где 

s – мощность алфавита  состояний Q = {q₁, q₂, …, q_s}. В каждый момент времени значением выхода автомата является элемент выходного алфавита Y = {y₁, y₂, …, y_m}. Каждая команда имеет вид

x_iq_j → y_kq_r                     (1),

где x_i – входная буква, q_j – текущее состояние, y_k – выходная буква и q_r – состояние в следующий за текущим момент времени (следующее состояние).

Функционирование конечного  автомата задают также кортежем

<X, X, Q, V, P>,          (2),

где  V: X Ч Q → Y (функция  выхода),

P: X Ч Q →  (функция  переходов).

Конечный автомат с  определенным состоянием в начальный  момент времени называется инициальным автоматом. В соответствии со своей системой команд инициальный автомат реализует автоматную функцию, которая произвольное входное слово в алфавите X преобразует в выходное слово в алфавите YY той же длины. Осуществляемое инициальным автоматом преобразование слов проиллюстрируем следующей таблицей:

Таблица 1

время	0	1	2	3	. …….	n	n + 1
входная буква	x(0))	x(1)	x(2)		……..	x(n)
состояние	q(0)	q(1)	q(2)	q(3)	………	q(n)	q(n + 1)
выходная буква	y(0)	y(1)	y(2)		……..	y(n)

 

Здесь и далее через x^(j) (y^(j)) обозначаем j-ю букву входного (выходного) слова, а через q^(j) – состояние автомата в момент времени j (при заданном входном слове).

По букве входного слова и состоянию, используя  функции выхода и переходов, находим  букву выходного слова в тот же момент времени и состояние в следующий момент.

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

Как известно, применяемые  при шифровании и расшифровывании  преобразования должны быть взаимно однозначными.⁸

Конечный автомат M назовем  обратимым (ОК-автоматом), если существует конечный автомат M₁, такой, что по описанию автомата M, его начальному состоянию и произвольному выходному слову автомата M автомат M₁ однозначно определяет входное слово. В этом случае автомат M₁ будем обозначать через M^–1. Таким образом, в качестве криптографических преобразований можно использовать только автоматные функции, соответствующие ОК-автоматам.

Для простоты изложения  будем рассматривать конечные автоматы, у которых входной и выходной алфавиты совпадают. Такие автоматы, у которых мощность входного алфавита (алфавита состояний) равна n (равна s), будем называть (n, s)-автоматами.⁹

Пусть V_j(x), 1 ≤ j ≤ s, – функция V(x, _qj). Нетрудно проверить, что необходимым условием того, что автомат M – это ОК-автомат, является инъективность функций V_j(x) для любого j.

Функция f(x) инъективна, если из неравенства x_i ≠ x_j следует неравенство f(x_i) ≠ f(x_j). В нашем случае (совпадение входного и выходного алфавитов) утверждение об инъективности функции V_j(x) эквивалентно утверждению о том, что она является перестановкой.

Справедливо следующее  утверждение.

Теорема. Автомат M=<X, Y, Q, V, P> является обратимым тогда  и только тогда, когда для любого j функция V_j(x) инъективна.

Известно, что число (n, s)-автоматов не превосходит nns. Нетрудно проверить, что число (n, s)-автоматов, являющихся ОК-автоматами, имеет оценку (n!)s. Отметим, что имеет место следующая (асимптотическая) формул Стирлинга:

                    (3),

 

Таким образом, доля ОК-автоматов  стремится к 0 при увеличении значений параметров автомата n и s. Однако ОК-автоматы образуют достаточно мощный класс.

При использовании ОК-автоматов  в криптографии ключи шифрования определяют описания (таблицы) функций V(x, q) и P(x, q).

Получение описаний функций V–1 (x, q) и P–1 (x, q) обратного автомата по описаниям функций V(x, q) и P(x, q) является эффективной процедурой. Следовательно, общеавтоматное шифрование является симметричным.

Задача криптоанализа  общеавтоматного шифрования – восстановление описания конечного

автомата (нахождение функций V(x, q) и P(x, q)) по наблюдению входных и выходных слов.

Такие работы велись давно. Из них следует, что при надлежащем выборе ключей общеавтоматное шифрование обладает достаточной криптостойкостью.

ЗАКЛЮЧЕНИЕ

С появлением многоядерных архитектур наступает эра универсальных параллельных вычислений. Но пока это параллелизм интуитивного представления о реализации параллельных процессов, не базирующийся на какой-либо формальной модели, что плохо. И от того, какая в основу параллельной архитектуры будет положена модель, зависит эффективность работы не только и не столько процессора, а и программистов, использующих данную архитектуру.

При этом формальная модель определяет технологию проектирования программ, от качества которой напрямую зависит качество программного продукта.

К нему же ныне просто огромные претензии.

Нельзя не отметить вновь  возникший интерес к автоматным моделям. Кроме UML, SWITCH-технологии и КА-технологии можно привести еще ряд примеров использования автоматных моделей в проектировании программ. Кроме этого есть целые разделы в программировании, где уже давно и постоянно ведется разработка программ с использованием автоматов.

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

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