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

1. ПОБУДОВА ОБ'ЄДНАНОЇ ГСА

1.1. Побудова ГСА

По описах граф-схем, приведених в завданні до курсової роботи, побудуємо ГСА Г₁-Г₅ (мал. 1.1-1.5), додавши початкові і кінцеві вершини і замінивши кожний оператор Yi операторною вершиною, а кожну умову X_i - умовною.

1.2. Методика об'єднання ГСА

У ГСА Г₁-Г₅ є однакові ділянки, тому побудова автоматів за ГСА Г₁-Г₅ приведе до невиправданих апаратурних витрат. Для досягнення оптимального результату скористаємося методикою С.І.Баранова, яка дозволяє мінімізувати число операторних і умовних вершин. Заздалегідь помітимо операторні вершини в початкових ГСА, керуючись слідуючими правилами:

1) однакові вершини Y_i в різних ГСА відмічаємо однаковими мітками A_j;

2) однакові вершини Y_i в межах однієї ГСА відмічаємо різними мітками A_j;

3) у всіх ГСА початкову вершину помітимо як А₀, а кінцеву - як A_k.

На наступному етапі кожній ГСА поставимо у відповідність набір змінних P_nО {P₁...P_q}, де q=]log₂N[, N -кількість ГСА. Означувальною для ГСА Г_n ми будемо називати кон`юнкцию P_n=p₁^eЩ...Щp_qⁿ еО{0,1}, причому p⁰=щр, p¹=р. Об'єднана ГСА повинна задовольняти слідуючим вимогам:

1) якщо МК A_i входить хоча б в одну часткову ГСА, то вона входить і в об'єднану ГСА Г₀, причому тільки один раз;

2) при підстановці набору значень (е₁...e_n), на якому P_q=1 ГСА Г₀ перетворюється в ГСА, рівносильну частковій ГСА Г_q.

При об'єднанні ГСА виконаємо слідуючі етапи:

-сформуємо часткові МСА М₁ - М₅, що відповідні ГСА Г₁ - Г₅;

- сформуємо об'єднану МСА М₀;

- сформуємо системи дужкових формул переходу ГСА Г₀;

- сформуємо об'єднану ГСА Г₀.

1.3. Об'єднання часткових ГСА

Часткові МСА М₁-М₅ побудуємо по ГСА Г₁-Г₅ (мал.1.1) відповідно. Рядки МСА відмітимо всіма мітками A_i, що входять до ГСА, крім кінцевої A_k.

ПОЧАТОК A₀

1

0 X₁ 1

2

A₁

3

0

4 X₂ A₂ 1

5

A₃

6

A₄

7

A₅

8

A₆

9

A₇

10

A₈

КіНЕЦь A_k

Мал.1.1. Часткова граф-схема алгоритму Г₁

ПОЧАТОК A₀

1

A₁

2

A₇

0 3 1

X₃

4 5

A₉ A₆

6 7

A₁₀ A₁₂

8 9

A₃ A₂₂

10

A₁₁

КіНЕЦЬ A_k

Мал.1.2. Часткова граф-схема алгоритму Г₂

ПОЧАТОК A₀

1

A₁₁

0 2 1

X₁

3 4

A₁₅ A₁₆

6

5 1

X₃ A₁₂

0

7 8

A₆ A₁₃

КіНЕЦЬ А_k

Мал.1.3. Часткова граф-схема алгоритму Г₃

ПОЧАТОК A₀

1

0 1

X₁

2

A₁₃

3

A₉

4

A₈

5

1 X₂

6 0

A₁₇

7

A₆

8

A₂

9

A₁₈

КіНЕЦЬ A_k

Мал.1.4. Часткова граф-схема алгоритму Г₄

ПОЧАТОК A₀

1

A₁

2

A₆

3

A₁₉

4

0 1

X₁

5

0 X₂

1

6

A₂₀

7

A₁₇

8

A₂

9

A₂₁

КіНЕЦЬ A_k

Мал.1.5. Часткова граф-схема алгортиму Г₅

Стовпці МСА відмітимо всіма мітками A_i­, що входять до ГСА, крім початкової A₀. На перетині рядка A_i і стовпця A_j запишемо формулу переходу f_ij від оператора A_i до оператора A_j. Ця функція дорівнює 1 для безумовного переходу або кон`юнкції логічних умов, відповідних виходам умовних вершин, через які проходить шлях з вершини з міткою A_i у вершину з міткою 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.2-1.6

Таблиця 1.2

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

Таблиця 1.3

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

Таблиця 1.4

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

Таблиця 1.5

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

Таблиця 1.6

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

На наступному етапі побудуємо об'єднану МСА М₀, в якій рядки відмічені всіма мітками А_i, крім А_k, а стовпці - всіма, крім А₀. На перетині рядка А_i і стовпця А_j запишемо формулу переходу, яка формується таким чином: F_ij=P₁f_ij¹+...+P_nf_ijⁿ (n=1...N). Де f_ijⁿ-формула переходу з вершини А_i у вершину А_j для n-ої ГСА. Наприклад, формула переходу А₀®А₁ буде мати вигляд F_0,1=щx₁щp₁щp₂щp₃+ щp₁щp₂p₃+ +p₁щp₂щp₃. У результаті ми отримаємо об'єднану МСА М₀ (табл.1.7). Ми маємо можливість мінімізувати формули переходу таким чином: розглядаючи ГСА Г₀ як ГСА Г_n, ми підставляємо певний набір P_n=1, при цьому змінні p₁..p_q не змінюють своїх значень під час проходу по ГСА. Таким чином, якщо у вершину А_i перехід завжди здійснюється при незмінному значенні p_q, то це значення p_q в рядку А_i замінимо на “1", а його інверсію на “0". Наприклад, у вершину А₃ перехід здійснюється при незмінному значенні щp₁ і щp₂, отже в рядку А₃ щp₁ і щp₂ замінимо на “1", а p₁ і p₂ на “0". У результаті отримаємо формули F_3,4=щp₃, F_3,11=p₃. Керуючись вищенаведеним методом, отримаємо мінімізовану МСА М₀ (табл.1.8).

По таблиці складемо формули переходу для об'єднаної ГСА Г₀. Формулою переходу будемо називати слідуюче вираження: A_i®F_i,1А₁+..+F_i,kА_k, де F_i,j- відповідна формула переходу з мінімізованої МСА. У нашому випадку отримаємо слідуючу систему формул:

A₀®щx₁щp₁щp₂щp₃A₁+щp₁щp₂p₃A₁+p₁щp₂щp₃A₁+x₁щx₂щp₁щp₂щp₃A₂+x₁x₂щp₁щp₂щp₃A₃+

+щx₁щp₁p₂p_3­A₈+x₁щp₁p₂p₃A₁₃+щp₁p₂щp₃A₁₄

A₁®щp₁щp₃A_2­+p₁щp₃A₆+щp₁p₃A₇

A₂®щp₁щp₂щp₃A₆+щp₁p₂p₃A₁₈+p₁щp₂p₃A₂₁

A₃®щp₃A₄+p₃A₁₁

A₄®A₅

A₅®А₆

Таблиця 1.7

Об`єднана МСА М_o

Таблиця 1.8

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

A₆®щp₁p₂p₃A₂+щp₁щp₂щp₃A₇+щp₁щp₂p₃A₁₂­+p₁щp₂щp₃A₁₉+щp₁p₂щp₃A_k

A₇®x₃p₃A₆+щp₃A₈+щx₃p₃A₉

A₈®x₂p₂p₃A₁₇+щp₂щp₃A_k+щx₂p₂p₃A_k

A₉®p_2­A₈+щp₂A₁₀

A₁₀®A₃

A₁₁®A_k

A₁₂®щp₂p₃A₂₂+p₂щp₃A₁₃

A₁₃®p₃A₉+щp₃A_k

A_14­®щx₁A₁₅+x₁A₁₆

A₁₅®x₃A₆+щx₃A_k

A₁₆®A₁₂

A₁₇®p₁щp₂щp₃A_2­+щp₁p₂p₃A₆

A₁₈®A_k

A₁₉®x₁щx₂A₂+x₁x₂A₂₀+щx₁A₂₁

A₂₀­®A₁₇

A₂₁®A_k

A₂₂®A_k

При побудові системи дужкових формул переходу необхідно кожну формулу привести до вигляду Аx₁+Вщx₁, де А і В -деякі вирази, а x₁ і щx₁-логічні умови переходу. Формули переходу для вершин А₃, А₄, А₅, А₉, А₁₀, А₁₁, А₁₃, А₁₄, А₁₅, А₁₆, А₁₈, А₂₀, А₂₁, А₂₂ вже є елементарними (розкладеними), а в інших є вирази виду А_n®x_j(А) +щx_jp_i(В). Тут p_i відповідає чекаючій вершині (мал.1.6). Подібних вершин в об'єднаній ГСА бути не повинно. Для їх усунення скористаємося слідуючим правилом: додавання виразу [P_qА_n] не змінить формулу, якщо набір P_q не використовується для кодування ГСА або вершина А_n відсутня в ГСА з кодом P_q. Таким чином, додаючи допоміжні набори, ми отримаємо можливість за допомогою елементарних перетворень звести формули до необхідного вигляду. Наприклад, формула A₈®x₂p₂p₃A₁₇+щp₂щp₃A_k+щx₂p₂p₃A спрощується таким чином A₈=p₃(x₂p₂A₁₇+щx₂p₂A_k)+щp₃щp₂A_k=p₃p₂(x₂A₁₇+щx₂A_k)+щp₃щp₂A_k=

1 X_j 0

P_i 0

1

Мал.1.6 Приклад чекаючої вершини P_i

=[щp₃p₂(x₂A₁₇+щx₂A_k)]+p₃p₂(x₂A₁₇+щx₂A_k)+щp₃щp₂A_k+[p₃щp₂A_k]=щp₂A_k+p₂(x₂A₁₇+щx₂A_k). Тут вершина А₈ не зустрічається у ГСА ,в кодах яких присутні комбінації щp₃p₂ і p₃щp₂. Нижче наведено розклад усіх неелементарних формул переходу.

A₀=p₁(щp₂щp₃A₁)+щp₁(щx₁щp₂щp₃A₁+щp₂p₃A₁+x₁щx₂щp₂щp_3­A₂+x₁x₂щp₂щp₃A_3­+

+щx₁p₂p₃A₈+x₁p₂p₃A₁₃+p₂щp₃A₁₄)=p₁(щp₂щp₃A₁)+[p₁щp₂щp₃A₁]+

+щp₁(p₂(щx₁p₃A₈+x₁p₃A₁₃+щp₃A₁₄)+щp₂(щx₁щp₃A₁+p₃A₁+x₁щx₂щp₃A₂+

+x₁x₂щp₃A_3­))=p₁(щp₂A₁)+[p₁p₂A₁]+щp₁(p₂(p₃(щx₁A₈+x₁A₁₃)+щp₃A₁₄)+

+щp₂(щp₃(щx₁A₁+x₁x₂A₃+x₁щx₂A₂­)+p₃A₁))= p₁A₁+щp₁(p₂(p₃( щx₁A₈+

+x₁A₁₃)+щp₃A₁₄)+щp₂(щp₃(щx₁A₁+x₁(x₂A₃+щx₂A₂))+p₃A_1­))

A₁=щp_1­(p₃A₇+щp₃A₂)+p₁щp₃A₆+[p₁p₃A₆]= щp_1­(p₃A₇+щp₃A₂)+p₁A₆

A₂=p₁(щp₂p₃A₂₁)+щp₁(щp₂щp₃A₆+p₂p₃A₁₈)= p₁(щp₂p₃A₂₁)+[p₁щp₂p₃A₂₁]+

+щp_1­(щp₂щp₃A₆+[p₂щp₃A₆]+p₂­p₃A₁₈+[p₃щp₂A₁₈])=p₁(щp₂A₂₁)+щp₁(щp₃A₆+

+p₃A₁₈)=p₁(щp₂A₂₁)+[p₁p₂A₂₁]+щp₁(щp₃A₆+p₃A₁₈)=p₁A₂₁+щp₁(щp₃A₆+

+p₃A₁₈)

A₆=p₁(щp₂щp₃A₁₉)+[p₁щp₂p₃A₁₉]+щp₁(p₂p₃A₂+щp₂щp₃A₇+щp₂p₃A₁₂+p₂щp₃A_k)=

=p₁щp₂A₁₉+[p₁p₂A₁₉]+щp₁(p₂(p₃A₂+щp₃A_k)+щp₂(щp₃A₇+p₃A₁₂­))=p₁A₁₉+

+щp₁(p₂(p₃A₂+щp₃A_k­)+щp₂(щp₃A₇+p₃A₁₂))

A₇=p₃(x₃A₆+щx₃A₉)+щp₃A₈

A₈=p₃(x₂p₂A₁₇+щx₂p₂A_k)+щp₃щp₂A_k=p₃p₂(x₂A₁₇+щx₂A_k)+щp₃щp₂A_k=

=[щp₃p₂(x₂A₁₇+щx₂A_k)]+p₃p₂(x₂A₁₇+щx₂A_k)+щp₃щp₂A_k+[p₃щp₂A_k]=щp₂A_k+

+p₂(x₂A₁₇+щx₂A_k)

A₁₂=щp₂p₃A₂₂+p₂щp₃A₁₃+[p₂p₃A₂₂]+[щp₂щp₃A₁₃]=p₃A₂₂+щp₃A₁₃

A₁₇=p₁щp₂щp₃A₂+[p₁щp₂p₃A₂]+щp₁p₂p₃A₆+[щp₁щp₂p₃A_6­]=p₁щp₂A₂+[p₁p₂A₂]+

+щp₁p₃A₆+[щp₁щp₃A₆]=p₁A₂+щp₁A₆­

A₁₉=x₁(щx₂A₂+x₂A₂₀)+щx₁A₂₁

Об'єднану ГСА Г₀ (мал.1.7) побудуємо відповідно до формул переходу, замінюючи кожну мітку А_i відповідною операторною вершиною Y_t, а кожний вираз X_i і P_j відповідними умовними вершинами.

2.СИНТЕЗ АВТОМАТА З ПРИМУСОВОЮ АДРЕСАЦІЄЮ МІКРОКОМАНД.

2.1. Принцип роботи автомата.

При примусовій адресації адреса наступної мікрокоманди задається в полі поточної мікрокоманди. Формат МК в такому випадку слідуючий (мал. 2.1.).

₁ Y _{m 1} X _{l 1} A_{0 k 1} A_{1 k}

Мал. 2.1 Формат команди автомата з ПА.

Тут у полі Y міститься код, що задає набір мікрооперацій, у полі X-код логічної умови, що перевіряється, у полях A₀ і A₁- адреси переходу при невиконанні логічної умови, що перевіряється або безумовному переході і при істинності логічної умови відповідно. Розрядність полів визначається таким чином:

m=]log₂T[ Т- число наборів мікрооперацій, що використовуються в ГСА, в нашому випадку Т=17, m=5

l=]log₂ (L+1)[ L-число логічних умов у ГСА, в нашому випадку L=6, l=3

k=]log₂ Q[ Q -кількість мікрокоманд.

Структурна схема автомата приведена на мал. 2.2. Автомат функціонує таким чином. Схема запуску складається з RS -тригера і схеми “&", яка блокує надходження синхроімпульсів на РАМК і РМК. За сигналом “Пуск" тригер встановлюється в одиницю і відбувається запис мікрокоманд до регістру. Поле Y надходить на схему формування МО і перетворюється в деякий набір мікрооперацій. Поле X надходить до схеми формування адреси, яка формує сигнал Z₂, якщо перехід безумовний (X=0) або ЛУ , що перевіряється, дорівнює 0, або сигнал Z₁ у випадку істинності ЛУ. За сигналом Z₁(Z₂) до адресного входу ПЗП надходить значення поля A₁(A₀). За сигналу y₀ тригер встановлюється в нуль і автомат зупиняє свою роботу. За сигналом "Пуск" до РАМК заноситься адреса початкової МК (А=0).

2.2. Перетворення початкової ГСА.

Перетворення буде полягати в тому, що у всі операторні вершини, пов'язані з кінцевою, вводиться сигнал y₀, а між всіма умовними вершинами, які пов'язані з кінцевою, вводиться операторна вершина, що містить сигнал y₀. Причому, ця вершина буде загальною для всіх умовних. З урахуванням вищесказаного отримаємо перетворену ГСА (мал. 2.3). У перетвореній ГСА ми зберігаємо позначення Y_i, але при цьому пам'ятаємо, що кожна мікрокоманда Y_i

РАМК

Z₁ Z₂

S T & ПЗП

“Пуск”

СІ R РМК Y X A₀ A₁ СФМО Z₁ y­₀ .... y_i СФА до ОА Z₂

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

розбивається на мікрооперації y_i..y_j згідно з табл. 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=]log₂N[ розрядів, де 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

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

Таблиця 2.3

Кодування Y

Таблиця 2.5

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

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

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

Z₁=X₁щT₇щT₈T₉+X₂щT₇T₈щT₉+X₃щT₇T₈T₉+P₁T₇щT₈щT₉+P₂T₇щT₈T₉+P₃T₇T₈щT₉

Z₂=щZ₁

або, звівши до заданого базису (4 АБО-НІ), отримаємо

Z₁=щ щ(щ щ(A+B+C+D)+E+F), де

A=щ щ( X₁щT₇щT₈T₉)=щ(щX₁+T₇+T₈+щT₉)

B=щ щ( X₂щT₇T₈щT₉)=щ(щX₂+T₇+щT₈+T₉)

C=щ щ( X₃щT₇T₈T₉)=щ(щX₃+T₇+щT₈+щT₉)

D=щ щ( P₁T₇щT₈щT₉)=щ(щP₁+щT₇+T₈+T₉)

E=щ щ( P₂T₇щT₈T₉)=щ(щP₂+щT₇+T₈+щT₉)

F=щ щ( P₃T₇T₈щT₉)=щ(щP₃+щT₇+щT₈+T₉)

Інформація, що надходить на адресні входи ПЗП формується таким чином: A_i=A_0iZ₁+A_1iZ₂ або, приводячи до заданого базису, отримуємо A_i=щщ(щ(щA_0i+щZ₁)+щ(щA_1i+щZ₂)).

Синтезуємо тепер схему дешифратора, що формує сигнали мікрооперацій y_i. Поява одиниці, відповідної кожному Y, відбувається при появі на вході дешифратора коду даного Y, тобто Y_i=T₂^eЩT₃^eЩT₄^еЩT₅^еЩT₆^е, де еО{0,1} T⁰=щT, T¹=T. Або приводячи до заданого базису, отримаємо: Y_i=щ(щ щ(T₂^щe+T₃^щe+T₄^ще+T₅^ще)+T₆^ще). Таким чином, схема, що формує сигнал Y з п`ятирозрядного коду виглядає таким чином(мал. 2.4)

T₆^щe

1 1 1 Y_i

T₂^щe

Мал. 2.4. Схема формування сигналу Yi.

Враховуючи, що розряд T₂ рівний “1" при формуванні тільки двох сигналів Y₁₈ і Y₂₀, то схему(мал. 2.4) будемо використовувати для формування Y₁, Y₂₀, для яких співпадають молодші чотири розряди та для Y₁₈, для якого молодші чотири розряди співпадають з кодом порожньої операторної вершини. А для всіх інших Y схему можна спростити (мал.2.5.).

T₆^щe

1 Y_i

T₃^щe

Мал.2.5. Спрощена схема формування сигналу Y_i.

Згідно з наведеними схемами запишемо формули для всіх Y_i.

Y₁=щ (щ щ(T₂+T₃+T₄+T₅)+щT₆)

Y₂= щ(T₃+T₄+щT₅+T₆)

Y₃= щ(T₃+T₄+щT₅+щT₆)

Y₅= щ(T₃+щT₄+T₅+T₆)

Y₇= щ(T₃+щT₄+T₅+щT₆)

Y₈= щ(T₃+щT₄+щT₅+T₆)

Y₉= щ(T₃+щT₄+щT₅+щT₆)

Y₁₀=щ(щT₃+T₄+T₅+T₆)

Сигнали мікрооперацій y_j отримаємо, об'єднуючи по “або" виходи відповідні операторам Y_i, в яких зустрічається МО y_j. При цьому будемо користуватися таблицею

Таблиця 2.5.

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

командами

На наступному етапі синтезуємо схеми РАМК і РМК, використовуючи щRщS тригери. Скористаємося класичним методом синтезу регістрів і заповнимо слідуючу таблицю (табл. 2.6.).

Таблиця 2.6.

Синтез РАМК та РМК

У результаті отримаємо слідуючу схему для базового елементу РАМК та РМК (мал.2.6).

A_i

1 S TT Q

СІ C

R

“Reset” R щQ

Мал. 2.6. Базовий елемент регістра.

Схема РАМК містить 6 таких елементів, а схема РМК - 21. При побудові схеми сигнали щT₁..щT₂₁ будемо знімати з інверсних виходів елементів регістрів. Кількість мікросхем ПЗП визначимо за формулою: N_ПЗП­=]R/3[, де R - розрядність мікрокоманди R=21, N_ПЗП=7. Для зберігання мікропрограми досить однієї лінійки ПЗП, оскільки Q_ПЗП=8, тобто одна мікросхема розрахована на зберігання 256 трьохбітових комбінацій, а в нашому випадку потрібно тільки 38. При побудові схеми будемо записувати в РАМК інверсію адреси, а до ПЗП будемо подавати адресу з інверсних виходів елементів регістра, таким чином, ми заощадимо 6 елементів-інверторів у СФА. З врахуванням вищесказаного побудуємо схему автомата з примусовою адресацією мікрокоманд(мал. 2.7).

3.СИНТЕЗ АВТОМАТА З ПРИРОДНОЮ АДРЕСАЦІЄЮ МІКРОКОМАНД

3.1. Принцип роботи автомата.

При природній адресації микрокоманд існує три формата МК (мал. 3.1.).

П ₁ FY _m ОМК

П ₁ FX _{l 1} FA _r УМК1 П ₁ Ж _{l 1} FA _r УМК2

Мал.3.1. Формати мікрокоманд автомата з природною адресацією..

Тут формат ОМК відповідає операторній вершині, УМК1-умовній, а УМК2-вершині безумовного переходу. При подачі сигналу “пуск" лічильник ЛАМК обнуляється, і за сигналом СІ відбувається запис МК до регістра. СФМО формує відповідні МО при П=1 або видає на всіх виходах нулі при П=0. СФА в залежності від П і вмісту поля FX, формує сигнали Z₁ і Z₂. Сигнал Z₁ дозволяє проходження синхроімпульсів на лічильний вхід ЛАМК, а Z₂ дозволяє запис до лічильника адреси наступної МК з приходом синхроімпульсу.

Визначимо розрядність полів. l=]log₂(L+1)[, де L-число умовних вершин. L=6, l=3

m=]log₂T[ Т- число наборів мікрооперацій, що використовуються в ГСА, в нашому випадку Т=17, m=5

r=]log₂ Q[, Q - кількість мікрокоманд.

3.2.Перетворення початкової ГСА.

Перетворення буде полягати в тому, що до всіх операторних вершин, пов'язаних з кінцевою, вводиться сигнал y₀, а між всіма умовними вершинами, які пов'язані з кінцевою, вводиться операторна вершина, що містить сигнал y₀. Крім цього, в ГСА вводяться спеціальні вершини безумовного переходу X₀, відповідні формату УМК2. Введення таких вершин необхідне для виключення конфліктів адресації мікрокоманд. У автоматі з природною адресацією (рис3.2.) при істинності(помилковість) логічної умови перехід здійснюється до вершини з адресою на одиницю великим, а при (помилковість)істинності ЛУ перехід відбувається за адресою, записаною в полі FA. У нашому випадку будемо додавати одиницю при істинності ЛУ або при переході з операторной вершини. Якщо в одній точці сходиться декілька переходів по “1" або з операторної вершини, то всі вершини з яких здійснювався перехід, повинні були б мати однакову (на одиницю меншу ) адресу, ніж наступна команда. Але це неможливо.

Z₁ +1

сі Z₂ А ЛАМК

“Пуск”

1 ПЗП

РМК

FY П FX FA

СФМО

СФА Z₁

y₀.....y_i к ОА

Z₂

Мал.3.2. Структурна схема автомата з природною адресацією.

Для виключення подібних ситуацій вводять спеціальну вершину безумовного перходу (мал. 3.3). Дані вершини додаємо таким чином, щоб в одній точці сходилася будь-яка кількість переходів по “0" і тільки один по “1" або з операторної вершини. З врахуванням вказаних перетворень отримаємо перетворену ГСА (мал. 3.4).

X₀ 0

1

Мал. 3.3. Вершина безумовного переходу.