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

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