Розробка алгоритму операційного автомату, синтез керуючого автомату з жорсткою логікою типу Мілі

Зміст

ВСТУП

1. РОЗРОБКА АЛГОРИТМУ ТА ОПЕРАЦІЙНОГО АВТОМАТУ

1.1 Опис операції множення

1.1.1 Основні методи множення

1.1.2 Множення чисел з фіксованою комою

1.1.3 Прискорені методи виконання операції множення

1.2 Розробка операційного автомату

1.2.1 Формалізований опис операційного автомату

1.2.2 Структурна схема операційного автомату

1.3 Розробка машинного алгоритму

1.3.1 Побудова граф-схеми алгоритму

1.3.2 Приклад реалізації алгоритму

2. СИНТЕЗ КЕРУЮЧОГО АВТОМАТУ

2.1 Основи теорії керуючих автоматів

2.2 Опис керуючого автомату Мілі

2.3 Кодування граф-схеми автомату

2.4 Побудова таблиці переходів

2.5 Синтез керуючого автомату

3. МЕТОДИКА КОНТРОЛЮ

3.1 Теоретичні відомості

3.2 Приклад контролю виконання операції множення за допомогою 11N-коду

ВИСНОВКИ

ПЕРЕЛІК ПОСИЛАНЬ

ВСТУП

В основу проектування операційних пристроїв різного призначення покладено принцип функціонального мікропрограмування і концепцію операційних і керуючих автоматів. При цьому мікропрограмування - це спосіб опису функцій операційних пристроїв безвідносно до технічних засобів, які використовуються для їх реалізації. Таке тлумачення мікропрограмування дозволяє формалізувати синтез структур будь-яких операційних пристроїв незалежно від способу керування роботою пристрою. Необхідно відзначити, що принципи побудови і методи проектування операційних і керуючих автоматів є тою основою, на якій базується теорія і практика проектування більшої частини пристроїв ЕОМ.

Складність і відповідальність задач, що вирішуються сучасними ЕОМ та системами, потребують від них високої надійності та продуктивності. Тому, однією з основних проблем, які стоять перед розробниками сучасної обчислювальної техніки, є підвищення продуктивності, відказостійкості та життєздатності.

В наш час основним напрямком вирішення цих проблем є створення обчислювальних машин, які побудовані з великої кількості однорідних модулів, що утворюють єдину систему шляхом встановлення логічних зв`язків між ними. В цьому суть концепції мультипроцесорних ЕОМ, частинними випадками яких є матричні, конвеєрні, з програмованою архітектурою і т.д. При цьому висовуються вимоги простоти контрольного обладнання і високої достовірності обробки інформації.

В даній курсовій роботі здійснюється розробка алгоритму операційного автомату виконання операції множення чисел в прямому коді, синтез керуючого автомату з жорсткою логікою типу Мілі. А також приведено приклад контролю виконання операції множення за допомогою 11N контролю.

1. РОЗРОБКА АЛГОРИТМУ ТА ОПЕРАЦІЙНОГО АВТОМАТУ

1.1 Опис операції множення

Множення може проводитись в прямому, оберненому та доповняльному кодах. Знак результату операції множення можна визначати окремо. Для цього використовується операція XOR над знаковими розрядами співмножників відповідно.

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

1.1.1 Основні методи множення

Методи множення чисел у двійковій системі числення можна класифікувати таким чином:

За формою подання чисел

методи множення чисел з фіксованою комою;

методи множення чисел з плаваючою комою.

За швидкодією

методи простого множення

методи прискореного множення

За видом використаного суматора:

методи множення на суматорі прямого коду;

методи множення на суматорі доповняльного коду;

методи множення на суматорі оберненого коду (рідко використовується ).

За аналізом розрядів множника:

множення з молодших розрядів;

множення зі старших розрядів;

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

Виходячи з вищевикладеного можна виділити чотири варіанти схем машинного множення:

Метод 1. Припустимо В-множене (В>0), A-множник (А>0) С-добуток. Тоді у випадку зображення чисел у формі з фіксованою комою отримуємо

А = а1а2…аn ;

B = b1b2…bn = b12-1 + b22-2 + … + bn2-n;

Звідси:

С = АВ = (0а1а2…аn)(b12-1 + … + bn2-n) = = (2-10,a1a2…an)b1 (1.1) + (2-10,a1a2…an)b2 + … + (2-n0,a1a2…an)bn .

Множник 2-n означає зсув на n розрядів вправо числа яке заключене в дужки тобто в даному випадку зсувається вправо множене і множення починається з старших розрядів.

Структурна схема пристрою що реалізує цей метод наведена на рис. 1а.

Метод 2. Множник B = 0b1b2…bn перетворюється по схемі Горнера

B = (…((bn2-1 + bn-1)2-1 + bn-2)2-1 + … + b2)2-1 + b1)2-1

Тоді:

C = AB = (…((bn0,a1a2…an)2-1 + bn-10,a1a2…an)2-1 … (1.2) …+b10,a1a2…an)2-1

Тут множення починається з молодших розрядів та зсувається вправо суми часткових добутків. Структурна схема пристрою що реалізує цей метод наведена на рис. 1б.

Метод 3. Множник записується таким чином

B = 2-n(bn + bn-121 + bn-222 + … +b12n-1).

С = AB = 2-n[bn0,a1a2…an + bn-1(210,a1a2…an) + (1.3)+ bn(220,a1a2…an) + … + b1(2n-10,a1a2…an)] .

Це означає що множення починається з молодших розрядів і множене зсувається вліво на один розряд в кожному такті.

Структурна схема пристрою що реалізує цей метод наведена на рис. 1в.

Метод 4. Якщо множник записати по схемі Горнера

B = 2-n(…((b121 + b2)21 + … + bn-1)21 + bn

C = AB = 2-n(…((b10,a1a2…an)21 + b20,a1a2…an)21 + … + (1.4)+ bn-10,a1a2…an)21 + bn0,a1a2…an).

У цьому випадку множення починається з старшого розряду і в кожному такті зсувається вліво сума часткових добутків.

Структурна схема пристрою що реалізує цей метод наведена на рис. 1

Другий варіант має найменші апаратурні витрати перший та третій – найменший час множення.

Таким чином для реалізації звичайної операції множення необхідно мати суматор регістри для зберігання множеного та схему аналізу розрядів множника. Суматор та регістри повинні мати ланцюги зсуву вмісту в ту чи іншу сторону у відповідності з прийнятим методом множення.

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

Якщо множник від’ємний то добуток чисел на суматорі оберненого коду отримують додаванням поправок [A]об та [A]об2-n до добутку обернених кодів співмножників.[А.Я. Савельєв «Прикладная теория цифровых автоматов» М.: Высш. шк.1987]

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

1.1.2 Множення чисел з фіксованою комою

В ЕОМ операція множення чисел з фіксованою комою за допомогою відповідних алгоритмів зводиться до операції додавання і зсуву.

Множення двох (n - 1) розрядних чисел може мати 2(n - 1) значущих розрядів.

Тому при операції множення цілих чисел необхідно побачити можливість формування в АЛП добутку, котрий має двохкратну в порівнянні із співмножниками довжину. В ЕОМ, в яких числа з фіксованою комою є дробами, молодші (n - 1) розрядів множення часто відкидаються (при відкиданні може виконуватись операція округлення добутку). Для виконання множення АЛП повинен мати регістри множеного, множника та схеми формування суми часткових добутків - суматор часткових добутків, в якому шляхом відповідної організації передач виконується послідовне додавання часткових добутків.

Операція множення складається з (n - 1) циклів. В кожному циклі аналізується слідуюча цифра множника, якщо це 1, то до суми часткових добутків додається множене, в іншому випадку додавання не виконується. Цикл закінчується з зсувом множеного відносно суми часткових добутків або з зсувом суми часткових добутків відносно нерухомого множеного.

1.1.3 Прискорені методи виконання операції множення

Прискорення операції множення дозволяє істотно підвищити продуктивність ЦОМ, оскільки приблизно 70% свого часу вони витрачають на виконання цієї операції. Аналізуючи (3.2) - (3.5), можна намітити такі шляхи скорочення часу множення: зменшення часу додавання і зсуву кодів; зменшення кількості додавань і кількості зсувів кодів.

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

Зменшення часу додавання двох кодів досягається за рахунок ускладнення кіл формування розрядних сум і перенесень у суматорі. Але це ні яким чином не впливає на організацію процесу множення. Тому основні підходи щодо прискорення операції множення базуються на зменшенні кількості додавань і кількості зсувів кодів.

Відомі на цей час методи прискорення множення розподілені на дві великі групи: логічні й апаратні.

Логічними методами прискорення множення називають такі методи, реалізація яких не вимагає змін основної структури арифметичних кіл пристрою для множення (див. рис. 3.1 - 3.5), а прискорення досягається тільки за рахунок ускладнення схеми керування цим пристроєм. Стосовно пристроїв для множення паралельних кодів ознакою того, що ми маємо справу з логічним методом прискорення множення, є незалежність кількості додаткової апаратури (у порівнянні з вихідною схемою) від кількості розрядів співмножників.

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

Розрізняють апаратні методи першого порядку і другого порядку. Для апаратних методів першого порядку характерна лінійна залежність кількості додаткової апаратури від кількості розрядів у співмножниках п. Тоді як реалізація методів другого порядку вимагає введення додаткової апаратури, кількість якої пропорційна .

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

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

Метод множення з пропусканням додавань є найпростішим з логічних методів прискорення множення. Схему керування взагалі простіше побудувати так, щоб за тактом зсуву щораз приділявся час на додавання, але додавання виконувалося б у залежності від цифри множника. Невелике ускладнення схеми керування, що дозволяє відводити час на додавання тільки тоді, коли воно дійсно необхідно, скорочує число тактів додавання в середньому вдвічі.

Цей метод прискорення рівною мірою підходить для тих випадків, коли множення починається зі старших розрядів множника, і для випадків, коли множення починається з молодших розрядів.

1.2 Розробка операційного автомату

1.2.1 Формалізований опис операційного автомату

В функцiональному та структурному вiдношеннi операцiйний пристрiй подiляється на двi частини: операцiйний та керуючий автомати. Операцiйний автомат ОА служить для збереження слiв iнформацiї, виконання набору мiкрооперацiй i обчислення значень логiчних умов, тобто операцiйний автомат є структурою, органiзованою для виконання дiй над iнформацiєю. Мiкрооперацiї, що реалiзуються операцiйним автоматом, iнiцiюються множиною керуючих сигналiв Y=[y(1),...,y(m)], з кожним iз них ототожнюється визначена мiкрооперацiя. Значення логiчних умов, якi обчислюються в операцiйному автоматi, вiдображаються множиною освiдомлюючих сигналiв X=[x(1),...,x(l)], кожний з яких ототожнюється з визначеною логiчною умовою. Керуючий автомат КА генерує послiдовнiсть керуючих сигналiв, визначену мiкропрограмою, яка вiдповiдає значенням логiчних умов. Іншими словами, керуючий автомат задає порядок виконання дiй в операцiйному автоматi, що зрозумiло з алгоритму виконання операцiй. Найменування операцiї, яку необхiдно виконати в пристрої, визначається кодом g операцiї. По вiдношенню до керуючого автомату сигнали g(1),...,g(h), за допомогою яких кодується найменування операцiї, i освiдомлюючi сигнали x(1),...,x(l), що формуються в операцiйному автоматi, грають однакову роль: вони впливають на порядок утворення робочих сигналiвY. Тому сигнали g(1),...,g(h) i x(1),...,x(l) вiдносяться до одного класу - класу освiдомлюючих сигналiв, що iдуть на вхiд управляючого автомату.

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

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

Функцiя операцiйного автомату визначається слiдуючою єднiстю вiдомостей:

Множиною вхiдних слiв d={d(1),...,d(H)}, що вводиться в автомат в якостi операндiв.

Множиною вихiдних слiв R={r(1),...,r(Q)}, що представляє результати операцiй.

Множиною мiкрооперацiй Y={y(m)}, m=1,...,M, реалiзуючих перетворення S={f(m)}(S) над словами iнформацiї, де f(m) - шукана функцiя.

Таким чином, функцiя операцiйного автомату задана, якщо визначенi множини D,R,S,Y,X. Час не є аргументом функцiї операцiйного автомату. Функцiя встановлює список дiй - мiкрооперацiй i логiчних умов,- якi може виконувати автомат, але нiяк не визначає порядок слiдування цих дiй у часi. Iнакше кажучи, функцiя операцiйного автомату характеризує засоби, якi можуть бути використанi для обчислень, але не сам обчислювальний процес. Порядок виконання дiй у часi визначається у формi функцiй управляючого автомату.

1.2.2 Структурна схема операційного автомату

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

Операційний автомат ОА розділяється на три частини: пам'ять S; комбінаційну схему Ф, яка реалізує мікрооперації; комбінаційну схему ψ, яка обчислює значення логічних умов. Пам’ять S забезпечує збереження слів s1,…sN, які представляють значення операндів D, проміжкові значення і кінцеві результати R. Для виконання мікрооперацій Y={ ym} служить комбінаційна схема Ф. Керуючі сигнали Y, що формуються управляючим автоматом УА, ініціюють виконання необхідних мікрооперацій. Так, якщо надходять сигнали ym1 і ym2, то схема Ф виконує дві мікрооперації що зводиться до обчислення значень і присвоєння їх словам . Для обчислення значень логічних умов служить комбінаційна схема ψ, що реалізує систему булевих функцій , значення яких представляються інформаційними сигналами X={xl}.

1.3 Розробка машинного алгоритму

1.3.1 Побудова граф-схеми алгоритму

Побудова словесного алгоритму:

1) У регістр А записується прямий код множеного А, який передається із вхідної шини:

РгА:=Швх1

2) У регістр В записується прямий код множника В, який передається із вхідної шини:

РгВ:=Швх2

3) Встановлюємо в нуль накопичувальний суматор:

НСМ:=0

4) У лічильник записуємо кількість разів повторення циклу:

ЛІЧ:=29

5) Перевіряємо чи рівні знакові розряди співмножників:

РгА[31]=РгВ[31] ?

Якщо так,то переходимо до пункту 7.

Якщо ні, то переходимо до пункту 6.

6) Знаковий розряд НСМ виставляється в 1:

НСМ[63]:=1

7) Аналізуємо старший розряд регістра В:

РгВ[30]=1?

Якщо так, тоді переходимо до пункту 8.

Якщо ні, тоді переходимо до пункту 9.

8) Додаємо до вмісту накопичувального суматора значення коду регістра А:

НСМ:=НСМ+РгА

9) Відновлюємо попередній вміст регістра В, циклічно зсуваючи його вліво на один розряд:

L1.РгB[0:30]

10) Вміст накопичувального суматора циклічно зсуваємо на один розряд вліво:

L1.НСМ[0:62]

11) Декрементуємо значення лічильника:

ЛІЧ:=ЛІЧ-1

12) Молодший розряд накопичувального суматора приймає значення нуль:

НСМ[0]=0

13) Перевіряємо, чи лічильник рівний нулеві:

ЛІЧ=0?

Якщо так, то переходимо до пункту 14

Якщо ні, то переходимо до пункту 7.

14) Значення накопичувального суматора циклічно зсуваємо на один розряд вправо:

R1.НСМ[0:62]

15) Закінчення операції множення. Значення результату, яке записане у накопичувальному суматорі, передається на шину даних:

Швих:=НСМ[0:63]

Для наочного зображення алгоритму виконання операцій використовують граф-схеми алгоритмів.

Граф-схема алгоритма (ГСА) - орієнтований зв'язаний граф, який містить одну початкову вершину (Початок), одну кінцеву вершину (Кінець) і довільну кількість умовних і операторних вершин. Вершина "Початок" входів не має.

Кінцева, операторна і умовна вершини мають по одному входу, початкова вершина входів не має. Вершина "Початок" і будь-яка операторна мають по одному виходу, умовна вершина має два виходи, позначених символами «1» та «0». Вершина "Кінець" виходів не має.

ГСА має задовольняти наступні умови:

входи і виходи вершин з'єднуються один з одним за допомогою дуг, направлених завжди від виходу до входу;

кожен вихід з'єднано лише з одним входом;

кожен вихід з'єднується лише з одним входом;

будь-який вхід з'єднується принаймні з одним виходом;

будь-яка вершина ГСА лежить принаймні на одному шляху від початкової вершини до кінцевої;

один із виходів умовної вершини може з'єднуватись з її входом, що є недопустимим для операторної вершини. Такі умовні вершини іноді називаються зворотними;

в кожній умовній вершині записується логічна умова із множини логічних умов;

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

При проектуванні різноманітних пристроїв ЕОМ зазвичай використовуються змістовні граф-схеми алгоритмів, які описують не лише формальні елементи, а також логічні умови і мікрооперації у змістовних термінах.

Структурна схема операційного автомата – на рисунку 1.

Рисунок 1 - Структурна схема операційного автомата

1.3.2 Приклад реалізації алгоритму

Приклад: Перемножити на суматорі прямого коду починаючи з старших розрядів множника А=57, В=-923 з використанням описаного у пункті 1.3.1 алгоритму.

Розв’язання.

Спочатку запишемо машинні зображення чисел А та В в прямих кодах з заданою розрядністю:

А = 0,[0] 30...[0] 6111001; В = 1,[0] 30…[0] 111110011011

Послідовність дій, що виконуються над числами, наведена у таблиці 1.

Відповідь: 1,[0] 62…[0] 1701100110011011000.

Таблиця 1 – Приклад реалізації алгоритму множення, починаючи зі старших розрядів множника

Суматор НСМ	Регістр РгА	Регістр РгВ	Примітки
0,[0]62…[0]1700000000000000000	0,[0]30...[0]6111001	1,[0]30…[0]111110011011	НСМ:=0; РгА:=Швх1; РгВ:=Швх2; ЛІЧ:=29;
1,[0]62…[0]18000000000000000000	0,[0]30...[0]6111001	1,[0]30…[0]121110011011_	НСМ[63]:=1; РгВ[30]=0; L1.РгВ[0:30]; ЛІЧ:=28; L1.НСМ[0:62]; НСМ[0]:=0;
1,[0]62…[0]1700000000000000000	0,[0]30...[0]6111001	1,01110011011[ _ ] 19…[ _ ] 0	РгВ[30]=0; L1.РгВ[0:30]; L1.НСМ[0:62]; НСМ[0]:=0; ЛІЧ:=10;
1,[0]62…[0]1700000000000000000 1,[0]62…[0]1700000000000111001 1,[0]62…[0]1700000000001110010	0,[0]30...[0]6111001	1,1110011011[_] 20…[_] 0	РгВ[30]=1; НСМ:=НСМ+РгА; L1.РгВ[0:30]; L1.НСМ[0:62]; НСМ[0]:=0; ЛІЧ:=9;
1,[0]62…[0]1700000000001110010 1,[0]62…[0]1700000000010101011 1,[0]62…[0]1700000000101010110	0,[0]30...[0]6111001	1,110011011[_] 21…[_] 0	РгВ[30]=1; НСМ:=НСМ+РгА; L1.РгВ[0:30]; L1.НСМ[0:62]; НСМ[0]:=0; ЛІЧ:=8;
1,[0]62…[0]1700000000101010110 1,[0]62…[0]1700000000110001111 1,[0]62…[0]1700000001100011110	0,[0]30...[0]6111001	1,10011011[_] 22…[_] 0	РгВ[30]=1; НСМ:=НСМ+РгА; L1.РгВ[0:30]; L1.НСМ[0:62]; НСМ[0]:=0; ЛІЧ:=7;
1,[0]62…[0]1700000001100011110 1,[0]62…[0]1700000011000111100	0,[0]30...[0]6111001	1,0011011[_] 23…[_] 0	РгВ[30]=0; L1.РгВ[0:30]; L1.НСМ[0:62]; НСМ[0]:=0; ЛІЧ:=6;
1,[0]62…[0]1700000011000111100 1,[0]62…[0]1700000110001111000	0,[0]30...[0]6111001	1,011011[_] 24…[_] 0	РгВ[30]=0; L1.РгВ[0:30]; L1.НСМ[0:62]; НСМ[0]:=0; ЛІЧ:=5;
1,[0]62…[0]1700000110001111000 1,[0]62…[0]1700000110010110001 1,[0]62…[0]1700001100101100010	0,[0]30...[0]6111001	1,11011[_] 25…[_] 0	РгВ[30]=1; НСМ:=НСМ+РгА; L1.РгВ[0:30]; ЛІЧ:=4; L1.НСМ[0:62]; НСМ[0]:=0;
1,[0]62…[0]1700001100101100010 1,[0]62…[0]1700001100110011011 1,[0]62…[0]1700011001100110110	0,[0]30...[0]6111001	1,1011[_] 26…[_] 0	РгВ[30]=1; НСМ:=НСМ+РгА; L1.РгВ[0:30]; ЛІЧ:=3; L1.НСМ[0:62]; НСМ[0]:=0;
1,[0]62…[0]1700011001100110110 1,[0]62…[0]1700110011001101100	0,[0]30...[0]6111001	1,011[_] 27…[_] 0	РгВ[30]=0; L1.РгВ[0:30]; L1.НСМ[0:62]; НСМ[0]:=0; ЛІЧ:=2;
1,[0]62…[0]1700110011001101100 1,[0]62…[0]1700110011010100101 1,[0]62…[0]1701100110011011000	0,[0]30...[0]6111001	1,11[_] 28…[_] 0	РгВ[30]=1; НСМ:=НСМ+РгА; L1.РгВ[0:30]; ЛІЧ:=1; L1.НСМ[0:62]; НСМ[0]:=0;
1,[0]62…[0]1701100110011011000 1,[0]62…[0]1701100110110000011 1,[0]62…[0]1711001100110110000	0,[0]30...[0]6111001	1,1[_] 29…[_] 0	РгВ[30]=1; НСМ:=НСМ+РгА; L1.РгВ[0:30]; ЛІЧ:=0; L1.НСМ[0:62]; НСМ[0]:=0;
1,[0]62…[0]1711001100110110000 1,[0]62…[0]1701100110011011000	0,[0]30...[0]6111001	1,1[_] 29…[_] 0	R1.НСМ[0:62]; Швих:=НСМ[0:63]

2. СИНТЕЗ КЕРУЮЧОГО АВТОМАТУ

2.1 Основи теорії керуючих автоматів

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

В основі опису керуючих автоматів лежить принцип мікропрограмного керування. Він полягає в тому що будь-яка операція розглядається як складна що містить більш прості операції які називаються мікроопераціями тобто кожна операція – це визначена послідовність мікрооперацій.

Існують два основні типи керуючих автоматів

1. Керуючий автомат з жорсткою чи схемною логікою. Для кожної операції будується набір комбінаційних схем які в потрібних тактах збуджують відповідні керуючі сигнали. Іншими словами будується скінчений автомат в якому необхідна множина станів представляється станами k запам’ятовуючих елементів

q = {q1 q2, …, qk}

2. Керуючий автомат з збереженою в пам’яті логікою (програмованою логікою). Кожній операції що виконується в операційному пристрої ставиться у відповідність сукупність збережених в пам’яті слів-мікрокоманд кожна з яких містить інформацію про мікрооперації що підлягають виконанню на протязі одного машинного такту та вказівку (яка в загальному випадку залежить від значень вхідних сигналів) яке повинно бути вибране з пам’яті наступне слово (наступна мікрокоманда). Таким чином в цьому випадку функції переходів та виходів А та В керуючого автомату реалізуються збереженою в пам’яті сукупністю мікрокоманд.

Послідовність мікрокоманд що виконують одну машинну команду чи окрему процедуру створює мікропрограму. Звичайно мікропрограми зберігаються в спеціальній пам’яті мікропрограм (керуючій пам’яті).

В керуючих автоматах з збереженоюю в пам’яті програмою мікропрограми використовуються в явній формі вони програмуються в кодах мікрокоманд і в такому вигляді заносяться в пам’ять. Тому такий метод управління цифровим пристроєм називається мікропрограмуванням а керуючі блоки що використовують цей метод - мікропрограмними керуючими пристроями.

В залежності від прийнятого способу кодування мікрооперацій розрізняють три варіанти організації мікропрограмного керування горизонтальне вертикальне та комбіноване мікропрограмування. При горизонтальному мікропрограмуванні для кожної мікрооперації виділяється один розряд у мікрокоманді. При такому кодуванні всі операції що виконуються одночасно визначаються одиницями у відповідних розрядах однієї мікрокоманди. Код операції задає адресу першої мікрокоманди в мікропрограмі. Адреси наступних мікрокоманд визначаються за принципом примусової адресації згідно цього мікрокоманда складається з двох частин-мікроопераційної та адресної. Основною перевагою горизонтального мікропрограмування є висока швидкодія як за рахунок простоти та можливості одночасної генерації довільного числа сигналів мікрооперацій так і за рахунок швидкого формування адреси наступної мікрокоманди. Однак при горизонтальному мікропрограмуванні довжина поля мікрооперації повинна бути не менша за максимальну кількість несумісних мікрооперацій тобто вимагаються довгі формати мікрокоманд та комірки запам’ятовуючого пристрою що призводить до значних витрат обладнання. Крім того лише невелике число розрядів в полі мікрооперації буде містити одиниці тобто запам’ятовуючий пристрій буде використовуватись неефективно.

Скоротити довжину мікрокоманд дозволяє застосування вертикального мікропрограмування при якому кожна мікрооперація кодується ]log2 n[ - розрядним кодом де n – загальна кількість мікрооперацій. Таке