4.2. УМНОЖЕНИЕ, ВЫПОЛНЯЕМОЕ МЕТОДОМ НАКОПЛЕНИЯ ЧАСТИЧНЫХ ПРОИЗВЕДЕНИЙ

Операция умножения в современных ЭВМ чаще всего выполняется суммированием сдвинутых на один или несколько разрядов частичных произведений, каждое из которых является результатом умножения множимого на соответствующий разряд (разряды) множителя.

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

нескольких чисел. Поэтому в произведении только в отдельных случаях используют двойное количество разрядов, обычно же ограничиваются количеством разрядов, которое имели сомножители. Здесь учитывается то обстоятельство, что правила приближенных вычислений рекомендуют оставлять в произведении столько же значащих цифр, сколько их содержится в наименее точном из сомножителей. Младшие разряды результата при этом отбрасываются, а старшие обычно округляются по известным правилам с тем, чтобы ошибка произведения стала знакопеременной и ее математическое ожидание было равно 0 с учетом равновероятности любых значений отброшенных младших разрядов.

Наиболее просто операция умножения в ЭВМ выполняется в прямом коде. При этом на первом этапе определяется знак произведения путем сложения знаковых цифр сомножителей по модулю 2.

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

Так как умножение производится в двоичной системе счисления» частные произведения либо равны 0 (при умножении на 0), либо самому сомножителю (при умножении на 1), сдвинутому на соответствующее количество разрядов.

Пример. Заданы

Процессом накопления суммы частных произведений можно управлять с помощью цифр множителя в соответствии с выражением

где С — искомое произведение; А — множимое; В — множитель.

Управление процессом умножения может начинаться как с младших разрядов множителя, так и со старших.

При этом полную сумму (произведение) можно получить двумя путями:

1) сдвигом множимого на требуемое количество разрядов и добавлением полученного очередного частного произведения ранее накопленной сумме;

2) сдвигом суммы ранее полученных частных произведений на каждом шаге на один разряд и последующим добавлением к сдвинутой сумме неподвижного множимого либо 0.

Основываясь на вышеизложенном можно создать четыре варианта схем машинного умножения:

I) умножение младшими разрядами множителя со сдвигом накапливаемой суммы вправо;

2) умножение младшими разрядами множителя со сдвигом множимого влево;

3) умножение старшими разрядами множителя со сдвигом суммы частичных произведений влево;

4) умножение старшими разрядами множителя со сдвигом множимого вправо.

Рассмотрим более детально каждую из четырех схем умножения.

Умножение младшими разрядами множителя со сдвигом суммы частичных произведений вправо.

Выражение (4.5) можно представить в виде схемы Горнера для вычисления полиномов.

которое может быть сведено к -кратному выполнению цикла

при начальных значениях

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

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

Реализация данного способа требует -разрядного сдвигающего регистра множителя, схем И, пропускающих множимое на вход сумматора при и запрещающих его передачу при -разрядного регистра множимого -разрядного сумматора, в котором накапливается сумма и имеются цепи для ее сдвига вправо на один разряд. Структура умножителя представлена на рис. 4.1.

Если дополнительные разряды СМ исключить, то произведение будет вычисляться с тем же количеством разрядов, что и сомножители. Однако для округления результата желательно удлинить СМ на один дополнительный разряд, чтобы после вычисления произведения прибавить к дополнительному разряду единицу и вывести из СМ результат без дополнительного разряда.

Количество разрядов СМ может быть уменьшено вдвое также при вычислении полноразрядного произведения, если вместо

Рис. 4.1

Рис. 4.2

использовать освобождающиеся разряды регистра множителя, соединив при этом младший разряд СМ со старшим разрядом регистра множителя и объединив их в общий сдвиговый регистр.

Пример. Заданы Получить . В примерах выполняется умножение только модулей чисел. Для наглядности разряд регистра множителя, управляющий передачей множимого в сумматор, отделен сплошной вертикальной линией.

Исходное состояние сумматора — нуль.

Здесь сумматор содержит вспомогательный разряд переполнений, отделенный от остальных сплошной линией, в качестве которого можно использовать знаковый разряд сумматора.

2. Умножение младшими разрядами множителя со сдвигом множимого влево.

Представим выражение (4.5) в виде

Вычисление выражения (4.7) сводится к -кратному выполнению цикла:

где при начальных значениях

В каждом цикле умножения множимое сдвигается на один разряд влево и либо передается в СМ (при ), либо нет (при ).

Для реализации данного способа умножения требуется поразрядный сдвигающий регистр множителя, -разрядный сдвигающий регистр множимого и рядный сумматор (рис. 4.2).

Пример.

Знаковый разряд отделен сплошной вертикальной чертой. Для большей наглядности старшие разряды , значение которых 0, опущены.

3. Умножение старшими разрядами множителя со сдвигом суммы частичных произведений влево.

Если преобразовать выражение (4.5) к виду

то умножение двух чисел А и В сводится к -кратному повторению цикла

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

Таким образом, для реализации данной схемы необходимы: сдвигающий влево регистр множителя с разрядами, -разрядный регистр множимого и -разрядный сумматор со сдвигом влево (рис. 4.3).

Рис. 4.3

Рис. 4.4

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

Пример. Заданы

4. Умножение старшими разрядами множителя со сдвигом множимого вправо.

Если представить (4.5) в виде

то вычисление произведения может быть сведено к -кратному выполнению цикла:

при начальных условиях

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

С учетом этого для реализации данной схемы умножения необходим поразрядный регистр множителя со сдвигом влево, регистр множимого со сдвигом вправо и -разрядный сумматор (рис. 4.4).

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

При дополнительных разрядах погрешность произведения обусловлена двумя причинами:

1. В каждом цикле передачи множимого в СМ после будут пропадать его младшие разряды. Тогда при условии, что все младших разрядов множимого равны 1, максимальная погрешность произведения составит

2. После окончания умножения отбрасываются все младших разрядов Если все они равны 1, погрешность от этого составит

Если потребовать, чтобы было меньше то из неравенства

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

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

Пример. Заданы .

Первое частное произведение формируется как множимое, сдвинутое на один разряд вправо.