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

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

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

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

Кафедра ???

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

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

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

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

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

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

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

                                                                                         ????

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

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

                                                                                          ????            

???

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

2.4   Выводы по разделу……………………………………………… 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.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.2  Теоретические сведения.

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

а) Для  A, B, C    S 

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

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

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

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

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

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

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

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

                        ;

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

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

Неповторяющиеся значения 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, принимающем произвольное значение.

Страницы: 1, 2, 3