Метод пропуска такта суммирования

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

Если принять, что в двоичном коде множителя в любом разряде с равной вероятностью может находиться как цифра 0, так и 1, то среднее количество тактов суммирования при перемножении двух разрядных чисел сокращается вдвое, то есть становится равным . Иначе говоря, на один разряд множителя приходится 0,5 операции сложения. Учитывая это, получаем, что при использовании метода пропуска такта суммирования в схемах умножения, где такты суммирования и сдвига не могут быть совмещены по времени, среднее время выполнения операции умножения

,

 

то есть применение данного метода приводит к сокращению среднего времени умножения в следующем отношении:

,

 

где и - соответственно длительности циклов суммирования и сдвига.

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

 

,

 

где - время суммирования для разрядов множителя, содержащих цифру 1;

- время выполнения сдвигов для разрядов множителя, содержащих цифру 0.

Следовательно, в данном случае среднее время выполнения операции умножения сокращается в следующем отношении:

.

 

При имеет место а , то есть сокращение среднего времени умножения составляет соответственно 33 % и 25 %. При имеет место а , то есть соответствующее сокращение среднего времени умножения равно 40 % и 37,5 %.

 

Метод анализа сомножителей

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

 

Метод расшифровки и одновременного умножения

На два разряда множителя

 

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

При разбиении множителя, начиная с младших его разрядов, на группы по два разряда в каждой возможны следующие равновероятные комбинации: 00; 01; 10; 11, которые можно выразить следующим образом: 00=0; 01=2⁰; 10=2¹; 11=2² -2⁰.

В зависимости от результатов анализа пары разрядов множителя необходимо выполнить следующие операции.

При комбинации 00 произвести сдвиг на два разряда вправо предшествующей суммы частичных произведений.

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

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

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

В самом деле, комбинация 11 = 2¹ + 2⁰ может быть представлена следующим образом: 11 = 2² -2⁰ = 100 – 01. При таком представлении следует, что отрицательный член правой части рассматриваемого равенства должен учитываться путем вычитания множимого из накопленной суммы частичных произведений, а член 100 представляет собой единицу младшего разряда следующей анализируемой пары разрядов множителя и должен учитываться при ее расшифровке. Для этого данная единица должна запоминаться в схеме анализа. При обработке следующей пары разрядов множителя эта запомненная единица учитывается путем прибавления к младшему разряду этой пары по обычным правилам:

 

00 + 01 = 01

01 + 01 = 10

10 + 01 = 11

11 + 01 = 00 + 100

 

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

Для пояснения описанного метода рассмотрим пример выполнения операции умножения при анализе одновременно двух разрядов множителя.

Пусть множимое , а множитель .

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

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

Пример.

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

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

.

 

Дадим оценку времени выполнения операции умножения рассмотренным выше методом.

Поскольку при комбинации разрядов множителя, равной 00, сложения не производится, то на каждую пару разрядов множителя приходится ¾ операции сложения и, следовательно, на один разряд – 3/8 сложения. Отсюда вытекает, что при организации сдвигов на один разряд за такт время выполнения операции умножения определяется выражением

,

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

 

 

 

Анализ разрядов множителя	Операции в сумматоре	Пояснение
		Доп.pаз.	3H1; 3H2	Модуль суммы частичных произведений	Доп. pаз.
			0 0	0 0 0 0 0 0 0 0		[CM]=0
			0 0	1 1 1 1 0 1 0 1
			0 0	1 1 1 1 0 1 0 1		[CM]+
			0 0	0 0 1 1 1 1 0 1
			1 1	0 0 0 0 1 0 1 0
			1 1	0 1 0 0 0 1 1 1		[CM]
			1 1	1 1 0 1 0 0 0 1
			0 0	1 1 1 1 0 1 0 1
			0 0	1 1 0 0 0 1 1 0	1
			0 0	1 1 0 0 0 1 1 1	0	[CM]
			0 0	0 0 1 1 0 0 0 1
			0 1	1 1 1 0 1 0 1 0
			1 0	0 0 0 1 1 0 1 1		[CM]
			0 0	1 0 0 0 0 1 1 0		Округление
			0 0	1 0 0 0 0 1 1 1		[CM]=

 

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

 

.

 

Очевидно, что в первом случае имеет место сокращение среднего времени умножения в отношении

 

,

 

а во втором случае

 

.

 

При имеем а то есть сокращение времени выполнения операции умножения в первом случае составляет 41,67 %, а во втором случае 58,34 %. При имеем а и соответственно сокращение времени выполнения операции умножения на 50 % и 60 %.

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

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