Главная Учебники - Разные Лекции (разные) - часть 62
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 A2 A3 A4 A5 A6 A7 A8
Таблиця
1.3
Часткова
МСА М2 A1 A3 A6 A7 A9 A10 A11 A12 A22 Ak A0 A1 A3 A6 A7 x3 щx3 A9 A10 A11 A12 A22
Таблиця
1.4
Часткова
МСА М3 A6 A12 A13 A14 A15 A16 Ak A0 A6 A12 A13 A14 щx1 x1 A15 x3 щx3 A16
Таблиця
1.5
Часткова
МСА М4 A2 A6 A8 A9 A13 A17 A18 Ak A0 щx1 x1 A2 A6 A8 x2 щx2 A9 A13 A17 A18
Таблиця
1.6
Часткова
МСА М5 A1 A2 A6 A17 A19 A20 A21 Ak A0 A1 A2 A6 A17 A19 x1щx2 x1x2 щx1 A20 A21
На наступному
етапі побудуємо
об'єднану
МСА
М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
Таблиця
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
A6®щp1p2p3A2+щp1щp2щp3A7+щp1щp2p3A12+p1щp2щp3A19+щp1p2щp3Ak
A7®x3p3A6+щp3A8+щx3p3A9
A8®x2p2p3A17+щp2щp3Ak+щx2p2p3Ak
A9®p2A8+щp2A10
A10®A3
A11®Ak
A12®щp2p3A22+p2щp3A13
A13®p3A9+щp3Ak
A14®щx1A15+x1A16
A15®x3A6+щx3Ak
A16®A12
A17®p1щp2щp3A2+щp1p2p3A6
A18®Ak
A19®x1щx2A2+x1x2A20+щx1A21
A20®A17
A21®Ak
A22®Ak
При
побудові
системи дужкових
формул переходу
необхідно кожну
формулу привести
до вигляду
Аx1+Вщx1,
де А і В -деякі
вирази, а x1
і щx1-логічні
умови переходу.
Формули переходу
для вершин А3,
А4,
А5,
А9,
А10,
А11,
А13,
А14,
А15,
А16,
А18,
А20,
А21,
А22
вже є елементарними
(розкладеними),
а в інших є вирази
виду Аn®xj(А)
+щxjpi(В).
Тут pi
відповідає
чекаючій вершині
(мал.1.6). Подібних
вершин в об'єднаній
ГСА
бути не повинно.
Для їх усунення
скористаємося
слідуючим
правилом: додавання
виразу
[PqАn]
не змінить
формулу, якщо
набір Pq
не використовується
для кодування
ГСА
або вершина
Аn
відсутня в ГСА
з кодом Pq.
Таким чином,
додаючи допоміжні
набори, ми отримаємо
можливість
за допомогою
елементарних
перетворень
звести формули
до необхідного
вигляду.
Наприклад,
формула
A8®x2p2p3A17+щp2щp3Ak+щx2p2p3A
спрощується
таким чином
A8=p3(x2p2A17+щx2p2Ak)+щp3щp2Ak=p3p2(x2A17+щx2Ak)+щp3щp2Ak=
1 Xj 0
Pi 0
1
Мал.1.6
Приклад чекаючої
вершини Pi
=[щp3p2(x2A17+щx2Ak)]+p3p2(x2A17+щx2Ak)+щp3щp2Ak+[p3щp2Ak]=щp2Ak+p2(x2A17+щx2Ak).
Тут вершина
А8 не
зустрічається
у ГСА ,в кодах
яких присутні
комбінації
щp3p2
і
p3щp2.
Нижче наведено
розклад усіх
неелементарних
формул переходу.
A0=p1(щp2щp3A1)+щp1(щx1щp2щp3A1+щp2p3A1+x1щx2щp2щp3A2+x1x2щp2щp3A3+
+щx1p2p3A8+x1p2p3A13+p2щp3A14)=p1(щp2щp3A1)+[p1щp2щp3A1]+
+щp1(p2(щx1p3A8+x1p3A13+щp3A14)+щp2(щx1щp3A1+p3A1+x1щx2щp3A2+
+x1x2щp3A3))=p1(щp2A1)+[p1p2A1]+щp1(p2(p3(щx1A8+x1A13)+щp3A14)+
+щp2(щp3(щx1A1+x1x2A3+x1щx2A2)+p3A1))=
p1A1+щp1(p2(p3(
щx1A8+
+x1A13)+щp3A14)+щp2(щp3(щx1A1+x1(x2A3+щx2A2))+p3A1)) A1=щp1(p3A7+щp3A2)+p1щp3A6+[p1p3A6]=
щp1(p3A7+щp3A2)+p1A6
A2=p1(щp2p3A21)+щp1(щp2щp3A6+p2p3A18)=
p1(щp2p3A21)+[p1щp2p3A21]+
+щp1(щp2щp3A6+[p2щp3A6]+p2p3A18+[p3щp2A18])=p1(щp2A21)+щp1(щp3A6+
+p3A18)=p1(щp2A21)+[p1p2A21]+щp1(щp3A6+p3A18)=p1A21+щp1(щp3A6+
+p3A18) A6=p1(щp2щp3A19)+[p1щp2p3A19]+щp1(p2p3A2+щp2щp3A7+щp2p3A12+p2щp3Ak)=
=p1щp2A19+[p1p2A19]+щp1(p2(p3A2+щp3Ak)+щp2(щp3A7+p3A12))=p1A19+
+щp1(p2(p3A2+щp3Ak)+щp2(щp3A7+p3A12)) A7=p3(x3A6+щx3A9)+щp3A8 A8=p3(x2p2A17+щx2p2Ak)+щp3щp2Ak=p3p2(x2A17+щx2Ak)+щp3щp2Ak=
=[щp3p2(x2A17+щx2Ak)]+p3p2(x2A17+щx2Ak)+щp3щp2Ak+[p3щp2Ak]=щp2Ak+
+p2(x2A17+щx2Ak) A12=щp2p3A22+p2щp3A13+[p2p3A22]+[щp2щp3A13]=p3A22+щp3A13 A17=p1щp2щp3A2+[p1щp2p3A2]+щp1p2p3A6+[щp1щp2p3A6]=p1щp2A2+[p1p2A2]+
+щp1p3A6+[щp1щp3A6]=p1A2+щp1A6 A19=x1(щx2A2+x2A20)+щx1A21
Об'єднану
ГСА
Г0
(мал.1.7) побудуємо
відповідно
до формул переходу,
замінюючи кожну
мітку
Аi
відповідною
операторною
вершиною Yt,
а кожний вираз
Xi
і Pj
відповідними
умовними вершинами.
2.СИНТЕЗ
АВТОМАТА З
ПРИМУСОВОЮ
АДРЕСАЦІЄЮ
МІКРОКОМАНД.
2.1. Принцип
роботи
автомата.
При
примусовій
адресації
адреса наступної
мікрокоманди
задається в
полі поточної
мікрокоманди.
Формат МК
в такому випадку
слідуючий
(мал. 2.1.).
1
Y m 1
X l 1
A0
k
1
A1
k
Мал. 2.1
Формат команди
автомата з ПА.
Тут у
полі Y міститься
код, що задає
набір мікрооперацій,
у полі X-код логічної
умови, що перевіряється,
у полях A0
і A1-
адреси переходу
при невиконанні
логічної умови,
що перевіряється
або безумовному
переході і при
істинності
логічної умови
відповідно.
Розрядність
полів визначається
таким чином:
m=]log2T[
Т- число наборів
мікрооперацій,
що використовуються
в ГСА, в нашому
випадку Т=17, m=5
l=]log2
(L+1)[ L-число логічних
умов у ГСА, в
нашому випадку
L=6, l=3
k=]log2
Q[ Q -кількість
мікрокоманд.
Структурна
схема автомата
приведена на
мал. 2.2. Автомат
функціонує
таким чином.
Схема запуску
складається
з RS -тригера і
схеми “&", яка
блокує надходження
синхроімпульсів
на РАМК і РМК.
За сигналом
“Пуск" тригер
встановлюється
в одиницю і
відбувається
запис мікрокоманд
до регістру.
Поле Y надходить
на схему формування
МО і перетворюється
в деякий набір
мікрооперацій.
Поле X надходить
до схеми формування
адреси, яка
формує сигнал
Z2,
якщо перехід
безумовний
(X=0) або ЛУ , що
перевіряється,
дорівнює 0, або
сигнал Z1
у випадку істинності
ЛУ. За сигналом
Z1(Z2)
до адресного
входу ПЗП надходить
значення поля
A1(A0).
За сигналу y0
тригер встановлюється
в нуль і автомат
зупиняє свою
роботу. За сигналом
"Пуск" до РАМК
заноситься
адреса початкової
МК (А=0).
2.2. Перетворення
початкової
ГСА.
Перетворення
буде полягати
в тому, що у всі
операторні
вершини, пов'язані
з кінцевою,
вводиться
сигнал y0,
а між всіма
умовними вершинами,
які пов'язані
з кінцевою,
вводиться
операторна
вершина, що
містить сигнал
y0.
Причому, ця
вершина буде
загальною для
всіх умовних.
З урахуванням
вищесказаного
отримаємо
перетворену
ГСА (мал. 2.3). У
перетвореній
ГСА ми зберігаємо
позначення
Yi,
але при цьому
пам'ятаємо, що
кожна мікрокоманда
Yi
|