3. Алгоритм множення починаючи з старших розрядів множника і зсувом розрядів суматора вліво

Третій основний алгоритм одержимо, записавши добуток Z у вигляді

(6)

.

Отже, добуток можна одержати за рекурентною формулою

, (7)

де . Відповідно до алгоритму (7) множення починається зі старших розрядів множника і зсувом накопиченої суми часткових добутків вліво (рис. 3, а). Число кроків множення дорівнює п, закінчується виконання алгоритму додаванням. ГСА для цього випадку наведена на рис. 3, б. Довжину в 2п розрядів тут повинен мати тільки регістр PZ.

Рис. 3

Приклад 3. Складемо цифрову діаграму множення чисел і за третім основним алгоритмом (табл. 3).

Таблиця 3

	←	←	ЛЧК	Пояснення
1011	1 101	00000000	001	Вихідний стан
		1011
		00001011		Результат підсумовування
1010	1 010	00010110	010	Зсув
		1011
		00100001		Результат підсумовування
1010	0 100	01000010	011	Зсув
1010	1 000	10000100	100	Зсув
		1011
		10001111		Результат підсумовування
			END

Результат:

3. Алгоритм множення починаючи з старших розрядів множника і зсувом розрядів множеного вправо

Четвертий основний алгоритм множення базується на представленні добутку у вигляді

(8)

.

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

, (9)

де . За даним алгоритмом множення починається з старших розрядів множника, сума часткових добутків нерухома, а множене в процесі множення зсувається вправо, закінчується множення підсумовуванням (рис. 4, а). ГСА такого множення наведено на рис. 4, б.

Рис. 4

Приклад 4. Складемо цифрову діаграму множення чисел і , за четвертим основним алгоритмом (табл. 4).

Таблиця 4

→	←		ЛЧК	Пояснення
0101 1000	1 101	0000 0000	001	Вихідний стан
		0101 1
		0101 1000		Результат підсумовування
0010 1100	1 010	0101 1000	010	Зсув
		0010 11
		1000 0100		Результат підсумовування
0001 0110	0 100	1000 0100	011	Зсув
0000 1011	1 000	1000 0100	100	Зсув
		0000 1011
		1000 1111	END	Результат підсумовування

Результат:

Приклад 1.1. Скласти цифрову діаграму множення чисел і , (табл. 1.1).

Таблиця 1.1

	→	→	ЛЧК	Пояснення
1010	1110 0111	00000000 00000000	000 001	Вихідний стан Зсув
		1010
		10100000		Результат підсумовування
	0011	01010000	010	Зсув
		1010
		11110000		Результат підсумовування
	0001	01111000 1010	011	Зсув
	0000	1 00011000 10001100	100	Результат підсумовування Зсув
			END

Приклад 2.1. Скласти цифрову діаграму множення чисел і , за другим основним алгоритмом (табл. 2.1).

Таблиця 2.1

←	→		ЛЧК	Пояснення
00001010	1110	00000000	001	Вихідний стан
00010100	0111	00000000	010	Зсув
		00010100
		00010100		Результат підсумовування
00101000	0011	00010100	011	Зсув
		00101000
		00111100		Результат підсумовування
01010000	0001	00111100	100	Зсув
		01010000
		10001100		Результат підсумовування
			END

Приклад 3.1. Складемо цифрову діаграму множення чисел і за третім основним алгоритмом (табл. 3.1).

Таблиця 3.1

	←	←	ЛЧК	Пояснення
1010	1110	00000000	001	Вихідний стан
		1010
		00001010		Результат підсумовування
1010	1100	00010100	010	Зсув
		1010
		00011110		Результат підсумовування
1010	1000	00111100	011	Зсув
		1010
		01000110		Результат підсумовування
1010	0000	10001100	100	Зсув
			END

Приклад 4.1. Складемо цифрову діаграму множення чисел і , за четвертим основним алгоритмом (табл. 4.1).

Таблиця 4.1

→	←		ЛЧК	Пояснення
01010000	1110	00000000	001	Вихідний стан
		01010000
		01010000		Результат підсумовування
00101000	1100	00101000	010	Зсув
		00101000
		01111000		Результат підсумовування
00010100	1000	01111000	011	Зсув
		00010100
		10001100		Результат підсумовування
00001010	0000	10001100	100	Зсув
		00000000
		10001100		Результат підсумовування
			END

Рис. 1

Рис. 2

Рис. 3

Рис. 4

Приклад 1.2. Скласти цифрову діаграму множення чисел і , (табл. 1.2).

Таблиця 1.2

	→		→		ЛЧК	Пояснення
101011	10011	1		000000000000 101011	000	Вихідний стан
				101011000000
	1001	1		010101100000	001	Зсув
				101011
			1	000000100000
	100	1		100000010000 101011	010	Зсув
	10	0	1	001011010000 100101101000 000000	011	Зсув
	1	0		010010110100 000000	100	Зсув
		1		001001011010 101011	101	Зсув
				110100011010
				011010001101	110 END	Зсув

Приклад 2.2. Скласти цифрову діаграму множення чисел і , за другим основним алгоритмом (табл. 2.2).

Таблиця 2.2

←	→				ЛЧК	Пояснення
000000101011	10011	1		000000000000 000000101011	001	Вихідний стан
				000000101011
000001010110	1001	1		000001010110	010	Зсув X+
				000010000001
000010101100	100	1		000010101100	011	Зсув X+
000101011000	10	0		000100101101 000000000000	100	Зсув X
001010110000	1	0		000100101101 000000000000	101	Зсув X
010101100000		1		000100101101 010101100000	110	Зсув X+
				011010001101
					END

Приклад 3.2. Складемо цифрову діаграму множення чисел і , за третім основним алгоритмом (табл. 3.2).

Таблиця 3.2

	←		←		ЛЧК	Пояснення
000000101011	100111	1		000000000000 000000101011	001	Вихідний стан X+
	00111			000000101011 000001010110	010	Зсув
		0		000000000000		X*0
	0111			000010101100	011	Зсув
		0		000000000000		X*0
	111	1		000101011000 000000101011	100	Зсув X+
	11	1		000110000011 001100000110 000000101011	101	Зсув X+
	1	1		001100110001 011001100010000000101011	110	Зсув X+
				011010001101
				END

Таблиця 3.2

Приклад 4.2. Складемо цифрову діаграму множення чисел і , за четвертим основним алгоритмом (табл. 4.1).

Таблиця 4.2

→	←				ЛЧК	Пояснення
101011000000 010101100000	100111	1		000000000000 010101100000	001	Вихідний стан ЗсувX+
001010110000	00111	0		010101100000 000000000000	010	X*0
				010101100000
000101011000	0111	0		000000000000	011	X*0
000010101100	111	1		010101100000000010101100	100	X+
000001010110 000000101011	11 1	1 1		011000001100 000001010110 011001100010 000000101011	101 110	Х+ Х+
				011010001101
				END

15