Dodawanie i odejmowanie
Dodawanie i odejmowanie w systemach naturalnych (1)
& &
xi-1 ą yi-1 ą ci-1 = ą�ci + si-1
xi ą yi ą ci = ą�ci+1 + si
xi+1 ą yi+1 ą ci+1 = ą�ci+2 + si+1
& &
X = {xk -1,..., x1, x0,..., x-m}� , Y = {yk -1,..., y1, y0,..., y-m}�
Ó! Ó!
xi ą yi ą ci = si ą �ci+1
Ó!
S = {sk -1,...,s1, s0,...,s-m}�
" cyframi rozszerzenia prawostronnego s zera, wi c c-m = 0
" xi, yi,si "{0,1,...,� -1} �! ci "{0,1} �! ci+1 "{0,1}
z

� Janusz Biernat, 02-06-Dodawanie i odejmowanie.doc, 6 pa dziernika 2006 ADS 1
 Dodawanie i odejmowanie
Dodawanie i odejmowanie w systemach naturalnych (2)
(rozszerzenie)
ś
rozszerzenie
zakres dodawania/ odejmowania
test poprawno ci
0 xk 1 xk 2 & xi+1 xi xi 1 xi 1 & x m 0... 0 (0)
0 yk 1 yk 2 & yi+1 yi yi 1 yi 1 & y m 0... 0 (0)
ck ck 1 ck 2 & ci+1 ci ci 1 ci 1 & 0 0... 0 (0)
ą
ck sk 1 sk 2 & si+1 si si 1 si 1 & s m 0... 0 (0)
!! Je li ck`" 0, to nast piło przekroczenie zakresu [0,2k)
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
z

� Janusz Biernat, 02-06-Dodawanie i odejmowanie.doc, 6 pa dziernika 2006 ADS 2
 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 =
"(x ą yi )� = "[s ą (�ci+1 - ci)]� =
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  je li ck=1, to wynik przekracza zakres (nadmiar):
k k k k
0 d" S < � �! (ck = 1 �! (S + ck � > � ) '" (S - ck � < 0)
z

� Janusz Biernat, 02-06-Dodawanie i odejmowanie.doc, 6 pa dziernika 2006 ADS 3
 Dodawanie i odejmowanie
Dodawanie i odejmowanie w systemach uzupełnieniowych
1
k-
k i
1 1 1
xk- x-m+ x-m = -� xk- � +
"x �
i
i=-m
1
1 2 1
gdzie � xk- = + xk- - � +
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
1
k-
k i
1 1 0 1
gdzie S = sk- s s s-m U = -� sk- � +
"s � , V  nadmiar
i
i=-m
z

� Janusz Biernat, 02-06-Dodawanie i odejmowanie.doc, 6 pa dziernika 2006 ADS 4
 Dodawanie i odejmowanie
Praktyczne aspekty wykrywania nadmiaru
W systemie naturalnym lub uzupełnieniowym o podstawie � lewostronne
rozszerzenie liczb o 1 pozycję daje �-krotne rozszerzenie zakresu
WNIOSEK 1: W rozszerzonym lewostronnie o 1 pozycję systemie naturalnym
lub uzupełnieniowym suma nie więcej ni\
� liczb musi być poprawna.
WNIOSEK 2: Aby wykryć nadmiar w dodawaniu (odejmowaniu) nale\
y dodać
operandy rozszerzone lewostronnie o 1 pozycję xe = �(xk -1)(� -1) ,
ye = �(yk-1)(� -1) i sprawdzić, czy dodatkową pozycję sumy (ró\
nicy).
ś
test poprawno ci
rozszerzenie
zakres dodawania/ odejmowania
?
xe xk 1 xk 2 & xi+1 xi xi 1 & x m 0& 0 (0)
ye yk 1 yk 2 & yi+1 yi yi 1 & y m 0& 0 (0)
ck ck 1 ck 2 & ci+1 ci ci 1 & 0 0& 0 (0)
ą
sk sk 1 sk 2 & si+1 si si 1 s m 0& 0 (0)
Jeśli sk nie jest cyfrą rozszerzenia, czyli sk `" �(sk-1)(� -1), to w oryginalnym
dodawaniu (odejmowaniu) wystąpi nadmiar.
z

� Janusz Biernat, 02-06-Dodawanie i odejmowanie.doc, 6 pa dziernika 2006 ADS 5
 Dodawanie i odejmowanie
Poprawno dodawania i odejmowania w systemach uzupełnieniowych
Skutkiem wykonania działań zgodnie z regułą dodawania / odejmowania jest
k-
k i
X ą Y = - � xk- ą� yk- � + xi ą yi � =
"
i=-m
k-
k i
= - � xk- ą� yk- � + si ą �ci+ - ci � ,
"
i=-m
skąd przy c-m = 0 otrzymamy
k-
k i k
X ą Y = - � xk- ą� yk- � +
"s � ą ck �
i
i=-m
Z porównania wzorów wynika
k
X ą Y = S + � sk- ą ck - � xk- ą� yk- �
v = (�(sk -1) ą ck ) - (�(xk -1) ą�(yk -1))  wska nik nadmiaru
z

� Janusz Biernat, 02-06-Dodawanie i odejmowanie.doc, 6 pa dziernika 2006 ADS 6
 Dodawanie i odejmowanie
Dodawanie i odejmowanie w systemach komplementarnych*
k -1
i
{xk -1,..., x-m+1, x-m} = -�(xk -1)R +
"x �
i
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 +
"s � , V  nadmiar
i
i=-m
z

� Janusz Biernat, 02-06-Dodawanie i odejmowanie.doc, 6 pa dziernika 2006 ADS 7
 Dodawanie i odejmowanie
Poprawno dodawania i odejmowania w systemach komplementarnych*
Skutkiem wykonania działań zgodnie z regułą dodawania / odejmowania jest
k -1
i
|X| ą |Y| = -[�(xk -1) ą �( yk -1)]R +
"(x ą yi)� =
i
i=-m
k -1
i
= -[�(xk -1) ą�(yk -1)]R +
"[s ą (�ci+1 - ci )]� ,
i
i=-m
skąd przy c-m = 0 otrzymamy
k -1
i k
|X| ą |Y| = -[�(xk -1) ą �( yk -1)]R +
"s � ą ck �
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))  wska 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)
z

� Janusz Biernat, 02-06-Dodawanie i odejmowanie.doc, 6 pa dziernika 2006 ADS 8
 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
z

� Janusz Biernat, 02-06-Dodawanie i odejmowanie.doc, 6 pa dziernika 2006 ADS 9
 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
z

� Janusz Biernat, 02-06-Dodawanie i odejmowanie.doc, 6 pa dziernika 2006 ADS 10
 Dodawanie i odejmowanie
Dodawanie w dwójkowym systemie uzupełnieniowym  nadmiar
Analiza wszystkich przypadków:
xi + yi = (2ci+1 - ci) + si
Ck-1 0 0 0 1
k-2
X = -xk-12k-1 +
(0) 0... (0) 0...
"x 2i
i
i=...
+ (0) 0... + (0) 0...
k-2
(0) 0... (0) 1...
Y = - yk-12k-1 + yi 2i
"
i=...
ck-1 0 0 1 1
suma:
k-2
(0) 0... (0) 0...
= -(xk-1 + yk-1)2k-1 +
"(x + yi)2i =
i
+ (1) 1... + (1) 1...
i=...
(1) 1... (1) 1...
k-2
= -sk-12k-1 +
"s 2i +
i
ck-1 1 0 1 1
i=...
k-2 (1) 1... (1) 1...
- (2ck - ck-1)2k-1 +
+ (1) 1... + (1) 1...
"(2c - ci)2i =
i+1
i=...
(1) 1... (1) 1...
k-2
= -sk-12k-1 + WNIOSEK:
"s 2i + (ck-1 - ck )2k
i
i=...
Nadmiar gdy ró\
ne ck oraz ck-1
z

� Janusz Biernat, 02-06-Dodawanie i odejmowanie.doc, 6 pa dziernika 2006 ADS 11
 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
z

� Janusz Biernat, 02-06-Dodawanie i odejmowanie.doc, 6 pa dziernika 2006 ADS 2
 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 = -� + yi� ) + �
"(� -1)� - (- yk � + "
-1
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 + ulp , czyli
k- k-
�ł
k i k i k -m
- � - - yi � - � - �
"y � łł = � yk- � + "
i
�ł-� yk- � + śł
�ł i=-m �ł i=-m
a poniewa\
�(yk -1) = 1-�(yk -1)
k-
k i -m
- Y = -� yk- � +
"y � + �
i
i=-m
z

� Janusz Biernat, 02-06-Dodawanie i odejmowanie.doc, 6 pa dziernika 2006 ADS 3
 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 + ulp ,
X - Y = 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
z

� Janusz Biernat, 02-06-Dodawanie i odejmowanie.doc, 6 pa dziernika 2006 ADS 4
 Dodawanie i odejmowanie
Zmiana znaku liczby w systemie komplementarnym*
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 = -� + yi� ) + �
"(� -1)� - (- yk � + "
-1
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
�ł-�( yk )R + k -1 yi � łł
i i k -m
- = �(yk -1)R +
" "[(� -1) - yi ]� - (� - � )
-1
�ł śł
�ł 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
z

� Janusz Biernat, 02-06-Dodawanie i odejmowanie.doc, 6 pa dziernika 2006 ADS 5
 Dodawanie i odejmowanie
Odejmowanie przez dodawanie w systemie komplementarnym*
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/dopeł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
z

� Janusz Biernat, 02-06-Dodawanie i odejmowanie.doc, 6 pa dziernika 2006 ADS 6
 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
Ł Ł Ł Ł
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
z

� Janusz Biernat, 02-06-Dodawanie i odejmowanie.doc, 6 pa dziernika 2006 ADS 7
 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
z

� Janusz Biernat, 02-06-Dodawanie i odejmowanie.doc, 6 pa dziernika 2006 ADS 8
 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
k-1
i k
S = -sk-1 k-1 +
"s ą ck-1 - ck
i
i=-m
1. Wska nikiem nadmiaru jest niezgodno przeniesie v=ck 1�"ck
2. Poprawny wynik mo na zawsze odtworzy 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}
z

� Janusz Biernat, 02-06-Dodawanie i odejmowanie.doc, 6 pa dziernika 2006 ADS 9
 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 -1
- X = [(-2k -1 + xi 2i )]+ 2-m
"2 ) - (-xk 2k + "
-1
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)
z

� Janusz Biernat, 02-06-Dodawanie i odejmowanie.doc, 6 pa dziernika 2006 ADS 10
 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 +
"(x ą yi )2i = "s 2i ą ck 2k
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 +
"(x + (1- yi ))2i + 2-m = "s 2i - (1- ck )2k
i i
i=-m i=-m
z

� Janusz Biernat, 02-06-Dodawanie i odejmowanie.doc, 6 pa dziernika 2006 ADS 11
 Dodawanie i odejmowanie
Dodawanie i odejmowanie w dwójkowych systemach spolaryzowanych
k -1 k -2
Gdy N = 2k -1 jest X = xi 2i - 2k -1 = -(1- xk -1)2k -1 + xi 2i ,
" "
+ N
i=0 i=0
(i) �! {xk-1, xk-2,..., x0}U2 = {xk-1, xk-2,..., x0}+2ę!(k-1)
k -2
i
Gdy N = 2k -1-1, to poniewa\
(2k -1 -1) =
"2 , więc otrzymamy
i=0
k -1 k -2 k -2
-1
X = xi 2i -(2k -1 -1) = xk -12k -1 +
�ł �ł
" "(x -1)2i = -�ł- xk 2k + "(1- xi )2i �ł
+ N i -1
i=0 i=0 �ł i=0 łł
(ii) �! - {xk-1, xk-2,..., x-m}U2 = {xk-1, xk -2,..., x-m}+2ę!(k-1)-1
A
atwa konwersja (bitowa) na i z kodu U2 uzasadnia celowość algorytmu:
ALGORYTM
1. Wykonaj konwersję argumentów na U2 zgodnie z formułą (i) (lub (ii))
2. Wykonaj działanie w U2 i sprawdz
poprawność (nadmiar)
3. Wykonaj konwersję sumy/ró\
nicy zgodnie z formułą (i) (lub (ii))
z

� Janusz Biernat, 02-06-Dodawanie i odejmowanie.doc, 6 pa dziernika 2006 ADS 12
 Dodawanie i odejmowanie
Rekurencyjne dodawanie wieloargumentowe
jeśli liczba argumentów k>�+1, to dodawanie mo\
na wykonać etapami
0 0 ak 1 ak 2 & a m+3 a m+2 a m+1 a m
0 0
0 0
0 0 bk 1 bk 2 & b m+3 b m+2 b m+1 b m
0 0
0 0
0 0 ck 1 ck 2 & c m+3 c m+2 c m+1 c m
0 0
0 0
0 0 dk 1 dk 2 & d m+3 d m+2 d m+1 d m
0 0
0 0
& & & & & & & & &
& &
& &
+ 0 0 pk 1 pk 2 & p m+3 p m+2 p m+1 p m
0 0
0 0
& & & & & & & & &
& & & & & & & & &
(0) (0) (0) (0) (0) (0)
0 0 xk 1 xk 2 & x m+3 x m+2 x m+1 x m
0 0
0 0
(1) (1) (1) (1) (1) (1)
0 xk 1 xk 2 & x m+3 x m+2 x m+1 x m 0
0 0
0 0
(2) (2) (2) (2) (2) (2)
xk 1 xk 2 & x m+3 x m+2 x m+1 x m 0 0
0 0
0 0
+ & & & & & & & & &
& &
& &
(0) (0) (0) (0) (0) (0) (0) (0)
& uk+1 uk uk 1 uk 2 & u m+3 u m+2 u m+1 x m
(1) (1) (1) (1) (1) (1)
& uk uk 1 uk 2 & u m+3 u m+2 u m+1 0
0
0
(0) (0)
& sk+1 sk sk 1 sk 2 s m+3 s m+2 u m+1 x m
z

� Janusz Biernat, 02-06-Dodawanie i odejmowanie.doc, 6 pa dziernika 2006 ADS 13
>
+1
argumentów
d" +1
arg.
2 arg
 Dodawanie i odejmowanie
Dodawanie wieloargumentowe w systemach uzupełnieniowych (1)
W dodawaniu argumentów k zakres wyniku jest o log2k bitów większy, więc
jeśli liczba argumentów k>�+1 dodawanie nale\
y wykonać rekurencyjnie
nale\
y u\
yć co najmniej m=�łlog� kłł cyfr lewostronnego rozszerzenia
Dodawanie mo\
na wykonać dwuetapowo (z u\
yciem cyfr rozszerzenia):
" na ka\
dej pozycji obliczyć wielopozycyjne (wektorowe) sumy argumentów
1-cyfrowych (w dowolnej kolejności  są niezale\
ne)
" dodać wielocyfrowe sumy z uwzględnieniem ich wag
& (xe) (xe) xk 1 xk 2 & x m+3 x m+2 x m+1 x m
& (ye) (ye) yk 1 yk 2 & y m+3 y m+2 y m+1 y m
& & & & & & & & & &
+ (ze) (ze) zk 1 zk 2 & z m+3 z m+2 z m+1 z m
(& ) (& ) uk 1 uk 2 u m+3 u m+2 u m+1 u m
(& ) vk vk 1 vk 2 & v m+3 v m+2 v m+1 0
(se) (& ) sk sk 1 sk 2 s m+3 s m+2 s m+1 s m
z

� Janusz Biernat, 02-06-Dodawanie i odejmowanie.doc, 6 pa dziernika 2006 ADS 14
 Dodawanie i odejmowanie
Dodawanie wieloargumentowe w systemach uzupełnieniowych (2)
U\
ywanie wielu bitów rozszerzenia jest zbędne, bo:
k-1
k-1
X = -xk-1 2k-1 + + xk-2 k-2 + xk-3 k-3 +
"x 2i = -2k-1 +[(1 - xk-1
i
i=-m
a zatem jeśli X' = {1 - xk-1 , xk-2 ,..., x-m} = {xk-1 , xk-2 ,..., x-m}, to
X =|X'|-2k-1
Algorytm:
1. Dodajemy m liczb dodatnich
2. Dodajemy stałą  m�"2k 1 zapisaną w systemie U2
z

� Janusz Biernat, 02-06-Dodawanie i odejmowanie.doc, 6 pa dziernika 2006 ADS 15
 Dodawanie i odejmowanie
Dodawanie i odejmowanie w innych systemach reprezentacji liczb
" algorytmy specyficzne dla reprezentacji
" skomplikowane wykrywanie nadmiaru
System znak-moduł (SM) (moduł w reprezentacji naturalnej)
Jeśli wykonywane jest odejmowanie, zmień znak odjemnej
Jeśli znaki liczb są jednakowe, wykonaj dodawanie modułów
" jeśli przekroczono zakres modułu sygnalizuj nadmiar,
" w przeciwnym razie znak sumy jest taki jak znaki składników
Jeśli znaki liczb są ró\
ne, wykonaj odejmowanie modułów
" jeśli ró\
nica jest dodatnia, znak sumy jest taki jak znak odjemnej
" jeśli ró\
nica jest ujemna, znak sumy jest przeciwny do znaku odjemnej
a moduł jest równy uzupełnieniu ró\
nicy
System dopełnieniowy (U1, D1)
Wykonaj dodawanie lub odejmowanie jak w systemie uzupełnieniowym,
" jeśli przekroczono zakres sygnalizuj nadmiar,
" jeśli przeniesienie wyjściowe jest równe 1 wykonaj korekcję sumy
dodając  1 na najni\
szej pozycji sumy (przeniesienie okr ne, eac)
z

� Janusz Biernat, 02-06-Dodawanie i odejmowanie.doc, 6 pa dziernika 2006 ADS 16