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", а його інверсію на “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 відповідними умовними вершинами. 29 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
РАМК Z1 Z2 S T & ПЗП “Пуск” СІ R РМК Y X A0 A1 СФМО Z1 y0 .... yi СФА до ОА Z2
Мал.2.2. Структурна схема автомата з ПА
розбивається на мікрооперації yi..yj згідно з табл. 2.1.
Таблиця 2.1.
Розподіл МО по мікрокомандам. МК | Мікрооперації | МК | Мікрооперації | Y1 | y1y2y9y10 | Y12 | y5y6y12y17y19 | Y2 | y1y5y12y19 | Y13 | y4y6y20y21 | Y3 | y1y6y11y20 | Y14 | y3y11y17y18y22 | Y5 | y3y4y13y30 | Y15 | y4y5y6y18y19y23 | Y7 | y2y6y7y16 | Y16 | y12y14y16y24 | Y8 | y5y13y15y29 | Y17 | y2y13y25 | Y9 | y6y17 | Y18 | y5 | Y10 | y3y4y5y18y19 | Y20 | y3y27y28 | Y11 | y7y8y17y20 |
|
| 2.3.Формування вмісту керуючої пам'яті.
Перший етап - виділення мікрокоманд заданого формату. В автоматі з ПА в одному такті можуть виконуватися МО і перевірятися логічна умова. Тому мікрокоманда відповідає парі ОПЕРАТОРНА ВЕРШИНА - УМОВНА ВЕРШИНА. Виходячи з цього, отримаємо, що можливими є пари: ОПЕРАТОРНА ВЕРШИНА - УМОВНА ВЕРШИНА, ОПЕРАТОРНА ВЕРШИНА - БЕЗУМОВНИЙ ПЕРЕХІД, ПОРОЖНЯ ОПЕРАТОРНА - УМОВНА ВЕРШИНА. При цьому потрібно враховувати, що при виборі пари ОПЕРАТОРНА ВЕРШИНА - УМОВНА ВЕРШИНА недопустим перехід ззовні в точку між операторною і умовною вершинами, крім ситуації, коли умовна вершина входить до складу іншої мікрокоманди. У результаті ми отримаємо слідуюче разбиття на мікрокоманди (мал. 2.3.). Ми отримали 38 допустимих МК. Закодуємо їх в природному порядку, привласнивши початковій МК нульову адресу (табл.2.2). Для цього необхідно q=]log2N[ розрядів, де N- кількість МК заданого формату. У нашому випадку N=38, q=6.
Таблиця 2.2 Кодування МК МК | А1А2А3А4 А5А6 | О1 | 0 0 0 0 0 0 | О2 | 0 0 0 0 0 1 | ...... | ........................ | О38 | 1 0 0 1 0 1 |
Аналогічним чином закодуємо оператори Yi, надавши нульовий код порожньому операторному полю (табл. 2.3).
Таблиця 2.3 Кодування Y Yi | T2T3T4T5T6 | Ж | 00000 | Y1 | 00001 | Y2 | 00010 | Y3 | 00011 | Y5 | 00100 | Y7 | 00101 | Y8 | 00110 | Y9 | 00111 | Y10 | 01000 | Y11 | 01001 | Y12 | 01010 | Y13 | 01011 | Y14 | 01100 | Y15 | 01101 | Y16 | 01110 | Y17 | 01111 | Y18 | 10000 | Y20 | 10001 | Таблиця 2.5
Вміст керуючої пам`яті. № | A | FY | FX | FA0 | FA1 | Оп. | A1A2A3A4A5A6 | T1T2T3T4T5T6 | T7T8T9 | T10T11T12T13T14T15 | T16T17T18T19T20T21 | 1 | 000000 | 000000 | 100 | 000001 | 001100 | 2 | 000001 | 000000 | 101 | 000010 | 011001 | 3 | 000010 | 000000 | 110 | 000011 | 001100 | 4 | 000011 | 000000 | 001 | 001100 | 000100 | 5 | 000100 | 000000 | 010 | 001001 | 000101 | 6 | 000101 | 000110 | 110 | 000111 | 000110 | 7 | 000110 | 101100 | 000 | 000000 | 000000 | 8 | 000111 | 000111 | 000 | 001000 | 000000 | 9 | 001000 | 001001 | 000 | 001110 | 000000 | 10 | 001001 | 001000 | 100 | 001010 | 011000 | 11 | 001010 | 000000 | 110 | 001110 | 001011 | 12 | 001011 | 100111 | 000 | 000000 | 000000 | 13 | 001100 | 000001 | 100 | 001101 | 001110 | 14 | 001101 | 000000 | 110 | 001001 | 010010 | 15 | 001110 | 000100 | 100 | 001111 | 010111 | 16 | 001111 | 000000 | 101 | 010001 | 010000 | 17 | 010000 | 000000 | 110 | 010100 | 010101 | 18 | 010001 | 000000 | 110 | 010010 | 011110 | 19 | 010010 | 000110 | 110 | 011111 | 010011 | 20 | 010011 | 000000 | 011 | 100011 | 001110 | 21 | 010100 | 100000 | 000 | 000000 | 000000 | 22 | 010101 | 000000 | 010 | 001001 | 010110 | 23 | 010110 | 000001 | 000 | 100101 | 000000 | 24 | 010111 | 001010 | 001 | 011000 | 010101 | 25 | 011000 | 101010 | 000 | 000000 | 000000 | 26 | 011001 | 000000 | 110 | 011011 | 011010 | 27 | 011010 | 000000 | 001 | 011111 | 100001 | 28 | 011011 | 001101 | 001 | 011100 | 011101 | 29 | 011100 | 001110 | 011 | 010100 | 001110 | 30 | 011101 | 000101 | 000 | 011110 | 000000 | 31 | 011110 | 001111 | 010 | 100001 | 100000 | 32 | 011111 | 000111 | 101 | 010100 | 100010 | 33 | 100000 | 100011 | 000 | 000000 | 000000 | 34 | 100001 | 010000 | 110 | 010100 | 100011 | 35 | 100010 | 000000 | 010 | 010100 | 100101 | 36 | 100011 | 000001 | 101 | 100100 | 011111 | 37 | 100100 | 001011 | 000 | 000101 | 000000 | 38 | 100101 | 010001 | 100 | 001110 | 001001 |
2.4. Синтез схеми автомата.
Схема СФА являє собою мультиплексор, який в залежності від коду логічної умови, що перевіряється, передає на вихід Z1 значення відповідної ЛУ. При цьому сигнал Z2 завжди є інверсією сигналу Z1. Таким чином, отримаємо слідуючі вирази для Z1 і Z2: Z1=X1щT7щT8T9+X2щT7T8щT9+X3щT7T8T9+P1T7щT8щT9+P2T7щT8T9+P3T7T8щT9 Z2=щZ1 або, звівши до заданого базису (4 АБО-НІ), отримаємо Z1=щ щ(щ щ(A+B+C+D)+E+F), де
A=щ щ( X1щT7щT8T9)=щ(щX1+T7+T8+щT9) B=щ щ( X2щT7T8щT9)=щ(щX2+T7+щT8+T9) C=щ щ( X3щT7T8T9)=щ(щX3+T7+щT8+щT9) D=щ щ( P1T7щT8щT9)=щ(щP1+щT7+T8+T9) E=щ щ( P2T7щT8T9)=щ(щP2+щT7+T8+щT9) F=щ щ( P3T7T8щT9)=щ(щP3+щT7+щT8+T9) Інформація, що надходить на адресні входи ПЗП формується таким чином: Ai=A0iZ1+A1iZ2 або, приводячи до заданого базису, отримуємо Ai=щщ(щ(щA0i+щZ1)+щ(щA1i+щZ2)). Синтезуємо тепер схему дешифратора, що формує сигнали мікрооперацій yi. Поява одиниці, відповідної кожному Y, відбувається при появі на вході дешифратора коду даного Y, тобто Yi=T2eЩT3eЩT4еЩT5еЩT6е, де еО{0,1} T0=щT, T1=T. Або приводячи до заданого базису, отримаємо: Yi=щ(щ щ(T2щe+T3щe+T4ще+T5ще)+T6ще). Таким чином, схема, що формує сигнал Y з п`ятирозрядного коду виглядає таким чином(мал. 2.4) T6щe 1 1 1 Yi T2щe Мал. 2.4. Схема формування сигналу Yi.
Враховуючи, що розряд T2 рівний “1" при формуванні тільки двох сигналів Y18 і Y20, то схему(мал. 2.4) будемо використовувати для формування Y1, Y20, для яких співпадають молодші чотири розряди та для Y18, для якого молодші чотири розряди співпадають з кодом порожньої операторної вершини. А для всіх інших Y схему можна спростити (мал.2.5.).
T6щe 1 Yi T3щe
Мал.2.5. Спрощена схема формування сигналу Yi. Згідно з наведеними схемами запишемо формули для всіх Yi. Y1=щ (щ щ(T2+T3+T4+T5)+щT6) Y2= щ(T3+T4+щT5+T6) Y3= щ(T3+T4+щT5+щT6) Y5= щ(T3+щT4+T5+T6) Y7= щ(T3+щT4+T5+щT6) Y8= щ(T3+щT4+щT5+T6) Y9= щ(T3+щT4+щT5+щT6) Y10=щ(щT3+T4+T5+T6)
Сигнали мікрооперацій yj отримаємо, об'єднуючи по “або" виходи відповідні операторам Yi, в яких зустрічається МО yj. При цьому будемо користуватися таблицею
Таблиця 2.5. Розподіл МО за мікро- командами
МО | номери МК | y1 | 1,2,3 | y2 | 1,7,17 | y3 | 5,10,14,20 | y4 | 5,10,13,15 | y5 | 2,8,10,12,15,18 | y6 | 3,7,9,12,13,15 | y7 | 7,11 | y8 | 11 | y9 | 1 | y10 | 1 | y11 | 3,14 | y12 | 2,12,16 | y13 | 5,8,17 | y14 | 16 | y15 | 8 | y16 | 7,16 | y17 | 9,11,12,14 | y18 | 10,14,15 | y19 | 2,10,12,15 | y20 | 3,11,13 | y21 | 13 | y22 | 14 | y23 | 15 | y24 | 16 | y25 | 17 | y27 | 20 | y28 | 20 | y29 | 8 | y30 | 5 |
На наступному етапі синтезуємо схеми РАМК і РМК, використовуючи щRщS тригери. Скористаємося класичним методом синтезу регістрів і заповнимо слідуючу таблицю (табл. 2.6.).
Таблиця 2.6.
Синтез РАМК та РМК
У результаті отримаємо слідуючу схему для базового елементу РАМК та РМК (мал.2.6). Ai 1 S TT Q СІ C R “Reset” R щQ Мал. 2.6. Базовий елемент регістра.
Схема РАМК містить 6 таких елементів, а схема РМК - 21. При побудові схеми сигнали щT1..щT21 будемо знімати з інверсних виходів елементів регістрів. Кількість мікросхем ПЗП визначимо за формулою: NПЗП=]R/3[, де R - розрядність мікрокоманди R=21, NПЗП=7. Для зберігання мікропрограми досить однієї лінійки ПЗП, оскільки QПЗП=8, тобто одна мікросхема розрахована на зберігання 256 трьохбітових комбінацій, а в нашому випадку потрібно тільки 38. При побудові схеми будемо записувати в РАМК інверсію адреси, а до ПЗП будемо подавати адресу з інверсних виходів елементів регістра, таким чином, ми заощадимо 6 елементів-інверторів у СФА. З врахуванням вищесказаного побудуємо схему автомата з примусовою адресацією мікрокоманд(мал. 2.7). 39 3.СИНТЕЗ АВТОМАТА З ПРИРОДНОЮ АДРЕСАЦІЄЮ МІКРОКОМАНД
3.1. Принцип роботи автомата.
При природній адресації микрокоманд існує три формата МК (мал. 3.1.). П 1 FY m ОМК
П 1 FX l 1 FA r УМК1 П 1 Ж l 1 FA r УМК2
Мал.3.1. Формати мікрокоманд автомата з природною адресацією..
Тут формат ОМК відповідає операторній вершині, УМК1-умовній, а УМК2-вершині безумовного переходу. При подачі сигналу “пуск" лічильник ЛАМК обнуляється, і за сигналом СІ відбувається запис МК до регістра. СФМО формує відповідні МО при П=1 або видає на всіх виходах нулі при П=0. СФА в залежності від П і вмісту поля FX, формує сигнали Z1 і Z2. Сигнал Z1 дозволяє проходження синхроімпульсів на лічильний вхід ЛАМК, а Z2 дозволяє запис до лічильника адреси наступної МК з приходом синхроімпульсу. Визначимо розрядність полів. l=]log2(L+1)[, де L-число умовних вершин. L=6, l=3 m=]log2T[ Т- число наборів мікрооперацій, що використовуються в ГСА, в нашому випадку Т=17, m=5 r=]log2 Q[, Q - кількість мікрокоманд.
3.2.Перетворення початкової ГСА.
Перетворення буде полягати в тому, що до всіх операторних вершин, пов'язаних з кінцевою, вводиться сигнал y0, а між всіма умовними вершинами, які пов'язані з кінцевою, вводиться операторна вершина, що містить сигнал y0. Крім цього, в ГСА вводяться спеціальні вершини безумовного переходу X0, відповідні формату УМК2. Введення таких вершин необхідне для виключення конфліктів адресації мікрокоманд. У автоматі з природною адресацією (рис3.2.) при істинності(помилковість) логічної умови перехід здійснюється до вершини з адресою на одиницю великим, а при (помилковість)істинності ЛУ перехід відбувається за адресою, записаною в полі FA. У нашому випадку будемо додавати одиницю при істинності ЛУ або при переході з операторной вершини. Якщо в одній точці сходиться декілька переходів по “1" або з операторної вершини, то всі вершини з яких здійснювався перехід, повинні були б мати однакову (на одиницю меншу ) адресу, ніж наступна команда. Але це неможливо.
Z1 +1 сі Z2 А ЛАМК “Пуск” 1 ПЗП
РМК
FY П FX FA СФМО СФА Z1 y0.....yi к ОА Z2
Мал.3.2. Структурна схема автомата з природною адресацією.
Для виключення подібних ситуацій вводять спеціальну вершину безумовного перходу (мал. 3.3). Дані вершини додаємо таким чином, щоб в одній точці сходилася будь-яка кількість переходів по “0" і тільки один по “1" або з операторної вершини. З врахуванням вказаних перетворень отримаємо перетворену ГСА (мал. 3.4).
X0 0 1
Мал. 3.3. Вершина безумовного переходу.
3.3.Формування вмісту керуючої пам'яті.
На перетвореній ГСА виділимо мікрокоманди форматів ОМК, УМК1, УМК2. У результаті отримаємо 63 МК. Виконаємо їх адресацію. Для цього запишемо всі природні послідовності команд (ланцюжки вершин, перехід між якими здійснюється по “1" або через операторну вершину). У результаті отримаємо:
a1=[O1,O5] a2=[ O2 ,O6 ,O7 ,O36 ,O48 ,O51 ,O55 ,O34 ,O47 ,O49 ,O56 ,O59 ,O12 ,O16 ,O45] a3=[ O3 ,O9 ,O13 ,O18] a4=[ O4 ,O10 ,O11] a5=[ O8 ,O14 ,O20 ,O30 ,O32 ,O35] a6=[ O60 ,O15 ,O21 ,O22] a7=[ O17 ,O52 ,O57 ,O61 ,O62] a8=[ O19 ,O28 ,O29] a9=[ O23 ,O25 ,O27 ,O31 ,O37 ,O44 ,O43 ,O53 ,O54] a10=[ O24 ,O26] a11=[ O33] a12=[ O38 ,O41 ,O42] a13=[ O39 ,O40] a14=[ O46] a15=[ O50] a16=[ O58] a17=[ O63]
Перерахуємо в таблиці адресації (табл. 3.1) підряд всі послідовності a1-a17 і закодуємо їх R-розрядним кодом. R=]log2N[, N-кількість мікрокоманд (N=63, R=6). Закодуємо також оператори Yi, поставивши їм у відповідність п`ятирозрядний код. Будемо використовувати те ж кодування, що і в автоматі з ПА.(табл. 2.3., 2.4). У таблиці 3.2 відобразимо вміст керуючої пам'яті, заповнивши поля FX, FY, FA.
Таблиця 3.1. Таблиця 3.1. (продовження) Адресація МК. мк | А1А2А3А4А5А6 | O1 | 000000 | O5 | 000001 | O2 | 000010 | O6 | 000011 | O7 | 000100 | O36 | 000101 | O48 | 000110 | O51 | 000111 | O55 | 001000 | O34 | 001001 | O47 | 001010 | O49 | 001011 | O56 | 001100 | O59 | 001101 | O12 | 001110 | O16 | 001111 | O45 | 010000 | O3 | 010001 | O9 | 010010 | O13 | 010011 | O18 | 010100 | O4 | 010101 | O10 | 010110 | O11 | 010111 | O8 | 011000 | O14 | 011001 | O20 | 011010 | O30 | 011011 | O32 | 011100 | O35 | 011101 | O60 | 011110 | O15 | 011111 | O21 | 100000 | O22 | 100001 | O17 | 100010 | O52 | 100011 | O57 | 100100 | O61 | 100101 | O62 | 100110 |
Таблиця 3.2. Вміст керуючої пам`яті автомата з природною адресацією. МК | Адреса | П |
| FY | Формула переходу |
|
|
| FX | FA |
|
| А1А2А3А4А5А6 | T1 | T2T3T4 | T5T6T7T8T9T10 |
| O1 | 000000 | 1 | 100 | 000010 | O1®щP1O2+P1O5 | O5 | 000001 | 1 | 000 | 010010 | O5®O9 | O2 | 000010 | 1 | 101 | 010001 | O2®щP2O3+P2O6 | O6 | 000011 | 1 | 110 | 011000 | O6®щP3O8+P3O7 | O7 | 000100 | 1 | 001 | 001001 | O7®щX1O34+X1O36 | O36 | 000101 | 0 | 010 | 000000 | O36®O48 | O48 | 000110 | 1 | 110 | 111110 | O48®щP3O63+P3O51 | O51 | 000111 | 0 | 000 | 010000 | O51®O55 | O55 | 001000 | 1 | 101 | 011110 | O55®щP2O60+P2O34 | O34 | 001001 | 0 | 000 | 111000 | O34®O47 | O47 | 001010 | 1 | 101 | 111011 | O47®щP2O46+P2O49 | O49 | 001011 | 1 | 010 | 111100 | O49®щX2O50+X2O56 | O56 | 001100 | 0 | 010 | 001000 | O56®O59 | O59 | 001101 | 1 | 100 | 101100 | O59®щP1O27+P1O12 | O12 | 001110 | 0 | 001 | 000000 | O12®O16 | O16 | 001111 | 1 | 100 | 110011 | O16®щP1O24+P1O45 | O45 | 010000 | 0 | 101 | 010000 | O45®K | O3 | 010001 | 1 | 110 | 010101 | O3®щP3O4+P3O9 | O9 | 010010 | 0 | 000 | 001000 | O9®O13 | O13 | 010011 | 1 | 100 | 100010 | O13®щP1O17+P1O18 | O18 | 010100 | 1 | 000 | 101100 | O18®щO27 | O4 | 010101 | 1 | 001 | 010010 | O4®щX1O9+X1O10 | O10 | 010110 | 1 | 010 | 001110 | O10®щX2O12+X2O11 | O11 | 010111 | 1 | 000 | 011111 | O11®O15 | O8 | 011000 | 0 | 001 | 101000 | O8®O14 | O14 | 011001 | 1 | 001 | 100111 | O14®щX1O19+X1O20 | O20 | 011010 | 0 | 000 | 101000 | O20®O30 | O30 | 011011 | 0 | 001 | 111000 | O30®O32 | O32 | 011100 | 1 | 110 | 000101 | O32®щP3O36+P3O35 | O35 | 011101 | 0 | 100 | 011000 | O35®K | O60 | 011110 | 0 | 001 | 011000 | O60®щO15 | O15 | 011111 | 0 | 000 | 110000 | O15®O21 | O21 | 100000 | 1 | 110 | 101010 | O21®щP3O23+P3O22 | O22 | 100001 | 0 | 101 | 100000 | O22®K | O17 | 100010 | 1 | 110 | 001110 | O17®щP3O12+P3O52 | O52 | 100011 | 0 | 000 | 110000 | O52®O57 | O57 | 100100 | 1 | 110 | 001001 | O57®щP3O34+P3O61 | O61 | 100101 | 1 | 011 | 000111 | O61®щX3O51+X3O62 | O62 | 100110 | 1 | 000 | 101100 | O62®O27 | O19 | 100111 | 0 | 001 | 110000 | O19®O28 | Таблица 3.2. (продовження) O28 | 101000 | 1 | 011 | 110101 | O28®щX3O33+X3O29 | O29 | 101001 | 1 | 000 | 101100 | O29®O27 | O23 | 101010 | 0 | 000 | 111000 | O23®O25 | O25 | 101011 | 0 | 001 | 001000 | O25®O27 | O27 | 101100 | 0 | 000 | 100000 | O27®O31 | O31 | 101101 | 1 | 100 | 110110 | O31®щP1O38+P1O37 | O37 | 101110 | 0 | 001 | 010000 | O37®O44 | O44 | 101111 | 1 | 001 | 010000 | O44®щX1O45+X1O43 | O43 | 110000 | 1 | 010 | 001110 | O43®щX2O12+X2O53 | O53 | 110001 | 0 | 000 | 001000 | O53®O54 | O54 | 110010 | 1 | 000 | 001100 | O54®O56 | O24 | 110011 | 1 | 110 | 101100 | O24®щP3O27+P3O26 | O26 | 110100 | 0 | 100 | 111000 | O26®K | O33 | 110101 | 0 | 100 | 000000 | O33®K | O38 | 110110 | 1 | 101 | 111001 | O38®щP2O39+P2O41 | O41 | 110111 | 1 | 110 | 111101 | O41®щP3O58+P3O42 | O42 | 111000 | 1 | 000 | 001110 | O42®щO12 | O39 | 111001 | 1 | 110 | 100011 | O39®щP3O52+P3O40 | O40 | 111010 | 1 | 000 | 011011 | O40®O30 | O46 | 111011 | 0 | 100 | 000000 | O46®K | O50 | 111100 | 0 | 100 | 000000 | O50®K | O58 | 111101 | 0 | 100 | 000000 | O58®K | O63 | 111110 | 0 | 100 | 000000 | O63®K |
3.4. Синтез схеми автомата.
Синтезуємо схему, що формує сигнал Z1. Сигнал Z1 рівний 1, якщо ознака П=0 або П=1 і при цьому логічна умова, що перевіряється, істинна. Скористаємося формулою Z1 для автомата з ПА, яка в залежності від коду умови передає на вихід Z1 значення відповідного ЛУ.
Z1=X1щT2щT3T4+X2щT2T3щT4+X3щT2T3T4+P1T2щT3щT4+P2T2щT3T4+P3T2T3щT4
З врахуванням вищенаведених вимог запишемо формули для сигналів Z1 і Z2 в автоматі з природною адресацією.
Z1=щT1+T1(X1щT2щT3T4+X2щT2T3щT4+X3щT2T3T4+P1T2щT3щT4+P2T2щT3T4+P3T2T3щT4) Z2=щZ1
Або , звівши до заданого базису отримаємо:
Z1=щ щ(щ(щ(щ щ(A+B+C+D)+E+F)+щT1)+щT1), где
A=щ щ( X1щT7щT8T9)=щ(щX1+T2+T3+щT4) B=щ щ( X2щT7T8щT9)=щ(щX2+T2+щT3+T4) C=щ щ( X3щT7T8T9)=щ(щX3+T2+щT3+щT4) D=щ щ( P1T7щT8щT9)=щ(щP1+щT2+T3+T4) E=щ щ( P2T7щT8T9)=щ(щP2+щT2+T3+щT4) F=щ щ( P3T7T8щT9)=щ(щP3+щT2+щT3+T4)
Схема формування МО подібна СФМО автомата з ПА, але поява сигналів на виходах yi можлива тільки при П=0, тобто коли поточна мікрокоманда відповідає операторній вершині. Тому схему формування Yi змінимо таким чином: сигнал щT1(щП) кон`юнктивно об'єднаємо з кожним сигналом T3...T7,щT3...щT7 (мал. 3.5). При цьому відсутність цих сигналів приведе до відсутності сигналів yi, бо комбінація з усіх нулів на вході дншифратора відповідає порожній операторній вершині. Виняток складає сигнал y0, для якого передбачений окремий розряд, тому його ми кон`юнктивно об'єднаємо з сигналом щT1(щП) (мал. 3.6.)
щT3...щT7 T3..T7 1 T3...T7 1 щT3...щT7 T1 T1
Мал.3.5. Схеми підключення щП.
щT2 1 y0 T1
Рис.3.6.Схема формування y0.
Схема базового елементу РМК аналогічна відповідній схемі в автоматі з ПА(мал2.6). У якості ЛАМК будемо використовувати лічильник, що має слідуючу функціональну схему(мал. 3.7.). Вхід V відповідає сигналу Z1, якщо він рівний 1, то ЛАМК збільшує свій вміст на 1, в протилежному випадку, на вихід передається інформація з входів A1...Ai. Синтезуємо лічильник з крізним перенесенням. Для цього складемо слідуючу таблицю(табл.3.3).Таблиця складена для одного розряду.
A1 CT A2 A1 A3 A2 A4 A3 A5 A4 A6 A5 A6 V C R
Мал.3.7. Функціональне зображення лічильника.
Таблиця.3.3 Синтез схеми ЛАМК.
V | T | Ai | Qt | Qt+1 | щR | щS | 0 | 0 | 0 | 0 | 0 | * | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | * | 0 | 1 | 0 | 0 | 0 | * | 1 | 0 | 1 | 0 | 1 | 1 | 1 | * | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | * | 1 | 0 | 0 | 0 | 0 | * | 1 | 1 | 0 | 0 | 1 | 1 | 1 | * | 1 | 0 | 1 | 0 | 0 | * | 1 | 1 | 0 | 1 | 1 | 1 | 1 | * | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | Схема РМК містить 10 базових елементів. При побудові схеми сигнали щT1...щT10 будемо знімати з інверсних виходів елементів регістра. Кількість мікросхем ПЗП визначимо за формулою: NПЗП=]R/3[, де R - розрядність мікрокоманди R=10, NПЗП=4 Для зберігання мікропрограми досить однієї лінійки ПЗП, оскільки QПЗП=8, тобто одна мікросхема розрахована на зберігання 256 трьохбітових комбінацій, а в нашому випадку потрібно тільки 63. З урахуванням вищесказаного побудуємо схему автомата з природною адресацією мікрокоманд(мал. 3.8).
V 1 1 T0 1 1 1 Q0 S TT C Ai 1 1 R 1 1 R C “Reset”
T1 Q1
щT1 T2 1 Q2 щQ1
щT2 T3 1 Q3
щQ2
........................................................................
Мал.3.8.Схема ЛАМК (усього 6 елементів, сигнали V,C,”Reset”,Ai для всіх, окрім першого, не показані). 48 4.СИНТЕЗ АВТОМАТА З КОМБІНОВАНОЮ АДРЕСАЦІЄЮ МІКРОКОМАНД.
4.1.Принцип роботи автомата.
Автомат з комбінованою адресацією є комбінацією з автоматів з примусовою і природною адресацією . У даному автоматі адреса наступної МК задається в полі поточної мікрокоманди, при цьому при невиконанні ЛУ, що перевіряється, або при безумовному переході перехід здійснюється за заданою адресою, а при істинності - за адресою на одиницю більшу, ніж поточна. Формат команди автомата з КА наступний(мал. 4.1).
1 Y m 1 Х k 1 A l
Мал. 4.1.Формат команди автомата з КА.
Тут у полі Y міститься код, що задає набір мікрооперацій, у полі X-код логічної умови, що перевіряється, в полі А - адреса переходу при невиконанні логічної умови або при безумовному переході. Розрядність полів визначається таким чином: m=]log2T[ Т- число наборів мікрооперацій, що використовуються в ГСА, в нашому випадку Т=17, m=5 k=]log2(L+1)[ L-число логічних умов в ГСА, в нашому випадку L=6, l=3 l=]log2Q[ Q -кількість мікрокоманд. Структурна схема автомата приведена на мал. 4.2. Автомат функціонує таким чином. Схема запуску складається з RS -тригера і схеми “&", яка блокує надходження синхроімпульсів на РМК. За сигналом “Пуск" тригер встановлюється в одиницю і відбувається запис мікрокоманди до регістру. Поле Y поступає на схему формування МО і перетворюється в деякий набір мікрооперацій. Поле X поступає на схему формування адреси, яка формує сигнал Z2, якщо перехід безумовний (X=0) або ЛУ, що перевіряється,дорівнює нулю або сигнал Z1 у випадку істинності ЛУ. За сигналом Z2 вміст поля А надходить до лічильника,а з нього - на адресний вхід ПЗП. А за сигналом Z1 на адресний вхід також надходить вміст лічильника але тепер це адреса поточної мікрокоманди, збільшена на одиницю. За сигналом y0 тригер скидається в нуль і автомат зупиняє свою роботу.
4.2. Перетворення початкової ГСА.
Перетворення будемо виконувати двома етапами. На першому - введемо сигнал y0 до вершин, пов'язаних з кінцевою, якщо вершина умовна, то введемо
+1 Z1
СT Z2 S T & ПЗП “Пуск” СІ R РМК Y X A СФМО y0 .... yi Z1 СФА до ОА Z2
Мал.4.2. Структурна схема автомата з КА.
додаткову операторну вершину з сигналом y0. Крім того, введемо додаткові вершини безумовного переходу, виходячи з тих же міркувань, що і для автомата з природною адресацією. Будемо, однак, мати на увазі, що для автомата з КА перехід з операторної вершини прирівнюється до безумовного, тому в одній точці може сходитися будь-яка кількість безумовних переходів або переходів з операторних вершин і тільки один по істинності ЛУ, що перевіряється. На другому етапі виділимо мікрокоманди заданого формату, користуючись тими ж правилами, що і для автомата з ПА. З врахуванням вищесказаного отримаємо перетворену ГСА (мал. 4.3).
4.3.Формування вмісту керуючої пам'яті.
При формуванні вмісту керуючої пам'яті скористаємося тим же кодуванням наборів мікрооперацій і ЛУ, що і для автоматів з ПА і природною адресацією (табл. 2.3, 2.4). Для адресації мікрокоманд випишемо їх природні послідовності так само, як і для автомата з природною адресацією, враховуючи, що природним вважається тільки перехід по істинності ЛУ.
a1=[O1,O14] a2=[ O2 ,O19 ,O18 ,O46 ,O6 ,O42 ,O43 ,O44 ,O9 ,O38 ] a3=[ O3 ,O15 ,O17 ] a4=[ O4 ,O5 ,O7,O8] a5=[ O10 ] a6=[ O11 ,O13] a7=[ O12] a8=[ O16,O29,O30,O25,O37,O35,O36] a9=[ O20 ,O22 ] a10=[ O21,O23] a11=[ O26,O32,O33] a12=[ O27 ,O24 ,O45] a13=[ O34] a14=[ O39] a15=[ O40] a16=[ O41] a17=[ O28] a18=[O31]
Перерахуємо в таблиці адресації (табл. 4.1) підряд всі послідовності a1-a18 і закодуємо їх R-розрядним кодом. R=]log2N[, N-кількість мікрокоманд(N=46, R=6). Закодуємо також оператори Yi, поставивши їм у відповідність п`ятирозрядний код. У таблиці 4.2 відобразимо вміст керуючої пам'яті, заповнивши поля FX, FY, FA.
Таблиця 4.1. Адресація МК. мк | А1А2А3А4А5А6 | O1 | 000000 | O14 | 000001 | O2 | 000010 | O19 | 000011 | O18 | 000100 | O46 | 000101 | O6 | 000110 | O42 | 000111 | O43 | 001000 | O44 | 001001 | O9 | 001010 | O38 | 001011 | O3 | 001100 | O15 | 001101 | O17 | 001110 | O4 | 001111 | O5 | 010000 | O7 | 010001 | O8 | 010010 | O10 | 010011 | O11 | 010100 | O13 | 010101 | O12 | 010110 | O16 | 010111 | O29 | 011000 | O30 | 011001 | O25 | 011010 | O37 | 011011 | O35 | 011100 | O36 | 011101 | O20 | 011110 | O22 | 011111 | O21 | 100000 | O23 | 100001 | O26 | 100010 | O32 | 100011 | O33 | 100100 | O27 | 100101 | O24 | 100110 | O45 | 100111 | O34 | 101000 | O39 | 101001 | O40 | 101010 | O41 | 101011 | O28 | 101100 | O31 | 101101 | Таблиця 4.2
Вміст керуючої пам`яті. № | A | FY | FX | FA | Оп. | A1A2A3A4A5А6 | T1T2T3T4T5T6 | T7T8T9 | T10T11T12T13T14T15 | O1 | 000000 | 000000 | 100 | 000010 | O14 | 000001 | 000000 | 000 | 001101 | O2 | 000010 | 000000 | 101 | 001100 | O19 | 000011 | 000000 | 110 | 011110 | O18 | 000100 | 000000 | 001 | 000111 | O46 | 000101 | 010000 | 110 | 101101 | O6 | 000110 | 000010 | 101 | 101100 | O42 | 000111 | 000111 | 101 | 101010 | O43 | 001000 | 000000 | 010 | 101011 | O44 | 001001 | 010001 | 100 | 011010 | O9 | 001010 | 001000 | 100 | 010100 | O38 | 001011 | 101010 | 000 | 000000 | O3 | 001100 | 000000 | 110 | 001111 | O15 | 001101 | 000001 | 100 | 010111 | O17 | 001110 | 000000 | 000 | 011010 | O4 | 001111 | 000000 | 001 | 001101 | O5 | 010000 | 000000 | 010 | 001010 | O7 | 010001 | 000110 | 110 | 010011 | O8 | 010010 | 101100 | 000 | 000000 | O10 | 010011 | 000111 | 000 | 010110 | O11 | 010100 | 000000 | 110 | 011010 | O13 | 010101 | 100111 | 000 | 000000 | O12 | 010110 | 001001 | 000 | 011010 | O16 | 010111 | 000000 | 110 | 001010 | O29 | 011000 | 000110 | 110 | 000111 | O30 | 011001 | 000000 | 011 | 000110 | O25 | 011010 | 000100 | 100 | 100010 | O37 | 011011 | 001010 | 001 | 001011 | O35 | 011100 | 000000 | 010 | 001010 | O36 | 011101 | 000001 | 000 | 001001 | O20 | 011110 | 001101 | 001 | 100000 | O22 | 011111 | 000101 | 000 | 100110 | O21 | 100000 | 001110 | 011 | 101001 | O23 | 100001 | 000000 | 000 | 011010 | O26 | 100010 | 000000 | 101 | 100101 | O32 | 100011 | 000000 | 110 | 101000 | O33 | 100100 | 000000 | 000 | 001010 | O27 | 100101 | 000000 | 110 | 011000 | O24 | 100110 | 001111 | 110 | 000101 | O45 | 100111 | 100011 | 000 | 000000 | O34 | 101000 | 100000 | 000 | 000000 |
Таблиця 4.2. (продовження) O39 | 101001 | 100000 | 000 | 000000 | O40 | 101010 | 100000 | 000 | 000000 | O41 | 101011 | 100000 | 000 | 000000 | O28 | 101100 | 001011 | 000 | 010001 | O31 | 101101 | 100000 | 000 | 000000 |
4.4.Синтез схеми автомата.
При синтезі схеми скористаємося вже розробленими вузлами для автоматів з ПА і природною адресацією. СФА автомата з КА аналогічна СФА автомата з природною адресацією. Схеми СФМО, РМК аналогічні відповідним вузлам автомата з ПА (розд.2.4), а схема ЛАМК запозичена з автомата з природною адресацією (розд.3.4). Відмінність полягає лише в тому, що для РМК буде потрібно 15 базових елементів. Враховуючи вищесказане, побудуємо схему автомата з комбінованою адресацією мікрокоманд(мал. 4.4). 5. ПОРІВНЯЛЬНА ХАРАКТЕРИСТИКА АВТОМАТІВ.
5.1. Підрахунок апаратурних витрат.
Визначимо апаратурні витрати на кожний з автоматів. Оскільки синтез лічильника не був обов'язковим, то при визначенні апаратурних витрат будемо вважати його єдиним вузлом. 1. У автоматі з примусовою адресацією схема СФА містить 28 логічних елементів, СФМО - 57 ЛЕ, вузол запуску і схема “&" - 4 ЛЕ і, крім того, необхідно 6 елементів-інверторів для отримання сигналів щX1...щX3,щP1...щP3 Також потрібно 27 елементів для РАМК і РМК. Таким чином, сумарне число ЛЕ дорівнює 122. Для побудови РАМК і РМК також буде потрібно 27 тригерів. Кількість ПЗП- 7. 2. У автоматі з природною адресацією схема СФА містить 12 логічних елементів, СФМО - 68 ЛЕ, вузол скидання - 2 ЛЕ і, крім того, необхідно 6 елементів-інверторів для отримання сигналівщX1...щX3,щP1...щP3 і 10 елементів для РМК. Таким чином, сумарне число ЛЕ дорівнює 98. Для побудови РМК також буде потрібно 10 тригерів. Кількість ПЗП- 4. Схема також містить один лічильник. 3. У автоматі з комбінованою адресацією схема СФА містить 10 логічних елементів, СФМО - 57 ЛЕ, вузол запуску і схема “&" - 4 ЛЕ і, крім того, необхідно 6 елементів-інверторів для отримання сигналів щX1...щX3,щP1...щP3 і 15 елементів для РМК. Таким чином, сумарне число ЛЕ дорівнює 92. Для побудови РМК також буде потрібно 15 тригерів. Кількість ПЗУ- 5. Схема також містить один лічильник.
Складемо зведену таблицю витрат на синтезовані автомати.(табл. 5.1.)
Таблиця 5.1. Апаратурні витрати для синтезованих автоматів. Тип автомата | Логічні елементи | Тригери | ПЗП | Лічильники | ПА | 122 | 27 | 7 | 0 | ПрА | 98 | 10 | 4 | 1 | КА | 92 | 15 | 5 | 1 |
5.2. Визначення автомата з мінімальними апаратурними витратами.
Заповнимо таблицю, де для кожного автомата знаком “+" відмітимо мінімальні витрати на даний тип елементів, а знаком “-" -немінімальні (табл. 5.2.).
Таблиця 5.2. Тип автомата | Логічні елементи | Тригери | ПЗП | Лічильники | ПА | - | - | - | + | ПрА | - | + | + | - | КА | + | - | - | - | Як видно з таблиці 5.2., автомат з природною адресацією виграє по двом параметрам: по кількості тригерів і ПЗП. Для підтвердження правильності вибору автомата застосуємо також оцінку за Квайном (за сумарною кількістю входів елементів). Будемо вважати кількість входів у ЛЕ - 4, у тригера - 4, у ПЗП -9 і у лічильника - 9. З врахуванням вищенаведених значень, для автомата з ПА показник оцінки складе - 659, для автомата з ПрА - 477, для автомата з КА- 482. Як видно з приведених оцінок, автомат з примусовою адресацією далеко не оптимальний, а автомати з природною і комбінованою адресацією по витратах практично однакові, але все ж автомат з ПрА має деяку перевагу перед автоматом з КА. Таким чином, результатом проектування буде схема автомата з природною адресацією мікрокоманд. |