2.5. Другий алгоритм множення у прямому коді.

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

де

Регістр множника повинен мати довжину в n розрядів, регістри множеного та суми часткових добутків – по 2n розрядів.

Перед початком множення множене повинно бути записано в відповідний регістр зі зсувом вправо на n розрядів для того, щоб було сформовано значення Y_n. ГСА такого множення показана на рис.4.

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

Приведемо приклад цифрової діаграми, табл.2., множення чисел Х = 13/16 та Y = 12/16, n = 4.

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

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

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

PX xn*	PY		PZ	СТК	Пояснення
1101 0110 0011 0001	00001100 00011000 00110000 01100000	+	00000000 00001100	001 010 011 100 END	Початковий стан +Y Результат сумування Зсув Зсув +Y Результат сумування Зсув +Y Результат сумування
			00001100 00001100 00001100 00110000
		+
			00111100 00111100 01100000
		+
			10011100

Час множення по даному алгоритму визначається за формулою

Т=(n-1)(tз+ t+)+ t+

tз – t зсуву t+ - t сумування

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

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

2.6. Третій алгоритм множення у прямому коді.

Третій основний алгоритм множення Z= X*Y можна отримати за рекурентною формулою добутку Z_i = Z_i-1 2 + x_i 2 ^{– n} Y, i = де Z₀ = 0, Z_n = Z.

В відповідності з цією формулою множення починається зі старших розрядів множника, сума часткових добутків зсувається вліво, число кроків множення дорівнює n, закінчується виконання алгоритму додаванням. Довжину в 2n розрядів повинен мати тільки регістр PZ. ГСА алгоритму має вигляд, рис.5.:

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

Проте оскільки зсуви в РХ та PZ виконуються в одну й ту ж сторону, то в варіантах цього алгоритму старші розряди добутку можна заносити в регістр РХ.

Приклад цифрової діаграми, табл.3., множення чисел Х=11/16 та Y=10/16, n=4.

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

x1*PX	PY	PZ	СТК	Пояснення
1011 0110 1100 1000	1010 1010 1010 1010	00000000 1010	001 010 011 100 END	Початковий стан +Y Результат сумування Зсув Зсув +Y Результат сумування Зсув +Y Результат сумування
		00001010 00010100 00101000 1010
		00110010 01100100 1010
		01101110

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

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