6.4.4.2. Багатомісна операція додавання часткових добутків

Алгоритм виконання багатомісної операції додавання часткових добутків залежить від типу використовуваних операторів додавання. Це можуть бути зокрема оператори попарного n-розрядного додавання двох чисел, оператори попарного однорозрядного додавання двох чисел, оператори багатомісного паралельного додавання чисел і т. д. Якщо використовувати оператори попарного n-розрядного додавання двох чисел, тобто двох часткових добутків, то можуть бути запропоновані наступні алгоритми:

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

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

• алгоритм паралельного попарного додавання часткових добутків з використан­ням структури бінарного дерева.

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

Тут послідовно з'єднані оператори двомісного (попарного) додавання (ОДД), причо­му часткові добутки подаються для додавання із зміщенням на і (L1,L2, ..,Li,L_n-1) розря­дів ліворуч. Молодший розряд результату кожного і-го ОДД (ОДД,, ОДД₂,..., ОДД_n-1) є відповідним розрядом добутку Zi, а нульовий розряд добутку є рівним молодшому роз­ряду першого часткового добутку. Розряди добутку від Z_2n-1-го до Z_n-1-го отримуються з виходів (nІ)-го оператора ОДД, починаючи з другого виходу.

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

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

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

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

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

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

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

220

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

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