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

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. Вершина безумовного переходу.

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

На перетвореній ГСА виділимо мікрокоманди форматів ОМК, УМК1, УМК2. У результаті отримаємо 63 МК. Виконаємо їх адресацію. Для цього запишемо всі природні послідовності команд (ланцюжки вершин, перехід між якими здійснюється по “1" або через операторну вершину). У результаті отримаємо:

a₁=[O₁,O₅]

a₂=[ O₂ ,O₆ ,O₇ ,O₃₆ ,O₄₈ ,O₅₁ ,O₅₅ ,O₃₄ ,O₄₇ ,O₄₉ ,O₅₆ ,O₅₉ ,O₁₂ ,O₁₆ ,O₄₅]

a₃=[ O₃ ,O₉ ,O₁₃ ,O₁₈]

a₄=[ O₄ ,O₁₀ ,O₁₁]

a₅=[ O₈ ,O₁₄ ,O₂₀ ,O₃₀ ,O₃₂ ,O₃₅]

a₆=[ O₆₀ ,O₁₅ ,O₂₁ ,O₂₂]

a₇=[ O₁₇ ,O₅₂ ,O₅₇ ,O₆₁ ,O₆₂]

a₈=[ O₁₉ ,O₂₈ ,O₂₉]

a₉=[ O₂₃ ,O₂₅ ,O₂₇ ,O₃₁ ,O₃₇ ,O₄₄ ,O₄₃ ,O₅₃ ,O₅₄]

a₁₀=[ O₂₄ ,O₂₆]

a₁₁=[ O₃₃]

a₁₂=[ O₃₈ ,O₄₁ ,O₄₂]

a₁₃=[ O₃₉ ,O₄₀]

a₁₄=[ O₄₆]

a₁₅=[ O₅₀]

a₁₆=[ O₅₈]

a₁₇=[ O₆₃]_­

Перерахуємо в таблиці адресації (табл. 3.1) підряд всі послідовності a₁-a₁₇ і закодуємо їх R-розрядним кодом. R=]log₂N[, N-кількість мікрокоманд (N=63, R=6). Закодуємо також оператори Y_i, поставивши їм у відповідність п`ятирозрядний код. Будемо використовувати те ж кодування, що і в автоматі з ПА.(табл. 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