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

Умножение чисел, представленных в дополнительных (обратных) кодах

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

Отметим особенности данного алгоритма:

1) Сомножители в процессе умножения должны быть представлены в прямых кодах.

2) Операция выполняется над модулями чисел.

3) Умножение начинается со старших разрядов множителя, так что в первом такте умножения находится первое частное произведение С₁ и первая сумма частных произведений S₁ = C₀ + C₁. В каждом такте множитель сдвигается влево.

4) Множимое в каждом такте сдвигается вправо, например, в первом такте оно имеет вид A₁ = A₀ · 2^-1.

5) Знак произведения определяется логическим путем.

Выполним числовой пример с целью рассмотрения указанного алгоритма

А=3/8=0.011; B=5/8=0.101;

C=А*В = 15/64 = 0.001111

A=.011 A₀=A

B= * .111

Cч сдв=0.000000 С₀= S₀=0

Cч сдв=1 + .0011 A₁= А₀*2^-1* b₁, (b₁=1)

.001100 S₁= С₀+ А₁

Cч сдв=2 .000000 A₂= А₁*2^-1* b₂, (b₂=0)

.001100 S₂= S₁+ А₂

Cч сдв=3 .000011 A₃= А₂*2^-1* b₃, (b₃=1)

.001111 S₃= S₂+ А₃

S = |C| =.001111 = 15/64.

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

S_i= S_i-1+ А_i-1*2^-1* b_i.

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

1-й способ. Перед началом операции умножения анализируются знаки чисел, принятых в АЛУ из оперативной памяти.

Для отрицательных чисел осуществляются преобразования

[A]_о — [A]_п или [A]_д — [A]_п (см. раздел 1.3).

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

2-й способ. Операнды из оперативной памяти поступают в АЛУ в дополнительном коде и без всяких промежуточных преобразований выполняется операция умножения по алгоритму для прямых кодов, а после окончания умножения выполняется, если необходимо, коррекция.

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

Итак выполняется операция

С=А*В; |A|<1; |B|<1; A≠0; B≠0.

Напомним, что операция умножения в прямых кодах производится над модулями сомножителей, ЗНС= М2(ЗНА,ЗНВ) (1.15)

1) A>0; B>0; |C|=|A|*|B| — результат правильный.

2) A<0; B>0; при использовании алгоритма умножения в прямых кодах вычислется псевдопроизведение модулей:

|С|`= [-|A|]_д*|B| = (1-|A|)*|B| = |B| - |A|*|B| = |B|-|C|;

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

C``=|C|`-|B|=C`+[-|B|]_д=|B|-|A|*|B|+(1-|B|);c

C``=1-|A|*|B|= [-|C|]_д,

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

3) A>0; B<0; Этот случай аналогичен предыдущему.

|C|` = |A| * [-|B|]_д = |A| * (1 - |B|) = |A| - |A| * |B| = |A| - |C|

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

C``=C`+[-|A|]_д= |A|-|A|*|B|+(1-|A|) = 1 - |A| * |B|

C``=[-|C|]_д,

4) A<0; B<0. В регистрах АЛУ оба числа представлены в дополнительном коде. Вычисляем псевдопроизведение, как и в случаях 2) и 3).

|C|`=[-|А|]_д*[-|B|]_д= (1-|A|)*(1-|B|);

|C|`= 1-|A|-|B| +|A|*|B| = 1-|A|-|B|+|C|. (1.16)

Так как по условию выполняются операции над числами, модуль которых меньше единицы, то ``1`` в выражении (1.16) выйдет за пределы разрядной сетки. Следовательно, это выражение примет вид

|C|`= -|A| - |B| + |C|

Выполним коррекцию. Будем находить |C|.

|C|=|C|`+|B|+|A|

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

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

T_умн2 = T_{умн.п.к.} + t_сл

Дата добавления: 2015-05-09