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

Посмотреть архив целиком

Государственный комитет Российской Федерации по высшему образованию

Кубанский государственный технологический университет



Кафедра ???









ПОЯСНИТЕЛЬНАЯ ЗАПИСКА


к курсовой работе по предмету

математические основы теории систем

тема курсовой работы:

« Синтез комбинационных схем и конечных

автоматов. Сети Петри ».











Выполнил : студент гр. ??–??–??

????

номер зачётной книжки ??–??–???

Руководитель : ????

????










???

1999

Государственный комитет Российской Федерации по высшему образованию

Кубанский государственный технологический университет


ЗАДАНИЕ



На курсовую работу


Студенту гр.


По дисциплине




Тема курсовой работы




Исходные данные











1 Выполнить расчёты:


1.1


1.2


1.3


1.4



2 Выполнить графические работы:


2.1


2.2


3 Выполнить научные и учебно-исследовательские работы:


3.1


3.2


3.3


3.4


4 Оформить расчётно-пояснительную записку


5 Основная литература








Задание выдано


Срок сдачи работы


Задание принял


Руководитель


Работа защищена


С оценкой



ЧЛЕНЫ КОМИССИИ :

РЕФЕРАТ


МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ, КОМБИНАЦИОННАЯ СХЕМА, МИНИМИЗАЦИЯ КОНЕЧНЫХ АВТОМАТОВ, АВТОМАТ МИЛИ, СЕТЬ ПЕТРИ.


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

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

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



Курсовая работа содержит 38 страниц, 11 рисунков, 8 таблиц,

4 источника, 1 приложение .
























СОДЕРЖАНИЕ


Введение ………………………………………………………………6


1 Синтез комбинационных схем
1.1 Постановка задачи ……………………………………………… 7
1.2 Теоретические сведения …………………………………………7

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

1.4 Выводы по разделу………………………………………………13


2 Синтез конечных автоматов

2.1 Постановка задачи ……………………………………………… 14
2.2 Теоретические сведения …………………………………………14

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

    1. Выводы по разделу……………………………………………… 20


3 Сети Петри
3.1 Постановка задачи ……………………………………………… 21
3.2 Теоретические сведения ……………………………………… 21

3.3 Расчёты и полученные результаты …………………………… 26

3.4 Выводы по разделу……………………………………………… 31


Заключение …………………………………………………………. 32


Литература ………………………………………………………… 33


Приложение А ……………………………………………………… 34





















ВВЕДЕНИЕ


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

В первой части рассмотрена минимизация булевых функций, заданных в виде СДНФ, с помощью двух различных способов : карт Карно и метода склеивания Квайна – МакКласки. Полученные в виде минимизированных ДНФ функции были приведены к базисам, состоящим всего из одной функции : И – НЕ и ИЛИ – НЕ , а затем реализованы в виде комбинационных схем на соответствующих логических элементах.

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

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


























1 Синтез комбинационных схем


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


Для двух булевых функций, построенных по варианту задания в виде


(1.1.1)

, (1.1.2)


где gi, zi десятичные числа из диапазона от 0 до 15 в двоичном виде,

сделать следующее:

а) представить F1 и F2 в виде СДНФ.

б) минимизировать (по количеству переменных в ДНФ) F1 с

помощью карт Карно, F2 методом Квайна-МакКласки.

в) реализовать в виде комбинационной схемы на логических элементах F1 в базисе И – НЕ, F2 в базисе ИЛИ – НЕ, предварительно приведя F1 и F2 к соответствующим базисам.

gi и zi вычислять по выражениям:


(1.1.3)

(1.1.4)


при g0 = A, z0 = B . Параметр изменять от 1 до тех пор, пока не будет получено 9 различных значений gi и zi.


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

Булевой алгеброй называется множество S объектов A, B, C…, в котором определены две бинарные операции (логическое сложение – дизъюнкция(+) и логическое умножение – конъюнкция(∙)) и одна унарная операция(логическое отрицание()). Оно обладает следующими свойствами:

а) Для A, B, C S

  1. , (замкнутость);

  2. (коммутативные законы);

  3. (ассоциативные законы);

  4. (дистрибутивные законы);

  5. (свойства идемпотентности);

  6. в том и только том случае, если

(свойство совместимости);

  1. S содержит элементы 1 и 0 такие, что для всякого элемента

;

  1. для каждого элемента A класс S содержит элемент Ã (дополнение элемента A, часто обозначаемое символами Ā или 1- A ) такой, что

, .


В каждой булевой алгебре


(законы поглощения),

(законы склеивания),

(двойственность, законы де Моргана).


Если даны n булевых переменных X1, X2,…, Xn, каждая из которых может быть равна любому элементу булевой алгебры, то булевой функцией называется выражение


(1.2.1)

В каждой булевой алгебре существует ровно различных булевых функций n переменных.

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

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

Введём понятие многомерного куба.

Любую булеву функцию n переменных, заданную в ДНФ или СДНФ, можно отобразиь на n-мерном кубе, построенном в ортогональном базисе n булевых переменных. Каждое слагаемое в ДНФ или СДНФ представляется гиперплоскостью соответствующей размерности: если оно представляет собой конъюнкцию n переменных – точка, n-1 переменных – прямая, n-2 переменных – плоскость и т.д. Элементы n-мерного куба, имеющие s измерений, назовём s-кубами.

Комплекс K(y) кубов функции y=ƒ(x1,x2,…,xn) есть объединение Ks(y) множеств всех её кубов. Отсутствующие в конъюнкциях переменные будем обозначать через x.













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

По варианту задания находим gi и zi:



i

gi

zi

0

5

0

1

1

6

2

8

2

3

5

9

4

13

6

5

11

14

6

4

12

7

3

5

8

13

4

9

13

14

10

8

14

11

9

9

12

5

10

13

7

6



Неповторяющиеся значения gi: 5, 1, 8, 13, 11, 4, 3, 9, 7. Неповторяющиеся значения zi: 0, 6, 2, 9, 14, 12, 5, 4, 10. Таким образом, для F1 получаем выражение


, (1.3.1)


для F2:


. (1.3.2)


Для минимизации первой функции применяем метод карт Карно.

Карта Карно – прямоугольник с 2n клетками, каждой из которых соответствует своя конъюнкция из n переменных и их отрицаний (дополнений).

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









x3x4

00 01 11 10


00 1 1


01 1 1 1

x1x2

11 1



10 1 1 1



Рисунок 1.2.1 – карта Карно


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


. (1.3.3)


Для второй функции применяем метод Квайна-МакКласки.

На первом шаге алгоритма выписываем комплекс K0-кубов заданной функции, упорядоченных по возрастанию количества единиц:


0 0 0 0 0 1 1 1 1

0 0 1 1 1 0 0 1 1

K0 = 0 1 0 0 1 0 1 0 1 (1.3.4)

0 0 0 1 0 1 0 0 0 .


Второй этап основан на операции склеивания. Каждый из кубов проверяется на “склеиваемость” со всеми остальными. Склеивающиеся кубы должны различаться не более чем в одном разряде. Склеенный разряд в дальнейшем обозначается как x. Куб, участвовавший в операции склеивания, соответствующим образом помечается. Поскольку таких кубов мало, будем отмечать не участвовавшие в операции склеивания кубы. В результате получаем комплекс K1-кубов, также упорядоченный по возрастанию количества единиц в разрядах:


0 0 0 x 0 0 x x 1 1

0 x x 0 1 1 1 1 x 1

K1 = x 0 1 1 0 x 0 1 1 x (1.3.5)

0 0 0 0 x 0 0 0 0 0 .



Повторяем вышеописанную операцию для комплекса K1-кубов, после чего удаляем из полученного комплекса K2-кубов повторяющиеся:

0 0 x x x x 0 x x

x x x x 1 1 x x 1

K2 = x x 1 1 x x = x 1 x (1.3.6)

0 0 0 0 0 0 0 0 0



Те кубы, которые не участвовали в операциях склеивания, называются импликантами – это кандидаты на то, чтобы попасть в итоговую ДНФ. Для них составляем таблицу покрытий K0-кубов. Импликанта считается покрывающей K0-куб, если они совпадают при x, принимающем произвольное значение.



K0


z

0

0

0

0

0

0

1

0

0

1

0

0

0

1

0

1

0

1

1

0

1

0

0

1

1

0

1

0

1

1

0

0

1

1

1

0


Импликанты

1001






+




010x



+

+






0xx0

+

+

+


+





xx10


+



+


+


+

x1x0



+


+



+

+


Таблица 1.3.1 – Покрытия K0-кубов


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

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


. (1.3.7)



Комбинационная схема – это дискретное устройство, каждый из выходных сигналов которого в момент времени tm определяется так:


yj(tm) = ƒ ( x1(tm), x2(tm),…,xn(tm)) , (1.3.8)


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

Приведём F1 к базису И – НЕ, а F2 – к базису ИЛИ – НЕ:

(1.3.9)




. (1.3.10)



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




Рисунок 1.3.1 – Схема на И – НЕ-элементах













Рисунок 1.3.2 – Схема на ИЛИ – НЕ-элементах




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

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
















2 Синтез конечных автоматов


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

Конечный автомат задан своими уравнениями переходов и выходов:


s(j+1) = [2∙s(j) + x(j) + B] mod 8 ,


y(j) = [ s(j) + x(j) + A] mod 2 ,


.


Требуется:

а) построить таблицы переходов, выходов и общую таблицу переходов автомата;

б) минимизировать автомат по числу состояний с использованием таблиц, полученных ранее;

в) построить граф минимизированного автомата и выписать для него матрицу переходов;

г) переходя ко двоичному представлению входа X, выхода Y и состояния S, составить таблицу входов и выходов комбинационной схемы автомата и выполнить минимизацию булевых функций, соответствующих выходам и состояниям автомата;

д) разработать логическую схему автомата в базисе И – НЕ, реализуя элементы памяти на триггерах и задержках.


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

Конечным автоматом называется такое дискретное устройство, выходные сигналы которого в определённые моменты времени зависят не только от последнего пришедшего входного сигнала, но и от некоторого количества предыдущих его значений.

Различают синхронные и асинхронные автоматы. У асинхронных смена выходных сигналов y(tj) может происходить только в моменты изменения входных x(tj) , у синхронных – в моменты времени, определяемые дополнительным синхронизирующим сигналом c(t) .

Определим множества, которым могут принадлежать входные и выходные сигналы (условимся обозначать tj как j):

множетва входных и выходных сигналов.

Тогда выражения


(2.2.1)

определяют входной и выходной алфавиты автомата.

Пусть . Тогда если y(j) = λ(x(j)), то этот автомат является, очевидно, комбинационной схемой.


Введём дополнительную переменную для того, чтобы охарактеризовать состояние автомата в каждый момент времени j:

(2.2.2)


В том случае, если X, Y и S – конечные множества, то и сам автомат называют конечным.

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


(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’.

Если для любого существует по крайней мере одно