Прикладная теория цифровых автоматов
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 |
| |((p1(p2(p3) |
|М2 |0 0 1 |
| |((p1(p2p3) |
|М3 |0 1 0 |
| |((p1p2(p3) |
|М4 |0 1 1 |
| |((p1p2p3) |
|М5 |1 0 0 |
| |(p1(p2(p3) |
Частков( МСА М1-М5 наведен( в табл.1.2-1.6
Таблиця 1.2
Часткова МСА М1
| | A1 | A2 | A3 | A4 | A5 | A6 | A7 | A8 | Ak |
| A0 | (x1 |(x1(x2| 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 | | x1(x2| | | | x1x2 | (x1 | |
| A20 | | | | 1 | | | | |
| A21 | | | | | | | | 1 |
На наступному етапі побудуємо об'єднану МСА М0, в як(й рядки
відмічені всіма мітками Аi, крім Аk, а стовпці - всіма, крім А0. На
перетині рядка Аi і стовпця Аj запишемо формулу переходу, яка
формується таким чином: Fij=P1fij1+...+Pnfijn (n=1...N). Де fijn-
формула переходу з вершини Аi у вершину Аj для n-о( ГСА. Наприклад,
формула переходу А0(А1 буде мати вигляд F0,1=(x1(p1(p2(p3+ (p1(p2p3+
+p1(p2(p3. У результаті ми отримаємо об'єднану МСА М0 (табл.1.7). Ми
маємо можливість мінімізувати формули переходу таким чином: розглядаючи
ГСА Г0 як ГСА Гn, ми підставляємо певний набір Pn=1, при цьому
зм(нн( p1..pq не змінюють своїх значень під час проходу по ГСА. Таким
чином, якщо у вершину Аi перехід завжди здійснюється при незмінному
значенні pq, то це значення pq в рядку Аi замінимо на “1", а його
Страницы: 1, 2, 3
|