Синтез комбинацонных схем и конечных автоматов, сети Петри
Государственный комитет Российской Федерации по высшему образованию
Кубанский государственный технологический университет
Кафедра ???
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовой работе по предмету
математические основы теории систем
тема курсовой работы:
« Синтез комбинационных схем и конечных
автоматов. Сети Петри ».
Выполнил : студент гр. ??–??–??
????
номер зачётной книжки ??–??–???
Руководитель : ????
????
???
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
Выводы по разделу……………………………………………… 20
3 Сети Петри
3.1 Постановка задачи ……………………………………………… 21
3.2 Теоретические сведения ……………………………………… 21
3.3 Расчёты и полученные результаты …………………………… 26
3.4 Выводы по разделу……………………………………………… 31
Заключение …………………………………………………………. 32
Литература ………………………………………………………… 33
Приложение А ……………………………………………………… 34
ВВЕДЕНИЕ
Работа посвящена синтезу дискретных устройств с “памятью” (конечных автоматов) и “без памяти” (комбинационных схем), а также анализу реально протекающих процессов с помощью сетей Петри.
В первой части рассмотрена минимизация булевых функций, заданных в виде СДНФ, с помощью двух различных способов : карт Карно и метода склеивания Квайна – МакКласки. Полученные в виде минимизированных ДНФ функции были приведены к базисам, состоящим всего из одной функции : И – НЕ и ИЛИ – НЕ , а затем реализованы в виде комбинационных схем на соответствующих логических элементах.
Во второй части заданный по условию в функциональном виде конечный автомат был минимизирован по числу состояний. Для полученного автомата был построен граф состояний. Затем, перейдя к двоичному представлению входных, выходных сигналов и сигналов состояния, в автомате были выделены элементы памяти и комбинационная часть, которая затем была минимизирована по числу переменнных. Автомат был реализован в базисе И – ИЛИ – НЕ с использованием D - триггера и задержки.
В третьей части была проанализирована заданная сеть Петри с помощью двух способов: матричного и основанного на построении дерева покрываемости, а также написана программа для её моделирования.
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.
Теоретические сведения.
Булевой
алгеброй называется
множество S
объектов
A,
B,
C…,
в котором
определены
две бинарные
операции (логическое
сложение –
дизъюнкция(+)
и логическое
умножение –
конъюнкция(∙))
и одна унарная
операция(логическое
отрицание(
)).
Оно обладает
следующими
свойствами:
а)
Для
A,
B,
C
S

,
(замкнутость);
(коммутативные
законы);
(ассоциативные
законы);
(дистрибутивные
законы);
(свойства
идемпотентности);
в том и
только том
случае, если
(свойство
совместимости);
S содержит элементы 1 и 0 такие, что для всякого элемента

;
для каждого элемента 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.
Расчёты и полученные результаты.
По варианту задания находим 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