Реферат: Прикладная теория цифровых автоматов

Реферат: Прикладная теория цифровых автоматов

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

Кодування МСА

Часткові МСА М1-М5 наведені в табл.1.2-1.6

Таблиця 1.2

Часткова МСА М1

Таблиця 1.3

Часткова МСА М2

Таблиця 1.4

Часткова МСА М3

Таблиця 1.5

Часткова МСА М4

Таблиця 1.6

Часткова МСА М5

На наступному етапі побудуємо об'єднану МСА М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щp1p2p3­A8+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

Таблиця 1.8

Об`єднана мінімізована МСА Мo

A6®щp1p2p3A2+щp1щp2щp3A7+щp1щp2p3A12­+p1щp2щp3A19+щp1p2щp3Ak

A7®x3p3A6+щp3A8+щx3p3A9

A8®x2p2p3A17+щp2щp3Ak+щx2p2p3Ak

A9®p2­A8+щ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щp3­A2+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]+p2­p3A18+[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 y­0 .... yi СФА до ОА Z2

Мал.2.2. Структурна схема автомата з ПА

розбивається на мікрооперації yi..yj згідно з табл. 2.1.

Таблиця 2.1.

Розподіл МО по мікрокомандам.

2.3.Формування вмісту керуючої пам'яті.

Перший етап - виділення мікрокоманд заданого формату. В автоматі з ПА в одному такті можуть виконуватися МО і перевірятися логічна умова. Тому мікрокоманда відповідає парі ОПЕРАТОРНА ВЕРШИНА - УМОВНА ВЕРШИНА. Виходячи з цього, отримаємо, що можливими є пари: ОПЕРАТОРНА ВЕРШИНА - УМОВНА ВЕРШИНА, ОПЕРАТОРНА ВЕРШИНА - БЕЗУМОВНИЙ ПЕРЕХІД, ПОРОЖНЯ ОПЕРАТОРНА - УМОВНА ВЕРШИНА. При цьому потрібно враховувати, що при виборі пари ОПЕРАТОРНА ВЕРШИНА - УМОВНА ВЕРШИНА недопустим перехід ззовні в точку між операторною і умовною вершинами, крім ситуації, коли умовна вершина входить до складу іншої мікрокоманди. У результаті ми отримаємо слідуюче разбиття на мікрокоманди (мал. 2.3.). Ми отримали 38 допустимих МК. Закодуємо їх в природному порядку, привласнивши початковій МК нульову адресу (табл.2.2). Для цього необхідно q=]log2N[ розрядів, де N- кількість МК заданого формату. У нашому випадку N=38, q=6.

Таблиця 2.2

Кодування МК

Аналогічним чином закодуємо оператори Yi, надавши нульовий код порожньому операторному полю (табл. 2.3).

Таблиця 2.3

Кодування Y

Таблиця 2.5

Вміст керуючої пам`яті.

2.4. Синтез схеми автомата.

Схема СФА являє собою мультиплексор, який в залежності від коду логічної умови, що перевіряється, передає на вихід Z1 значення відповідної ЛУ. При цьому сигнал Z2 завжди є інверсією сигналу Z1. Таким чином, отримаємо слідуючі вирази для Z1 і Z­2:

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.

Розподіл МО за мікро-

командами

На наступному етапі синтезуємо схеми РАМК і РМК, використовуючи щ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).

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.

(продовження)

Адресація МК.

Таблиця 3.2.

Вміст керуючої пам`яті автомата з природною адресацією.

Таблица 3.2.

(продовження)

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

Синтез схеми ЛАМК.

Схема РМК містить 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 СФМО y­0 .... 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.

Адресація МК.

Таблиця 4.2

Вміст керуючої пам`яті.

Таблиця 4.2.

(продовження)

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.

Апаратурні витрати для синтезованих автоматів.

5.2. Визначення автомата з мінімальними апаратурними витратами.

Заповнимо таблицю, де для кожного автомата знаком “+" відмітимо мінімальні витрати на даний тип елементів, а знаком “-" -немінімальні (табл. 5.2.).

Таблиця 5.2.

Як видно з таблиці 5.2., автомат з природною адресацією виграє по двом параметрам: по кількості тригерів і ПЗП.

Для підтвердження правильності вибору автомата застосуємо також оцінку за Квайном (за сумарною кількістю входів елементів). Будемо вважати кількість входів у ЛЕ - 4, у тригера - 4, у ПЗП -9 і у лічильника - 9. З врахуванням вищенаведених значень, для автомата з ПА показник оцінки складе - 659, для автомата з ПрА - 477, для автомата з КА- 482.

Як видно з приведених оцінок, автомат з примусовою адресацією далеко не оптимальний, а автомати з природною і комбінованою адресацією по витратах практично однакові, але все ж автомат з ПрА має деяку перевагу перед автоматом з КА. Таким чином, результатом проектування буде схема автомата з природною адресацією мікрокоманд.