Реферат Прикладная теория цифровых автоматов 2
Работа добавлена на сайт bukvasha.net: 2015-10-28Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
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.
2
A1
A3
6
A4
7
A5
A6
9
A7
10
Мал.1.1. Часткова граф-схема алгоритму Г1
2
A7
4 5
6 7
A10 A12
8 9
A3 A22
10
A11
Мал.1.2. Часткова граф-схема алгоритму Г2
1
A11
5 1
7 8
Мал.1.3. Часткова граф-схема алгоритму Г3
0 1
2
A13
3
A9
A8
1 X2
A17
7
A6
A2
9
A18
Мал.1.4. Часткова граф-схема алгоритму Г4
1
A1
2
A6
3
A19
0 1
0 X2
6
A20
7
A17
A2
A21
Мал.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", а його інверсію на “0". Наприклад, у вершину А3 перехід здійснюється при незмінному значенні ùp1 і ùp2, отже в рядку А3 ùp1 і ùp2 замінимо на “1", а p1 і p2 на “0". У результаті отримаємо формули F3,4=ùp3, F3,11=p3. Керуючись вищенаведеним методом, отримаємо мінімізовану МСА М0 (табл.1.8).
По таблиці складемо формули переходу для об'єднаної ГСА Г0. Формулою переходу будемо називати слідуюче вираження: Ai®Fi,1А1+..+Fi,kАk, де Fi,j- відповідна формула переходу з мінімізованої МСА. У нашому випадку отримаємо слідуючу систему формул:
A0®ùx1ùp1ùp2ùp3A1+ùp1ùp2p3A1+p1ùp2ùp3A1+x1ùx2ùp1ùp2ùp3A2+x1x2ùp1ùp2ùp3A3+
+ùx1ùp1p2p3A8+x1ùp1p2p3A13+ùp1p2ùp3A14
A1®ùp1ùp3A2+p1ùp3A6+ùp1p3A7
A2®ùp1ùp2ùp3A6+ùp1p2p3A18+p1ùp2p3A21
A3®ùp3A4+p3A11
A4®A5
A5®А6
