217

Різниця в тому, що тут часткові добутки зміщуються на і (R1, R2, ...,Ri, R_n-1) розрядів праворуч, а це вимагає розширення на один біт розрядності кожного і-го ОДД в порів­нянні з (і-1)-м.

Обидва розглянуті алгоритми вимагають виконання послідовно n-1 додавання, тоб­то послідовного виконання ОДД, причому в другому алгоритмі ОДД є обчислювально складнішими.

Алгоритм паралельного попарного додавання часткових добутків з використанням структури бінарного дерева вимагає виконання лише log₂n послідовних додавань за ра­хунок розпаралелення обчислень. Граф цього алгоритму показано на рис. 6.16.

При цьому на рис. 6.16 часткові множники зміщуються ліворуч, як на рис. 6.14, хоча їх можна змістити і праворуч, як на рис. 6.15.

Найчастіше в якості операторів додавання в алгоритмах виконання багатомісної операції додавання часткових добутків використовується оператор двомісного однороз-

---

218

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

Для наочності обмежимося чотирирозрядними числами. Виконання багатомісної операції додавання часткових добутків для двох чотирирозрядних чисел А та В, де А -можна представити у вигляді, показаному на рис. 6.17.

Перший рядок даного виразу представляє перший частковий добуток, другий - дру­гий, і так далі. Окремі часткові добутки ah., як це було показано раніше на рис. 6.13, отримані за допомогою елементів AND. Додавання часткових добутків зводиться до до­давання розрядів часткових добутків з однаковими вагами (по стовпцях) з врахуванням переносів з молодших розрядів.

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

---

219

В наведеному алгоритмі знаком суми з трьома входами позначено оператор вико­нання повного однорозрядного двійкового додавання, представлений на рис. 6.8, де ар_і - вхідні дані; z_i - сума, а знаком суми з двома входами (три крайні зліва оператори) позначено оператор виконання неповного однорозрядного двійкового додавання, коли відсутній вхідний перенос, що спрощує алгоритм додавання. Цей оператор виконує опе­рації відповідно до табл. 6.8. На рис. 6.18 переноси не позначено з метою спрощення сприйняття.

Таблиця 6.8

X,	У;	z	с;+(
0	0	0	0
0	1	1	0
і	0	1	0
і	1	і_ ° А	1

Його роботу можна описати наступними формулами:

Обчислювальна складність даного алгоритму рівна: п² - п операцій двомісного од-норозрядного двійкового додавання {п² - 2п операцій повного та п операцій неповно­го двомісного однорозрядного двійкового додавання). Кількість операторів двомісного однорозрядного двійкового додавання на критичному шляху рівна Зп - 4.

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

Обчислювальна складність даного алгоритму рівна: п² - п операцій двомісного од­норозрядного двійкового додавання (п² - 2п операцій повного та п операцій неповного двомісного однорозрядного двійкового додавання). Кількість операторів двомісного од­норозрядного двійкового додавання на критичному шляху рівна 2n- 2.

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

---

220

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

На рис. 6.20 показано граф алгоритму Дадда виконання багатомісної операції додаван­ня часткових добутків, побудований на основі графа алгоритму паралельного попарного додавання часткових добутків з використанням структури бінарного дерева (рис. 6.16).

---

221

6.4.4.4. Прискорене множення двійкових чисел за методом Бута

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

де: X, Y, Z - множене, множник і добуток відповідно, Zi - сума часткових добутків на і-му етапі, Y(i, і-1) - і-й таі-1 розряди множника, п - кількість розрядів операндів X та Y без врахування знакового розряду

Можна проілюструвати цей алгоритм за допомогою блок-схеми, показаної на рис. 6.21.

---

Смотрите также файлы

• Екологія посібник.doc

• LR3_[5405].doc

• Питання до модуля 1 з АК.doc

• Питання до 1 модуля з КЕ.doc

• ДБН В.3.2-2-2009_Жил_здания_реконст_кап_ремонт.doc