Dodawanie i odejmowanie
Dodawanie i odejmowanie w systemach naturalnych
X = {xk -1,..., x1, x0,..., x-m}� , Y = {yk -1,..., y1, y0,..., y-m}�
Ó! Ó!
xi ą yi ą ci = si ą �ci+1
Ó! c-m = 0
S = {sk -1,...,s1,s0,...,s-m}�
xi, yi,si "{0,1,..., � -1}�!(ci "{0,1}�!ci+1 "{0,1})
x1 m y1 m x m y m
xk-1 yk-1 xk-2 yk-2
ck c2 m c1 m
ck-1 ck-2
c m
Ł Ł Ł Ł
s1 m s m
sk-1 sk-2
Schemat dodawania/odejmowania wielopozycyjnego
� Janusz Biernat, Dodawanie i odejmowanie, 14 paz
dziernika 2003 ADS 1
Dodawanie i odejmowanie
Poprawność dodawania i odejmowania w systemach naturalnych
X = X = {xk -1,..., x1, x0,..., x-m}� , Y = Y = {yk -1,..., y1, y0,..., y-m}�
Ó! xi ą yi ą ci = si ą �ci+1 Ó!
X ą Y =| X ą Y = {sk -1,..., s1, s0,..., s-m}� |
!! xi, yi,si "{0,1,..., � -1}�!(ci "{0,1}�!ci+1 "{0,1})
Wynikiem dodawania lub odejmowania pozycyjnego (przy c-m = 0) jest
k -1 k -1
i i
X ąY = ą yi )� = ą (�ci+1 - ci )]� ,
"(x "[s
i i
i=-m i=-m
k -1 k -1 k -1
i i+1 i i k k
X ą Y = � ą
"s "(c � - ci � ) = "s � ą ck � = S ą ck �
i i+1 i
i=-m i=-m i=-m
poprawność dodawania
k k k k
0 d" S < � �!(ck = 1�!(S + ck � > � ) '" (S - ck � < 0)
(ck = 1)  nadmiar (wynik przekracza zakres)
� Janusz Biernat, Dodawanie i odejmowanie, 14 paz
dziernika 2003 ADS 2
 Dodawanie i odejmowanie
Dodawanie i odejmowanie w systemach uzupełnieniowych
k -1
i
{xk -1,..., x-m+1, x-m} = -�(xk -1)R + xi �
"
i=-m
k -m
1
gdzie �(xk -1) = (1+ sgn(2xk -1- � +1)), R = � -�� (�=1 lub 0)
2
X = {xk -1,..., x1, x0,..., x-m}U, Y = {yk -1,..., y1, y0,..., y-m}U
Ó! Ó!
xi ą yi ą ci = si ą �ci+1
Ó! c-m = 0
S = {sk -1,...,s1,s0,...,s-m}U = X ą Y �! S = X ą Y
Wynik działania powinien dać się zapisać w postaci
X ą Y = S +V
k -1
i
gdzie |S| = {sk -1,...,s1,s0,...,s-m}U = -�(sk -1)R + � , V  nadmiar
"s
i
i=-m
� Janusz Biernat, Dodawanie i odejmowanie, 14 paz
dziernika 2003 ADS 3
Dodawanie i odejmowanie
Poprawność dodawania i odejmowania w systemach uzupełnieniowych
Skutkiem wykonania działań zgodnie z regułą dodawania / odejmowania jest
k -1
i
|X| ą |Y| = -[�(xk -1) ą �(yk -1)]R + ą yi )� =
"(x
i
i=-m
k -1
i
= -[�(xk -1 ) ą�(yk -1)]R + ą (�ci+1 - ci )]� ,
"[s
i
i=-m
skąd przy c-m = 0 otrzymamy
k -1
i k
|X| ą |Y| = -[�(xk -1) ą �(yk -1)]R + � ą ck �
"s
i
i=-m
Z porównania wzorów wynika
k
|X| ą |Y| =|S| +[(�(sk -1) ą ck ) - (�(xk -1) ą �( yk -1))]R ą ck (� - R)
v = (�(sk -1) ą ck ) - (�(xk -1) ą�(yk -1))  wskaz
nik nadmiaru
k -m
ck (� - R) = �ck�  korekcja wyniku (przeniesienie okrę\
ne)
" w systemie pełnym zbędna, bo �=0,
" w systemie niepełnym  ck na najni\
szej pozycji (�=1)
� Janusz Biernat, Dodawanie i odejmowanie, 14 paz
dziernika 2003 ADS 4
 Dodawanie i odejmowanie
Nadmiar w dodawaniu w systemach uzupełnieniowych
v = [�(sk -1) + ck ]-[�(xk -1) +�(yk -1)]
1
 znaki operandów dodatnie 0 d" xk -1, yk -1 d" � -1 (�(xk -1) +�(yk -1) = 0):
2
1
" albo 0 d" xk -1 + yk -1 + ck -1 d" � -1 �! ck = 0, �(sk -1) = 0, �! v=0
2
1
" albo � d" xk -1 + yk -1 + ck -1 d" � -1 �! ck = 0, �(sk -1) = 1 �! v=1
2
1
 znaki operandów ujemne � d" xk -1, yk -1 d" � -1 (�(xk -1) +�(yk -1) = 2):
2
1
" � + � d" xk -1 + yk -1 + ck -1 d" � + � -1 �! ck = 1, �(sk -1) = 1 �! v=0
2
1
" � d" xk -1 + yk -1 + ck -1 d" � + � -1 �! ck = 1, �(sk -1) = 0 �! v=-1
2
 znaki operandów ró\
ne (�(xk -1) +�(yk -1) = 1):
" albo � d" xk -1 + yk -1 + ck -1 d" � + (1 � -1) �! ck = 1, �(sk -1) = 0 �! v=0
2
1
" albo � d" xk -1 + yk -1 + ck -1 d" � -1 �! ck = 0, �(sk -1) = 1 �! v=0
2
� Janusz Biernat, Dodawanie i odejmowanie, 14 paz
dziernika 2003 ADS 5
Dodawanie i odejmowanie
Nadmiar w odejmowaniu w systemach uzupełnieniowych
v = [�(sk -1) - ck ]-[�(xk -1) -�(yk -1)]
 znaki operandów są identyczne (�(xk -1) - �(yk -1) = 0),
" �(sk -1) = ck �! v=0
 znaki operandów są ró\
ne, a odjemna jest ujemna (�(xk -1) -�(yk -1) = 1),
" ck = 0, �(sk -1) = 1 �! v=0
" ck = 0, �(sk -1) = 0 �! v=-1
 znaki operandów są ró\
ne, a odjemna jest dodatnia (�(xk -1) - �(yk -1) = -1),
" ck = 1, �(sk -1) = 0 �! v=0
" ck =1, �(sk -1) = 1 �! v=1
� Janusz Biernat, Dodawanie i odejmowanie, 14 paz
dziernika 2003 ADS 6
 Dodawanie i odejmowanie
Inkrementacja i dekrementacja w systemach naturalnych
X = {xk -1,..., x1, x0}�
Ó! Ó!
xi ą ci = si ą �ci+1
Ó! c0 = ą1
X ą 1 = {sk -1,..., s1, s0}�
xi , si "{0,1,..., � -1}�!(ci "{0,1}�!ci+1 "{0,1})
x1 x0
xk-1 xk-2
ck c2 c1
ck-1 ck-2
c0
ą ą ą ą
s1 s0
sk-1 sk-2
Schemat inkrementacji/dekrementacji
� Janusz Biernat, Dodawanie i odejmowanie, 14 paz
dziernika 2003 ADS 7
Dodawanie i odejmowanie
Zmiana znaku liczby w systemie uzupełnieniowym
W systemie pełnym
-m -m k -1 k -2 -m -m
-Y = (-� - Y ) + � = [-� + (� + ...�1 + � )(� -1) - Y ] + �
k -2 k -2
k -1 i k -1 i -m
-Y = -� + -1)� - (- yk -1� + yi� ) + �
"(� "
i=-m i=-m
k -2
k -1 i -m
- Y = - yk -1� + yi � + � = Y + ulp
"
i=-m
W ka\
dym systemie uzupełnieniowym 0 - Y = Y + (R - Q) , czyli
k -1 k -1
�ł-�( łł
i i k -m
- yk -1)R + yi � = �( yk -1)R +
" "[(� -1) - yi ]� - (� - � )
�ł śł
�ł i=-m �ł i=-m
k -m
gdzie R = � - �� oraz �=0 w systemie pełnym, 1  w niepełnym,
a poniewa\
�( yk -1) = 1-�( yk -1)
k -1
i -m
-Y = -�( yk -1)R + yi � + (1-� )�
"
i=-m
� Janusz Biernat, Dodawanie i odejmowanie, 14 paz
dziernika 2003 ADS 8
 Dodawanie i odejmowanie
Odejmowanie przez dodawanie
W systemie uzupełnieniowym
X - Y = X + Y
" schemat uniwersalny, ale bardziej czasochłonny (dwukrotne dopełnianie)
albo, poniewa\
0 - Y = Y + (R - Q),
~
X - Y = X + Y + Q == X + Y + � ulp
" dodawanie ulp  na najni\
szej pozycji (zamiast przeniesienia c m=0)
Odejmowanie liczb naturalnych przez dodanie uzupełnienia
{xk -1,..., x-m+1, x-m}� = {0, xk -1,..., x-m+1, x-m}U�
-m
- {yk -1,..., y-m+1, y-m}� = {� -1, yk -1,..., y-m+1, y-m}U� +��
Skoro yk = � -1, xk=0 i musi być sk=0, więc jeśli wynik jest poprawny, to
v = [�(sk ) + ck +1] -[�(xk ) +�( yk )] = ck +1 -1 �! ck+1=1 �! ck=1
� Janusz Biernat, Dodawanie i odejmowanie, 14 paz
dziernika 2003 ADS 9
Dodawanie i odejmowanie
Uniwersalny schemat dodawania i odejmowania
x1 m y1 m x m y m
xk-1 yk-1 xk-2 yk-2
M
( ) ( ) ( ) ( )
yMk-1 yMk-2 yM1-m yM-m
v
c2 m c1 m
ck-1 ck-2 � = 0
Ł Ł Ł Ł
� = 1
ck s1 m s m
sk-1 sk-2
Schemat dodawania i odejmowania w systemach uzupełnieniowych
M M
v = [�(sk -1) + ck ] -[�(xk -1) + �( yk -1)], yk -1 = (1- M ) yk -1 + M yk -1
Liczby naturalne:
" dodawanie  wynik poprawny gdy ck=0
" odejmowanie  wynik poprawny gdy ck=1
� Janusz Biernat, Dodawanie i odejmowanie, 14 paz
dziernika 2003 ADS 10
 Dodawanie i odejmowanie
Dodawanie i odejmowanie w naturalnym systemie dwójkowym
xi ą yi ą ci = ą2ci+1 + si
sumator pełny (full adder, FA)  realizuje funkcje
" sumy arytmetycznej si operandów dwójkowych xi , yi , ci na pozycji i-tej
" przeniesienia ci+1 na wy\
szą pozycję
si = xi �" yi �" ci,
ci+1 = xi yi + (xi �" yi)ci = xi yi + (xi + yi)ci
subtraktor pełny (full subtracter, FS)  realizuje funkcje
" ró\
nicy arytmetycznej si operandów dwójkowych xi , yi , ci na pozycji i-tej
" po\
yczki ci+1 z wy\
szej pozycji
si = xi �" yi �" ci,
ci+1 = xi yi + (xi �" yi) ci = xi yi + (xi �" yi) ci
półsumator (half adder, HA)  realizuje funkcje si = xi �" ci, ci+1 = xici
półsubtraktor (half subtracter, HS)  realizuje funkcje si = xi �" ci, ci+1 = xici
� Janusz Biernat, Dodawanie i odejmowanie, 14 paz
dziernika 2003 ADS 11
Dodawanie i odejmowanie
Dodawanie i odejmowanie w dwójkowych systemach uzupełnieniowych
�=2 �! �(xk -1) = xk -1 �! v = (sk -1 ą ck ) - (xk -1 ą yk -1 ) = ą(ck -1 - ck )
Mamy zatem ( R = 2k -� 2-m, �=0 w systemie U2 lub 1 w systemie U1)
k -1
S = -sk -1R + 2i ą (ck -1 - ck )R ą � ck 2-m
"s
i
i=-m
Poprawny wynik mo\
e być zawsze odtworzony w rozszerzeniu 1-pozycyjnym
" w dodawaniu (liczb o jednakowych znakach)
v=1 �! sk -1 = ck -1 �! Se = {ck , sk -1,..., s-m+1, s-m }
" w odejmowaniu (liczb o ró\
nych znakach),
v=1 �! sk -1 `" ck -1 �! Se = {ck -1, sk -1,..., s-m+1, s-m }
W systemie uzupełnieniowym do 2 (U2)
k -2
S = -sk -1 2k -1 + si 2i ą (ck -1 - ck )2k
"
i=-m
� Janusz Biernat, Dodawanie i odejmowanie, 14 paz
dziernika 2003 ADS 12
 Dodawanie i odejmowanie
Zmiana znaku liczby w kodzie uzupełnieniowym
- X = 0 - X = -2-m + 2-m - X
- X = (-2-m - X ) + 2-m = [-2k -1 + (2k -2 +...2-m+1 + 2-m ) - X ]+ 2-m
k -2 k -2
i
- X = [(-2k -1 + ) - (-xk -12k -1 + xi 2i )] + 2-m
"2 "
i=-m i=-m
k -2
- X = [-(1- xk -1)2k -1 +
"(1- xi )2i ] + 2-m = X + 2-m
i=-m
algorytmy mnemotechniczne: ( 1 =ulp=2 m  jednostka na najni\
szej pozycji)
" zaneguj wszystkie bity oryginału i do uzyskanego kodu dodaj pozycyjnie  1
" zaneguj wszystkie bity oryginału,
z wyjątkiem prawostronnego ciągu zer i poprzedzającej go  1
(propagacja dodawanej  1 kończy się na pozycji najni\
szej  1 oryginału)
� Janusz Biernat, Dodawanie i odejmowanie, 14 paz
dziernika 2003 ADS 13
Dodawanie i odejmowanie
Dodawanie i odejmowanie liczb naturalnych jako rozszerzeń w kodzie U2
{xk -1,..., x-m+1, x-m}NB = {0, xk -1,..., x-m+1, x-m}U2
(sk = ck), ponadto w dodawaniu (ck+1 = 0), w odejmowaniu (ck+1 = ck)
k -1 k -1
S = -(0 ą 0)2k + ą yi )2i = 2i ą ck 2k
"(x "s
i i
i=-m i=-m
Odejmowanie liczb naturalnych przez dodanie uzupełnienia
- {xm-1,..., x-m+1, x-m}NB = {1,(1- xk -1),...,(1- x-m+1),(1- x-m )}U2 + 2-m
xi + (1- yi ) + ci =2ci+1 + si
k -1 k -1
S = -(0 +1)2k + + (1- yi ))2i + 2-m = 2i - (1- ck )2k
"(x "s
i i
i=-m i=-m
� Janusz Biernat, Dodawanie i odejmowanie, 14 paz
dziernika 2003 ADS 14