Поняття граф-схеми алгоритму та правила її складання

Особливості виконання основних арифметичних операцій в ЕОМ

Операція алгебраїчного додавання

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

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

Знакова частина позитивного числа містить цифри 00, а від’ємного 11. Ознакою переповнення розрядної сітки є наявність у знаковій частині цифр 01 або 10.

Додавання у прямому коді виконується тільки над числами одного знаку. Числа з різними знаками підсумовують в оберненому або доповняльному коді.

Машинна операція додавання чисел з плаваючою комою здійснюється в шість наступних етапів:

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

· виконується перетворення мантис доданків в один з модифікованих кодів (обернений чи доповняльний);

· мантиси доданків додаються;

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

·  виконується нормалізація суми;

· виконується корекція порядку результату.

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

Кожний зсув мантиси вліво при нормалізації веде до зменшення порядку результату додавання на одиницю. А кожний зсув мантиси вправо – до збільшення. Таким чином відбувається корекція порядку.

 

Операція множення

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

 

Таблиця 1 - Правила визначення знаку добутку

Обчислення вручну	Обчислення в машині

 

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

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

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

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

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

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

1. Дії, що виконуються під час множення обернених (доповняльних) кодів, залежать від знаку множника.

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

3. Якщо множник є від'ємним числом, то обернений (доповняльний) код добутку одержується додаванням поправок  і  () до добутку обернених (доповняльних) кодів співмножників. Оскільки поправки мають різну вагу, то послідовність їх додавання залежить від того, з яких розрядів множника починається множення.

Для чисел  і , що представлені в формі з плаваючою комою, добуток обчислюється за формулою (1):

,        (1)

де , .

Звідси випливає, що процес множення складається з чотирьох етапів:

- множення мантис;

- додавання порядків;

- нормалізація й округлення мантиси добутку;

- корегування порядку добутку.

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

 

Операція ділення

Ділення чисел у двійковій системі числення класифікується таким чином:

· за формою подання чисел:

- з фіксованою комою;

- з плаваючою комою.

· за механізмом виконання операції:

- з відновленням остачі;

- без відновлення остачі;

· за швидкодією:

- просте;

- прискорене;

· за точністю результату:

- з округленням результату;

- без округлення результату.

Для того, щоб поділити двійкові числа з відновленням остачі, необхідно виконати такі операції:

1. Подвоїти модуль діленого .

2. Відняти від подвоєного модуля діленого модуль дільника. Одержана різниця  є першою остачею.

3. Проаналізувати знак остачі R. Якщо , то черговому розряду частки присвоїти 1 і перейти до п. 5; якщо ж R < 0, то черговому розряду частки присвоїти 0.

4. Відновити остачу, додавши модуль дільника .

5. Подвоїти остачу.

6. Визначити чергову остачу, віднявши від попередньої остачі модуль дільника. Перейти до п. 3.

Вищевказані дії слід виконувати до одержання всіх необхідних цифр частки.

Алгоритм ділення модулів чисел без відновлення остачi зводиться до виконання таких дій:

1. Подвоїти модуль діленого .

2. Відняти від подвоєного модуля діленого модуль дільника. Одержана різниця  є першою остачею.

3. Проаналізувати знак остачі R. Якщо , то черговому розряду частки присвоїти 1; якщо ж R < 0, то черговому розряду частки присвоїти 0.

4. Подвоїти остачу.

5. Визначити чергову остачу, віднявши від попередньої остачі модуль дільника якщо  і додавши до попередньої остачі модуль дільника якщо R < 0. Перейти до п. 3.

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

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

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

Після закінчення операції ділення двійкових чисел за обраним алгоритмом (з відновленням чи без відновлення остачі, з прискоренням чи без прискорення) для забезпечення округлення результату операцію ділення за обраним алгоритмом продовжують для визначення ще одного розряду результату. Потім аналізують молодший інформаційний розряд результату. Якщо у цьому розряді записана “1”, то її додають до попереднього розряду результату, якщо “0”, то останній інформаційний розряд результату просто ігнорують. При використанні методу ділення двійкових чисел без округлення результату описані дії не проводять, обмежуючись виконанням алгоритму ділення.

При діленні двійкових чисел з плаваючою комою спочатку визначають знак результату за правилом алгебри логіки “сума за модулем два”, потім проводять корекцію форми запису чисел (|mA| < |mB|) та визначають порядок результату за формулою (2):

 

,                                      (2)

де  - порядок результату;  - порядок числа А;  - порядок числа В.

Далі виконують операцію ділення мантиси числа А на мантису числа В за правилами ділення двійкових чисел з фіксованою комою за одним з обраних алгоритмів (з відновленням чи без відновлення остачі; з округленням чи без округлення; просте чи прискорене). Отриманий результат нормалізують.

 

Поняття граф-схеми алгоритму та правила її складання

 

Граф-схема алгоритму (ГСА) є найбільш наочною формою подання роботи автомата. ГСА – це орієнтоватий зв’язний граф, що містить вершини чотирьох типів (рис. 1). Кожен з існуючих входів і виходів вершин може розгалужуватись потрібну кількість разів.

Рис. 1 – Типи вершин ГСА

 

Вершина "Початок" входів не має. Вершина "Початок" (рис. 1а) і будь-яка операторна (рис. 1г) вершина мають по одному виходу. Вершина "Кінець" (рис. 1б) виходів не має. Будь-яка умовна вершина (рис. 1в) має два виходи, які позначаються символами "Так" і "Ні". Замість цих символів можуть бути використані цифри "1" і "0" відповідно.

ГСА повинна задовольняти таким вимогам:

1) містити скінченне число вершин;

2) мати лише одну початкову та одну кінцеву вершини;

3) входи і виходи кожної з вершин повинні з‘єднуватися дугами, спрямованими від виходу попередньої до входу наступної вершини;

4) кожний вихід повинени з’єднуватись тільки з одним входом;

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

6) для будь-якої вершини графа існує хоча б один шлях до кінцевої вершини;

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

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