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

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

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

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

Кафедра ???

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

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

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

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

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

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

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

????

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

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

????

????

???

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

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

3 Сети Петри

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

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

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

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

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

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

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

ВВЕДЕНИЕ

Работа посвящена синтезу дискретных устройств с “памятью” (конечных

автоматов) и “без памяти” (комбинационных схем), а также анализу реально

протекающих процессов с помощью сетей Петри.

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

виде СДНФ, с помощью двух различных способов : карт Карно и метода

склеивания Квайна – МакКласки. Полученные в виде минимизированных ДНФ

функции были приведены к базисам, состоящим всего из одной функции : И – НЕ

и ИЛИ – НЕ , а затем реализованы в виде комбинационных схем на

соответствующих логических элементах.

Во второй части заданный по условию в функциональном виде конечный

автомат был минимизирован по числу состояний. Для полученного автомата был

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

выходных сигналов и сигналов состояния, в автомате были выделены элементы

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

переменнных. Автомат был реализован в базисе И – ИЛИ – НЕ с использованием

D - триггера и задержки.

В третьей части была проанализирована заданная сеть Петри с помощью

двух способов: матричного и основанного на построении дерева покрываемости,

а также написана программа для её моделирования.

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

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

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

[pic] (1.1.1)

[pic], (1.1.2)

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

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

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

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

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

в) реализовать в виде комбинационной схемы на логических элементах F1

– в базисе И – НЕ, F2 – в базисе ИЛИ – НЕ, предварительно приведя F1 и F2

к соответствующим базисам.

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

[pic]

(1.1.3)

[pic]

(1.1.4)

при g0 = A, z0 = B . Параметр [pic] изменять от 1 до тех пор, пока не

будет получено 9 различных значений gi и zi.

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

Булевой алгеброй называется множество S объектов A, B, C…, в котором

определены две бинарные операции (логическое сложение – дизъюнкция(+) и

логическое умножение – конъюнкция(?)) и одна унарная операция(логическое

отрицание([pic])). Оно обладает следующими свойствами:

а) Для [pic] A, B, C [pic] S

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

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

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

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

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

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

[pic] (свойство совместимости);

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

[pic];

8) для каждого элемента A класс S содержит элемент Г (дополнение

элемента A, часто обозначаемое символами ? или 1- A ) такой, что

[pic], [pic].

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

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

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

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

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

быть равна любому элементу булевой алгебры, то булевой функцией называется

выражение

[pic]

(1.2.1)

В каждой булевой алгебре существует ровно [pic]различных булевых

функций n переменных.

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

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

системы.

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

достижение минимума букв в записи функции.

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

Любую булеву функцию n переменных, заданную в ДНФ или СДНФ, можно

отобразиь на n-мерном кубе, построенном в ортогональном базисе n булевых

переменных. Каждое слагаемое в ДНФ или СДНФ представляется гиперплоскостью

соответствующей размерности: если оно представляет собой конъюнкцию n

переменных – точка, n-1 переменных – прямая, n-2 переменных – плоскость и

т.д. Элементы n-мерного куба, имеющие s измерений, назовём s-кубами.

Комплекс K(y) кубов функции y=f(x1,x2,…,xn) есть объединение Ks(y)

множеств всех её кубов. Отсутствующие в конъюнкциях переменные будем

обозначать через x.

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

По варианту задания находим 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 получаем выражение

[pic], (1.3.1)

для F2:

[pic]. (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:

[pic]. (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, принимающем произвольное значение.

| |0 |0 |0 |0 |0 |1 |1 |1 |1 | |

|K0 |0 |0 |1 |1 |1 |0 |0 |1 |1 |Импликанты |

| |0 |1 |0 |0 |1 |0 |1 |0 |1 | |

|z |0 |0 |0 |1 |0 |1 |0 |0 |0 | |

|1001 | | | | | |+ | | | |[pic] |

|010x | | |+ |+ | | | | | |[pic] |

|0xx0 |+ |+ |+ | |+ | | | | |[pic] |

|xx10 | |+ | | |+ | |+ | |+ |[pic] |

|x1x0 | | |+ | |+ | | |+ |+ |[pic] |

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

Существенной импликантой, или экстремалью, называется такая

импликанта, которая в единственном числе покрывает хотя бы один из K0-

кубов.

Из таблицы следует, что все импликанты являются экстремалями.

Следовательно, они все войдут в запись функции в виде сокращённой ДНФ:

[pic]. (1.3.7)

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

сигналов которого в момент времени tm определяется так:

yj(tm) = f ( x1(tm), x2(tm),…,xn(tm)) ,

(1.3.8)

где [pic]. Видно, что выходной сигнал в m-й момент времени

определяется только комбинацией входных сигналов в данный момент и не

зависит от их предыдущих значений. Поэтому комбинационную схему можно

реализовать на логических элементах, выполняющих операции из определённого

базиса булевых функций.

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

[pic] (1.3.9)

[pic][pic] . (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 ,

[pic] .

Требуется:

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

автомата;

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

полученных ранее;

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

матрицу переходов;

г) переходя ко двоичному представлению входа X, выхода Y и

состояния S, составить таблицу входов и выходов комбинационной схемы

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

состояниям автомата;

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

элементы памяти на триггерах и задержках.

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

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

сигналы которого в определённые моменты времени зависят не только от

последнего пришедшего входного сигнала, но и от некоторого количества

предыдущих его значений.

Различают синхронные и асинхронные автоматы. У асинхронных смена

выходных сигналов y(tj) может происходить только в моменты изменения

входных x(tj) , у синхронных – в моменты времени, определяемые

дополнительным синхронизирующим сигналом c(t) .

Определим множества, которым могут принадлежать входные и выходные

сигналы (условимся обозначать tj как j):

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

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

[pic]

(2.2.1)

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

Пусть [pic]. Тогда если y(j) = ?(x(j)), то этот автомат является,

очевидно, комбинационной схемой.

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

состояние автомата в каждый момент времени j:

[pic]

(2.2.2)

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

называют конечным.

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

способами. Одна из возможных форм записи:

[pic]

(2.2.3)

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

это – более информативная форма записи по сравнению с автоматом Мура:

[pic][pic]

(2.2.4)

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

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