Реферат: Прикладная теория цифровых автоматов
Реферат: Прикладная теория цифровых автоматов
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 відповідними умовними вершинами.
30
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.
Синтез РАМК та РМК
|
С |
Ai |
Qt |
Qt+1 |
Ct |
щR |
щS |
|
0 |
0 |
0 |
0 |
0 |
* |
* |
|
|
0 |
1 |
1 |
0 |
* |
* |
|
|
1 |
0 |
0 |
0 |
* |
* |
|
0 |
1 |
1 |
1 |
0 |
* |
* |
|
1 |
0 |
0 |
0 |
1 |
* |
1 |
|
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
1 |
1 |
0 |
1 |
1 |
1 |
0 |
|
1 |
1 |
1 |
1 |
1 |
1 |
* |
0
0У результаті отримаємо слідуючу схему для базового елементу РАМК та РМК (мал.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).
41
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).
51
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.
Як видно з приведених оцінок, автомат з примусовою адресацією далеко не оптимальний, а автомати з природною і комбінованою адресацією по витратах практично однакові, але все ж автомат з ПрА має деяку перевагу перед автоматом з КА. Таким чином, результатом проектування буде схема автомата з природною адресацією мікрокоманд.
