Державний комітет Російської Федерації з вищої освіти
Кубанський державний технологічний університет
Кафедра ???
ПОЯСНЮВАЛЬНА ЗАПИСКА
до курсової роботи по предмету математичні основи теорії систем
тема курсової роботи:
«Синтез комбінаційних схем і кінцевих автоматів. Мережі Петрі ».
Виконав: студент гр. ??-??-??
????
номер залікової книжки ??-??-???
Керівник:
????
????
???
1999
Державний комітет Російської Федерації з вищої освіти
Кубанський державний технологічний університет
ЗАВДАННЯ
На курсову роботу
Студенту гр.
З дисципліни
Тема курсової роботи
Вихідні дані
1 Виконати розрахунки:
1.1
1.2
1.3
1.4
2 Виконати графічні роботи:
2.1
2.2
3 Виконати наукові та навчально-дослідницькі роботи:
3.1 < p> 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. Постановка завдання
Для двох бульових функцій, побудованих за варіантом завдання у вигляді
(1.1.1)
, (1.1.2) < p> де gi, zi - десяткові числа з діапазону від 0 до 15 в двійковому вигляді,зробити наступне: а) представити F1 і F2 у вигляді СДНФ. б) мінімізувати (за кількістю змінних в ДНФ) F1 здопомогою карт Карно, F2 - методом Квайна-МакКласкі. в) реалізувати у вигляді комбінаційної схеми на логічних елементах F1
- В базисі І - НЕ, F2 - в базисі АБО - НЕ, попередньо привівши F1 і F2до відповідних базисом. gi і zi обчислювати за виразами:
(1.1.3)
(1.1.4) < p> при g0 = A, z0 = B. Параметр змінювати від 1 до тих пір, поки небуде отримано 9 різних значень gi і zi.
2. Теоретичні відомості.
булевої алгеброю називається множина об'єктів S A, B, C ..., в якомувизначені дві бінарні операції (логічне додавання - диз'юнкція (+) талогічне множення - кон'юнкція (?)) і одна унарний операція (логічнезаперечення ()). Воно має такі властивості: а) Для A, B, CS
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 = 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 отримуємо вираз
, (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 xx 1 1
0 xx 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 xxxx 0 xxxxxx 1 1 xx 1
K2 = xx 1 1 xx = 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 | | | | | | + | | | | |
| 010x | | | + | + | | | | | | |
| 0xx0 | + | + | + | | + | | | | | |
| xx10 | | + | | | + | | + | | + | |
| x1x0 | | | + | | + | | | + | + | |
Таблиця 1.3.1 - Покриття K0-кубів
Суттєвою імплікантой, або екстремали, називається такаімпліканта, яка в однині покриває хоча б один з K0 -кубів.
З таблиці випливає, що всі імпліканти є екстремалами.
Отже, вони всі увійдуть до запису функції у вигляді скороченої ДНФ:
. (1.3.7)
комбінаційних схем - це дискретний пристрій, кожен з вихіднихсигналів якого в момент часу tm визначається так:
yj (tm) = f (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 '.
Якщо для будь-якого існує принаймні одне,еквівалентне йому, то говорять, що M 'покриває M: M'? M.
Якщо одночасно M '? M і M? M ', то M ~ M'. Отримуємоеквівалентні автомати. У цьому випадку неможливо розрізнити M і M 'по їхреакції на вхідні сигнали.
Існують два основних положення визначення поняття еквівалентностістанів: а) стану si і sj явно різні, якщо відповідні їм рядкав таблиці виходів різні; б) стану si і sj явно еквівалентні, якщо відповідні їмрядка в загальній таблиці переходів автомата однакові або стають такимипри заміні si на sj або навпаки.
Мінімізація (спрощення) автоматів засноване на понятті еквівалентнихавтоматів. Під мінімізацією автомата будемо розуміти скорочення числа йогостанів.
2.3 Розрахунки і отримані результати.
Побудова таблиць переходів, виходів та загальної таблиці переходів івиходів на основі заданих рівнянь автомата Милі очевидно:
| | 0 | 1 | 2 | 3 |
| x (j) | | | | |
| s (j) | | | | |
| 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 - Таблиця виходів автомата
| | 0 | 1 | 2 | 3 |
| x (j) | | | | |
| s (j) | | | | |
| 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 - Таблиця переходів автомата
| | 0 | 1 | 2 | 3 |
| x (j) | | | | |
| s (j) | | | | |
| 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.
Наступним кроком оформляємо загальну таблицю переходів для мінімізовануформи автомата:
| | 0 | 1 | 2 | 3 |
| x (j) | | | | |
| s (j) | | | | |
| 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)
безліч позицій (кінцеве),
T = (t1, t2, ..., tm), m> 0
(3.2.3)
безліч переходів (кінцеве),
I: T> P
(3.2.4)
функція входів (відображення безлічі переходів під вхідні позиції),
O: T> P
(3.2.5)
функція виходів (відображення безлічі переходів у вихідні позиції).
Якщо pi I (tj), то pi - вхідна позиція j - го переходу,якщо pi I (tj), то pi - вихідна позиція j - го переходу.
Для наочного подання мереж Петрі використовуються графи.
Граф мережі Петрі є дводольних орієнтований мультіграф
G = (V ,),
(3.2.6)
де V = PUT, причому P? T = Ш.
Виходячи з графічного представлення мережі Петрі, її можна визначити ітак:
C = (P, T, A),
(3.2.7)
де А - матриця інцідентності графа мережі.
Визначимо поняття маркованої мережі Петрі - воно є ключовим длябудь-якої мережі.
Маркування? мережі Петрі C = (P, T, I, O) є функція:
N =? (P), NN,
(3.2.8)
відображає безліч позицій на безліч натуральних чисел. Маркуванняможна також визначити як вектор:
? = (? 1, № 2, ...,? N),
(3.2.9)
де n = | P |, а? I N. Між цими визначеннями є зв'язок:
? I =? (pi)
(3.2.10)
На графі маркування відображається ссответствующім числом точок в кожнійпозиції. Точки називаються маркерами або фішками. Якщо фішок багато (більшетрьох), то їх кількість відображається числом.
Таким чином, маркована мережа Петрі є п'ятіркуелементів:
M = (P, T, I, O, ?).
(3.2.11)
Приклад найпростішої мережі Петрі:
p1
??? t1 p3
p2?
Малюнок 3.2.1 - Приклад мережі Петрі
Правила роботи з мережами Петрі.
Мережа Петрі виконується за допомогою запуску переходів. Перехід можебути запущений в тому випадку, коли він дозволений. Перехід є дозволеним,якщо кожна з його вхідних позицій містить число фішок не менше, ніжчисло дуг з неї в даний перехід.
Процедура запуску полягає у видаленні з кожної вхідної позиціїпереходу числа фішок, рівного числа дуг з неї, і в виставленні в кожнійвихідний позиції числа фішок, рівного числа дуг, що входить до неї.
Проілюструємо сказане на прикладі вже намальованою мережі Петрі.
Запустимо в ній перехід t1 - він є дозволеним:
p1
? t1 p3
?
p2?
Малюнок 3.2.2 - Приклад запуску переходу мережі Петрі
Простір станів і поведінкові властивості мереж Петрі .
Нехай є маркована мережа Петрі:
M = (P, T, I, O,?)
(3.2.12)
У неї n позицій. У кожній позиції не більше N фішок. Тодіпростір сотоянии є безліч всіх можливих маркувань мережі.
Визначимо? - Функцію наступного стану.
Якщо перехід tj дозволений при поточній маркування? , То наступнамаркування? 'визначиться так:
?' =? (?, Tj)
(3.2.13)
Якщо перехід tj не дозволено, то? не визначена.
Нехай (tj0, tj1, ..., tjs) - послідовність запущених переходів.
Тоді їй буде відповідати послідовність (? 0,? 1, ...,? S +1), тобто
? K +1 =? (? K, tjk)
(3.2 .14)
На підставі останньої рівності можна визначити поняттябезпосередньо досяжною маркування. Для мережі C = (P, T, I, O)маркування? 'називається безпосередньо досяжною з? , Якщоіснує такий перехід tj T, при якому
? ' =? (?, Tj)
(3.2.15)
Можна поширити це поняття на безліч досяжних з даноїмаркувань. Визначимо безліч досяжних з? маркувань R (C,?)наступним чином: по - перше,? R (C,?), По - друге, якщо? 'R (C,?),?' =? (?, Tj) і?''= ?(?',tk), то й?''R (C, ?).
На основі введених понять можна сформулювати ряд властивостей мережі
Петрі, що характеризують її в процесі зміни маркувань - назвемо їхповедінковими властивостями мережі Петрі. Визначимо найбільш важливі з них.
1. Досяжність даної маркування. Нехай є деяка маркування
?, Відмінна від початкової. Тоді виникає питання досяжності: чи можна шляхом запуску певної поледовательності переходів перейти з початкової в задану маркування.
2. Обмеженість. Мережа Петрі називається k-обмеженою, якщо за будь-якої маркування кількість фішок в будь-якій з позицій не перевищує k. Зокрема, мережа називається безпечною, якщо k одно 1. Крім того, мережа називається однорідною, якщо в ній відсутні петлі і одинарної (простий), якщо в ній немає кратних дуг.
3. Активність. Мережа Петрі називається активною, якщо незалежно від дотігнутой з? 0 маркування існує послідовність запусків, що призводить до запуску цього переходу.
Реально вводять поняття декількох рівнів активності для конкретних переходів. Перехід tj T називається: а) пасивним (L0-активних), якщо він ніколи не може бути запущений; б) L1-активним, якщо він може бути запущений послідовністю переходів з? 0 хоча б один раз; в) L2-активним, якщо для будь-якого числа K існує послідовність запусків переходів з? 0, при якій цей перехід може спрацювати K і більше разів; г) L3-активним, якщо він є L2-активним при K>
?.
4. Оборотність. Мережа Петрі оборотна, якщо для будь-якої маркування?
R (C,? 0) маркування? 0 досяжна з?.
5. Покриваемость. Маркування? покриваема, якщо існує інша маркування? 'R (C,? 0) така, що в кожній позиції?' фішок не менше, ніж у позиціях маркування?.
6. Стійкість. Мережа Петрі називається стійкою, якщо для будь-яких двох дозволених переходів спрацьовування одного з них не призводить до заборони спрацювання іншого.
Існують два основні методи аналізу мереж Петрі: матричні ізасновані на побудові дерева покриваемості.
Перша група методів заснована на матричному поданні маркувань іпослідовностей запуску переходів. Для цього визначимо дві матрицірозмірності кількість позицій кількість переходів, пов'язані зіструктурою мережі. Перша матриця називається матрицею входів:
D - [i, j] = # (pi, I (tj )),
(3.2.16)
кожен її елемент дорівнює числу фішок, що йдуть з j-й позиції при запускуi-го переходу. Друга матриця називається матрицею виходів:
D + [i, j] = # (pi, O (tj )),
(3.2.17)
кожен її елемент дорівнює числу фішок, що приходять у j-у позицію під час запуску i-го переходу. Визначимо одиничний вектор e [j] розмірності m,містить нулі у всіх позиціях крім тієї, яка відповідаєяка завантажується в даний момент переходу. Очевидно, що перехід дозволений, якщо
? ? e [j] · D -. Тоді результат запуску j-го переходу можна описати так:
? '=? + E [j]? D,
(3.2.18)
де D = (D + - D -) - матриця змін. Тоді всі сформульованіраніше проблеми мережі Петрі легко інтерпретуються матричними рівняннямивиду
? =? 0 +?? D,
(3.2.19)
де? - Досліджувана маркування,? - Вектор, компоненти якогопоказують, скільки разів спрацьовує кожен перехід.
Хоча даний метод досить простий, він не позбавлений деяких недоліків.
А саме, його застосування дає лише необхідні умови існування якого-небудь властивості, іншими словами, може гарантувати лише його відсутність, а проприсутності ми зможемо говорити з упевненістю, тільки проаналізувавшидерево покриваемості (зміни) маркувань.
Дерево маркувань мережі - це пов'язаний граф, у вершинах якогознаходяться маркування, яких ми досягли в результаті послідовногозапуску дозволених переходів, а на дугах, що з'єднують вершини - зпускаемиепереходи. Шлях від кореня до кожної маркування відображає послідовністьзапусків, що привела до неї. Коренем дерева є початкова маркування. Принеобмеженій накопичення фішок у позиції на дереві утворюється петля, а вмаркування на місці, що відповідає зациклилися позиції, ставиться? --символ нескінченно великого числа.
Ясно, що цей метод хоча і вимагає стомлюючого перебору всіхможливих маркувань мережі, але зате по вже готовому дереву досить легкоаналізувати проблеми досяжності, покриваемості, активності, оборотностімережі.
Описавши поведінкові властивості та методи аналізу, можна перейтибезпосередньо до аналізу конкретної мережі Петрі.
3.3 Розрахунки і отримані результати
Вихідна мережу у вигляді графа:
p1 p6
?
?
t1? p4 t4
p2 p7
t2? p5 t5
p3 p8
t3 t6
Малюнок 3.3.1 - Вихідна мережа Петрі
Для матричного аналізу мережі знайдемо її матрицю змін .
(3.3.1)
(3.3.2)
Матрицю змін знайдемо як різниця між (3.3.2) та (3.3.1):
(3.3.3)
Таким чином, отримавши матрицю змін, можна записати матричнерівняння зміни маркувань виду (3.2.19). Вектор початкової маркуваннявизначимо так:
? 0 = (10011100)
(3.3.4)
Складемо дерево покриваемості маркувань мережі.
(10011100 ) 'Нова'
t1t4
'Нова'
'Нова'
(01001100) (10010010)
t2 t4t1 t5
(00100100) (01000010) (01000010)
(10000001)
'Нова' 'Тупик' 'Тупик'
'Нова' t3 t6
(10011100) 'Стара'
(10011100) 'Стара'
Малюнок 3.3.1 - Дерево покриваемості маркувань
Дерево покриваемості зручно оформити у вигляді графа. При цьому більшенаочно видно зациклюються переходи, тупикові маркування ніякимидодатковими поясненнями постачати не потрібно - відсутність дуг,вихідних з даної маркування, говорить саме за себе. При досягненні староїмаркування її не потрібно заново наносити на граф - досить з'єднати дугоюпопередню маркування і вже існуючу "стару".
Граф покриваемості мережі виглядає наступним чином:
? 0 t3 t6
10011100
00100100 t1t4 10000001
t2 t5
01001100 10010010
t4 t1
01000010
Малюнок 3.3.2 - Граф покриваемості маркувань мережі Петрі
Проаналізуємо мережа двома методами - матричним і графічним і порівняємоотримані результати.
Питання досяжності будь-якого маркування легше за все вирішується, дивлячисьна граф покриваемості. Дійсно, візьмемо для прикладу дві маркування:
? 1 = (01000010) і? 2 = (00100010). Перша з них досяжна, і можливідва шляхи приходу до неї: t1, t4 або t4, t1. Проте вони не єдині,перед другим запуском переходу можливо нескінченне число раз запустити дляпершого випадку послідовність t2, t3, для другого випадку - t5, t6
. Друга маркування явно недосяжна, тому що її немає на графі.
За допомогою матриць це питання вирішується в такий спосіб. Складаєморівняння виду (3.2.19), у якому замість? ставимо невідомий вектор xтієї ж розмірності, а замість? - Нас цікавить, маркування? 1. У підсумкуотримуємо систему з 8 рівнянь відносно 6 невідомих компонентвектора x.
(3.3.5)
Проаналізувавши дану систему, бачимо, що п'яте рівняння єнаслідком з третього та шостого, шосте - з сьомого та восьмого, перший --з другого і третього. З (1) та (4) випливає, що x5 = 0, x6 = 0, з
(7) випливає, що x4 = 1. Перші три рівняння в (3.3.5) є лінійнозалежними, тому за вільне невідоме приймемо x1. Тоді одержуєморішення у вигляді x1 = (y y-1 y-1 1 0 0), де y - будь-яке ціле число.
Отримане рішення говорить про досяжності маркування? 1 і вказує,які з переходів і скільки разів повинні бути для цього запущені.
Порівнявши обидва способи рішення, відразу можна побачити недоліки другого.
По-перше, рішення (3.3.5) не вказує, в якій самепослідовності повинні бути запущені зазначені переходи.
По-друге, дивлячись на матрицю змін, ми не можемо судити про наявність у мережіпетель. Крім того, отримане матричне рішення не дає, взагалі кажучи,гарантій своєї реалізованості - воно є лише необхідною умовоюдосяжності. Однак, не отримавши рішення, можна говорити про недосяжностімаркування.
Дійсно, записав (3.2.19) для? 2, отримуємо систему:
(3.3.6)
Система є несумісні, тому що після вирахування третійрівняння з шостого отримуємо рівняння, що суперечить п'ятий. Томуможна зробити висновок про недосяжності? 2, що співпадає з отриманим з графапокриваемості маркувань.
Виходячи з графа (3.3.2), можна зробити висновок, що мережа єбезпечною. Дійсно, ні в одній з позицій на маркування ненакопичується більше однієї фішки. Це говорить про те, що реальний процес,описуваний мережею, протікає без конфліктів. Однак про повну відсутністьконфліктів говорити поки рано. Даний висновок неможливо отримати зматричного рівняння, так як він є узагальненням, зробленим на основізнання всіх можливих маркувань, що виходять в мережі.
Дана мережа є активною - в ній кожен перехід може спрацюватихоча б один раз. Проаналізуємо рівні активності окремих переходів.
Переходи t1 і t4 є L1-активними, тому що вони в гіршому випадку
(тобто при отримання тупикової маркування) можуть спрацювати хоча б одинразів. Переходи t2, t3, t5 і t6 є L2-активними, так як вони можутьспрацювати будь-який наперед задане число разів і навіть більше.
Звідси можна зробити висновок про те, що дана мережа не єбезконфліктної - у неї є тупикове стан.
Можна також сказати, що мережа є оборотної. Цей висновок можнаотримати і матричним шляхом - вирішивши рівняння
x · D = 0
(3.3.7)
Отримуємо систему
(3.3.8)
Дана система має 2 рішення: (yyy 0 0 0) і (0 0 0 yyy), де y - будь-яке. Дійсно, запускаючи будь-яке число раз послідовності t1t2 t3 або t4 t5 t6, кожного разу ми повертаємося до вихідної маркування.
З графа (3.3.2) також випливає, що жодна з маркувань мережі неє покривається. Дійсно, ні для однієї маркування не існуєіншої такої, для якої в кожній позиції було б не менше фішок, ніж увихідної.
Можна сказати, що дана мережа не є стійкою. У неї єглухий кут, і, крім того, безпосередньо перед переходом в тупиковестан завжди існують дві дозволених переходу. Запускаючи
'неправильний' перехід, ми забороняємо обидва - і опиняємося в глухому куті. Такевластивість мережі говорить про наявність потенційно можливих конфліктів.
Па підставі графа (3.3.2) можна виписати безліч досяжних з
? 0 маркувань:
(3.3.9)
Для моделювання мережі була написана програма на мові Turbo Pascal.
Вона відображає стан мережі та дозволені в кожен момент переходи. Длявибору запускається переходу використовується миша.
3.4 Висновки по розділу
У даному розділі биа проаналізовано і змодельована мережа Петрі,яка є моделлю функціонування двох виробничих процесів,пов'язаних двома спільними ресурсами. В результаті можна зробити висновок пропринциповому наявності в системі тупикової ситуації, яка виникає приспробі одночасного запуску обох процесів на виконання. Щоб невиникало глухого кута, необхідно кожен з процесів доводити до завершення, іне запускати інший процес, поки не закінчені всі три цикли першим. Всівищесказане повністю підтверджується написаною програмою, що моделюєвсі описані ситуації, що виникають в мережі.
ВИСНОВОК
У роботі були розглянуті питання спрощення і синтезу дискретнихдвійкових пристроїв з 'пам'яттю' і без неї, а також проаналізовано мережу
Петрі, моделююча конкретний виробничий процес і зробленівідповідні висновки щодо самого процесу.
ЛІТЕРАТУРА
1. Сигорський В.П. Математичний апарат інженера .- Київ: Техніка,
1975. -538 С.
2. Г. Корн, Т. Корн Довідник з математики для науковців та інженерів .- М.: Наука, 1984. -831 С.
3. В. Брауер Введення в теорію кінцевих автоматів .- М.: Радіо і зв'язок,
1987. -392 С.
4. Фаронов В.В. Турбо Паскаль 7.0: практика програмування. - М.:
Нолидж, 1997. -432 С.
Додаток А
Програма моделювання мережі Петрі
Program Farewell_Pascal_Please_Forgive_Me;
Uses graph, crt;
Const m_0 = $ 9C; r_0 = $ 90; path = 'cursor.dat'; mask: array [0 .. 5] of byte = ($ 90, $ 48, $ 20, $ 0C, $ 12, $ 01); jump: array [0 .. 5] of word = ($ 406F, $ 20B7, $ 98DF, $ 02F3, $ 01ED, $ 1CFE);
