1. ПОБУДОВА ОБ'ЄДНАНОЇ ГСА
1. ПОБУДОВА ОБ'ЄДНАНОЇ ГСА
1.1. Побудова ГСА
По описах граф-схем, приведених в завданні до курсової роботи, побудуємо ГСА Г1-Г5 (мал. 1.1-1.5), додавши початкові і кінцеві вершини і замінивши кожний оператор Yi операторною вершиною, а кожну умову Xi - умовною.
1.2. Методика об'єднання ГСА
У ГСА Г1-Г5 є однакові ділянки, тому побудова автоматів за ГСА Г1-Г5 приведе до невиправданих апаратурних витрат. Для досягнення оптимального результату скористаємося методикою С.І.Баранова, яка дозволяє мінімізувати число операторних і умовних вершин. Заздалегідь помітимо операторн вершини в початкових ГСА, керуючись слдуючими правилами:
1) однакові вершини Yi в різних ГСА відмічаємо однаковими мітками Aj;
2) однакові вершини Yi в межах однієї ГСА відмічаємо різними мітками Aj;
3) у всіх ГСА початкову вершину помітимо як А0, а кінцеву - як Ak.
На наступному етапі кожнй ГСА поставимо у відповідність набір змінних Pn {P1...Pq}, де q=]log2N[, N -кльксть ГСА. Означувальною для ГСА Гn ми будемо називати кон`юнкцию Pn=p1e...pqn е{0,1}, причому p0=р, p1=р. Об'єднана ГСА повинна задовольняти слдуючим вимогам:
1) якщо МК Ai входить хоча б в одну часткову ГСА, то вона входить і в об'єднану ГСА Г0, причому тільки один раз;
2) при підстановці набору значень (е1...en), на якому Pq=1 ГСА Г0 перетворюється в ГСА, рівносильну частковй ГСА Гq.
При об'єднанні ГСА виконаємо слдуючі етапи:
-сформуємо часткові МСА М1 - М5, що відповідні ГСА Г1 - Г5;
- сформуємо об'єднану МСА М0;
- сформуємо системи дужкових формул переходу ГСА Г0;
- сформуємо об'єднану ГСА Г0.
1.3. Об'єднання часткових ГСА
Часткові МСА М1-М5 побудуємо по ГСА Г1-Г5 (мал.1.1) відповідно. Рядки МСА відмітимо всіма мітками Ai, що входять до ГСА, крім кінцевої Ak.
ПОЧАТОК A0
1
0 X1 1
2
A1
3
0
4 X2 A2 1
5
A3
6
A4
7
A5
8
A6
9
A7
10
A8
КНЕЦь Ak
Мал.1.1. Часткова граф-схема алгоритму Г1
ПОЧАТОК A0
1
A1
2
A7
0 3 1
X3
4 5
A9 A6
6 7
A10 A12
8 9
A3 A22
10
A11
КНЕЦЬ Ak
Мал.1.2. Часткова граф-схема алгоритму Г2
ПОЧАТОК A0
1
A11
0 2 1
X1
3 4
A15 A16
6
5 1
X3 A12
0
7 8
A6 A13
КНЕЦЬ Аk
Мал.1.3. Часткова граф-схема алгоритму Г3
ПОЧАТОК A0
1
0 1
X1
2
A13
3
A9
4
A8
5
1 X2
6 0
A17
7
A6
8
A2
9
A18
КНЕЦЬ Ak
Мал.1.4. Часткова граф-схема алгоритму Г4
ПОЧАТОК A0
1
A1
2
A6
3
A19
4
0 1
X1
5
0 X2
1
6
A20
7
A17
8
A2
9
A21
КНЕЦЬ Ak
Мал.1.5. Часткова граф-схема алгортиму Г5
Стовпці МСА відмітимо всіма мітками Ai-, що входять до ГСА, крім початкової A0. На перетині рядка Ai і стовпця Aj запишемо формулу переходу fij від оператора Ai до оператора Aj. Ця функція дорвню 1 для безумовного переходу або кон`юнкц логічних умов, відповідних виходам умовних вершин, через які проходить шлях з вершини з мткою Ai у вершину з мткою Aj.
За методикою об'єднання закодуємо МСА таким чином:
Таблиця 1.1
Кодування МСА
МСА | P1P2P3
М1 | 0 0 0 (p1p2p3)
М2 | 0 0 1 (p1p2p3)
М3 | 0 1 0 (p1p2p3)
М4 | 0 1 1 (p1p2p3)
М5 | 1 0 0 (p1p2p3)
Частков МСА М1-М5 наведен в табл.1.2-1.6
Таблиця 1.2
Часткова МСА М1 |
A1 | A2 | A3 | A4 | A5 | A6 | A7 | A8 | Ak
A0 | x1 | x1x2 | x1x2
A1 | 1
A2 | | 1
A3 | 1
A4 | 1
A5 | 1
A6 | 1
A7 | 1
A8 | 1
Таблиця 1.3
Часткова МСА М2 |
A1 | A3 | A6 | A7 | A9 | A10 | A11 | A12 | A22 | Ak
A0 | 1
A1 | 1
A3 | 1
A6 | 1
A7 | x3 | x3
A9 | 1
A10 | 1
A11 | 1
A12 | 1
A22 | 1
Таблиця 1.4
Часткова МСА М3 |
A6 | A12 | A13 | A14 | A15 | A16 | Ak
A0 | 1
A6 | 1
A12 | 1
A13 | 1
A14 | x1 | x1
A15 | x3 | x3
A16 | 1
Таблиця 1.5
Часткова МСА М4 |
A2 | A6 | A8 | A9 | A13 | A17 | A18 | Ak
A0 | x1 | x1
A2 | 1
A6 | 1 |
A8 | x2 | x2
A9 | 1
A13 | 1
A17 | 1
A18 | 1
Таблиця 1.6
Часткова МСА М5 |
A1 | A2 | A6 | A17 | A19 | A20 | A21 | Ak
A0 | 1
A1 | 1
A2 | 1
A6 | 1
A17 | 1
A19 | x1x2 | x1x2 | x1
A20 | 1
A21 | 1
На наступному етапі побудуємо об'єднану МСА М0, в якй рядки відмічені всіма мітками Аi, крім Аk, а стовпці - всіма,