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

Зміст

ВСТУП

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 забезпечує збереження слів s>1>,…s>N>, які представляють значення операндів D, проміжкові значення і кінцеві результати R. Для виконання мікрооперацій Y={ y>m>} служить комбінаційна схема Ф. Керуючі сигнали Y, що формуються управляючим автоматом УА, ініціюють виконання необхідних мікрооперацій. Так, якщо надходять сигнали y>m1 >і y>m2>, то схема Ф виконує дві мікрооперації що зводиться до обчислення значень і присвоєння їх словам . Для обчислення значень логічних умов служить комбінаційна схема ψ, що реалізує систему булевих функцій , значення яких представляються інформаційними сигналами X={x>l>}.

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] >6>111001; В = 1,[0] >30>…[0] >11>1110011011

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

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

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

Суматор НСМ

Регістр РгА

Регістр РгВ

Примітки

0,[0]>62>…[0]>17>00000000000000000

0,[0]>30>...[0]>6>111001

1,[0]>30>…[0]>11>1110011011

НСМ:=0; РгА:=Швх1; РгВ:=Швх2; ЛІЧ:=29;

1,[0]>62>…[0]>18>000000000000000000

0,[0]>30>...[0]>6>111001

1,[0]>30>…[0]>12>1110011011_

НСМ[63]:=1; РгВ[30]=0; L1.РгВ[0:30]; ЛІЧ:=28;

L1.НСМ[0:62]; НСМ[0]:=0;

1,[0]>62>…[0]>17>00000000000000000

0,[0]>30>...[0]>6>111001

1,01110011011[ _ ] >19>…[ _ ] >0>

РгВ[30]=0; L1.РгВ[0:30];

L1.НСМ[0:62];

НСМ[0]:=0; ЛІЧ:=10;

1,[0]>62>…[0]>17>00000000000000000

1,[0]>62>…[0]>17>00000000000111001

1,[0]>62>…[0]>17>00000000001110010

0,[0]>30>...[0]>6>111001

1,1110011011[_] >20>…[_] >0>

РгВ[30]=1;

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

L1.РгВ[0:30];

L1.НСМ[0:62];

НСМ[0]:=0; ЛІЧ:=9;

1,[0]>62>…[0]>17>00000000001110010

1,[0]>62>…[0]>17>00000000010101011

1,[0]>62>…[0]>17>00000000101010110

0,[0]>30>...[0]>6>111001

1,110011011[_] >21>…[_] >0>

РгВ[30]=1;

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

L1.РгВ[0:30];

L1.НСМ[0:62];

НСМ[0]:=0; ЛІЧ:=8;

1,[0]>62>…[0]>17>00000000101010110

1,[0]>62>…[0]>17>00000000110001111

1,[0]>62>…[0]>17>00000001100011110

0,[0]>30>...[0]>6>111001

1,10011011[_] >22>…[_] >0>

РгВ[30]=1;

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

L1.РгВ[0:30];

L1.НСМ[0:62];

НСМ[0]:=0; ЛІЧ:=7;

1,[0]>62>…[0]>17>00000001100011110

1,[0]>62>…[0]>17>00000011000111100

0,[0]>30>...[0]>6>111001

1,0011011[_] >23>…[_] >0>

РгВ[30]=0; L1.РгВ[0:30];

L1.НСМ[0:62];

НСМ[0]:=0; ЛІЧ:=6;

1,[0]>62>…[0]>17>00000011000111100

1,[0]>62>…[0]>17>00000110001111000

0,[0]>30>...[0]>6>111001

1,011011[_] >24>…[_] >0>

РгВ[30]=0; L1.РгВ[0:30];

L1.НСМ[0:62];

НСМ[0]:=0; ЛІЧ:=5;

1,[0]>62>…[0]>17>00000110001111000

1,[0]>62>…[0]>17>00000110010110001

1,[0]>62>…[0]>17>00001100101100010

0,[0]>30>...[0]>6>111001

1,11011[_] >25>…[_] >0>

РгВ[30]=1;

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

L1.РгВ[0:30]; ЛІЧ:=4;

L1.НСМ[0:62]; НСМ[0]:=0;

1,[0]>62>…[0]>17>00001100101100010

1,[0]>62>…[0]>17>00001100110011011

1,[0]>62>…[0]>17>00011001100110110

0,[0]>30>...[0]>6>111001

1,1011[_] >26>…[_] >0>

РгВ[30]=1;

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

L1.РгВ[0:30]; ЛІЧ:=3; L1.НСМ[0:62]; НСМ[0]:=0;

1,[0]>62>…[0]>17>00011001100110110

1,[0]>62>…[0]>17>00110011001101100

0,[0]>30>...[0]>6>111001

1,011[_] >27>…[_] >0>

РгВ[30]=0; L1.РгВ[0:30];

L1.НСМ[0:62];

НСМ[0]:=0; ЛІЧ:=2;

1,[0]>62>…[0]>17>00110011001101100

1,[0]>62>…[0]>17>00110011010100101

1,[0]>62>…[0]>17>01100110011011000

0,[0]>30>...[0]>6>111001

1,11[_] >28>…[_] >0>

РгВ[30]=1;

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

L1.РгВ[0:30]; ЛІЧ:=1;

L1.НСМ[0:62]; НСМ[0]:=0;

1,[0]>62>…[0]>17>01100110011011000

1,[0]>62>…[0]>17>01100110110000011

1,[0]>62>…[0]>17>11001100110110000

0,[0]>30>...[0]>6>111001

1,1[_] >29>…[_] >0>

РгВ[30]=1;

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

L1.РгВ[0:30]; ЛІЧ:=0;

L1.НСМ[0:62]; НСМ[0]:=0;

1,[0]>62>…[0]>17>11001100110110000

1,[0]>62>…[0]>17>01100110011011000

0,[0]>30>...[0]>6>111001

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 – загальна кількість мікрооперацій. Таке кодування накладає обмеження на методи виконання операцій а саме не повинно бути операцій що потребують одночасного виконання ряда мікрооперацій. В тих випадках коли це обмеження виконати неможливо треба використовувати складні мікрооперації що складаються з сукупності простих.

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

За способом формування функції виходів виділяють три типи абстрактних автоматів: автомат Мілі, автомат Мура та С-автомат.

В абстрактному автоматі Мілі значення функції виходу в момент t залежить не лише від стану автомата, але і від набору значень вхідних сигналів.

Довільний абстрактний автомат Мілі має один вхідний і один вихідний канали.

Автомат Мілі характеризується системою рівнянь:

(2.1)

де – множина вхідних сигналів автомата (вхідний алфавіт);

– множина станів автомата (алфавіт станів);

– множина вихідних сигналів (вихідний алфавіт).

λ – функція виходів автомата;

φ – функція переходів автомата.

Іншими словами, функція виходів λ задає відображення (XS)→Y, тобто ставить у відповідність будь-якій парі елементів декартового добутку множин (XS) елемент множини S.

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

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

Позначення операцій та логічних умов наведено у таблиці 3.

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

Умови переходу по мікропрограмі від одного стану до іншого задають функцію переходів автомата.

Таблиця переходів (виходів) являє собою таблицю з подвійним входом, рядки якого пронумеровані вхідними буквами, а стовпці – станами. На перетині вказується стан, у який переходить автомат (в таблиці переходів) або вихідний сигнал, що видається ним (у таблиці виходів).

Іноді при завданні автоматів Мілі використовують одну суміщену таблицю переходів і виходів, в якій на перетині стовпця а>m> і рядка х>j> записуються у вигляді а>s>/y>g> наступний стан і вихідний сигнал, що видається.

У таблиці 4 для заданого автомата маємо суміщену таблицю переходів і виходів.

Таблиця 2 – Таблиця переходів і виходів

t

t+1

Тригери

JK2

JK1

JK0

a>i>

код a>i>

x>i>

a>i+1>

код a>i+1>

y>i>

J2

K2

J1

K1

J0

K0

a>0>

000

a>1>

001

y1,y2,y3,y4

0

0

0

0

1

0

a>2>

010

0

0

1

0

0

0

a>3>

011

0

0

1

0

1

0

a>1>

001

a>2>

010

y5

0

0

1

0

0

1

a>3>

011

0

0

1

0

0

0

a>2>

010

___

a>3>

011

y6

0

0

0

0

1

0

a>3>

011

___

a>4>

100

y7,y8

1

0

0

1

0

1

a>4>

100

a>5>

101

y9,y10

0

0

0

0

1

0

a>2>

010

0

1

1

0

0

0

a>3>

011

0

1

1

0

1

0

a>5>

101

____

a>6>

110

y11

0

0

1

0

0

1

a>6>

110

____

a>0>

000

y12

0

1

0

1

0

0

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

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

Для автомату Мілі вихідний сигнал залежить не лише від внутрішнього стану, а й від зовнішнього стану схеми. Можна побудувати граф переходів автомата Мура, де вершинами являються стани автомата, а дугами - умови переходу з одного стану в інший.

В залежності від способу визначення вихідного сигналу в синхронних автоматах існує два способи:

вихідний сигнал y(t) однозначно визначається вхідним сигналом x(t) і станом а(t-1) автомата в слідуючий момент часу;

вихідний сигнал y(t) однозначно визначається вхідним сигналом x(t) і станом а в даний момент часу.

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

Після побудови автомата Мілі функціонування керуючого автомата представляють у вигляді таблиць переходів і виходів. Для цього спочатку виробляють кодування станів автомата двійковими кодами, визначають тип та кількість тригерів. Потім по таблиці переходів встановлюють значення сигналів на входах тригерів, при яких відбуваються переходи; визначають функції збудження тригерів і виконують їх мінімізацію (спрощення). По знайдених виразах будується схема управляючого автомата на вибраних елементах.

В нашому випадку буде використовуватись три логічні умови Х = {х1,x2,х3} і дванадцять мікрооперацій Y = {y1, …, y10}

Отже, для кодування станів автомата необхідно 3 JK-тригера: JK0, JK1, JK2,. Закодуємо стани автомата так, як це показано у таблиці 5.

Для побудови функцій збудження тригерів і виходів використовується структурна таблиця автомата (таблиця 5).

На основі таблиці 5 будується канонічна система функцій виходів і функції збудження тригерів.

Функції виходів:

;

;

;

;

;

;

;

;

;

;

.

Функції збудження тригерів:

;

;

;

.

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

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

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

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

По-перше розглянемо зображення числа в відповідному коді, як єдину кодову комбінацію.

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

    роздільний контроль знакової і цифрової чистин зображень результату;

    загальний контроль всього зображення.

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

При загальному способі контролю потребує корекцію контрольного коду результату із-за того, що знак результату при додаванні повторює знак доданків.

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

Одним з таких кодів є AN-код, де А-контролюєме число, N-модуль. Для таких кодів змінюються поняття відстані і ваги.

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

А = 2і – 1 , і=2,3,…

АN>1 > АN>2> = A(N>1 > N>2>)

Якщо ділення виконується без остачі, помилок немає, якщо з остачею – помилки є.

АN>1 >АN>2> = A2N>1> N>2>

АN – використовуються для контролю лише в тих пристроях, де реалізується операція ділення.

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

Виконаємо числовий контроль за допомогою 11N-коду для заданих чисел:

N>1 >= 57

N>2> = -923

A=11

11*57*(-923)*11 = 121*(-52 611) = -6 365 931

Тепер отримане число ділимо на 121:

-6 365 931/121 = -52611

Отримаємо -52611 – це означає що націло ділиться отже не існує помилки. Остача в цьому прикладі дорівнює нулю.

Внесемо похибку в обчислення:

-6 365 933/121 = -52611 і остачу 2, отже результат не збігається.

ВИСНОВКИ

В ході виконання курсової роботи проведено аналіз проблеми логiчної реалізації операції множення чисел у формі з фіксованою комою, зокрема, алгоритму множення на суматорі прямого коду, починаючи зі старших розрядів множника. Вищевказана операція перевірена на прикладі чисел А= 57 та В= - 923, а також для заданої операції побудовано алгоритм виконання множення чисел у формі з фіксованою комою. Потім за даним алгоритмом розроблено операційний та керуючий автомати. А також описана методика 11N контролю даної операції.

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

    Методичні вказівки до оформлення курсових проектів (робіт) у Вінницькому національному технічному університеті / Г.Л. Лисенко, А.Г. Буда, Р.Р. Обертюх. – Вінниця: ВНТУ, 2006. – 60 с.

    Прикладная теория цифровых автоматов: Учеб. для вузов по спец. ЭВМ / А.Я. Савельев. – М.: Высшая школа, 1987. – 272 с.

    Прикладная теория цифровых автоматов / К.Г. Самофалов, А.М. Романкевич, В.Н. Валуйский, Ю.С Каневский, М.М. Пиневич. – К.: Вища школа. Головное изд-во, 1987. – 375 с.

    Структура электронных вычислительных машин / С.А. Майоров, Г.И. Новиков. – Л.: Машиностроение. Ленинградское отделение, 1979. – 384 с.

    Электронные вычислительные машины и системы: Учеб. пособие для вузов. – 3-е изд., перераб. и доп. / Б.М. Каган. – М.: Энергоатомиздат, 1991. – 592 с.

    Цифровые ЭВМ: Теория и проектирование / К.Г. Самофалов, В.И. Корнейчук, В.П. Тарасенко. – К.: Выща школа. Головное изд-во, 1989. – 424 с.

    Справочник по цифровой схемотехнике / В.И. Зубчук, В.П. Сигорский, А.Н. Шкуро. – К.: Тэхника, 1990. – 448 с.