Xreferat.com » Рефераты по информатике и программированию » Синтез комбинацонных схем и конечных автоматов, сети Петри

Синтез комбинацонных схем и конечных автоматов, сети Петри

возможных форм записи:


(2.2.3)


Записанный таким образом автомат называется автоматом Мили. Ясно, что это – более информативная форма записи по сравнению с автоматом Мура:


(2.2.4)


Способы задания автоматов.

Во - первых, автомат может быть задан непосредственно уравнениями вида (2.2.3) или (2.2.4).

Во - вторых, уравнения (2.2.3) и (2.2.4) могут быть представлены в табличной форме. Табличный аналог первого уравнения в (2.2.3) называется таблицей переходов, второго – таблицей выходов.

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

Граф автомата – это сигнальный граф, вершины которого обозначают состояния автомата, на дугах отражены условия перехода из состояния в состояние и значения выходных сигналов в виде дроби: над косой чертой – x(j), под ней – y(j).

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

Общее определение конечного автомата:


M = (X, Y, S, δ, λ), (2.2.5)


где X – входной алфавит, Y – выходной алфавит, S – множество состояний, δ – функция переходов, λ – функция выходов.

Пусть имеется два автомата: M и M’.

Если для любого существует по крайней мере одно , эквивалентное ему, то говорят, что M’ покрывает M: M’ ≥ M.

Если одновременно M’ ≥ M и M ≥ M’, то M ~ M’ . Получаем эквивалентные автоматы. В этом случае невозможно различить M и M’ по их реакции на входные сигналы.

Существуют два основных положения определения понятия эквивалентности состояний:

а) состояния si и sj явно различны, если соответствующие им строки в таблице выходов разные;

б) состояния si и sj явно эквивалентны, если соответствующие им строки в общей таблице переходов автомата одинаковы или становятся таковыми при замене si на sj или наоборот.

Минимизация (упрощение) автоматов основано на понятии эквивалентных автоматов. Под минимизацией автомата будем понимать сокращение числа его состояний.


2.3 Расчёты и полученные результаты.

Построение таблиц переходов, выходов и общей таблицы переходов и выходов на основе заданных уравнений автомата Мили очевидно:


x(j)

s(j)

0

1

2

3

0

1

0

1

0

1

0

1

0

1

2

1

0

1

0

3

0

1

0

1

4

1

0

1

0

5

0

1

0

1

6

1

0

1

0

7

0

1

0

1


Таблица 2.3.1 – Таблица выходов автомата


x(j)

s(j)

0

1

2

3

0

0

1

2

3

1

2

3

4

5

2

4

5

6

7

3

6

7

0

1

4

0

1

2

3

5

2

3

4

5

6

4

5

6

7

7

6

7

0

1


Таблица 2.3.2 – Таблица переходов автомата


x(j)

s(j)

0

1

2

3

0

0/1

1/0

2/1

3/0

1

2/0

3/1

4/0

5/1

2

4/1

5/0

6/1

7/0

3

6/0

7/1

0/0

1/1

4

0/1

1/0

2/1

3/0

5

2/0

3/1

4/0

5/1

6

4/1

5/0

6/1

7/0

7

6/0

7/1

0/0

1/1


Таблица 2.3.3 – Общая таблица переходов и выходов автомата


Перейдём непосредственно к минимизации полученного автомата по числу состояний. Для этого воспользуемся алгоритмом, известным в литературе как метод Гриса - Хопкрофта. Его достоинство в том, что он даёт гарантированно минимальную форму автомата. Однако в общем случае он является довольно трудоёмким и применяется, как правило, для автоматов с небольшим количеством состояний. Он основан на свойстве транзитивности эквивалентности


(si ~ sj) ∩ (sj ~ sk) (si ~ sk) (2.3.1)


Пара эквивалентных состояний переходит при всех возможных значениях входа в пары также эквивалентных состояний.

Алгоритм состоит из следующих шагов.

Сначала разбиваем все состояния автомата на множества по признаку совпадения выходных сигналов. В нашем случае получаем 2 множества: S1 = {0, 2, 4, 6} и S2 = {1, 3, 5, 7}.

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


пары

0

1

2

3

0;2

0;4

1;5

2;6

3;7

0;4

0;0

1;1

2;2

3;3

0;6

0;4

1;5

2;6

3;7

2;4

4;0

5;1

6;2

3;7

2;6

4;4

5;5

6;6

7;7

4;6

0;4

1;5

2;6

3;7

1;3

2;6

3;7

4;0

5;1

1;5

2;2

3;3

4;4

5;5

1;7

2;6

3;7

4;0

5;1

3;5

6;2

7;3

0;4

1;5

3;7

6;6

7;7

0;0

1;1

5;7

2;6

3;7

4;0

5;1


Таблица 2.3.4 – Таблица пар эквивалентных состояний


Ищем в полученной таблице неэквивалентные пары – пары из разных множеств. В таблице таких нет, значит, окончательно получаем автомат с двумя новыми состояниями – обозначим их 0 и 1.

Следующим шагом оформляем общую таблицу переходов для минимизированной формы автомата:


x(j)

s(j)

0

1

2

3

0

0/1

1/0

0/1

1/0

1

0/0

1/1

0/0

1/1


Таблица 2.3.5 – Новая общая таблица переходов.


На основании полученной общей таблицы переходов и выходов можно нарисовать граф минимизированного автомата с двумя состояниями:


0/1U 2/1 1/0 U 3/0 1/1U 3/1


0 1

0/0 U 2/0


Рисунок 2.3.1 – Граф минимизированного автомата

Для практической реализации полученного автомата надо двоично закодировать все сигналы. Для кодировки y и s достаточно одного двоичного разряда, x требует двух – x1 и x2:


x

x1

x2

0

0

0

1

0

1

2

1

0

3

1

1


Таблица 2.3.6 – Двоичная кодировка x


Составляем таблицу истинности для комбинационной части схемы на основе таблицы (2.3.5). Получаем две функции трёх аргументов:


x1(j)

0

0

0

0

1

1

1

1

x2(j)

0

0

1

1

0

0

1

1

s(j)

0

1

0

1

0

1

0

1

y(j)

1

0

0

1

1

0

0

1

s(j+1)

0

0

1

1

0

0

1

1


Таблица 2.3.7 – Таблица истинности комбинационной части


Каждую из функций y(j) и s(j+1) минимизируем с помощью карт Карно:

y(j) s(j+1)

x1(j)x2(j) x1(j)x2(j)

00 01 11 10 00 01 11 10

0 1 1 0 1 1

s(j) s(j)

1 1 1 1 1 1


Рисунок 2.3.2 – Карты Карно для комбинационной части


На основании выбранных покрытий записываем минимизированные выражения для функций переходов и выходов:


(2.3.2)


(2.3.3)


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





Рисунок 2.3.2 – Схема минимизированного автомата в базисе И – ИЛИ – НЕ


2.3.4 Выводы по разделу

В этом разделе был показан пример минимизации (упрощения) конечного автомата с сокращением числа состояний, а также пример реализации автомата на логических элементах и элементах памяти. Мы убедились в том, что конечный автомат является расширением понятия комбинационной схемы на случай, когда для получения выходного сигнала в данный момент времени требуется “помнить” некоторое количество предыдущих значений входного сигнала, а не только его текущее значение. При практической реализации автомата стала очевидной польза проведённых операций по упрощению исходного автомата и приведению его комбинационной части к конкретному базису.


3 Сети Петри

3.1 Постановка задачи

Для заданной сети Петри, описывающей распределение ресурсов для случая двух процессов, сделать следующее:

а) выписать матричное уравнение смены маркировок;

б) построить дерево и граф покрываемости маркировок;

в) описать поведенческие свойства сети на основе графа покрываемости и матричных уравнений;

г) выписать множество достижимых из μ0 маркировок;

д) разработать программу моделирования сети Петри.


3.2 Теоретические сведения

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

Определение. Сетью Петри называется четвёрка элементов


C = (P, T, I ,O), (3.2.1)

где


P = { p1, p2,…,pn }, n > 0 (3.2.2)


множество позиций (конечное),


Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: