Побудова об'єднаної ГСА

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, а стовпці - всіма, крім А0. На перетині рядка Аi і стовпця Аj запишемо формулу переходу, яка формується таким чином: Fij=P1fij1+...+Pnfijn (n=1...N). Де fijn-формула переходу з вершини Аi у вершину Аj для n-о ГСА. Наприклад, формула переходу А0А1 буде мати вигляд F0,1=x1p1p2p3+ p1p2p3+ +p1p2p3. У результаті ми отримаємо об'єднану МСА М0 (табл.1.7). Ми маємо можливість мінімізувати формули переходу таким чином: розглядаючи ГСА Г0 як ГСА Гn, ми підставляємо певний набір Pn=1, при цьому змнн p1..pq не змінюють своїх значень під час проходу по ГСА. Таким чином, якщо у вершину Аi перехід завжди здійснюється при незмінному значенні pq, то це значення pq в рядку Аi замінимо на “1", а його інверсію на “0". Наприклад, у вершину А3 перехід здійснюється при незмінному значенні p1 і p2, отже в рядку А3 p1 і p2 замінимо на “1", а p1 і p2 на “0". У результаті отримаємо формули F3,4=p3, F3,11=p3. Керуючись вищенаведеним методом, отримаємо мінімізовану МСА М0 (табл.1.8).
По таблиці складемо формули переходу для об'єднаної ГСА Г0. Формулою переходу будемо називати слдуюче вираження: AiFi,1А1+..+Fi,kАk, де Fi,j- відповідна формула переходу з мінімізованої МСА. У нашому випадку отримаємо слдуючу систему формул:
A0x1p1p2p3A1+p1p2p3A1+p1p2p3A1+x1x2p1p2p3A2+x1x2p1p2p3A3+
+x1p1p2p3-A8+x1p1p2p3A13+p1p2p3A14
A1p1p3A2-+p1p3A6+p1p3A7
A2p1p2p3A6+p1p2p3A18+p1p2p3A21
A3p3A4+p3A11
A4A5
A5А6


Таблиця 1.7
Об`днана МСА Мo |
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
A8 |
A9 |
A10 |
A11 |
A12 |
A13 |
A14 |
A15 |
A16 |
A17 |
A18 |
A19 |
A20 |
A21 |
A22 |
Ak
A0 | _ _ _ _
x1p1p2p3+
_ _
+p1p2p3+
_ _
+p1p2p3 |
_ _ _ _
x1x2p1p2p3 | _ _ _
x1x2p1p2p3 | _ _
x1p1p2p3 | _
x1p1p2p3 | _ _
p1p2p3
A1 |
_ _ _
p1p2p3 | _ _
p1p2p3 | _ _
p1p2p3
A2 |
_ _ _
p1p2p3 | _
p1p2p3 | _ _
p1p2p3
A3 |
_ _ _
p1p2p3 | _ _
p1p2p3
A4 |
_ _ _
p1p2p3
A5 |
_ _ _
p1p2p3
A6 |
_
p1p2p3 | _ _ _
p1p2p3 | _ _
p1p2p3 | _ _
p1p2p3 | _ _
p1p2p3
A7 |
_ _
x3p1p2p3 | _ _ _
p1p2p3 | _ _ _
x3p1p2p3
A8 | _
x2p1p2p3 | _ _ _
p1p2p3+
_ _
+x2p1p2p3
A9 |
_
p1p2p3 | _ _
p1p2p3
A10 |
_ _
p1p2p3
A11 |
_ _
p1p2p3
A12 |
_ _
p1p2p3 | _ _
p1p2p3
A13 |
_
p1p2p3 | _ _
p1p2p3
A14 |
_ _ _
x1p1p2p3 | _ _
x1p1p2p3
A15 |
_ _
x3p1p2p3 | _ _ _
x3p1p2p3
A16 |
_ _
p1p2p3
A17 |
_ _
p1p2p3 | _
p1p2p3
A18 |
_
p1p2p3
A19 |
_ _ _
x1x2p1p2p3 |
_ _
x1x2p1p2p3 | _ _ _
x1p1p2p3
A20 |
_ _
p1p2p3
A21 |
_ _
p1p2p3
A22 |
_ _
p1p2p3
Таблиця 1.8
Об`днана мнмзована МСА Мo |
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
A8 |
A9 |
A10 |
A11 |
A12 |
A13 |
A14 |
A15 |
A16 |
A17 |
A18 |
A19 |
A20 |
A21 |
A22 |
Ak
A0 | _ _ _ _
x1p1p2p3+
_ _
+p1p2p3+
_ _
+p1p2p3 |
_ _ _ _
x1x2p1p2p3 | _ _ _
x1x2p1p2p3 | _ _
x1p1p2p3 | _
x1p1p2p3 | _ _
p1p2p3
A1 |
_ _
p1p3 | _
p1p3 | _
p1p3
A2 |
_ _ _
p1p2p3 | _
p1p2p3 | _ _
p1p2p3
A3 |
_
p3 |
p3
A4 |
1
A5 |
1
A6 |
_
p1p2p3 | _ _ _
p1p2p3 | _ _
p1p2p3 | _ _
p1p2p3 | _ _
p1p2p3
A7 |

x3p3 | _
p3 | _
x3p3
A8 |
x2p2p3 | _ _
p2p3+
_
+x2p2p3
A9 |
p2 | _
p2
A10 |
1
A11 |
1
A12 |
_
p2p3 | _
p2p3
A13 |
p3 | _
p3
A14 |
_
x1 |
x1
A15 |

x3 | _
x3
A16 |
1
A17 |
_ _
p1p2p3 | _
p1p2p3
A18 |
1
A19 |
_
x1x2 |
x1x2 | _
x1
A20 |

1
A21 |

1
A22 |
1


A6p1p2p3A2+p1p2p3A7+p1p2p3A121p2p3A19+p1p2p3Ak
A7x3p3A6+p3A8+x3p3A9
A8x2p2p3A17+p2p3Ak+x2p2p3Ak
A9p2-A8+p2A10
A10A3
A11Ak
A12p2p3A22+p2p3A13
A13p3A9+p3Ak
A14-x1A15+x1A16
A15x3A6+x3Ak
A16A12
A17p1p2p3A2-+p1p2p3A6
A18Ak
A19x1x2A2+x1x2A20+x1A21
A20-A17
A21Ak
A22Ak
При побудові системи дужкових формул переходу необхідно кожну формулу привести до вигляду Аx1+Вx1, де А і В -деякі вирази, а x1 і x1-логічн умови переходу. Формули переходу для вершин А3, А4, А5, А9, А10, А11, А13, А14, А15, А16, А18, А20, А21, А22 вже є елементарними (розкладеними), а в інших є вирази виду Аnxj(А) +xjpi(В). Тут pi відповідає чекаючій вершині (мал.1.6). Подібних вершин в об'єднанй ГСА бути не повинно. Для їх усунення скористаємося слдуючим правилом: додавання виразу [PqАn] не змінить формулу, якщо набір Pq не використовується для кодування ГСА або вершина Аn вдсутня в ГСА з кодом Pq. Таким чином, додаючи допоміжні набори, ми отримаємо можливість за допомогою елементарних перетворень звести формули до необхідного вигляду. Наприклад, формула A8x2p2p3A17+p2p3Ak+x2p2p3A спрощується таким чином A8=p3(x2p2A17+x2p2Ak)+p3p2Ak=p3p2(x2A17+x2Ak)+p3p2Ak=

1 Xj 0
Pi 0
1
Мал.1.6 Приклад чекаючо вершини Pi
=[p3p2(x2A17+x2Ak)]+p3p2(x2A17+x2Ak)+p3p2Ak+[p3p2Ak]=p2Ak+p2(x2A17+x2Ak). Тут вершина А8 не зустрчаться у ГСА ,в кодах яких присутн комбнац p3p2 p3p2. Нижче наведено розклад усх неелементарних формул переходу.

A0=p1(p2p3A1)+p1(x1p2p3A1+p2p3A1+x1x2p2p3-A2+x1x2p2p3A3-+
+x1p2p3A8+x1p2p3A13+p2p3A14)=p1(p2p3A1)+[p1p2p3A1]+
+p1(p2(x1p3A8+x1p3A13+p3A14)+p2(x1p3A1+p3A1+x1x2p3A2+
+x1x2p3A3-))=p1(p2A1)+[p1p2A1]+p1(p2(p3(x1A8+x1A13)+p3A14)+
+p2(p3(x1A1+x1x2A3+x1x2A23A1))= p1A1+p1(p2(p3( x1A8+
+x1A13)+p3A14)+p2(p3(x1A1+x1(x2A3+x2A2))+p3A1-))
A1=p1-(p3A7+p3A2)+p1p3A6+[p1p3A6]= p1-(p3A7+p3A2)+p1A6
A2=p1(p2p3A21)+p1(p2p3A6+p2p3A18)= p1(p2p3A21)+[p1p2p3A21]+
+p1-(p2p3A6+[p2p3A6]+p23A18+[p3p2A18])=p1(p2A21)+p1(p3A6+
+p3A18)=p1(p2A21)+[p1p2A21]+p1(p3A6+p3A18)=p1A21+p1(p3A6+
+p3A18)
A6=p1(p2p3A19)+[p1p2p3A19]+p1(p2p3A2+p2p3A7+p2p3A12+p2p3Ak)=
=p1p2A19+[p1p2A19]+p1(p2(p3A2+p3Ak)+p2(p3A7+p3A121A19+
+p1(p2(p3A2+p3Akp2(p3A7+p3A12))
A7=p3(x3A6+x3A9)+p3A8
A8=p3(x2p2A17+x2p2Ak)+p3p2Ak=p3p2(x2A17+x2Ak)+p3p2Ak=
=[p3p2(x2A17+x2Ak)]+p3p2(x2A17+x2Ak)+p3p2Ak+[p3p2Ak]=p2Ak+
+p2(x2A17+x2Ak)
A12=p2p3A22+p2p3A13+[p2p3A22]+[p2p3A13]=p3A22+p3A13
A17=p1p2p3A2+[p1p2p3A2]+p1p2p3A6+[p1p2p3A6-]=p1p2A2+[p1p2A2]+
+p1p3A6+[p1p3A6]=p1A2+p1A6-
A19=x1(x2A2+x2A20)+x1A21

Об'єднану ГСА Г0 (мал.1.7) побудуємо відповідно до формул переходу, замінюючи кожну мітку Аi відповідною операторною вершиною Yt, а кожний вираз Xi і Pj відповідними умовними вершинами.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать