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

1.

Умножение чисел, представленных в
дополнительном коде
Утверждение. Если [Y]д=y0,y−1y−2y−3 ...y−n, то само число
Y = −y0+ 0,y−1 y−2 ...y−n
(1)
Доказательство. Начнём доказательство с правой части.
• Если y0=0, то Y = 0,y−1 y−2 … y−n > 0 ,поэтому [Y]д= Y = 0,y−1 y−2 ...y−n =
=y0,y−1 y−2 ...y−n
• Если y0=1, то Y =−1 + 0,y−1 y−2 ...y−n < 0, [Y]д= C + Y = 2 + Y = 2 − 1 +
+ 0,y−1 y−2 … y−n =1,y−1 y−2 ...y−n= y0,y−1 y−2 ...y−n , что и требовалось доказать.
Следует напомнить, что С – вес воображаемого разряда,
расположенного левее знакового. Для чисел с фиксированной запятой
С=2.

2.

Умножение чисел в дополнительном коде с
корректирующим шагом
На основании доказанного утверждения получаем следующий
алгоритм умножения чисел в дополнительном коде.
[X]д · [Y]д= [X]д · (−y0+0,y−1y−2…y−n)= [X]д · (−y0· 20 + y−1· 2−1 + y−2· 2−2 +
… y−n· 2−n)
(2)
В соответствии с (2), необходимо выполнить умножение
множимого на все разряды множителя, причём результат
умножения на знаковый разряд множителя взять с отрицательным
знаком. Этот шаг называется корректирующим шагом или
поправкой, а рассмотренный алгоритм называется алгоритмом
умножения в дополнительном коде с корректирующим шагом.

3.

Пример 1.
X =0,1001 [X]п=0,1001 [X]о=0,1001 [X]д=0,1001
Y =−0,1101 [Y]п=1,1101 [Y]о=1,0010 [Y]д= 1,0011
y0=1
y-1=0
y-2=0
y-3=1
y-4=1
0,0000
1,0111
1,0111
+
0,1001
0
1,0111
+
0,001001
1,0111
+
0,001001
0
+
+
1,1000001
0
0,0001001
S0
-[Х]д корректирующий шаг
S1
[Х]д · 2-1
S2=S1
[Х]д · 2-2
S3=S2
[Х]д · 2-3
S4
[Х]д · 2-4
[Z]д = 1,10001011
[Z]п= 1,01110101 = -(64+32+16+4+1)/256 = -117/256

4.

Пример 2.
X =−0,1001 [X]п=1,1001 [X]о=1,0110 [X]д=1,0111
Y = 0,1101 [Y]п=0,1101 [Y]о=0,1101 [Y]д= 0,1101
y0=0
y-1=1
y-2=1
y-3=0
y-4=1
0,0000
0,1001
0,0000
+
1, 10111
+ 1,10111
1, 10111
1
1,100101
+
1, 110111
1
+ 1,100101
1,1110111
1
[Z]д = 1,10001011
+
S0
-[Х]д корректирующий шаг
S1=S0
[Х]д · 2-1
S2
[Х]д · 2-2
S3
[Х]д · 2-3
S4=S3
[Х]д · 2-4
Получили такой же результат, что свидетельствует о правильности решения примера.

5.

Умножение чисел в дополнительном коде на
основе анализа смежных разрядов множителя
Рассмотрим ещё один алгоритм, который основывается на доказанном выше
утверждении. [X]д ·[Y]д=[X]д ·(−y0 · 20 + y−1· 2−1 + y−2· 2−2 + … + y−n·2−n)= −[X]д ·
20·y0+[X]д·y−1·(20−2−1) +[X]д·y−2·(2−1−2−2)+⋯+[X]д·y−n·(2−n+1−2−n)=[X]д · 20·(y−1−y0)+ [X]д ·
2−1·(y−2−y−1)+[X]д · 2−2 ·(y−3−y−2)+...+[X]д · 2−n+1·(y−n−y−n+1)+[X]д · 2−n·(y−n−1−y−n)
(3)
В соответствии с (3) выполняется анализ двух смежных разрядов множителя
y−iy−i−1.
• Если это 00 или 11, то сдвинутое множимое [X]д · 2−i не прибавляется к сумме
частичных произведений.
• Если 01, то сдвинутое множимое [X]д · 2−i прибавляется к сумме частичных
произведений.
• Если 10, то сдвинутое множимое [X]д · 2−i вычитается из суммы частичных
произведений.

6.

Пример 3.
X=−0,1001 [X]п=1,1001
Y=−0,1101 [Y]п=1,1101
0,0000
+
10
0,1001
0,1001
+
00
1,0111
1
01
[X]д=1,0111 −[X]д =0,1001
[Y]д= 1,00110
S0
−[X]д ⋅ 20
S1
[X]д ⋅ 2−1
0,1001
1,10111
1
S2 = S1
+[X]д ⋅ 2−2
+ 0,011011
S3
[X]д ⋅ 2−3
+
1,110111
1
+ 0,011011
10
0
0,0001001
11
[X]о=1,0110
[Y]о=1,0010
S4 = S3
−[X]д ⋅ 2−4
[Z]д = 0,01110101
Получили результат, который согласуется с предыдущими двумя примерами.

7.

Пример 4.
X=0,1001
Y=0,1101
[X]п=0,1001
[Y]п=0,1101
01
11
10
01
10
[X]д=0,1001
[Y]д= 0,11010
-[X]д=1,0111
+
0,0000
0,1001
S0
+[X]д ⋅ 20
+
0,1001
0,1001
0
S1
[X]д ⋅ 2−1
+
0,1001
1,110111
S2 = S1
- [X]д ⋅ 2−2
+
0,011011
0,001001
0
S3
+[X]д ⋅ 2−3
+
0,0111111
1,1110111
1
S4
−[X]д ⋅ 2−4
[Z]д = 0,01110101
Получили результат, который согласуется с предыдущими тремя примерами.

8.

Как видно из рассмотренных примеров, умножение выполняется
за n + 1 шаг. В отличие от предыдущего способа знаковый разряд
множителя обрабатывается вместе с цифровыми разрядами по
общим правилам.

9.

Умножение чисел, представленных в
обратном коде
Будем использовать подход, рассмотренный выше при обосновании способа
умножения чисел в дополнительном коде. Выразим число, которое
представлено в обратном коде через его обратный код. Докажем
утверждение.
Утверждение: Если [Y]о=y0,y−1y−2...y−n , то Y=0,y−1y−2...y−n+y0(−1+2−n)
(4)
Доказательство: Доказательство проведём также, как и в случае
дополнительного кода. Начнём с правой части.
• Если y0= 0, то Y=0,y−1y−2...y−n >0, [Y]о= Y=0,y−1y−2...y−n=y0,y−1y−2...y−n.
• Если y0 = 1, то Y=0,y−1y−2...y−n−1+2−n<0, [Y]о=B+Y=2−2−n +
• +0, y−1y−2...y−n−1+2−n=1,y−1y−2...y−n=y0,y−1y−2...y−n
Следует напомнить, что В - максимальное число без знака, которое может
быть размещено в разрядной сетке цифрового автомата. В нашем случае для
формата чисел с фиксированной запятой В=2-2-n.

10.

Умножение чисел в обратном коде с
корректирующими шагами
В соответствии с (4) получаем следующий алгоритм умножения
чисел в обратном коде.
Необходимо умножить множимое на цифровые разряды
множителя. Если знаковый разряд множителя равен 1, то требуется
поправка (коррекция), которая заключается в прибавлении
множимого со знаком «-» и в прибавлении [X]o·2−n.
[X]o·[Y]o = [X]o·(0,y−1y−2...y−n) − [X]o+[X]o·2−n
Поправка выделена красным цветом.

11.

Пример 5
X = 0,1001 [X]п = 0,1001 [X]о = 0,1001
Y = 0,0010 [Y]п = 0,0010 [Y]о = 0,0010
[Z]о = [X]о ⋅ [Y]о = ?
0,0000
+
y0 = 0
0,0000
0,0000
y−1 = 0
+
y−2 = 0
+
y−3 = 1
y−4 = 0
+
+
0,1001
0
0,0000
0,01001
0
0,0000
0,001001
0
0,0001001
0,0001001
0
0,00010010
[Z]о = 0,00010010
[Z]n = 0,00010010
Z = 18 / 256