ПТЦА — Прикладна теорія цифрових автоматов

1. Методи аналізу та синтезу комбінаційних схем.

Технічним аналогом булевой функції в обчислювальної техніки є, так звана, комбінаційна схема, на вхід якій надходять і із виходу знімаються електричні сигнали як однієї з рівнів напруги, відповідних значенням логічного 0 і логічного 1.

[pic].

Для з’ясування, що таке комбінаційна схема, розглянемо схему P. S, має m входів і n виходів (рис. 1). На її входи може бути подано набори значень вхідних змінних Xi {0,1}, [pic], але в виходах формуються вихідні перемінні Yj ({0,1}, [pic].

Схема P. S називається комбінаційної, якщо кожну з n функцій її виходів Y1, Y2, …, Yn можна подати як булеву функцію вхідних змінних X1, X2, …, Xm.

Комбінаційна схема описується з допомогою системи рівнянь (1), де Fi — булева функция.

[pic].

Відповідно до визначення комбінаційної схеми, значення вихідних змінних Yj в довільний час однозначно визначаються значеннями вхідних змінних Xi.

Структурно комбінаційна схема то, можливо представлена як сукупність елементарних логічних схем — логічних елементів (ЛЕ). ЛЕ виконують над вхідними перемінними елементарні логічні операції типу И-НЕ, І, АБО, ИЛИ-НЕ тощо. Кількість входів логічного елемента відповідає числу аргументів воспроизводимой їм булевой функції. Графічне зображення комбінаційної схеми, у якому показані зв’язок між різними елементами, не бажаючи елементи представлені умовними позначками, називається функціональної схемой.

У результаті розробки комбінаційних схем доводиться виконувати завдання аналізу та синтеза.

Завдання аналізу у визначенні статичних і динамічних властивостей комбінаційної схеми. У статиці визначаються булевы функції, реалізовані комбінаційної схемою відомою їй структурі. У динаміці розглядається здатність надійної функціонування схеми в перехідних процесах на зміну значень змінних на входах схеми, тобто. визначається наявність на виходах схеми можливих небажаних імпульсних сигналів, які йдуть безпосередньо з висловів для булевых функцій, реалізованих схемой.

Завдання синтезу у побудові з заданого набору логічних елементів комбінаційної схеми, реалізує задану систему булевых функций.

Рішення завдання синтезу перестав бути однозначним, можна запропонувати різні варіанти комбінаційних схем, що реалізують те ж систему булевых функцій, але які відрізняються тим чи іншим параметрами. Розробник комбінаційних схем від цього безлічі варіантів вибирає один, виходячи з додаткових критеріїв: мінімального кількості логічних елементів, необхідні реалізації схеми, максимального швидкодії тощо. Є різноманітні методи синтезу комбінаційних схем, серед яких найбільш розроблений канонічний метод.

1.1. Канонічний метод синтезу комбінаційних схем.

Як уже відзначалося вище, комбінаційна схема (КС) може мати кілька виходів. При канонічному методі передбачається, кожна вихідна функція реалізується своєї схемою, сукупність яких і було дає необхідну КС. Тому синтез складної КС з n виходами замінюється синтезом n схем з однією выходом.

Відповідно до канонічному методу синтез КС включає у собі ряд этапов.

1. Підлягаючий реалізації булева функція (чи її заперечення) представляється як СДНФ.

2. З використанням методів мінімізації визначається минимальная.

ДНФ (МДНФ) чи мінімальна КНФ (МКНФ). З отриманих двох мінімальних форм вибирається більш простая.

3. Булеву функцію в мінімальної формі відповідно до п. 2 у заданому (чи обраному розробником) базисі .

4. За поданням функції в заданому базисі будують комбінаційну схему.

Слід зазначити, що підлягаючий реалізації булева функція F (X1,X2,…, Xm) то, можливо задана не так на всіх можливих наборах аргументів X1, X2, …, Xm. На тих наборах, де функція невизначена, її доопределяют те щоб внаслідок мінімізації отримати просту МДНФ чи МКНФ. У цьому спроститься і самі КС. З іншого боку, частенько з з метою отримання ще більше простого уявлення функції МДНФ, отримана в п. 2, представляється в так званої скобочной формі, тобто. виносяться за дужки загальні частини импликант МДНФ.

Розглянемо канонічний метод синтезу з прикладу побудови схеми повного одноразрядного двоичного сумматора.

Як знаємо з курсу машинної арифметики, повний одноразрядный акумулятор — цей прилад, яку здійснює складання по mod 2 відповідних розрядів (X1,X2) двійкових чисел з урахуванням перенесення (Рm) в даний розряд із молодшого розряду суми. Акумулятор виробляє цифру результату (P.S) у цьому розряді і перенесення (Рс) у сусідній старший розряд суми. Таблиця істинності такого сумматора (тобто. уявлення булевой функції, що він реалізує, як СДНФ) представлена ниже.

|X1 |0|0|0|0|1|1|1|1| |X2 |0|0|1|1|0|0|1|1| |Pm |0|1|0|1|0|1|0|1| |P.S |0|1|1|0|1|0|0|1| |Pc |0|0|0|1|0|1|1|1|.

[pic].

Необхідно отримати булевы функції S=F1(X1,X2,Рm) і Рс=F2(X1,X2,Рm). Карти Карно тих функцій наведено нижче (рис.2).

Відповідно до приведених карт, МДНФ відповідних функцій має вид:

S=[pic][pic]Pm+[pic]X2[pic]+X1[pic][pic]+ X1 X2 Pm.

Pc= X1 X2+X1 Pm+X2 Pm.

Отримана система булевых функцій представленій у базисі І, АБО, НЕ. Відповідна їй КС приведено малюнку 4.

Отриману комбінаційну схему можна спростити, винісши за дужки загальні частини вчених у висловлюваннях для P. S і Рc, проте істотного результату це дасть (бажано самостійно у тому убедиться).

Значно спростити схему можна, згідно з іншим базисом, наприклад логічним елементом «ЯКИЙ ВИКЛЮЧАЄ АБО ». І тут вираз для P. S можна записати P. S = (X1+X2+ Рm) mod2= X1(X2(Рm. Тоді схема для P. S матиме вид (рис.3). [pic].

Іноді для синтезу КС з кількома виходами можна використовувати наступний прийом. Вважатимемо, що з синтезі схеми сумматора функція P. S є функцією чотирьох змінних: S=f (X1,X2,Рm, Рс). Таблиця істинності на цей випадок набирає вигляду зображений в таблиці 2.

[pic] |0 |0 |0 | |0 |1 |0 | |1 |0 |1 | |1 |1 |1 |.

З наведеної таблиці переходів для даного триггера Qt+1 = f (Qt, Dt) можна було одержати таблицю функцій його входів Dt = ((Qt, Qt+1).

|Q t |Q |D t | | |t+1 | | |0 |0 |0 | |0 |1 |1 | |1 |0 |0 | |1 |1 |1 |.

Як очевидно з таблиці, стан, у якому переходить тригер (середній стовпець), збігаються з котрі вступили з його вхід сигналом D (t) (правий стовпець). У зв’язку з цим таблиця функцій порушення пам’яті синтезованого автомата з допомогою D-триггеров буде цілком збігатися з кодованої таблицею переходів цього автомата. Промисловість випускає D-триггера в інтегральному виконанні. Наприклад, [pic] K155TM2 (рис. 25).Таких тригерів два щодо одного корпусі. Вхід З -вхід синхронізації, Q,(Q — виходи, Q — прямий, [pic] - інверсний. R, P. S — входи установки в 0 і одну відповідно. При подачі на вхід R і P. S логічного нуля тригер встановлюється на відповідні стану незалежно від сигналу на входах D і C.

T-триггер — тригер зі рахунковим входом — має один інформаційний вхід Т і тільки вихід Q та здійснює підсумовування по модулю два значень сигналу T і стан Q у заданий момент времени.

Умовне позначення і таблиця переходів T-триггера представлена на рис 26. [pic].

|T |Q t|Q | | | |t+1 | |0 |0 |0 | |0 |1 |1 | |1 |0 |1 | |1 |1 |0 |.

Таблиця функцій входів триггера Tt = f (Qt, Qt+1) представленій у таблице.

|Q t |Q |T t | | |t+1 | | |0 |0 |0 | |0 |1 |1 | |1 |0 |1 | |1 |1 |0 |.

З цієї таблиці можна одержувати функцію порушення елементів пам’яті при синтезі автомата з урахуванням T-триггера. Наприклад, якщо автомат перейшов із стану ai = 010 до стану aj = 110, то тут для забезпечення цього переходу функції порушення мали бути зацікавленими: на першому триггера під час переходу з 0 один T1 = 1, на другому триггера під час переходу з 1 один T2 = 0, для третього триггера під час переходу з 0 в 0 T3 =0 і т.д.

У чистому вигляді промисловість не випускає T-триггера.

RS-триггер — тригер з роздільними входами.

Цей тригер має дві вхідних каналу R і P. S і тільки вихідний Q. Вхід P. S (set) називається входом установки в одиницю, вхід R (reset) — входом установки в нуль. Умовне позначення і таблиця переходів RS-триггера представлена на рис. 27.

У таблиці переходів під час подачі комбінації P. S = R = 1 стан переходу Qt+1 не визначене, і ця комбінація сигналів є забороненої для RS-триггера.

Таблицю переходів можна більш компактно зобразити як (див. табл. 21б) Аналізуючи табл.21 б, в відзначаємо що, наприклад, перехід триггера з 0 в 0требует подачі комбінації R=0, S=0 чи R=1,S=0, тобто. можна сказати що це перехід буде за R=X (байдуже стан), S=0.

Аналогічно розмірковуючи стосовно іншим переходами одержимо таку таблицю функцій входов.

|R |P.S |Q t |Q | | |R |P.S |Q | | | | |t+1 | | | | |t+1 | |0 |0 |0 |0 | | |0 |0 |0 | |0 |0 |1 |1 | | |0 |1 |1 | |0 |1 |0 |1 | | |1 |0 |0 | |0 |1 |1 |1 | | |1 |1 |- | |1 |0 |0 |0 | | | | |б) | |1 |0 |1 |0 | | | | | | |1 |1 |0 |- | | | | | | |1 |1 |1 |- |а) | | | | |.

|Q t |Q |Rt |P.S | | |t+1 | | | |0 |0 |X |0 | |0 |1 |0 |1 | |1 |0 |1 |0 | |1 |1 |0 |X |.

З таблиці можна було одержати функцію порушення пам’яті автомата при синтезі з урахуванням RS-триггеров. Наприклад, якщо автомат переходить зі стану ai= 010 до стану aj=110, то тут для забезпечення такого переходу функції порушення повинні прагнути бути: на першому триггера під час переходу з 0 один R1 =0, S1 = 1; на другому триггера під час переходу з 1 один R2 =0, S2 = X; для третього триггера під час переходу з 0 в 0 R3 =X, S3= 0.

Аналогічно будь-якого іншого переходу автомата.

У чистому вигляді синхронний RS — тригер, використовуваний для синтезу ЦА, промисловістю не выпускается.

JKтригер — має дві інформаційних входу J і K і тільки вихід Q. Вхід J — вхід установки один, вхід K — вхід установки в 0, тобто. ці входи аналогічні відповідним входам RS-триггера: J — відповідає P. S, K — відповідає R. Проте, на відміну RS-триггера, вхідні комбінація J = 1, K= 1 перестав бути запрещённой. Умовне позначення і таблиця переходів JK-триггера представлені на рис. 28. й у табл. 22.

|J |K |Q t |Q | | |J |K |Q | | | | |t+1 | | | | |t+1 | |0 |0 |0 |0 | | |0 |0 |Q t | |0 |0 |1 |1 | | |0 |1 |0 | |0 |1 |0 |0 | | |1 |0 |1 | |0 |1 |1 |0 | | |1 |1 |Q t | |1 |0 |0 |1 | | | | |б) | |1 |0 |1 |1 | | | | | | |1 |1 |0 |1 | | | | | | |1 |1 |1 |0 |а) | | | | |.

Відповідно до таблиць переходів, для комбінацій вхідних сигналів JK = 00(10 тригер поводиться як RS-триггер, а при комбінації JK = 11 — як Tтриггер.

Аналізуючи таблицю переходів (табл. 22 а), відзначаємо, що перехід триггера, наприклад, з 0 один вимагає подачі вхідних сигналів J=1, K=0 чи J=1, K=1, тобто. J=1, K=Х (байдуже значення). Аналогічно розмірковуючи стосовно іншим переходами, одержимо таку таблицю функцій входів JK-триггера.

|Q t |Q |J |K | | |t+1 | | | |0 |0 |X |0 | |0 |1 |1 |X | |1 |0 |X |1 | |1 |1 |0 |X |.

З останньої таблиці можна було одержати функцію порушення елементів пам’яті при синтезі автомата на JK-триггерах. Наприклад, при переході автомата зі стану ai=010 до стану aj=110, функції порушення мали бути зацікавленими: на першому триггера під час переходу з 0 один J1 = 1,.

K1 = X; на другому триггера під час переходу з 1 один J2 = X,.

K2 = 0; для третього триггера під час переходу з 0 в 0 J3 = 0,.

K3 = X.

Приклад канонічного методу структурного синтезу автомата.

Виконаємо структурний синтез часткового автомата А, заданого своїми таблицями переходів і виходів (табл. 23 і 24.). [pic].

Синтез виконуватимемо наступного порядке:

1. Виберемо як елементи пам’яті D-триггер, функція входів якого представленій у таблиці стор. 33.

2. Закодируем вхідні, вихідні сигнали та внутрішні стану автомата.

Кількість вхідних абстрактних сигналів F = 3, отже кількість вхідних структурних сигналів L= ]log2 °F [ = ]log23[ = 2, тобто. х1, х2.

Кількість вихідних абстрактних сигналів G = 4, отже кількість вихідних структурних сигналів N =]log2G[ = ]log24[ = 2, тобто. у1, у2. Кількість внутрішніх станів абстрактного автомата M = 4, отже кількість двійкових елементів пам’яті (тригерів) R = ] log2M [ = ]log24[ = 2.

[pic].

Отже, структура ЦА з огляду на те, що вихідний автомат є автоматом Мілі, як елементи пам’яті використовується Dтригер, то, можливо представленій у виде (рис. 29):

Кодування вхідних, вихідних сигналів й наявність внутрішніх станів представленій у таблицах:

|0 |0 |0 | |0 |1 |1 | |1 |0 |1 | |1 |1 |0 |.

| |00 |01 |11 |10 | |00 |00 |11 |01 |- | |01 |- |10 |11 |- | |11 |01 |- |10 |01 |.

|0 |0 |X |0 | |0 |1 |0 |1 | |1 |0 |1 |0 | |1 |1 |0 |X |.

| |00 |01 |11 |10 | |0 |0 |0 |X | |0 |1 |1 |X | |1 |0 |X |1 | |1 |1 |X |0 |.

| |00 |01 |11 |10 | | | |1|2|2 | | | |1|3|1 | |T |=|1|5|1 | | | |2|3|3 | | | |2|4|1 | | | |2|5|1 | | | |3|4|2 | | | |3|5|2 |.

2. Впорядкуємо рядки матриці [pic], навіщо побудуємо матрицю [pic] так. У перший рядок матриці [pic] помістимо пару ((,() з найбільшим вагою р ((,(). У нашому випадку ((,() = (2,3), р (2,3) = 3. З всіх пар, мають загальний компонент з парою ((,() вибирається пара ((,() з найбільшим вагою і заноситься на другу рядок матриці [pic]. Зрозуміло, що {(,(}({(,(}(0. Потім із усіх пар, мають загальний компонент хоча б із однієї з внесених вже у матрицю [pic] пар вибирається пара з найбільшим вагою і заноситься в матрицю [pic] тощо. Що стосується рівності терезів пар обчислюються суми терезів компонентів пар (вагою р (() компонента (називається число появ (в матриці [pic]) й у матрицю [pic] заноситься пара з найбільшої сумою терезів. У означеному автоматі на друге місце слідом за парою (2,3) претендують пари: (1,2) з р (1,2) = 2; (3,4) з р (3,4) = 2, (3,5) з р (3,5) = 2.

Для визначення того, яка пара займе друге місце у матриці [pic] знаходимо ваги компонентів пар: р (1) = 3 р (2) = 3 р (1) + р (2) = 6 р (3) = 4 р (4) = 2 р (3) + р (4) = 6 р (3) = 4 р (5) = 2 р (3) + р (5) = 6.

У разі всім пар збігаються та його ваги та значимості їх компонентів. Тому на згадуваній друге місце матриці [pic] може бути з пар (1,2), (3,4), (3,5). Але тоді на 3-му і 4-му будуть інші дві. Виконавши упорядкування всіх пар, одержимо матрицю [pic] як: | | |i|j|p (i| | | | | |, j)| | | |2|3|3 | | | |1|2|2 | |M |=|3|4|2 | | | |3|5|2 | | | |1|3|1 | | | |1|5|1 | | | |2|4|1 | | | |2|5|1 |.

3. Визначаємо розрядність коду для кодування станів автомата (кількість елементів пам’яті - тригерів). Усього станів M=5. Тогда.

R = ]log2M[ = ]log25[ =3.

Закодируем капітал із першого рядка чудово матриці так: K2 = K (а2) = 000; K3 = K (а3) = 001.

Для зручності кодування будемо ілюструвати той процес картою Карно: [pic].

4. Викреслимо з матриці [pic] перший рядок, відповідну закодованим станам А2 і а3. Одержимо матрицю [pic].

| | |i|j|p (i| | | | | |, j)| | | |1|2|2 | | | |3|4|2 | |M'|=|3|5|2 | | | |1|3|1 | | | |1|5|1 | | | |2|4|1 | | | |2|5|1 |.

5. З огляду на упорядкування п. 2 У першій рядку закодований рівно один елемент. Виберемо з першого рядки незакодированный елемент і позначимо його (. (У нашому випадку (= 1). 6. Будуємо матрицю [pic], обравши з [pic] рядки, містять (.

| | | | |i|j|p (i| | | | | | | |, j)| | | | | |1|2|2 | |M (|=|M'|=|1|3|1 | | | | | |1|5|1 |.

Нехай B (= {(1,…,(F} - безліч елементів з матриці [pic], у яких закодовані. Їх коди К (1,…, K (F відповідно. У нашому случае:

B (= B3 = {2,3} K2 = 000 K3 = 001.

7. До кожного K (f (f=1, …, F) знайдемо [pic]- безліч кодів, сусідніх із [pic] і ще зайнятих для кодування станів автомата. (Для сусідніх кодів кодове відстань d=1).

K2 = 000 [pic] = {100, 010}.

K3 = 001 [pic] = {011, 101}.

Побудуємо безліч [pic] [pic] Якщо виявляється, що [pic], то будуємо нове безліч [pic], де [pic]- безліч кодів, які мають кодове відстань до коду [pic]равно 2 тощо. 8. До кожного коду з багатьох D (знаходимо кодове відстань до коду [pic].

K2 = 000 K3 = 001 d (100, 000) = 1 d (100, 001) = 2 d (010, 000) = 1 d (010, 001) = 2 d (011, 000) = 2 d (011, 001) = 1 d (101, 000) = 2 d (100, 001) = 1.

9. Знаходимо значення функції w кожному за коду з багатьох D (.

[pic].

10. З багатьох D (вибираємо код K (, яка має вийшло мінімальне значення w в п. 9. Вибираємо код для стану a1 К1 =100.

[pic].

11. З матриці [pic] викреслюємо рядки, у яких обидва елемента вже закодовані, у результаті одержимо нову матрицю [pic]. Якщо нової матриці [pic] не залишилося жодної рядки, то кодування закінчено. У іншому разі повертаємося до п. 5. У нашому випадку имеем:

| | |i|j|p (i| | | | | |, j)| | | |3|4|2 | | | |3|5|2 | |M'|=|1|5|1 | | | |2|4|1 | | | |2|5|1 |.

[pic].

К2 = 000 [pic] = {010}.

K3 = 001 [pic] = {011, 101}.

[pic].

K2 = 000 K3 = 001 d (010, 000) = 1 d (010, 001) = 2 d (011, 000) = 2 d (011, 001) = 1 d (101, 000) = 2 d (101, 001) = 1.

[pic].

Выбираем К4 = 101. [pic].

[pic].

К1 = 100 [pic] = {110}.

K2 = 000 [pic] = {010}.

К3 = 001 [pic] = {011}.

[pic].

К1 = 100 K2 = 000 K3 = 001 d (110, 100) = 1 d (110, 000) = 2 d (110, 001) = 3 d (010, 100) = 2 d (010, 000) = 1 d (010, 001) = 2 d (011, 100) = 3 d (011, 000) = 2 d (011, 001) = 1.

[pic].

Выбираем К5 = 011.

[pic].

Т.к. їхні капітали автомата закодовані, то робота алгоритму закінчується. Загальна кількість переключень тригерів: [pic] Мінімально можливу кількість переключень (якби стану були закодовані сусіднім кодированием).

[pic] Коефіцієнт ефективності кодирования:

[pic] Розглянутий алгоритм кодування є машино-ориентированным, існує програма, реалізують цей алгоритм.

Слід зазначити у висновку, що використання алгоритму кодування для D-триггеров чи евристичного алгоритму й інших типів тригерів забезпечує найбільш просту з погляду реалізації схему, та заодно можливі гонки. Для радикального усунення останніх використовують апаратні методи — тригери з подвійним пам’яттю: тригери, керовані фронтом і т.д.

Управляючі і операторные автоматы.

Принцип микропрограммного управления.

ЕОМ переробляє інформацію, виконуючи з неї якісь операції. Для операцій над інформацією використовуються операційні устрою — процесори, канали вводу-виводу, устрою управління зовнішніми пристроями тощо. Функцією операційного устрою є виконання заданого безлічі операцій F={f1,…, fG} над вхідними словами D={d1,…, dH} з метою обчислення слів R={r1,…, rQ}, які мають результати операцій R=fg (D), де g=1,2,…, G.

Функціональна і структурна організація операційних пристроїв виходить з принципі микропрограммного управління, яка полягає в наступному: 1. Будь-яка операція fg (g=1,…, G), реалізована пристроєм, сприймається як складне дію, яке поділяється на послідовність елементарних дій над словами інформації. Ці елементарні дії називаються микрооперациями. 2. Для управління порядком прямування микроопераций використовуються логічні умови, які залежно від значень слів, преобразуемых микрооперациями, приймають значення «брехня «чи «істина «(1 чи 0). 3. Процес операцій у пристрої описується у вигляді алгоритму, відрекомендовується в термінах микроопераций і логічних умов і називається мікропрограмою. Мікропрограма визначає порядок перевірки значень логічних умов і прямування микроопераций, необхідний отримання необхідних результатів. 4. Мікропрограма використовують як форма уявлення функції устрою, з урахуванням визначається структура і Порядок функціонування устрою у времени.

Т.а. з принципу микропрограммного управління слід, що структура і Порядок функціонування операційних пристроїв визначається алгоритмом здійснення операції F={f1,…, fG}.

До елементарним діям над словами інформації микрооперациям ставляться: передача інформації вже з регістру на другий, взяття зворотного коду, зрушення і т.д.

Поняття операційного і більше управляючих автоматов.

Як показав академік В. М. Глушков у кожному устрої обробки цифрової інформації можна назвати дві основні блоку — операційний автомат (ОА) і управляючий автомат (УА). [pic].

Операційний автомат (ОА) служить для зберігання слів інформації, виконання набору микроопераций і обчислення значень логічних умов, тобто. операційний автомат є структурою, організували виконання дій над інформацією. Микрооперации, що їх ОА, задаються безліччю управляючих сигналів Y={y1,…, yM}, з кожним із яких ототожнюється певна микрооперация.

Значення логічних умов, вычисляемые в операційному автоматі, відбиваються безліччю осведомительных сигналів X={x1,…, xL}, кожен із яких ототожнюється з певним логічним условием.

Керуючий автомат (УА) генерує послідовність управляючих сигналів, вказану мікропрограмою і значенням логічним умов. Інакше висловлюючись, управляючий автомат задає порядок виконання дій в ОА, що з алгоритму операцій. Найменування операції, яку треба виконати у пристрої, визначається кодом g операції, які у УА ззовні. Стосовно УА сигнали g1,…, gh, з яких кодується найменування операції, і осведомительные сигнали x1,…, xL, формовані в операційному автоматі, грають однакову роль: впливають значно вироблення управляючих сигналів Y. Тому сигнали g1,…, gh і x1,…, xL ставляться одного класу — до класу осведомительных сигналів, вступників на вхід УА.

Т.а. будь-яке операційне пристрій — процесор, канал вводу-виводу і т.д. — є композицією операційного і керує автоматів. Операційний автомат, реалізуючи дії над словами інформації, є виконавчої частиною устрою, роботою якого управляє управляючий автомат, генеруючий необхідні послідовності управляючих сигналов.

Операційний і управляючий автомати можуть визначити своїми функціями — переліком виконуваних ними дій. Функція ОА визначається наступній сукупністю відомостей: 1) безліччю вхідних слів D={d1,…, dH}, вводяться у автомат як операндов; 2) безліччю вихідних слів R={r1,…, rQ}, які мають результати операцій; 3) безліччю внутрішніх слів S={s1,…, sN}, що використовуються подання у виконання операцій. Можна вважати, що вхідні і вихідні слова збігаються з деякими внутрішніми D (S, R (S. 4) безліччю микроопераций Y={ym}, що реалізують перетворення S=(m (s) над словами інформації, де (m — вычисляемая функція; 5) безліччю логічних умов X={xi}, де xi=(i (si) і (і - булева функция;

T.o. функція ОА задана, якщо задано (визначено) безлічі D, R, P. S, Y, X. Час перестав бути аргументом функції ОА. Функція встановлює список действий-микроопераций і логічних умов, що може виконувати автомат, але ще не визначає порядок прямування цих дій у часу. Тобто. функція ОА характеризує кошти, які можна використовуватимуться обчислень, але з сам обчислювальний процесс.

Порядок виконання дій у часі визначається формі функцій управляючого автомата.

Функція управляючого автомата — це операторная схема алгоритму (мікропрограми), функціональними операторами якої є символи у1,…, уm, отождествляемые з микрооперациями, і як логічних умов використовуються булевы перемінні х1,…, хL. Операторная схема алгоритму найчастіше представляється як граф-схемы алгоритму (ДСА). ДСА визначає обчислювальний процес послідовно у часі, встановлюючи порядок перевірки логічних умов х1-хL і Порядок прямування микроопераций у1-уm.

СПОСОБИ ОПИСИ АЛГОРИТМІВ І МИКРОПРОГРАММ.

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

[pic].

— вершина «початок» має одного виходу, входів немає. Позначає початок микропрограммы.

— вершина «кінець» має будь-яке число входів, виходів немає. Позначає кінець микропрограммы.

— операторная вершина має будь-яке число входів, одного виходу. Усередині операторной вершини записується одна мікрокоманда — сукупність микроопераций, припускають спільне (тобто. одночасне) выполнение.

[pic].

— умовна вершина має будь-яке число входів і 2 виходу. Усередині умовної вершини записується булевое вираз, залежно від значення якого здійснюється вибір напрями виконання микропрограммы.

— особливий вид умовної вершини — чекає - має безліч входів, 2 виходу, 1 у тому числі заведено на вхід. Влучаючи в ждущую вершину вихід з неї можлива лише і під час умови Х.

Граф мікропрограми складається з сукупності перелічених вершин і дуг, що з'єднують виходи одних вершин з входами інших. Поєднання вершин і напрям дуг графа визначають, виходячи з алгоритму операції, описуваного графом, і структури операційного автомата.

Сама мікропрограма і його граф мали бути зацікавленими коректні, тобто. відповідати наступним условиям:

1. У графі має бути лише одна початкова і жодна кінцева вершина. 2. У будь-яку вершину графа має поводитися по крайнього заходу єдиний шлях з початковій вершини. 3. З кожного виходу будь-який вершини графа має існувати по крайнього заходу єдиний шлях в кінцеву вершину. 4. За всіх можливих значеннях логічних умов і використовуваних слів має існувати шлях з початковій вершини в конечную.

[pic].

Пример ДСА представлений рисунке:

ДСА на рис. 43 називається змістовної, т.к. всередині вершин записані вочевидь микрооперации і логічні умови. Якщо ж кожну микрооперацию позначити символами Yi, a логічні умови через Xi, то вийде так звана кодированная ДСА (рис.44). Для правильного сприйняття мікропрограми, заданої як кодованої ДСА, необхідно знати відповідності між Yi, Xi і змістом відповідних микроопераций і логічних условий.

Для записи микроопераций всередині вершин використовується так называемый.

Ф-язык. Докладно з зтим мовою можна ознайомитися у наступних курсах «Схемотехника ЕОМ», «Теорія і проектування ЕОМ». Але тут ми розглянемо лише основні тези цього языка.

У цьому вся мові існують двоичные константи і які змінюються: 0010 — константа, A (1:4) — четырехразрядное слово — четырехразрядная двоичная змінна. Наприклад, A (1:4)=1010 означає, що у першому розряді слова A буде 1, у другому — 0 тощо. A (2:3) — частина слова A, розміщена у другому і третьому розрядах. Найбільш уживані операції Ф-языка: присвоювання — A (0:3): = 1000, B (1:4): = A (5:8) тощо. інвертування — A (0:3): = ^ B (1:4) конкатенації - З (0:6): = A (0:3). B (1:3) Приклад 1. A (0:3): = 1100 B (1:4): = A (0:3) (B (1:4): = 1100.

2. B (1:4): = 0101 A (0:3): =^B (1:4) (A (0:3): = 1010.

3. A (0:3): = 1101 B (1:3): = 110 З (0:6): = A (0:3). B (1:3) (C (0:6):=1 101 110.

Запис виду A (2) означає, що саме розглядається другий розряд слова A, тобто. це біт, записаний у другому розряді слова A.

За виконання операцій присвоювання необхідно дотримуватися рівність розрядів за тими словами зліва і від знака присвоювання. Операції складання, логічного складання тощо. в Ф-языке записуються звичайним способом через оператор присваивания:

C (0:n):=A (0:n)+B (0:n).

D (0:n):=A (0:n)vB (0:n) і т.д.

ОПЕРАЦІЙНІ ЭЛЕМЕНТЫ.

Відповідно до принципу микропрограммного управління, будь-яка складна операція розпадається на цілий ряд микроопераций, які виконуються ОА. Різні микрооперации виконуються елементарними ОА — так званими операційними елементами (ОЕ), що є складовими частинами основного ОА.

Під операційним елементом розуміють пристрій, реалізує жодну з наступних функцій чи його довільну комбінацію: 1. зберігання слова інформації З; 2. виконання деяких микроопераций, у яких обчислюється нового значення слова З; 3. обчислення логічного умови, залежить від слова С;

Т.а. функція ОЕ визначено, якщо заданы:

4. опис закладеного чи вычисляемого слова; 5. опис безлічі микроопераций, виконуваних цим елементом; 6. опис вычисляемых цим елементом логічних условий.

Для побудови ОА ОЕ з'єднуються між собою з допомогою ланцюгів передачі слів інформації від виходів одних елементів до входам других.

Залежно від виконуваних микроопераций ОЕ діляться на різновиду: шина, регістр, лічильник, акумулятор, схема порівняння, дешифратор, шифратор і т.д.

Шина — це сукупність ланцюгів, виділені на передачі слова інформації. Умовне позначення шини представлене рис. 45. [pic].

Шини, зображені на рис. 45 називаються некерованими шинами.

Управляемые шини представлені на рис. 46. [pic].

Під впливом управляючого сигналу у керована шина виконує микрооперации: у=0: B (0:3):=0, y=1: B (0:3):=A (0:3).

Тобто. при y=1 здійснюється операція передачі. Розрядність шини може бути довільна, та це 8, 12, 16, 24, 32 і т.д.

Регістр — це операційний елемент, службовець для запам’ятовування слів і який би у випадку виконання таких микроопераций: 7. установка регістру в 0 (скидання); 8. прийом слова з іншого регістру, шини тощо.; 9. передача слова в інший регістр, шину тощо.; 10. перетворення кодів збережених слів в инверсные коди; 11. зрушення закладеного слова вліво чи вправо на необхідну число розрядів. [pic].

Регістр, виконує такі микрооперации, називається багатофункціональним. Т.к. регістр призначений для зберігання інформації, то він містить елементи пам’яті, як яких використовують тригери. Кількість тригерів визначає розрядність регістру. Будемо позначати регістр як прямокутника із зазначенням розрядності (рис.47).

Регістр може складатися зі окремих подрегистров, мають самостійного значення (рис. 48.). На рис. 48 представлений регістр, який зберігає число у вигляді з плаваючою коми. У цьому вся регістрі три подрегистра: для зберігання знака Рг (0), характеристики Рг (1:7), мантиси Рг (8:31) числа.

Регістр може виконувати ряд микроопераций, наприклад: [pic].

Регістр, який виконує микрооперацию у4 (зрушення вправо) чи у5 (зрушення вліво) називаються регістром сдвига.

Акумулятор — операційний елемент, виконує підсумовування кодів чисел. Залежно від кодів чисел розрізняють сумматоры прямого, зворотного, додаткового кодів. З іншого боку, сумматоры бувають комбінаційними і накапливающими.

Комбінаційний акумулятор виробляє вихідні сигнали суми і перенесення, зумовлені комбінацією цифр доданків, одночасно поданих на входи сумматора. Цей акумулятор не має пам’яттю і після зняття сигналів з входів вихідні сигнали також исчезают.

Умовне позначення комбинационного сумматора представлене рис. 50.

[pic].

Які Заощаджують називається акумулятор, що здійснює складання слів A і B під час подачі їх у акумулятор одного одним. У накапливающем сумматоре є додатковий регістр для зберігання результата.

[pic].

Структура і умовне позначення нагромаджуючого сумматора представлені на рис. 51.

Лічильник — операційний елемент, який реалізує микрооперацию рахунки. Микрооперация рахунки полягає у зміні стану лічильника (значення закладеного слова) на 1. З іншого боку лічильник може виконати і ті микрооперации: установка в 0 і достойний прийом довільного числа.

Т.е. повний набір можливих микроопераций для счетчика:

[pic].

[pic].

Лічильник, виконує микрооперацию у1 називається суммирующим, микрооперацию у2 — вычитающим, обидві микрооперации — реверсивный.

Дешифратор — операційний елемент, виконує функцію перетворення деякого n-разрядного двоичного коду в унітарний код «одне із N». Якщо N=2n — такий дешифратор називається повним, якщо N.