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

Зміст

ВСТУП

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₁,…s_N, які представляють значення операндів D, проміжкові значення і кінцеві результати R. Для виконання мікрооперацій Y={ y_m} служить комбінаційна схема Ф. Керуючі сигнали Y, що формуються управляючим автоматом УА, ініціюють виконання необхідних мікрооперацій. Так, якщо надходять сигнали y_m1 і y_m2, то схема Ф виконує дві мікрооперації   що зводиться до обчислення значень  і присвоєння їх словам . Для обчислення значень логічних умов служить комбінаційна схема ψ, що реалізує систему булевих функцій , значення яких представляються інформаційними сигналами X={x_l}.