 |
1.8.1. Умножение от младших разрядов множителя со сдвигом суммы частных произведений вправо
|
|
|
|
1. 8. 1. Умножение от младших разрядов множителя со сдвигом суммы частных произведений вправо
Отметим основные особенности алгоритма:
1) К началу умножения числа в регистрах АЛУ должны быть представлены в прямых кодах.
2) Операция умножения выполняется над модулями чисел.
3) Умножение начинается от младших разрядов множителя, т. е. в первом такте вычисляется Cn = | А |*bn и далее сдвиг вправо.
4) В каждом такте после определния очередой суммы частных произведений она сдвигается на один разряд вправо.
5) Знак произведения находится логическим способом.
Рассмотрим числовой пример, и на этой основе разработаем машинный алгоритм
А=3/8; B=5/8; Найти С=A * B; C=15 / 64;
Запишем в двоичном коде: [A]п = 0. 011; [B]п = 0. 101; [C]п = 0. 001111
Все алгоритмы умножения являются циклическими, поэтому
В машинных алгоритмах для подсчета числа циклов вводиться счет-
Чик сдвигов. Перед началом умножения в счетчик заносится нуль.
A=. 011
B=. 101
. 000000 С0=0
Cч сдв=0 + . 011 А* b3
. 011000 С0 + A * b3= С0 + С1
Cч сдв=1 . 001100 (С0+ С1)*2-1= S1
+. 000 А* b2
. 001100 S1 +А* b2
Cч сдв=2 . 000110 (S1 +А* b2)*2-1=S2
+. 011 А* b1
. 011110 ((С0+ А* b3)*2-1 +А* b2))*2-1 +А* b1
Cч сдв=3 . 001111 (((С0+ А* b3)*2-1 +А* b2))*2-1 +А* b1)*2-1 =S3
В нашем примере n=3, поэтому умножение закончено и в последней строке примера находится искомое произведение
S3 = |C| =. 001111 = 15/64.
В результате произведенного анализа можно записать следующее рекурентное соотношение, в соответствии с которым выполняются действия в каждом такте умножения при вычислении очередной частичной суммы
Si=(Si-1+ А* bn-i+1)*2-1
|
|
|
При использовании этого алгоритма, возможно получение произведения с двойной точностью. Если достаточно получить произведение с одинарной точностью, то после окончания всех тактов умножения необходимо выполнить округление. При этом число разрядов в сумматоре регистра результата должно равняться (n+1).
Время умножения в прямых кодах в общем случае определяется следующим выражением:
Тумн. пк=n*( tсдв+ tсл), где t сдв – время выполнения операции сдвиг,
t сл - время выполнения операции сложение.
tсдв — длительность сдвига, где
tсл — длительность операции сложения.
1. 8. 2. Умножение со старших разрядов множителя со сдвигом множимого вправо
Отметим особенности данного алгоритма:
1) Сомножители в процессе умножения должны быть представлены в прямых кодах.
2) Операция выполняется над модулями чисел.
3) Умножение начинается со старших разрядов множителя, так что в первом такте умножения находится первое частное произведение С1 и первая сумма частных произведений S1 = C0 + C1. В каждом такте множитель сдвигается влево.
4) Множимое в каждом такте сдвигается вправо, например, в первом такте оно имеет вид A1 = A0 · 2-1.
5) Знак произведения определяется логическим путем.
Выполним числовой пример с целью рассмотрения указанного алгоритма
А=3/8=0. 011; B=5/8=0. 101;
C=А*В = 15/64 = 0. 001111
A=. 011 A0=A
B= * . 111
Cч сдв=0 . 000000 С0= S0=0
Cч сдв=1 +. 0011 A1= А0*2-1* b1, (b1=1)
. 001100 S1= С0+ А1
Cч сдв=2 . 000000 A2= А1*2-1* b2, (b2=0)
. 001100 S2= S1+ А2
Cч сдв=3 . 000011 A3= А2*2-1* b3, (b3=1)
. 001111 S3= S2+ А3
S = |C| =. 001111 = 15/64.
Запишем рекуррентную формулу для нахождения суммы частных произведений на каждом шаге умножения
Si= Si-1+ Аi-1*2-1* bi.
|
|
|
1. 8. 3. Умножение чисел, представленных в дополнительных ( обратных ) кодах
В тех случаях, когда числа в оперативной памяти хранятся в дополнительном или обратном кодах, возможны несколько способов реализации операции умножения.
1. 8. 3. 1. Использование алгоритмов умножения в прямых кодах
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сл
1. 8. 3. 2. Алгоритм умножения непосредственно в дополнительных кодах.
Числа из памяти принимаются в АЛУ в дополнительных кодах и непосредственно в этих же кодах вычисляются псевдопроизведение
С`=[А]д*[В]д;
[B]д = b0*20+ b1*2-1+ b2*2-2+... + bi*2-i + bi+1*2-(i+1) +…+ bn*2-n
В разряде b0*20 представлен знак множителя.
Особенности алгоритма:
Умножение выполняется в дополнительных кодах.
Знаки чисел участвуют в процессе умножения, и знак результата получается автоматически после окончания вычислений.
В каждом такте умножения анализируются два разряда множителя: bi, bi+1, и в зависимости от их содержимого формируется определенное значение частного произведения в i-том такте (см. табл. 1. 4).
Процесс умножения выполняется аналогично рассмотренному выше алгоритму умножения в прямых кодах от младших разрядов множителя со сдвигом суммы частных произведений вправо.
Произведение получается в дополнительном коде и записывается в память без всяких преобразований.
Время умножения увеличивается на один такт сложения за счет того, что выполняется умножение и на знаковый разряд множителя. Tу мн. д. к. = Tумн. п. к. + tсл.
|
|
|
Таблица 1. 4
| bi | bi+1 | Сi |
| -А | ||
| А |
.
Рассмотрим пример: C=A*B; А=7/8 = 0. 111; B=-5/8 = -0. 101;
[А]п=0. 111; [В]д =1. 0110; C=-35/64 [C]п = 1. 100011
[-А]д =1. 001 [C]д = 1. 011101
Вычисления представим в табл. 1. 5.
|
|
|
