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

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

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.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]_д = b₀*2⁰+ b₁*2^-1+ b₂*2^-2+...+ b_i*2^-i+ b_i+1*2^-(i+1)+…+ b_n*2^-n

В разряде b₀*2⁰ представлен знак множителя.

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

Умножение выполняется в дополнительных кодах.

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

В каждом такте умножения анализируются два разряда множителя: b_i, b_i₊₁, и в зависимости от их содержимого формируется определенное значение частного произведения в i-том такте (см. табл.1.4).

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

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

Время умножения увеличивается на один такт сложения за счет того, что выполняется умножение и на знаковый разряд множителя. T_{у мн.д.к.}= T_{умн.п.к.} + t_сл.

Таблица 1.4

b_i	b_i+1	С_i
0	0	0
1	1	0
1	0	-А
0	1	А

Рассмотрим пример: 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.

Поясним табл. 1.5. В первом такте умножения рассматривается первая пара разрядов множителя b_nb_n₊₁ = b₃b₄ = 10, во втором такте – вторая пара – b₂b₃ = 11, в третьем такте – пара b₁b₂ = 01, в четвертом такте – пара b₀b₁ = 10. Следует также обратить внимание, что при сдвиге суммы частных произведений вправо цифра в разряде знака не изменяется (так называемый, арифметический сдвиг). В последнем такте после суммирования сдвиг вправо не выполняется (вес разряда b₀ = 2⁰).

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

Таблица 1.5

b_i ,b_i_+-1	С_i ,S_i	Пояснения
10 11	0.000000 +1.001 1.001000 1.100100 1.110010	C₀=0 C₁=[-А]_д C₀+C₁ (C₀+C₁)2^-1= S₁ C₂=0 S₁2^-1= S₂
01 10	+ 0.111 10.101010 0.010101 1.001 1.011101	C₃= [А]_пр C₃+S₂ (C₃+S₂)*2^-1= S₃ C₄= [-A]_д [C]_д=C₄+S₃

Деление двоичных чисел

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

C =A / B; |A| < 1; |B| < 1; A ≠ 0; B ≠ 0.

Используются два основных способа:

- деление чисел, представленных в прямых кодах;

- деление чисел, представленных в дополнительных кодах.

1.9.1. Операция деления в прямых кодах

Отметим следующие основные особенности алгоритма:

1) К началу деления числа должны быть представлены в прямых кодах;

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

3) Знак частного определяется логическим путем;

4) Операция сравнения модулей может выполняться с использованием любого из рассмотренных выше способов вычитания;

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

6) На каждом i-том шаге сравниваются по модулю частичная разность R_i и делитель |B_i|. При этом последовательно будут получаться цифры частного.

Если | R_i|<|B|, то C[i]=0; | R_i+1|=| R_i|.

Если | R_i|≥|B|, то C[i]=1; | R_i+1|=| R_i|-|B_i|,

где C_i — цифра частного, полученная на i-том шаге.

Предлагаемый алгоритм рассмотрим подробно на числовом примере

А=-3/16 [А]_п=1.0011; |A|=.0011

B=12/16 [В]_п= 0.1100; |B|=.1100

Операцию сравнение будем выполнять в дополнительном модифицированном коде, для этого запишем [-|B|]_д^м = 11.0100

Пример запишем в виде таблицы 1.6.

Таблица 1.6

№ такта	Сравнение \| R_i\|-\|B\|=\| R_i\|+[-\| B\|]_д	Пояснения
Такт “0”	00.0011 +11.0100 11.0111	R₀=\|A\|; B₀= [-B]_д [-\|B\|]_д \|R₀\|<\| B₀\|; С[0]=0; Деление возможно
Такт “1”	00.0011 +11.1010 11.1101	R₁=\|А₀\| [-\|B₁\|]_д =[-\|B₀\|]_д*2^-1 \|R₁\|<\| B₁\|; С[1]=0;
Такт “2”	00.0011 +11.1101 00.0000	R₂=\|А₀\| [-\|B₂\|]_д =[-\|B₁\|]_д*2^-1 \|R₂\|=\| B₂\|; С[2]=1;

Как следует из этого пример, на очередном такте сравнения сдвигается вправо на 1 разряд делитель (умножается на 2^-1). Цифры частного получаются,начиная со старшего разряда, и заносятся в регистр результата с помощью операции сдвига влево.

Поскольку после второго такта частичная разность R₃=0 , очевидно, что следующие цифры частного также будут нули.

Итак, |С|= 0.0100 = 1/4.

Знак произведения — отрицательный, окончательный ответ : С = 1.0100.

Дата добавления: 2018-05-12; просмотров: 3069; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 1 2 3 4 567 8 9 10 Следующая ⇒

Мы поможем в написании ваших работ!