Умножение на два разряда множителя в дополнительных кодах

i	i+1	i	i+1
+4Mн	-Mн	+4Mн	-2Mн

В отличие от умножения в прямых кодах преобразованию подвергается не только пара 11, но также и пара 10. Это позволяет упростить анализ кода и формирование преобразованного множителя.

В табл. 2 приведены преобразования i и i+1 пары множителя.

Таблица 2

i-я пара	i+1-я пара	Преобраз. пара	Алгоритм
х	y	z	-	x¢	y¢	A	Г
			-
			-
			-
			-
1			-
1			-
1			-
			-

Действия, осущестляемые при выполнении, например, алгоритмов А и Г следующие:

(1) (6)

(2) (7)

(3) (8)

(4) (9)

(5) (10)

Если i+1 пара имеет старшую цифру 1, то умножение на эту пару будет соответствовать вычитанию одного или двух множителей. На рис. 9 приведена логическая схема для формирования сигнала выполняемого действия при анализе пары (xy) и старшего разряда (z) предыдущей пары при умножении чисел согласно алгоритму Г.

Как было показано выше, при умножении чисел в дополнительных кодах в общем случае необходимо вводить поправку для получения верного произведения. Однако при умножении на два разряда множителя этого выполнять не требуется. Если на умножение поступает отрицательный множитель, то при преобразовании его старшей пары происходит формирование дополнительной пары:

Мт = -10110

[Мт]_доп= 1.0 10 10

[Мт]_доп^п= 01 01 01 10

При умножении на дополнительную пару (01) происходит вычитание одного множителя, а затем он должен быть добавлен в качестве поправки. Таким образом, тратится два такта на выполнение взаимоисключающих операций.

Рис. 9. Логическая схема формирования сигнала выполняемого действия

Пример:

Мн = + 0101 умножение выполним согласно

Mт = + 1100111 алгоритму Г

[Mн]_доп = 0.0101

[Mт]_доп = 0.1 10 01 11

Анализ пар Мт можно производить начиная от старших (при умножении по алгоритмам В и Г) и от младших разрядов (алгоритмы А и Б).

= 10 10 10 01

[-2Mн]_доп = 1.0110 [2Mн]_доп = 0.1010

0.0000 00000000

⁺ 0. 00 10 10000000 = 2M_H∙2^-2

0.0010 10000000

⁺ 1. 1111 01100000 = -2M_H∙2^-4

0.0001 11100000

⁺ 0. 0000 00 101000 = 2M_H∙2^-6

0.0010 00001000

⁺ 1. 1111 1111 1011 = -M_H∙2^-8

0.0010 00000011 = [Mн Mт]_доп

 

Пример:

Mн= - 0101 умножение выполним согласно

Mт = -1100111 алгоритму Б

[Mн]_доп = 1.1011

[Mт]_доп = 1.0 01 10 01

= 1.0 10 10 01

[2Mн]_доп = 1.0110 [-2Mн]_доп = 0.1010

 

0.000000 0000

⁺ 1.111111 1011 = Mн

1.111111 1011

⁺ 0.000010 10 00 = -2Mн ∙ 2²

0.000010 0011

⁺ 1.110110 0000 = 2Mн ∙ 2⁴

1.111000 0011

⁺ 0.1010 00 0000 = -2Mн ∙ 2⁶

0.100000 0011 =Mн×Mт

 

Матричные методы умножения

Кроме рассмотренных методов ускоренного умножения существуют методы умножения, основанные на использовании матриц промежуточных результатов.

Пусть имеем сомножители:

Мн = А = а_n ... a₂ a₁

Мт = B = b_n... b₂ b₁

Рассмотрим схему умножения чисел согласно алгоритму Б. Данная схема умножения может быть представлена в виде матрицы (табл.3).

Каждый элемент a_i b_j (i, j = 1, n) принимает значение 0 или 1. Произведение A∙B может быть получено, если суммировать элементы матрицы (по диагонали).

Для суммирования по столбцам могут быть использованы счетчики. Однако при достаточно большом значении величины n потребуются счетчики с большим числом входов, что существенно увеличит время сложения. Но этот принцип умножения может быть реализован на устройствах, имеющих не более трех входов. В качестве их могут быть использованы одноразрядные двоичные сумматоры и полусумматоры.

На рис. 10 приведена структурная схема устройства умножения для реализации матричного алгоритма.

Реализация методов матричного умножения требует большего количества оборудования, чем метод последовательного умножения, и дает больший выигрыш во времени. В связи с увеличением степени интеграции элементной базы ограничения по количеству оборудования становятся не столь строгими.

 

Машинные методы деления

Деление - простое многократное вычитание делителя вначале из делимого, затем из остатков. Введем обозначения, используемые ниже: Дм - делимое, Дт - делитель, А_i – очередной (i-й) остаток, Чт – частное. Известны два основных подхода к операции деления:

§ с восстановлением остатков;

§ без восстановления остатков.

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

может быть достижение заданной точности (по числу сдвиговых сигналов). Если при выполнении деления получен нулевой i-й остаток, то деление прекращается и в оставшиеся разряды частного записываются нули. Первым шагом деления двух чисел машиной является пробное вычитание, выявляющее соотношение между делимым и делителем. При делении в случае переполнения следует: для чисел с фиксированной запятой процесс остановить, с плавающей запятой продолжить до конца, а потом, после получения последней n-й цифры частного, число сдвигается вправо на один разряд с добавлением единицы к порядку, равному разности порядков делимого и делителя.