2.7. Четвертий алгоритм множення у прямому коді.

По четвертому основному алгоритму множення Z=X*Y зводиться до обчислювання за рекурентною формулою

Z_i = Z_i-1 + x_i Y_i, i = де Z₀ = 0, Z_n = Z. Y₀ = Y, Y_i = Y_i-12^-1.

Тут множення починається зі старших розрядів множника, сума часткових добутків нерухома, в процесі множення множене зсувається вправо, закінчується множення додаванням. Очевидно, що довжину в 2n розрядів тут повинні мати регістри PY та PZ. Оскільки сума часткових добутків нерухома, то використовувати для зберігання її частини регістр РХ, що звільняється, неможливо. Проте закінчення операції можна визначати за нулоьвим вмістом РХ і, таким чином, виключити СТК. Відмінностями на ГСА, як і при множенні за другим основним алгоритмом, буде заміна умови СТК = n умовою PX = 0 та вилучення елементарних операцій на СТК. ГСА такого множення має вигляд, рис.6.:

Рис. 6. Четвертий алгоритм множення у прямому коді

Цифрова діаграма, табл.4. множення чисел Х = 7/16; Y = 15/16, n = 4.

Таблиця 4. Цифрова діаграма при множенні за IV алгоритмом множення у ПК

x1*PX	PY	PZ	СТК	Пояснення
0111 1110 1100 1000	01111000 00111100 00011110 00001111	00000000 00000000 00111100	001 010	Початковий стан Зсув +Y Результат додавання Зсув +Y Результат додавання Зсув +Y Результат додавання
		00111100 00111100 00011110	011
		01011010 01011010 00001111	100
		01101001	END

T = (n-1)(t_з+t₊)+t₊

Продовження додатку

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

2.8. Множення чисел в додатковому коді

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

1. Якщо Х>0, Y<0, то їхній добуток повинен бути від’ємним та представлений додатковим кодом. Тоді можна записати, що

В цьому випадку кожний частковий добуток виду дорівнює або 0 або .

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

2. При від’ємному множнику X і додатному множеному Y, як показано вище для випадку множення додаткових кодів операндів з урахуванням їх знаків, псевдо множення має вигляд Z'= 2 |Y| - |X| x |Y|. Разом з тим, частковий добуток, який був сформований при множенні на знакове число множника, дорівнює |Y|. Отже, якщо при множенні на знакове число множника не додавати останній частковий добуток до їхньої суми, а відняти його, то тим самим Z' буде зменшене на 2 |Y|. Більше того, якщо для подання від’ємного останнього часткового добутку скористатися додатковим кодом, тобто записати його у вигляді 2- |2Y| = 2-2|Y|, то при його додатку не тільки буде відкоректована числова частина добутку, але й сформується правильний його знак. На підставі цього можна побудувати такий алгоритм множення операндів у додатковому коді. При від’ємному множнику вважають його представленим у надлишковій двійковій системі числення із числами {-1,0,1}, а знаковий розряд множника – від’ємним числом. Далі за звичайною методикою виконують множення множеного (разом зі знаковим розрядом) на всі розряди множника. На останньому кроці (тобто, при множенні на знаковий розряд) виконують операцію -Y замість + Y. В разі якщо множник додатний, то його знаковий розряд не міняють, а множення на знаковий розряд виконується як звичайно (можна вважати, що виконують операцію +0 ). ГСА такого множення на базі першого основного алгоритму наведена на рис.7, де (х₀ *) у нижній умовній вершині вказує на перевірку знакового числа множника.

Продовження додатку

Рис 7. ГСА множення на базі першого основного алгоритму

3. Якщо Х<0, Y<0, то корекція результату може бути зроблена об'єднанням двох попередніх варіантів, тобто, при множенні на знаковий розряд множника виконують розрахунки, а підсумовування й зрушення часткових добутків роблять із використанням модифікованого додаткового коду. Очевидно, що час множення в цьому випадку буде дорівнювати

T_{У ДК} = (n+1)(t_c+t+).

2.9. Корекція добутку з підсумовуванням часткових добутків

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

Тому далі будемо розглядати лише варіанти, що відповідають Х<0.

1. Нехай Х<0, Х>0_, тоді абсолютна величина вмісту числових розрядів операнду ХДК дорівнює |1- | Х ||. Тому, якщо до числових розрядів операнду ХДК додати знаковий розряд, зважаючи при цьому, що він має штучну вагу -1, тоді абсолютна величина вмісту числових розрядів множника, перетвореного таким чином, складе

Продовження додатку

Отже, множення на X'_дк можна виконувати так само, як і в прямому коді, тобто

2. У випадку Х<0, Y<0, достатньо привести множник до виду Х ДК, а підсумовування й зсув виконувати за правилами підсумовування й зсуву модифікованих додаткових кодів.

Для перетворення ХДК в Х ДК немає необхідності виконувати окремі операції відповідно до вищенаведених формул. Покажемо, як таке перетворення можна сполучити із зсувом множника й суми часткових добутків. Позначимо числову частину операнду Х_ДК як X'.

Нехай .

Тоді можна записати,

Представимо ваги розрядів (крім знакового) у цьому вираз як

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

Рис.8.

Продовження додатку

Однак оскільки , то Очевидно, що для одержання досить порівняти числа в сусідніх розрядах множника (табл. 5). При х' і=0 підсумовування не виконується, при =1 приводять додаток множеного до суми часткових добуток, при = -1 виконують віднімання множимого із суми часткових добутків. Так як множення виконується на знаковий розряд, то число кроків множення дорівнює п+1. Для того, щоб окремі розряди добутку займали наприкінці операції правильні вагові позиції, зрушення на останньому кроці не виконується. У перетворенні i -го числа множника беруть участь i -і та i +1-і його числа. Тому при множенні з молодших розрядів регістр множника повинен мати додатковий молодший розряд, де зберігається i+1 число. ГСА множення в додатковому коді з перетворенням чисел множника наведений на рис.8, де - вміст молодшого додаткового розряду (перед початком множення =0).

Таблиця.5

0	0	0
0	1	1
1	0	-1
1	1	0

Складемо числову діаграму множення, табл.7., чисел X=-5/16 та Y=-15/16 у додатковому коді за алгоритмом з перетворенням чисел множника (табл.6). Зауважимо, що Xдк=1.1011 та YДК=1.0001.

Таблиця 6.

0	0	0
0	1	1
1	0	-1
1	1	0

Таблиця 7. Числова діаграма при множенні

РХ	* Хп		PY	PZ	СТШ	Пояснення
1. 101	1	0	11. 0001	00,00000000 00,1111	000	Початковий стан -Y
11,10 111,1	1 0	1 1		00.1111 00.01111 00.001111 11.0001	001 010	Результат підсумовування Зсув Зсув,+0 +Y
1111	1	0		11.010011 11.1010011 00.1111	011	Результат підсумовування Зсув
1111	1	0		00. 1001011 00.01001011 00, 0000	100	Результат підсумовування Зсув +0
				00. 01001011	END

Продовження додатку

Складемо числову діаграму множення чисел Х=9/16 і Y=-12/I6 у додатковому коді за алгоритмом на мал. 29. Зауважимо, що Xдк=1.1001 та YДК=1.0100 і оскільки Х>0, то в цьому випадку число не впливає на процес множення (табл. 8).

Таблиця 8

РХ	*Хп		PY	PZ	СТШ	Пояснення
0,100	1	0	11,0100	00,00000000	ООО	Початковий стан
				11,0100		+Y
				11,0100		Результат підсумовування
00,10	0	1		11,10100	001	Зсув
000,1	0	0		11,110100	010	Зсув
0000,	1	0		11,1110100	он	Зсув
						+Y
				11,0010100		Результат підсумовування
0000	0	1		11,10010100	100	Зсув
				Z	END

Складемо числову діаграму множення чисел Х=-9/16 та Y=12/16 у додатковому коді за алгоритмом на мал. 29 (табл.9). Зауважимо, що Xдк=1.0111 та YДК=1.1100.

Таким чином, Zдк=1,10010100 та ZПК=1,01101100 відповідно Z=-108/256. Як передбачалося, результат множення тут такий, як і в попередньому прикладі (тобто Z=-108/256), незважаючи на іншу послідовність мікрооперацій для його отримання.

Таблиця 9

РХ	*Хп		PY	PZ	СТШ	Пояснення
1,011	1	0	00,1100	00,00000000 11,0100	000	Початковий стан -Y
11,01	1	1		11,0100 11,10100	001	Результат підсумовування Зсув
111,0	1	1		11,110100	010	Зсув
1111,	0	1		11,1110100 00,1100	011	Зсув +Y
1111	1	0		00,1010100 00,01010100 11.0100	100	Результат підсумовування Зсув -Y
			Z	11,10010100 END		Результат підсумовування

Продовження додатку