Теория автоматов. Часть 3. Арифметика ЭВМ (стр. 11 )

+	(СМ)=00 10001 1
1
	(СМ)=00 10010 0

и определяется знак произведения

Произведение равно 0,10010.

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

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

Представим формулу (4.1) в виде:

С=2-n(A·b-n+2·A·b-(n-1)+…+2j·A·b-(n-j)+…+2n-1·A·b-1) (4.3)

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

Aj+1=2·Aj

Cj+1=2·(Cj+Ab-j)

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

j=0,

C=0,

A=A

В каждом цикле умножения множимое А умножается на 2, т. е. сдвигается влево на один разряд и либо передается в сумматор, если b-(n-j)=1, либо не передается, если b-(n-j)=0.

После завершения n циклов в сумматоре образуется код

C=2n·C=2n·A·B

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

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

Представим формулу (4.1) в виде:

С=2-n((…(0+A·b-1)·2+A·b-2)·2+…+A·b-j)·2+…+A·b-(n-1))·2+A·b-n (4.4)

Вычисление 2-n·С сводится к n - кратному выполнению цикла

Cj+1=2(Cj+A·b-j)

c начальными значениями

j=0, C0=0.

В каждом (т. е. в j - ом) цикле множимое А. передается в сумматор, если

b-j=1

либо не передается, если

b-j=0

и сумма сдвигается на один разряд влево.

Реализация умножения указанным методом требует сдвига влево в регистре множителя и в сумматоре и удлинения сумматора на n разрядов со стороны старших разрядов.

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

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

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

Представим формулу (4.1) в виде

С=A·2-1·b-1+A·2-2·b-2+…+A·2-j·b-j+…+A·2-(n-2)·b-(n-1)+A·2-n·b-n (4.5)

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

Aj+1=Aj·2-j

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

j=0, A0=A, C0=0.

После окончания n-го цикла в сумматоре образуется

Cn=C=A·B

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

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

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

1. В каждом цикле передачи множимого в сумматор после К.-го пропадают его младшие разряды (в первых циклах множимое заполняет дополнительные разряды). Если считать, что погрешность при каждой передаче равна единице младшего разряда, т. е. 2-(n+k) (эта оценка погрешности является преувеличенной), то предельное значение погрешности равно

δ1max=(n-k)·2-(n+k)

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

δ2max=2-n(1-2-k)≈2-n

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

Например, количество дополнительных разрядов, при котором погрешность δ1max меньше, чем единица младшего разряда 2-n может быть определено путем решения трансцендентного неравенства

(n-k)·2-(n+k)<2-n

легко преобразуемого к виду

k>log2(n-k)

Обе составляющие ошибки произведения имеют отрицательный знак. Округление первой составляющей ошибки следовало бы выполнять путем дополнения сумматора дополнительными (n+k+1) разрядами и добавления к нему единицы после каждой передачи множимого в сумматор. Округление второй составляющей ошибки следовало бы выполнять путем добавления единицы к (n+1)-му разряду сумматора после окончания всех циклов передачи множимого в сумматор.

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

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

1. Возможность использования общих цепей сдвига для умножения и деления.

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

3. Исключение промежуточных пересылок в случае, когда произведение А·B и нужно прибавить к числу, ранее вычисленному на сумматоре. В этом случае умножение выполняется, как и обычно, по циклическим формулам (4.5) с тем лишь отличием, что сумматор перед началом умножения не сбрасывается на 0, т. е. начальное значение С0 отлично от нуля. Это удобно, например, использовать при вычислении сумм парных произведений: промежуточные суммы сохраняются на сумматоре и к ним прибавляются новые произведения.

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

Множимое А = 0 10111 вводится в регистр P1. Множитель В = 0 11001 вводится в регистр Р2. Сумматор устанавливается в нулевое положение.

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

	+	(СМ)=00 00000 00	(Р2)=0 11001
Сдвиг	(Р1)=00 01011 10	(Р2)=1 10010	цикл 1
Сложение	+	(СМ)=00 01011 10
Сдвиг	(Р1)=00 00101 11	(Р2)=1 00100	цикл 2
Сложение		(СМ)=00 10001 01
Сдвиг		(Р1)=00 00010 11	(Р2)=0 01000	цикл 3
Сложения нет		(СМ)=00 10001 01
Сдвиг		(Р1)=00 00001 01	(Р2)=0 10000	цикл 4
Сложения нет		(СМ)=00 10001 01
Сдвиг		(Р1)=00 00000 10	(Р2)=1 00000	цикл 5
Сложение		(СМ)=00 10001 11

Далее выполняется округление произведения путем добавления 1 к старшему из дополнительных разрядов сумматора

+	(СМ)=00 10001 11
1
	(СМ)=00 10010 01

и определяется знак произведения.