Rok I ARYTMETYKA KOMPUTERÓW Lista nr 0
1. Znajdz
podstawę x systemu naturalnego, w którym: a) 41x = 5 , b) 22x = 4 c) a2 =301x , d) b2 =562x
2. Znajdz
podstawÄ™ ² systemu naturalnego, w którym liczby naturalne x1 oraz x2 sÄ… rozwiÄ…zaniami
równania ax2+ bx+c = 0. Wykonaj obliczenia dla x1 = 5² , x2 = 8² i równania 5² x2 50² x+125² = 0
3* Znajdz
podstawę systemu naturalnego, w którym x1, x2" są rozwiązaniami równania ax2+ bx+c = 0
gdzie a,b,c " (całkowite).**Rozwią\
zadanie jeśli wiadomo, \
e w tym systemie a,x1,x2 sÄ… liczbami
2
jednocyfrowymi, b jest liczbÄ… dwucyfrowÄ… b = b1²+b0, zaÅ› c jest liczbÄ… o postaci c = c2² + c1²+c0,
c2 = 0 lub 1. Wykonaj obliczenia dla x1 = 5² , x2 = 8² oraz a = 1 lub 3.
4. Wyka\
, \
e w standardowym systemie naturalnym o podstawie ² suma wartoÅ›ci cyfr iloczynu liczby
jednocyfrowej przez ² - 1 jest staÅ‚a. Ułó\
tabliczki mno\
enia w systemach o bazie ² = 5, 7, 9, 11, 13.
5* Wyka\
, \
e w dowolnym systemie naturalnym suma cyfr iloczynu dowolnej liczby jednocyfrowej
przez najwiÄ™kszÄ… liczbÄ™ dwucyfrowÄ… {² 1, ² 1}² jest staÅ‚a. Spróbuj uogólnić uzyskany wynik.
6. Oblicz metodÄ… pisemnÄ… iloczyn 0,324² × 2,41² i iloraz 43,4² : 3,2² dla ² = 5, 7, 9, 11, 13 oraz dla ² = Ä…2,
korzystajÄ…c z tabliczki mno\
enia w systemie o podstawie Ä… = 3, 4.
7. Przeprowadz
konwersje podstawy (bazy), z dokładnością do 4 cyfr części ułamkowej wyniku:
a) 674,58110 = (& )16 = (& )4 b) 0CD,1216 = (& )2= (& )10 c) 3,0128 = & (& )2 & = (& )16
d) 34,5610 ×2 5 = (& )2 = (& )16 e) 102,213×5 2 = (& )5 f) 0BACA16 ×5 3 = (& )10
g) 6745,819 = (& )7 = (& )10 h) 0AA,1211 = (& )10 = (& )9 i) 102,213×15 2 = (& )5
j) 347/567 = (& )2 k) 234,(56)9 = (& )7 l) 12,3(45)7 = (& )10 = (& )11
8* Wyka\
, \
e wynikiem konwersji ułamka nieskracalnego w systemie o danej podstawie, na
reprezentacjÄ™ w innym systemie naturalnym, mo\
e być ułamek nieskończony (**okresowy), jeśli
istnieje nierozkła-dalny podzielnik podstawy z
ródłowej, który nie jest podzielnikiem podstawy
docelowej.
9. Przeprowadz
konwersję ułamka okresowego na system, w którym jego reprezentacja jest skończona:
a) 0,(27)10 = b) 0,(101)2 = c) 1  0,(56)9 = d) 0,(35)11  0,(2)11 = e) 0,1(23)7=
* Wyka\
, \
e taka konwersja ułamka okresowego jest wykonalna w ka\
dym systemie naturalnym.
A. Wyka\
, \
e w systemie naturalnym przeniesienie otrzymane w wyniku dodawania lub po\
yczka
podczas odejmowania na ka\
dej pozycji są zawsze równe 0 lub 1.
B. Opracuj algorytm dodawania lub odejmowania liczb znakowanych zapisanych w systemie znak-moduł
(SM). Przyjmij, \
e znak liczby jest kodowany standardowo (0  plus, 1  minus).
C. Opracuj algorytmy działań w systemie naturalnym o dowolnej podstawie:
a) dodawania i odejmowania, b) mno\
enia, c) dzielenia
©Janusz Biernat, ARYT-ZADANIA-schematy 02 3 kwietnia 2004
0
Rok I ARYTMETYKA KOMPUTERÓW Lista nr 1
D. Oblicz odpowiednio wartości największej i najmniejszej liczby całkowitej, reprezentowanych przez
Å‚aÅ„cuch k cyfr w systemie a) naturalnym o podstawie ² b) negabazowym, c) z cyframi znakowanymi,
d)* uzupeÅ‚nieniowym peÅ‚nym i niepeÅ‚nym, e)* spolaryzowanym  +1/2² k 1 oraz  +1/2² k 1 1 .
©Janusz Biernat, ARYT-ZADANIA-schematy 02 3 kwietnia 2004
1
Rok I ARYTMETYKA KOMPUTERÓW Lista nr 2
1. Zapisz w systemie uzupełnieniowym do 2 (U2) z czterema bitami części ułamkowej liczby:
a)  674,58110 b)  0A,1216 c)  3,0128 d) + 34,5610 e) 4,5610  4,5(6)10
Porównaj otrzymane kody z notacją w systemie uzupełnieniowym do 1 (U1) i systemie znak-moduł.
2. Dodaj i odejmij liczby 4-cyfrowe podane w dziesiętnym uzupełnieniowym systemie pełnym (U10):
a) 6745 Ä… 8123 b) 9,745 Ä… 0,8(23) c) 31,56Ä… 84,23 d) 9,994Ä… 9,916
U\
ywając lewostronnego rozszerzenia zweryfikuj poprawność wyników otrzymanych na 4 pozycjach.
3* Wyka\
, \
e w systemie stałobazowym i uzupełnieniowym, w dodawaniu lub odejmowaniu o ustalonej
liczbie pozycji argumentów i wyniku, u\
ycie dodatkowej pozycji lewostronnego rozszerzenia wyniku
i argumentów wystarczy do wykrycia nadmiaru (przekroczenia zakresu).
4* Wyka\
, \
e w systemach uzupełnieniowych pełnych o bazach skojarzonych konwersję podstawy
S S
mo\
na wykonać przez grupowanie (² ² ) lub dekompozycjÄ™ cyfr (² ² ).
5. Oblicz sumę i ró\
nicę liczb danych jako 10011101 i 01111001, 11011101 i 10111101, zakładając, \
e
podane łańcuchy k = 8 bitów (ciągi zero-jedynkowe) reprezentują liczby w kodzie
a) naturalnym (NB) b) uzupełnieniowym pełnym (U2) c) uzupełnieniowym niepełnym (U1)
d) znak-moduł (SM) e) spolaryzowanym  +2k 1 1 f) spolaryzowanym  +2k 1 .
Zweryfikuj poprawność otrzymanych wyników: A) wykonując działanie odwrotne (suma  argument,
ró\
nica + odjemnik) B) u\
ywając lewostronnego rozszerzenia (oprócz e) i f)).
6. Znanych jest kilka najbardziej znaczących bitów liczb 48-bitowych w kodzie uzupełnieniowym U2.
11101010..?? oraz 10011110..?? Sprawdz
, czy w ich dodawaniu i odejmowaniu wystÄ…pi nadmiar.
7. KorzystajÄ…c z zale\
ności X -Y = X + Y i zakładając, \
e liczby sÄ… dane w systemie naturalnym, oblicz:
a) 6745  8123 b) 9,745  0 , 823 c) 34,56 81,23 d) 100111012  011110012
Sprawdz
otrzymane wyniki wykonując działania odwrotne (ró\
nica + odjemnik).
8. Wyka\
, \
e w systemie naturalnym lub uzupełnieniowym pełnym mno\
enie liczb m pozycyjnych nie
powoduje nadmiaru, jeśli wynik jest kodowany na co najmniej 2m pozycjach.
9. Wynik mno\
enia m bitowych liczb w kodzie U2 jest kodowany na 2m 1 bitach. Czy jest mo\
liwe
wystąpienie nadmiaru, a jeśli tak to przy jakich wartościach mno\
nej i mno\
nika?
A. PrzyjmujÄ…c, \
e 6-bitowe operandy są dane w dwójkowym kodzie uzupełnieniowym a) pełnym (U2),
b) niepełnym (U1) wykonaj mno\
enia: i) 110101×011011 ii) 011101×110111 iii)
101001×111111.
Wykonaj mno\
enie (U2) stosując przekodowanie iloczynów częściowych eliminujące rozszerzenia.
B. Poka\
, \
e w systemie naturalnym dwójkowym i systemie uzupełnieniowym do 2 mno\
enie przez stałą,
która jest sumą lub ró\
nicą potęg dwójki mo\
na wykonać jako dodawanie skalowanej mno\
nej.
C. Oblicz iloczyn liczb 4-cyfrowych podanych w dziesiętnym uzupełnieniowym systemie pełnym (U10):
a) 6745U10 × 8123U10 b) 9745U10 × 0823 U10 c) 3156 U10 × 8423 U10 d) 9994 U10 × 9916 U10
©Janusz Biernat, ARYT-ZADANIA-schematy 02 3 kwietnia 2004
2
Rok I ARYTMETYKA KOMPUTERÓW Lista nr 3
©Janusz Biernat, ARYT-ZADANIA-schematy 02 3 kwietnia 2004
3
Rok I ARYTMETYKA KOMPUTERÓW Lista nr 4
1. Oblicz iloczyn liczb 4-cyfrowych podanych w ósemkowym uzupełnieniowym systemie pełnym (U8):
a) 5745U8 × 7123U8 b) 7745U8 × 0723 U8 c) 3156 U8 × 6423 U8 d) 7774 U8 × 7716 U8
2. Oblicz bezpośrednio metodą sekwencyjną ( kolejnych reszt ) z dokładnością do 4 pozycji znaczących
iloraz liczb reprezentowanych w systemie uzupełnieniowym pełnym
a) 01010011U2 : 1011U2 b) 1010011U2 : 01011U2 c) 876U10 : 176U10 d) 876U10 : 761U10.
3. Wykonaj bezpośrednio w systemie U10 dzielenia z dokładnością do 4 cyfr znaczących ilorazu:
a) 110101 : 011011 b) 011101 : 110111 c) 101001 : 11111 d) 101001 : 10011
e) 1,10101 : 01101,1 f) 0,11101 : 110,111 g) 1010,01 : 111,11 h) 101001 : 100,11
Sprawdz
, wykonujÄ…c mno\
enie, poprawność otrzymanych wyników.
4. Wykonaj bezpośrednio w kodzie U2 dzielenia z dokładnością do 4 cyfr znaczących ilorazu:
a) 110101 : 011011 b) 011101 : 110111 c) 101001 : 11111 d) 101001 : 10011
e) 1,10101 : 01101,1 f) 0,11101 : 110,111 g) 1010,01 : 111,11 h) 101001 : 100,11
Sprawdz
, wykonujÄ…c mno\
enie, poprawność otrzymanych wyników.
5. Wykonaj bezpośrednio w kodzie U2 z dokładnością do 4 cyfr znaczących ilorazu dzielenie
nieodtwarzajÄ…ce liczb:
a) 110101 : 011011 b) 011101 : 110111 c) 101001 : 11111 d) 101001 : 10011
e) 1,10101 : 01101,1 f) 0,11101 : 110,111 g) 1010,01 : 111,11 h) 101001 : 100,11
6. Oblicz metodÄ… sekwencyjnÄ… ( kolejnych reszt ) pierwiastek kwadratowy z liczb
a) 1234567, b) 1010 0010 0111 11002, c) 98765432110 d) 123,4567, e) 10100 0100,1111 1002
z dokładnością do jednej, dwóch i siedmiu cyfr znaczących oraz podaj trzecią i czwartą resztę.
7. Dane jest przybli\
enie pierwiastka kwadratowego z dokładnością do 3 cyfr znaczących i trzecia reszta.
Podaj dwie kolejne cyfry przybli\
enia pierwiastka, jeśli:
a) Q3 =1237, r3 =34567, b) Q3 =12310, r3 = 345610, c) Q3 =1012, r3 =111012,
8. Dane jest przybli\
enie pierwiastka kwadratowego z dokładnością do 4 cyfr znaczących i czwarta reszta
równa 0. Oszacuj wartość liczby pierwiastkowanej, jeśli: a) Q4 =12,347, b) Q4 =1,23410, c) Q4 =11012.
9. Oblicz metodÄ… nieodtwarzajÄ…cÄ… pierwiastek kwadratowy z liczb:
a) 1010 0010 0111 11002, b) 123,4568, c) 10100 0100,1111 1002
z dokładnością do dwóch i pięciu cyfr znaczących oraz podaj trzecią i czwartą resztę.
A* Poka\
, \
e w naturalnym systemie dwójkowym dzielenie przez stałą, która jest sumą lub ró\
nicÄ…
dwóch potęg dwójki, mo\
na wykonać przez odejmowanie, jeśli dzielenie nie wytwarza reszty.
©Janusz Biernat, ARYT-ZADANIA-schematy 02 3 kwietnia 2004
4
Rok I ARYTMETYKA KOMPUTERÓW Lista nr 5
1. Twierdzenie Euklidesa o podzielności liczb orzeka, \
e największy wspólny podzielnik dwóch liczb
naturalnych jest podzielnikiem reszty z dzielenia większej przez mniejszą. Wyka\
, równowa\
ność tej
tezy z tezÄ…, \
e największy wspólny podzielnik dwóch liczb jest podzielnikiem ich ró\
nicy.
2. KorzystajÄ…c z twierdzenia Euklidesa znajdz
największy wspólny podzielnik liczb:
a) 6745 i 8123 b) 9994, 92 i 9916 c) 375, 243, 345 i 126 d) 220 1 oraz 25+1
k k + 1
3. Poka\
, \
e liczby 2 + 1 i 2 + 1 są względnie pierwsze (k " N  jest liczbą naturalną)
k r
*Czy prawdziwe jest twierdzenie, \
e liczby 2 + 1 i 2 + 1 (k , r " N ) są względnie pierwsze?
4* Wyka\
, \
e liczby (22n +1) oraz (2n +1) i (22n+1 + 2) i (2n -1) (n" N ) są względnie pierwsze.
5. Nie wykonujÄ…c dzielenia wyznacz resztÄ™ z dzielenia liczby 1011 0011 0111 11012 przez
a) 11112 b) 100012 c) 111112 d) 100000012.
6. Stosując reguły arytmetyki resztowej oblicz reszty całkowite (dodatnie lub ujemne) wobec modułów:
25710, 78 , 6510, 3F16, 1116, 0FF16 dla liczb 46528 i 0ABCD16, oraz ich sumy, ró\
nicy i iloczynu.
7. Podaj reprezentacjÄ™ resztowÄ… liczby 2345610 w bazie: a) (29, 30, 31), b) (99, 100, 101), a) (63, 64, 65).
8* Znajdz
odwrotności multyplikatywne iloczynów par modułów bazy systemu resztowego (a 1, a, a+1)
względem trzeciego z nich, zakładając, \
e a jest liczbÄ… parzystÄ….
9* Wektor (1, 2, 3) jest reprezentacja resztowÄ… liczby x w bazie (29, 30, 31). Znajdz
tÄ™ liczbÄ™ w zbiorze
kongruencji naturalnych (x"[0, M=29Å"30Å"31)) i caÅ‚kowitych (x" ðÅ‚ (M 1)ûÅ‚ /2, ðÅ‚M 1ûÅ‚ /2)).
A. Zapisz w 32-bitowym formacie zmiennoprzecinkowym standardu IEEE 754 liczby o wartościach:
-61
a) 674,5318 b) 0,128 Å" 8-51 c)  0ABC,DE16 d) 10,1010101010U2 Å" 4
B. Zapisz w 32-bitowym formacie zmiennoprzecinkowym IEEE 754 pierwiastki kwadratowe z liczb:
a) 1010 0010, 0111 11002, b) 123,4568, c) 10100 0100, 1111 1002
C. Oblicz i zapisz w 32-bitowym formacie zmiennoprzecinkowym standardu IEEE 754 z dokładnością do
5 cyfr znaczÄ…cych pierwiastki kwadratowe z liczb danych w tym formacie:
a) 0 0100 0100 111 1100 1010 0010 0111 1100, b) 0 1010 0101 1111 1010 0100 1111 1111 1002
c) 0 0100 0101 111 1100 1010 0010 0111 1100, d) 0 1010 0100 1111 1010 0100 1111 1111 1002
D* Wyka\
, \
e w odejmowaniu (dodawaniu) zmiennoprzecinkowym operandów dokładnych, bit S dla
znormalizowanej ró\
nicy (sumy) mo\
e być wyznaczony przed wykonaniem działania.
E. Wyznacz z dokładnością do 4 bitów znacznika zaokrąglenia argumentów 1,101111011 i 1,101111001
uzupełnione bitami G, R, S. Wykonaj ich mno\
enie i porównaj z wynikiem pełnego mno\
enia.
F* Wyka\
, \
e w mno\
eniu znormalizowanych operandów, bit S znormalizowanego iloczynu mo\
e być
wyznaczony przed mno\
eniem. Poka\
, \
e jeden z czynników mo\
e być zdenormalizowany.
G* Oszacuj maksymalny błąd przybli\
enia ró\
nicy podczas odejmowania znormalizowanych operandów
obliczonych z taką samą dokładnością bezwzględną znacznika (mantysy).
©Janusz Biernat, ARYT-ZADANIA-schematy 02 3 kwietnia 2004
5
Rok I ARYTMETYKA KOMPUTERÓW Lista nr 6
1. Stosując reguły działań w algebrze Boole a uprość poni\
sze wyra\
enia
a) x+(x•"y) b) xyz+(x•"y) +(z•"y) c) x+xy+xyz
d) zy+(x•"y) e) zx+z(x•"1) f) x+xy+(x•"yz)
2. Na podstawie tabel wartości funkcji logicznych f1 i f2 (tzw. tabel prawdy) podaj ich wszystkie
mintermy (konstytuenty iloczynu) i maxtermy (konstytuenty sumy) oraz postaci formalne
x3 x2 x1 f1(x) x3 x2 x1 f2(x)
0 0 0 0 0 0 0 1
0 0 1 0 0 0 1 1
0 1 0 1 0 1 0 1
0 1 1 0 0 1 1 0
1 0 0 1 1 0 0 0
1 0 1 1 1 0 1 1
1 1 0 1 1 1 0 0
1 1 1 0 1 1 1 1
3. Wyznacz funkcje dualne i komplementarne do funkcji f1(x) = x2 x1 + x3x2 i f2 (x) = x3x1 + x3(x2 + x1)
oraz ich sumy logicznej i iloczynu logicznego. Narysuj sieci logiczne realizujÄ…ce te funkcje.
4. Korzystając z twierdzenia Shannona rozwiń wszystkie funkcje z zadania 3 względem zmiennej x3.
5. Wyka\
, \
e wartość funkcji logicznej [zÅ"f(x)+(z•"f(x))] f(x) nie zale\
y od zmiennej z.
6* Poka\
, \
e ka\
dÄ… funkcjÄ™ logicznÄ… mo\
na wyrazić za pomocą tylko funkcji NOR (suma negacji) lub
tylko funkcji NAND (iloczyn negacji).
7. Wyznacz charakterystyki AT sieci logicznych realizujacych funkcje dane przez wyra\
enia w zadaniu 1
8. Subtraktor 1-bitowy realizuje funkcje logiczne ró\
nicy d = f (x, y, z) i po\
yczki b = h (x, y, z)
równowa\
ne arytmetycznemu równaniu odejmowania 1-bitowego x  y  z =  2d + b
(x , y , z , d , b " {0, 1}) . Podaj tabelÄ™ prawdy subtraktora i wyznacz charakterystyki AT subtraktora 8-
bitowego.
9. Sumator 1-bitowy realizuje funkcje logiczne sumy s = f (x, y, z) i przeniesienia c = h (x, y, z) równowa\
ne
arytmetycznemu równaniu dodawania 1-bitowego x + y + z = 2c + s (x , y , z , s , c " {0, 1}) . Zaprojektuj
ogniwo inkrementera realizujÄ…cego funkcje s = f (x, 1, z) oraz c = h (x, 1, z) i oblicz charakterystyki AT.
A. Sumator warunkowy 1-bitowy realizuje funkcje logiczne warunkowej sumy s0 = f (x, y, 0), s1 = f (x, y, 1)
i przeniesienia c0 = h (x, y, 0), c1 = h (x, y, 1) równowa\
ne równaniu dodawania 1-bitowego przy
zało\
eniu, \
e przeniesienie wejściowe jest odpowiednio równe 0 albo 1. Wyznacz te funkcje.
B* Narysuj schemat logiczny sumatora 1-bitowego, którego wyjścia sumy i przeniesienia są wytwarzane
z u\
yciem multiplekserów sterowanych przeniesieniem wejściowym na podstawie funkcji sumy
i przeniesienia zerowego i jedynkowego s0 , s1 , c0 , c1 . Wyznacz charakterystyki AT tego układu.
C* Poka\
, \
e charakterystyki AT sieci realizujÄ…cych funkcjÄ™ dualnÄ… i komplementarnÄ… sÄ… jednakowe.
©Janusz Biernat, ARYT-ZADANIA-schematy 02 3 kwietnia 2004
6
Rok I ARYTMETYKA KOMPUTERÓW Lista nr 7
1. Oblicz charakterystyki AT sumatorów uniwersalnych RCA dla kodów k-bitowych:
a) uzupełnieniowego pełnego (U2) b) uzupełnieniowego niepełnego (U1) c) znak-moduł,
d) spolaryzowanego ujemnie  +2k 1 e) spolaryzowanego dodatnio  +2k 1 1
2. Zaproponuj sposób kodowania cyfr i zaprojektuj sumator jedno- i cztero-pozycyjny dla systemu
a) U10 z kodowaniem cyfr w kodzie  +3 i kodzie BCD
b) dwójkowego negabazowego (² =  2),
c)* naturalnego trójkowego (² = 3) i dwójkowego z cyfrÄ… znakowanÄ… SD (D={ 1,0,+1})
3. Oblicz charakterystyki AT sumatora 24-bitowego z przeniesieniami przeskakującymi (carry-skip) jeśli
ma on strukturÄ™ a) 3-4-4-3-4-4-2, b) 3-3-4-4-4-3-3, c) 4-4-4-4-4-4, d) 6-6-6-6, e) optymalnÄ….
4. Zaprojektuj 8-bitowe układy inkrementacji i dekrementacji i wyznacz ich charakterystyki AT.
5. Zaprojektuj 4- i 8-bitowy sumator sum warunkowych i wyznacz ich charakterystyki AT.
6. Zaprojektuj 4- i 8-bitowy sumator prefiksowy PPA i wyznacz ich charakterystyki AT.
7. W celu dodania n operandów k-bitowych u\
yto sumatora CSA (carry-save). Ile bitów zawiera suma?
Jakie jest opóz
nienie (T) podczas obliczania sumy, jeśli sumę końcową wytwarza
a) sumator ze skrośną propagacją przeniesień RCA, b) sumator sum warunkowych COSA.
Obliczenia wykonaj dla n = 7, 15, 31 oraz k = 8, 16, 32.
8. Ile poziomów musi zawierać sumator CSA u\
yty do redukcji iloczynów częściowych tworzonych
w mno\
eniu liczb 32-bitowych w kodzie naturalnym (NB)? Ile sumatorów elementarnych (3,2)
zawiera najbardziej skomplikowana gałąz
CSA odpowiadajÄ…ca bitom o tej samej wadze.
9. Zaprojektuj sumator CSA dodający odpowiednio 3, 4 i 8 operandów 4-bitowych w kodzie U2.
A. Wyznacz, uwzględniając czas końcowego dodawania, najkrótszy czas dodawania 32 operandów 64-
bitowych w sumatorze CSA jeśli dysponujesz:
a) reduktorami (3,2) generującymi przeniesienia 1-bitowe, wnoszące opóz
nienia T = 4 ka\
dy
b) *reduktorami (4,2) generującymi przeniesienia 2-bitowe, wnoszące opóz
nienia T = 6 ka\
dy
B* Opracuj i uzasadnij algorytmy konwersji dwójkowo dziesiętnej liczb całkowitych dodatnich, bez
wykonywania dzielenia, jeśli cyfry dziesiętne są kodowane: a) w kodzie BCD, b) w kodzie BCD+3.
C* Zaprojektuj generator reprezentacji resztowej liczby całkowitej 8- i 16-bitowej w kodzie NB
a) mod 11112 b) mod 100012 c) mod 1112 d) mod 10012
D* Zaprojektuj generator reprezentacji resztowej liczby całkowitej 8- i 16-bitowej w kodzie U2
a) mod 11112 b) mod 100012 c) mod 1112 d) mod 10012
E. Zaprojektuj sumator mod (28 1) dwóch liczb całkowitych 8-bitowych w kodzie U2.
F* Zaprojektuj sumatory mod (24 1) i mod (24+1) 4 liczb całkowitych 4-bitowych w kodzie U2.
©Janusz Biernat, ARYT-ZADANIA-schematy 02 3 kwietnia 2004
7
Rok I ARYTMETYKA KOMPUTERÓW Lista nr 8
1. Zakoduj na 8 bitach według prostej i odwrotnej reguły Booth a w bazie 2 oraz w bazie 4 liczby:
a)  8710 b) +12110 c) 1011012 c) 1011101U2
2. PrzyjmujÄ…c, \
e 6-bitowe operandy są dane w dwójkowym kodzie uzupełnieniowym a) pełnym (U2),
b) niepełnym (U1) i u\
ywajÄ…c mno\
nika przekodowanego wg reguły Booth a w bazie 2 i 4 wykonaj
mno\
enia: i) 110101×011011 ii) 011101×110111 iii) 101001×111111
3. Oblicz charakterystyki AT matrycy mno\
Ä…cej dwa operandy: a) 4-bitowe, b) 8-bitowe c)* n-bitowe
4* Zaprojektuj matrycÄ™ mno\
Ä…cÄ… operandy 4-bitowe w kodzie U2 z wykorzystaniem przekodowania
mno\
nika wg reguły Bootha w bazie 4. Porównaj z innymi układami matrycowymi.
5. Oblicz charakterystyki AT sumatora CSA u\
ytego do redukcji iloczynów częściowych w mno\
eniu
operandów 4-, 8- bitowych danych: a) w kodzie NB, b) w kodzie U2 z eliminacją bitów rozszerzenia.
*Podaj oszacowanie charakterystyk AT dla mno\
enia operandów n-bitowych.
6. W dzieleniu w systemie naturalnym w bazie 4 skalowana reszta częściowa ma wartość 2,2D. Wyznacz:
analitycznie i na podstawie parametrycznego wykresu dzielenia, kolejne dwie cyfry ilorazu.
7. W dzieleniu w systemie U2 przeskalowana reszta częściowa ma wartość: i)  0,2D, ii) +0,7D.
Wyznacz: analitycznie i na podstawie parametrycznego wykresu dzielenia kolejne dwie cyfry ilorazu,
zakładając, \
e dzielnik D jest: a) ujemny, b) dodatni.
8. Wykonaj bezpośrednio w kodzie U2 dzielenia z dokładnością do 4 cyfr znaczących ilorazu:
a) 110101 : 011011 b) 011101 : 110111 c) 101001 : 11111 d) 101001 : 10011
e) 1,10101 : 01101,1 f) 0,11101 : 110,111 g) 1010,01 : 111,11 h) 101001 : 100,11
Sprawdz
, wykonujÄ…c mno\
enie, poprawność otrzymanych wyników.
9. Wykonaj wykres P-D dla dzielenia w bazie 4 i dzielnika z zakresu [1,2). Podaj ile bitów musi być
porównywanych w celu wyznaczenia cyfr ilorazu.
A. Oblicz charakterystyki AT matryc dzielÄ…cych operandy 8-bitowe w kodzie NB i U2
B. Oblicz metodÄ… Newtona iloraz 3,1416 :2,7183.
C. Oceń czas obliczania pierwiastka kwadratowego z liczby całkowitej metodą sekwencyjną ( kolejnych
reszt ) oraz na podstawie to\
samości:  suma n kolejnych nieparzystych liczb naturalnych jest równa
kwadratowi z ich liczby (np. 1+3+5=32 1+3+5+7=42, 1+3+5+7+9=52 itd.)
*Określ minimalny czas obliczeń, jeśli liczba jest zakodowana odpowiednio na 8, 16, 32 bitach.
D* Oszacuj liczbę kroków algorytmu CORDIC potrzebnych do obliczenia wartości funkcji exp, ln, sin,
cos, arctg dla argumentu z przedziału [ 1,1] z dokładnością do 32 bitów części ułamkowej.
E* Oceń czas obliczania pierwiastka trzeciego stopnia na podstawie algorytmu opartego na zale\
ności:
n n n j-1 n-1 j
2
n3 - n =
"(3Å"i - 3Å"i) = 3"(i Å" (i -1)) = 3""2i = 6""i
i=1 i=1 j=1 i=0 j=1 i=1
©Janusz Biernat, ARYT-ZADANIA-schematy 02 3 kwietnia 2004
8
Rok I ARYTMETYKA KOMPUTERÓW Lista nr 9
Zadania z kartkówek
1. Zapisz w dwójkowym systemie uzupełnieniowym (U2), z dokładnością do 6 cyfr części ułamkowej,
wynik dziaÅ‚ania 1234,(56)² - 4321,(65)², ² = 9, 11, 12, 13.
2. Zapisz w dwójkowym systemie uzupełnieniowym (U2), z dokładnością do 4 cyfr części ułamkowej,
wynik dziaÅ‚ania 10101,(01)² - 100,(1)², ² = 3, 5, 7, 9.
3. Przeprowadz
konwersjÄ™ na system o podstawie ² = 7 wyniku dziaÅ‚ania X + Y, X - Y, Y - X, 2X - Y, jeÅ›li
X = 10101,011U2 oraz Y = 0 1011,101U2.
©Janusz Biernat, ARYT-ZADANIA-schematy 02 3 kwietnia 2004
9
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
Lista nr 0
1. Znajdz
podstawę x systemu naturalnego, w którym: a) 41x = 5 , b) 22x = 4 c) a2 =301x , d) b2 =562x
Wskazówka: a) i b): Nale\
y podnieść obie strony równości do kwadratu i rozwiązać stosowne równanie
ze względu na nieznaną podstawę. Trzeba te\
zauwa\
yć, \
e szukana podstawa musi być większa od
największej z cyfr występujących w równaniu (stąd wynika, \
e wartości cyfr <10 mo\
na uwa\
ać za
wartoÅ›ci w systemie dziesiÄ™tnym). Na przykÅ‚ad 5x×5x =41x skÄ…d wynika, \
e 25=4x+1, zatem x=6.
Jeśli liczba pierwiastkowana ma k cyfr, to trzeba rozwiązać równanie stopnia k 1 względem x. Na
przykład
c) i d): Poniewa\
kwadrat jest liczbą trzycyfrową, to x musi być liczbą dwucyfrową, co więcej
starszÄ… cyfrÄ… musi być 1 (bo (²)2 < 301² = 3² 2+1 <(2²)2). Mamy stÄ…d równanie (²+z)2 = 3² 2+1, czyli
2² 2 2z²+(1 z2) = 0. Zatem (wzory Viete y), poniewa\
z nie mo\
e być równe 1 (bo wtedy wystąpi
sprzeczność ² = 1 ), jedno z rozwiÄ…zaÅ„ musi być ujemne (ujemny jest iloczyn pierwiastków (1 z2)).
Poniewa\
oba rozwiązania muszą być te\
całkowite (ich suma wynosi z), to wystarczy badać wartości
nieparzyste z (3,5,7,...). I tak przy z=3 otrzymamy ² = 4 (lub  1), gdy z=11 to ² = 15 (lub  4).
Podobnie, dla przykÅ‚adu d) mamy (2²)2 < 562² = 5² 2+6² +2 <(3²)2), skÄ…d wynika, \
e starszÄ… cyfrÄ…
2
liczby b jest 2. Mamy stÄ…d równanie (2²+z)2 = 5² 2+6² +2, czyli ² 2+(6 4z)² +(2 z ) = 0 z warunkiem
² > 6 , a poniewa\
z nie mo\
e być równe 1 (bo wtedy ² =  1), iloczyn pierwiastków (2 z2) jest ujemny
zaÅ› suma (4z 6) dodatnia. Otrzymamy odpowiednio dla kolejnych z zestawy (z: suma, iloczyn) takie
jak: (2:+2,  2), (3,+6, 7)  ² = 7 , (4,+10, 14), (5,+14, 23), (6,+18, 34), ... JeÅ›li kwadrat jest liczbÄ…
k-cyfrowÄ…, to trzeba analizować równanie stopnia k 1 wzglÄ™dem nieznanej podstawy ².
2. Znajdz
podstawÄ™ ² systemu naturalnego, w którym liczby naturalne x1 oraz x2 sÄ… rozwiÄ…zaniami
równania ax2+ bx+c = 0. Wykonaj obliczenia dla x1 = 5² , x2 = 8² i równania 5² x2 50² x+125² = 0
Wskazówka: Poniewa\
znamy pierwiastki, więc na podstawie wzorów Viete y nale\
y uło\
yć równania ze
wzglÄ™du na ² . W tym zadaniu mamy 5² ( x1 +x2) = 50² , skÄ…d natychmiast wynika (5² ×10² =50² ) \
e x1
+x2 = 10² = ² . Trzeba jeszcze sprawdzić, czy 513×(513×813) = 12513 (OK., bo 132+2×13+1 = 200).
*JeÅ›li rozwiÄ…zania równania x2 15² x+53² = 0 sÄ… naturalne, to x1 + x2 = ² + 5 oraz = x1 x2 = 5² + 3.
Musi wiÄ™c być x1 > 5 oraz x2 < ² (w przeciwnym razie jeden musi być ujemny) JeÅ›li x1 = 6 , x2 = ² - 1 ,
to ² = 9 . (powinny być dwa symetryczne rozwiÄ…zania dla x1 oraz x2  jedno rozwiÄ…zanie dla ² ).
3* Znajdz
podstawę systemu naturalnego, w którym x1, x2" są rozwiązaniami równania ax2+ bx+c = 0
gdzie a,b,c " (całkowite).**Rozwią\
zadanie jeśli wiadomo, \
e w tym systemie a,x1,x2 sÄ… liczbami
2
jednocyfrowymi, b jest liczbÄ… dwucyfrowÄ… b = b1²+b0, zaÅ› c jest liczbÄ… o postaci c = c2² + c1²+c0,
c2 = 0 lub 1. Wykonaj obliczenia dla x1 = 5² , x2 = 8² oraz a = 1 lub 3.
©Janusz Biernat, ARYT-ZADANIA-schematy 02 3 kwietnia 2004
10
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
Wskazówka: *Na podstawie wzorów Viete y uło\
yć ukÅ‚ad równaÅ„ wzglÄ™dem nieznanej podstawy ²
i nieznanego drugiego pierwiastka x2:  a (x1 + x2) = b oraz a x1 x2= c. **Pierwiastki całkowite muszą
być podzielnikami c  zale\
nie od wartości c mo\
na określić dozwolony zakres ich wartości. Powstałe
przypadki przeanalizować (łatwo to zrobić gdy pierwiastki są jednocyfrowe), zbadać te\
wyró\
nik ".
& & &
4. Wyka\
, \
e w standardowym systemie naturalnym o podstawie ² suma wartoÅ›ci cyfr iloczynu liczby
jednocyfrowej przez ² - 1 jest staÅ‚a. Ułó\
tabliczki mno\
enia w systemach o bazie ² = 5, 7, 9, 11, 13.
Wskazówka: x × ( ²  1 ) = ( x  1 ) ² + ( ²  x ), zaÅ› ( x  1 ) + ( ²  x ) = ²  1. SÄ…siednie wielokrotnoÅ›ci m
najÅ‚atwiej obliczyć wykonujÄ…c dodawanie lub odejmowanie: mÅ"(a Ä… 1) = mÅ"a Ä… m.
5* Wyka\
, \
e w dowolnym systemie naturalnym suma cyfr iloczynu dowolnej liczby jednocyfrowej
przez najwiÄ™kszÄ… liczbÄ™ dwucyfrowÄ… {² 1, ² 1}² jest staÅ‚a. Spróbuj uogólnić uzyskany wynik.
Wskazówka: x×|{(² 1),(² 1)}| = x×(² 2 1)=(x 1)² 2+ ²(² 1)+(² x). Podobnie x×|{(² 1),& (² 1),(²
1)}|= = x×(² k 1) = (x 1)² k +(² 1)² k 1 +& +²(² 1)+(² x) , zatem suma cyfr wynosi k(² 1).
6. Oblicz metodÄ… pisemnÄ… iloczyn 0,324² × 2,41² i iloraz 43,4² : 3,2² dla ² = 5, 7, 9, 11, 13 oraz dla ² = Ä…2,
korzystajÄ…c z tabliczki mno\
enia w systemie o podstawie Ä… = 3, 4.
Wskazówka: JeÅ›li Ä… = ² 2, to {z,& ,x}Ä…= {(z div ²),( z mod ²),& ,(x div ²),( x mod ²)}², np. 0,539 = 0,12103
7. Przeprowadz
konwersje podstawy (bazy), z dokładnością do 4 cyfr części ułamkowej wyniku:
a) 674,58110 = (& )16 = (& )4 b) 0CD,1216 = (& )2= (& )10 c) 3,0128 = & (& )2 & = (& )16
d) 34,5610 ×2 5 = (& )2 = (& )16 e) 102,213×5 2 = (& )5 f) 0BACA16 ×5 3 = (& )10
g) 6745,819 = (& )7 = (& )10 h) 0AA,1211 = (& )10 = (& )9 i) 102,213×15 2 = (& )5
j) 347/567 = (& )2 k) 234,(56)9 = (& )7 l) 12,3(45)7 = (& )10 = (& )11
Wskazówka: Konwersja przez podstawÄ™ skojarzonÄ… (Ä… = ² k) przyÅ›piesza obliczenia  wyznaczamy k cyfr
w ka\
dym kroku (np. konwersję na system dwójkowy łatwo wykonać przez system ósemkowy). Jeśli
mno\
nik jest potęgą podstawy z
ródłowej, to skalowanie nale\
y wykonać przed konwersją, a jeśli jest
potęgą bazy docelowej, skalowanie przeprowadzić po konwersji. Konwersję ułamka wymiernego (po
skróceniu) wykonać jako konwersję licznika i mianownika (zawsze dokładna) a następnie dzielenie
z \
ądaną dokładnością. Ułamek okresowy nale\
y zamienić na ułamek wymierny, albo u\
ywajÄ…c kilku
(>2) cykli okresu zaobserwować regularność zapisu wielokrotności ułamka.
8* Wyka\
, \
e wynikiem konwersji ułamka nieskracalnego w systemie o danej podstawie, na
reprezentacjÄ™ w innym systemie naturalnym, mo\
e być ułamek nieskończony (**okresowy), jeśli
©Janusz Biernat, ARYT-ZADANIA-schematy 02 3 kwietnia 2004
11
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
istnieje nierozkła-dalny podzielnik podstawy z
ródłowej, który nie jest podzielnikiem podstawy
docelowej.
Wskazówka: Znajdz
licznik uÅ‚amka danego w bazie ² w bazie p² gdy (p,²)=1. (dowód podobnego
twierdzenia podano w ksiÄ…\
ce  Metody i układy arytmetyki komputerowej ). Twierdzenie jest
fałszywe, bowiem są przypadki gdy tak nie jest np. 0,510 = 0,12, ale np. 0,110 = 0,(00011)2.
9. Przeprowadz
konwersję ułamka okresowego na system, w którym jego reprezentacja jest skończona:
a) 0,(27)10 = b) 0,(101)2 = c) 1  0,(56)9 = d) 0,(35)11  0,(2)11 = e) 0,1(23)7=
* Wyka\
, \
e taka konwersja ułamka okresowego jest wykonalna w ka\
dym systemie naturalnym.
Wskazówka: Wartość ułamka okresowego jest równa granicy szeregu nieskończonego. Nale\
y obliczyć tę
granicę w postaci ułamka wymiernego, skrócić go i wtedy mianownik jest szukaną podstawą systemu
a licznik wyznacza wartość ułamka w systemie o tej podstawie. Na przykład 0,(3)10 =
1
0,3 + 0,03 + & = = 0,3 / ( 1  0,1 ) = /3 = 0,13, c) 1  0,(56)9 = 0,(32)9 , d) 0,(35)11  0,(2)11 = 0,(35)11 
0,(22)11 = 0,(13)11
A. Wyka\
, \
e w systemie naturalnym przeniesienie otrzymane w wyniku dodawania lub po\
yczka
podczas odejmowania na ka\
dej pozycji są zawsze równe 0 lub 1.
Dowód: Poniewa\
najwiÄ™kszÄ… liczbÄ… jest ²  1, wiÄ™c ich najwiÄ™kszÄ… sumÄ… jest ² +(²  2), co oznacza
wystąpienie przeniesienia =1. Jeśli tę liczbę powiększymy o 1 przeniesienie będzie bez zmian.
Poniewa\
na pozycji najni\
szej przeniesienie jest równe 0, więc nigdy nie mo\
e wystąpić
przeniesienie inne ni\
0 lub 1.
B. Opracuj algorytm dodawania lub odejmowania liczb znakowanych zapisanych w systemie znak-moduł
(SM). Przyjmij, \
e znak liczby jest kodowany standardowo (0  plus, 1  minus).
Wskazówka: Sprawdz
, jakie działanie nale\
y faktycznie wykonać w zale\
ności od znaków argumentów.
C. Opracuj algorytmy działań w systemie naturalnym o dowolnej podstawie:
a) dodawania i odejmowania, b) mno\
enia, c) dzielenia
Wskazówka: Zapisz algorytm dodawania / odejmowania jednopozycyjnego. Utwórz tabliczki mno\
enia.
D. Oblicz odpowiednio wartości największej i najmniejszej liczby całkowitej, reprezentowanych przez
Å‚aÅ„cuch k cyfr w systemie a) naturalnym o podstawie ² b) negabazowym, c) z cyframi znakowanymi,
d)* uzupeÅ‚nieniowym peÅ‚nym i niepeÅ‚nym, e)* spolaryzowanym  +1/2² k 1 oraz  +1/2² k 1 1 .
Odpowiedz
: Nale\
y podstawić do ogólnego wzoru wartości odpowiadające skrajnym liczbom 
w systemie naturalnym i spolaryzowanym odpowiednio zero lub największą cyfrę na ka\
dej pozycji,
w systemach uzupeÅ‚nieniowych odpowiednio {²/2  1, ²  1,& , ²  1} dla podstaw parzystych oraz
{²/2,0,& ,0} dla nieparzystych, tak aby zakres byÅ‚ symetryczny.
©Janusz Biernat, ARYT-ZADANIA-schematy 02 3 kwietnia 2004
12
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
©Janusz Biernat, ARYT-ZADANIA-schematy 02 3 kwietnia 2004
13
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
Lista nr 1
1. Zapisz w systemie uzupełnieniowym do 2 (U2) z czterema bitami części ułamkowej liczby:
a)  674,58110 b)  0A,1216 c)  3,0128 d) + 34,5610 e) 4,5610  4,5(6)10
Porównaj otrzymane kody z notacją w systemie uzupełnieniowym do 1 (U1) i systemie znak-moduł.
Wskazówka: Najpierw kodujemy wartość bezwzględną, roszerzając ją lewostronnie zerem (w systemie
znak-moduł rozszerzenie jest zbędne), potem wykonujemy  wchłonięcie znaku  w systemie U1
negujÄ…c wszystkie bity, w systemie U2 odejmujÄ…c od 0 (lub mnemotechnicznie).
2. Dodaj i odejmij liczby 4-cyfrowe podane w dziesiętnym uzupełnieniowym systemie pełnym (U10):
a) 6745 Ä… 8123 b) 9,745 Ä… 0,8(23) c) 31,56Ä… 84,23 d) 9,994Ä… 9,916
U\
ywając lewostronnego rozszerzenia zweryfikuj poprawność wyników otrzymanych na 4 pozycjach.
Uwaga: Dodawanie jak w systemie dziesiętnym, rozszerzeniem dodatniej jest  0 , ujemnej  9 . Jeśli
wynik bez cyfry rozszerzenia oznacza tę samą liczbę co z cyfrą rozszerzenia nie wystąpił nadmiar. Na
przykład (9)6745 + (9)8123= (9)4858 jest ujemne ale 4858 jest dodatnie, zatem wystąpił nadmiar.
Poprawne zaokrÄ…glenie w b) wymaga u\
ycia 2 cykli okresu.
3* Wyka\
, \
e w systemie stałobazowym i uzupełnieniowym, w dodawaniu lub odejmowaniu o ustalonej
liczbie pozycji argumentów i wyniku, u\
ycie dodatkowej pozycji lewostronnego rozszerzenia wyniku
i argumentów wystarczy do wykrycia nadmiaru (przekroczenia zakresu).
Wskazówka: Zakres argumentów z u\
yciem pozycji rozszerzenia jest większy od oryginalnego, tyle razy,
jaka jest podstawa. Zatem wynik z rozszerzeniami jest zawsze poprawny. Rozszerzenie wyniku jest
zbędne, jeśli nie zostanie przekroczony oryginalny zakres, więc wystarczy to sprawdzić.
4* Wyka\
, \
e w systemach uzupełnieniowych pełnych o bazach skojarzonych konwersję podstawy
S S
mo\
na wykonać przez grupowanie (² ² ) lub dekompozycjÄ™ cyfr (² ² ).
Wskazówka: Liczby ujemne zapisz w konwencji znak-moduł.
5. Oblicz sumę i ró\
nicę liczb danych jako 10011101 i 01111001, 11011101 i 10111101, zakładając, \
e
podane łańcuchy k = 8 bitów (ciągi zero-jedynkowe) reprezentują liczby w kodzie
a) naturalnym (NB) b) uzupełnieniowym pełnym (U2) c) uzupełnieniowym niepełnym (U1)
d) znak-moduł (SM) e) spolaryzowanym  +2k 1 1 f) spolaryzowanym  +2k 1 .
Zweryfikuj poprawność otrzymanych wyników: A) wykonując działanie odwrotne (suma  argument,
ró\
nica + odjemnik) B) u\
ywając lewostronnego rozszerzenia (oprócz e) i f)).
Wskazówka: W systemach spolaryzowanych wygodnie jest wykonać konwersję na system U2.
©Janusz Biernat, ARYT-ZADANIA-schematy 02 3 kwietnia 2004
14
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
6. Znanych jest kilka najbardziej znaczących bitów liczb 48-bitowych w kodzie uzupełnieniowym U2.
11101010..?? oraz 10011110..?? Sprawdz
, czy w ich dodawaniu i odejmowaniu wystÄ…pi nadmiar.
Wskazówka: Nale\
y znalez
ć najwy\
szą pozycję na której jest zawsze wytwarzane przeniesienie
w dodawaniu (1+1) albo po\
yczka w odejmowaniu (0 1), a następnie (wynik na pozycjach wy\
szych
od tak znalezionej nie zale\
y od wartości na pozycjach ni\
szych) zbadać 2 najwy\
sze przeniesienia
lub celowość u\
ycia bitów rozszerzenia lewostronnego.
7. KorzystajÄ…c z zale\
ności X -Y = X + Y i zakładając, \
e liczby sÄ… dane w systemie naturalnym, oblicz:
a) 6745  8123 b) 9,745  0 , 823 c) 34,56 81,23 d) 100111012  011110012
Sprawdz
otrzymane wyniki wykonując działania odwrotne (ró\
nica + odjemnik).
Uwaga: Nale\
y sprawdzić, czy nie powstaje nadmiar (w systemie naturalnym wynik musi być dodatni!).
8. Wyka\
, \
e w systemie naturalnym lub uzupełnieniowym pełnym mno\
enie liczb m pozycyjnych nie
powoduje nadmiaru, jeśli wynik jest kodowany na co najmniej 2m pozycjach.
Wskazówka: Zakresem iloczynu jest [0, (² m 1 )2]= [0, ² 2m 2² m +1<² 2m 1]
9. Wynik mno\
enia m bitowych liczb w kodzie U2 jest kodowany na 2m 1 bitach. Czy jest mo\
liwe
wystąpienie nadmiaru, a jeśli tak to przy jakich wartościach mno\
nej i mno\
nika?
Wskazówka: Zakresem iloczynu jest [ 2m 1×(2m 1 1), ( 2m 1)2]= [ 22m 2+2m 1, 22m 2]. Liczba 22m 2 musi
być zakodowana na 2m bitach, dla pozostałych wystarczy 2m 1 bitów.
A. PrzyjmujÄ…c, \
e 6-bitowe operandy są dane w dwójkowym kodzie uzupełnieniowym a) pełnym (U2),
b) niepełnym (U1) wykonaj mno\
enia: i) 110101×011011 ii) 011101×110111 iii)
101001×111111.
*Wykonaj mno\
enie (U2) stosując przekodowanie iloczynów częściowych eliminujące rozszerzenia.
Uwaga: Iloczyn częściowy odpowiadający najwy\
szemu bitowi mno\
nika ma wagę ujemną. Pamiętaj
o bitach rozszerzenia, zaś w kodzie U1 uwzględnij przeniesienie okrę\
ne (e-a-c).
* Pamiętaj o poprawnym kodowaniu zera, przekodowaniu iloczynu częściowego odpowiadającego
najwy\
szemu bitowi mno\
nika oraz korekcji wyniku.
B. Poka\
, \
e w systemie naturalnym dwójkowym i systemie uzupełnieniowym do 2 mno\
enie przez stałą,
która jest sumą lub ró\
nicą potęg dwójki mo\
na wykonać jako dodawanie skalowanej mno\
nej.
Rozwiązanie: Oczywiste, to jest po prostu zwykły sekwencyjny algorytm mno\
enia.
C. Oblicz iloczyn liczb 4-cyfrowych podanych w dziesiętnym uzupełnieniowym systemie pełnym (U10):
a) 6745U10 × 8123U10 b) 9745U10 × 0823 U10 c) 3156 U10 × 8423 U10 d) 9994 U10 × 9916 U10
©Janusz Biernat, ARYT-ZADANIA-schematy 02 3 kwietnia 2004
15
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
Wskazówka: Wartość przypisana najbardziej znaczÄ…cej cyfrze liczby ujemnej jest ujemna i wynosi d - ²,
gdzie d jest standardowÄ… wartoÅ›ciÄ… cyfry (| ²-1 | = ²-1- ² = -1) (w systemie U10 | 9 | = -1).
©Janusz Biernat, ARYT-ZADANIA-schematy 02 3 kwietnia 2004
16
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
Lista nr 2
1. Oblicz iloczyn liczb 4-cyfrowych podanych w ósemkowym uzupełnieniowym systemie pełnym (U8):
a) 5745U8 × 7123U8 b) 7745U8 × 0723 U8 c) 3156 U8 × 6423 U8 d) 7774 U8 × 7716 U8
Wskazówka: Zauwa\
, \
e wartość przypisana najbardziej znaczącej cyfrze liczby ujemnej jest ujemna
i w systemie U8 wynosi d - 8, gdzie d jest standardową wartością cyfry, zatem | 7 |= -1.
2. Oblicz bezpośrednio metodą sekwencyjną ( kolejnych reszt ) z dokładnością do 4 pozycji znaczących
iloraz liczb reprezentowanych w systemie uzupełnieniowym pełnym
a) 01010011U2 : 1011U2 b) 1010011U2 : 01011U2 c) 876U10 : 176U10 d) 876U10 : 761U10.
Wskazówka: Nie zapomnij o skalowaniu, tak aby |X|<|D| oraz odwrotnym przeskalowaniu ilorazu. Aby
uniknąć generowania nieznaczących bitów, zadbaj aby |D/2|<|X|<|D|.
3. Wykonaj bezpośrednio w systemie U10 dzielenia z dokładnością do 4 cyfr znaczących ilorazu:
a) 110101 : 011011 b) 011101 : 110111 c) 101001 : 11111 d) 101001 : 10011
e) 1,10101 : 01101,1 f) 0,11101 : 110,111 g) 1010,01 : 111,11 h) 101001 : 100,11
Sprawdz
, wykonujÄ…c mno\
enie, poprawność otrzymanych wyników.
Wskazówka: Zauwa\
, \
e mo\
na tak przeskalować dzielnik (dzielną), aby iloraz był ułamkiem właściwym
4. Wykonaj bezpośrednio w kodzie U2 dzielenia z dokładnością do 4 cyfr znaczących ilorazu:
a) 110101 : 011011 b) 011101 : 110111 c) 101001 : 11111 d) 101001 : 10011
e) 1,10101 : 01101,1 f) 0,11101 : 110,111 g) 1010,01 : 111,11 h) 101001 : 100,11
Sprawdz
, wykonujÄ…c mno\
enie, poprawność otrzymanych wyników.
Wskazówka: Przeskaluj dzielnik (dzielną) tak, aby iloraz był ułamkiem.
5. Wykonaj w kodzie U2 z dokładnością do 4 cyfr znaczących ilorazu dzielenie nieodtwarzające liczb:
a) 110101 : 011011 b) 011101 : 110111 c) 101001 : 11111 d) 101001 : 10011
e) 1,10101 : 01101,1 f) 0,11101 : 110,111 g) 1010,01 : 111,11 h) 101001 : 100,11
Wskazówka: Przeskaluj dzielnik (dzielną) tak, aby iloraz był ułamkiem. Wykonaj pierwsze działanie
stosownie do znaków dzielnej i dzielnika (dodaj dzielnik gdy znaki są przeciwne).
6. Oblicz metodÄ… sekwencyjnÄ… ( kolejnych reszt ) pierwiastek kwadratowy z liczb
a) 1234567, b) 1010 0010 0111 11002, c) 98765432110 d) 123,4567, e) 10100 0100,1111 1002
z dokładnością do jednej, dwóch i siedmiu cyfr znaczących oraz podaj trzecią i czwartą resztę.
Uwaga: Zwróć uwagę na poprawne wstępne skalowanie.
7. Dane jest przybli\
enie pierwiastka kwadratowego z dokładnością do 3 cyfr znaczących i trzecia reszta.
Podaj dwie kolejne cyfry przybli\
enia pierwiastka, jeśli:
a) Q3 =1237, r3 =34567, b) Q3 =12310, r3 = 345610, c) Q3 =1012, r3 =111012,
©Janusz Biernat, ARYT-ZADANIA-schematy 02 3 kwietnia 2004
17
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
Wskazówka: Przeanalizuj nierówność, która jest podstawą obliczenia czwartej cyfry ilorazu  występuje
w niej podwojone skalowane trzecie przybli\
enie Q3 oraz reszta r3 :
8. Dane jest przybli\
enie pierwiastka kwadratowego z dokładnością do 4 cyfr znaczących i czwarta reszta
równa 0. Oszacuj wartość liczby pierwiastkowanej, jeśli: a) Q4 =12,347, b) Q4 =1,23410, c) Q4 =11012.
Wskazówka: Przeanalizuj nierówność, która jest podstawą obliczenia piątej cyfry ilorazu  występuje
w niej podwojone skalowane czwarte przybli\
enie Q4 oraz reszta r4. Zastanów się jaka musiała być
czwarta reszta, jeśli piąta jest zerem. Zauwa\
, \
e mo\
e istnieć wiele rozwiązań.
9. Oblicz metodÄ… nieodtwarzajÄ…cÄ… pierwiastek kwadratowy z liczb:
a) 1010 0010 0111 11002, b) 123,4568, c) 10100 0100,1111 1002
z dokładnością do dwóch i pięciu cyfr znaczących oraz podaj trzecią i czwartą resztę.
A* Poka\
, \
e w naturalnym systemie dwójkowym dzielenie przez stałą, która jest sumą lub ró\
nicÄ…
dwóch potęg dwójki, mo\
na wykonać przez odejmowanie, jeśli dzielenie nie wytwarza reszty.
Wskazówka: Przyjmij dla uproszczenia, \
e stałą jest 2m 1ą1. Zauwa\
, \
e wtedy X = (2m 1Ä…1)Q, skÄ…d
wynika, \
e Q = ą (X 2m 1Q), zatem wartości (k 1) najni\
szych bitów ilorazu są takie jak najni\
sze
bity dzielnej, a drugi argument odejmowania lub dodawania na wy\
szych pozycjach jest
sekwencyjnie wyznaczany jako wartość o (k 1) pozycji ni\
szego bitu obliczonych ju\
pozycji ilorazu.
©Janusz Biernat, ARYT-ZADANIA-schematy 02 3 kwietnia 2004
18
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
Lista nr 3
1. Twierdzenie Euklidesa o podzielności liczb orzeka, \
e największy wspólny podzielnik dwóch liczb
naturalnych jest podzielnikiem reszty z dzielenia większej przez mniejszą. Wyka\
, równowa\
ność tej
tezy z tezÄ…, \
e największy wspólny podzielnik dwóch liczb jest podzielnikiem ich ró\
nicy.
Wskazówka: Reszta jest wynikiem wielokrotnego odejmowania mniejszej od większej  tyle razy ile
wynosi iloraz. Ró\
nica jest więc równa wielokrotności mniejszej liczby + reszta...(XmodY=X kY2. Korzystając z twierdzenia Euklidesa znajdz
największy wspólny podzielnik liczb:
a) 6745 i 8123 b) 9994, 92 i 9916 c) 375, 243, 345 i 126 d) 220 1 oraz 25+1
Wskazówka: Zastosuj twierdzenie Euklidesa b) NWD(a,b,c)= NWD(NWD(a,b), NWD(b,c))
k k + 1
3. Poka\
, \
e liczby 2 + 1 i 2 + 1 są względnie pierwsze (k " N  jest liczbą naturalną)
k r
*Czy prawdziwe jest twierdzenie, \
e liczby 2 + 1 i 2 + 1 (k , r " N ) są względnie pierwsze?
k + 1 k k k
Wskazówka: Zastosuj twierdzenie Euklidesa. Zauwa\
, \
e 2 = 2 ×2 = 2 + 2
k k + 2
*Poka\
kontrprzykład  (21+1,23+1) = 3. Udowodnij, \
e gdy k jest nieparzyste, to (2 + 1 , 2 ) = 3 .
4* Wyka\
, \
e liczby (22n +1) oraz (2n +1) i (22n+1 + 2) i (2n -1) (n" N ) są względnie pierwsze.
Wskazówka: Zastosuj twierdzenie Euklidesa i związki potęg oraz wzory skróconego mno\
enia.
5. Nie wykonujÄ…c dzielenia wyznacz resztÄ™ z dzielenia liczby 1011 0011 0111 11012 przez
a) 11112 b) 100012 c) 111112 d) 100000012.
Wskazówka: Zastosuj właściwości kongruencji i zale\
ność (m ą 1) mod m = ą 1 .
6. Stosując reguły arytmetyki resztowej oblicz reszty całkowite (dodatnie lub ujemne) wobec modułów:
25710, 78 , 6510, 3F16, 1116, 0FF16 dla liczb 46528 i 0ABCD16, oraz ich sumy, ró\
nicy i iloczynu.
Wskazówka: Zastosuj właściwości kongruencji i zale\
ność (m ą 1) mod m = ą 1 .
7. Podaj reprezentacjÄ™ resztowÄ… liczby 2345610 w bazie: a) (29, 30, 31), b) (99, 100, 101), a) (63, 64, 65).
Wskazówka: Wyznacz reprezentację liczby w systemie o podstawie a) 30, b) 100, c) 64 oraz zastosuj
właściwości kongruencji i zale\
ność (m ą 1) mod m = ą 1 .
8* Znajdz
odwrotności multyplikatywne iloczynów par modułów bazy systemu resztowego (a 1, a, a+1)
względem trzeciego z nich, zakładając, \
e a jest liczbÄ… parzystÄ….
Wskazówka: Wykorzystaj zale\
ność (m ą 1) mod m = ą 1
9* Wektor (1, 2, 3) jest reprezentacja resztowÄ… liczby x w bazie (29, 30, 31). Znajdz
tÄ™ liczbÄ™ w zbiorze
kongruencji naturalnych (x"[0, M=29Å"30Å"31)) i caÅ‚kowitych (x" ðÅ‚ (M 1)ûÅ‚ /2, ðÅ‚M 1ûÅ‚ /2)).
©Janusz Biernat, ARYT-ZADANIA-schematy 02 3 kwietnia 2004
19
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
Wskazówka: Wykorzystując zale\
ność (m ą 1) mod m = ą 1 znajdz
odwrotności multyplikatywne
niepełnych iloczynów modułów bazy i zastosuj chińskie twierdzenie o resztach. Zauwa\
, \
e jeśli m0
jest najmniejszym modułem bazy, to (x, x, x, & , x) = x oraz ( x,  x,  x, & ,  x) =  x = M x, na
przykład zawsze jest (1, 1, 1, & , 1) = 1 oraz ( 1,  1,  1, & ,  1) =  1 = M  1, a tak\
e (m1 1, m2 1,
m3 1, & , mk 1) = M  1 =  1.
A. Zapisz w 32-bitowym formacie zmiennoprzecinkowym standardu IEEE 754 liczby o wartościach:
-61
a) 674,5318 b) 0,128 Å" 8-51 c)  0ABC,DE16 d) 10,1010101010U2 Å" 4
Wskazówka: Zapisz liczbę w systemie znak-moduł i tak przeskaluj, aby moduł był standardowy.
B. Zapisz w 32-bitowym formacie zmiennoprzecinkowym IEEE 754 pierwiastki kwadratowe z liczb:
a) 1010 0010, 0111 11002, b) 123,4568, c) 10100 0100, 1111 1002
Wskazówka: Pamiętaj o skalowaniu i bicie ukrytym.
C. Oblicz i zapisz w 32-bitowym formacie zmiennoprzecinkowym standardu IEEE 754 z dokładnością do
5 cyfr znaczÄ…cych pierwiastki kwadratowe z liczb danych w tym formacie:
a) 0 0100 0100 111 1100 1010 0010 0111 1100, b) 0 1010 0101 1111 1010 0100 1111 1111 1002
c) 0 0100 0101 111 1100 1010 0010 0111 1100, d) 0 1010 0100 1111 1010 0100 1111 1111 1002
Wskazówka: Zwróć uwagę na nieparzyste wykładniki. Pamiętaj o skalowaniu i bicie ukrytym.
D* Wyka\
, \
e w odejmowaniu (dodawaniu) zmiennoprzecinkowym operandów dokładnych, bit S dla
znormalizowanej ró\
nicy (sumy) mo\
e być wyznaczony przed wykonaniem działania.
Wskazówka: Rozpatrz przypadki składników o identycznych i ró\
nych wykładnikach.
E. Wyznacz z dokładnością do 4 bitów znacznika zaokrąglenia argumentów 1,101111011 i 1,101111001
uzupełnione bitami G, R, S. Wykonaj ich mno\
enie i porównaj z wynikiem pełnego mno\
enia.
Wskazówka: Bit G to bit piąty, bit R wynika z przybli\
enia do najbli\
szej (tu obojętne czy parzystej czy
nieparzystej, bit S wskazuje, czy na odcinanych pozycjach była choć jedna  1 .
F* Wyka\
, \
e w mno\
eniu znormalizowanych operandów, bit S znormalizowanego iloczynu mo\
e być
wyznaczony przed mno\
eniem. Poka\
, \
e jeden z czynników mo\
e być zdenormalizowany.
Wskazówka: Zauwa\
, \
e iloczyn ma tyle samo pozycji znaczÄ…cych, co ka\
dy z czynników, a co najmniej
jeden z czynników ma określony zakres (jest znormalizowany).
G* Oszacuj maksymalny błąd przybli\
enia ró\
nicy podczas odejmowania znormalizowanych operandów
obliczonych z taką samą dokładnością bezwzględną znacznika (mantysy).
Wskazówka: Zbadaj najgorszy przypadek. Wykorzystaj analizę z zad. D
©Janusz Biernat, ARYT-ZADANIA-schematy 02 3 kwietnia 2004
20
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
Lista nr 4
1. Stosując reguły działań w algebrze Boole a uprość poni\
sze wyra\
enia
a) x+(x•"y) b) xyz+(x•"y) +(z•"y) c) x+xy+xyz
d) zy+(x•"y) e) zx+z(x•"1) f) x+xy+(x•"yz)
Wskazówka: Zamień wyra\
enia zawierajÄ…ce •" na sumy iloczynów i zminimalizuj.
2. Na podstawie tabeli prawdy (tabeli wartości) funkcji logicznych f1 i f2 podaj ich wszystkie mintermy
(konstytuenty iloczynu) i maxtermy (konstytuenty sumy) oraz postaci formalne
x3 x2 x1 f1(x) x3 x2 x1 f2(x)
0 0 0 0 0 0 0 1
0 0 1 0 0 0 1 1
0 1 0 1 0 1 0 1
0 1 1 0 0 1 1 0
1 0 0 1 1 0 0 0
1 0 1 1 1 0 1 1
1 1 0 1 1 1 0 0
1 1 1 0 1 1 1 1
Wskazówka: Zapisz funkcje jako sumy iloczynów lub iloczyny sum. Upraszczaj wyra\
enia bezpośrednio
na podstawie podobieństw ciągów wartości zmiennych odpowiadających tej samej wartości funkcji,
np. f(x1, & , xi 1, Ć, xi+1, & , xn) = f(x1, & , xi 1, 0, xi+1, & , xn) + f(x1, & , xi 1, 1, xi+1, & , xn) .
3. Wyznacz funkcje dualne i komplementarne do funkcji f1(x) = x2 x1 + x3x2 i f2 (x) = x3x1 + x3(x2 + x1)
oraz ich sumy logicznej i iloczynu logicznego. Narysuj sieci logiczne realizujÄ…ce te funkcje.
Wskazówka: Zastosuj prawa de Morgana.
4. Korzystając z twierdzenia Shannona rozwiń wszystkie funkcje z zadania 3 względem zmiennej x3.
Wskazówka: Oblicz f(x3 = 0) oraz f(x3 = 1) i wyniki podstaw do wzoru Shannona.
5. Wyka\
, \
e wartość funkcji logicznej [zÅ"f(x)+(z•"f(x))] f(x) nie zale\
y od zmiennej z.
Wskazówka: Zamień wyra\
enie zawierajÄ…ce •" na sumÄ™ iloczynów i zminimalizuj lub poka\
, \
e ró\
nica
boole owska względem z wynosi 0.
6* Poka\
, \
e ka\
dÄ… funkcjÄ™ logicznÄ… mo\
na wyrazić za pomocą tylko funkcji NOR (suma negacji) lub
tylko funkcji NAND (iloczyn negacji).
Wskazówka: Przedstaw funkcje sumy, iloczynu i negacji za pomocą funkcji NOR lub NAND
7. Wyznacz charakterystyki AT sieci logicznych realizujacych funkcje dane przez wyra\
enia w zadaniu 1
Odpowiedz
: Wyznacz najdłu\
szą ście\
kę, policz bramki przeliczeniowe na tej ście\
ce (T) i wszystkie (A).
©Janusz Biernat, ARYT-ZADANIA-schematy 02 3 kwietnia 2004
21
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
8. Subtraktor 1-bitowy realizuje funkcje logiczne ró\
nicy d = f (x, y, z) i po\
yczki b = h (x, y, z)
równowa\
ne arytmetycznemu równaniu odejmowania 1-bitowego x  y  z =  2d + b
(x , y , z , d , b " {0, 1}) . Podaj tabelÄ™ prawdy subtraktora i wyznacz charakterystyki AT subtraktora 8-
bitowego.
Odpowiedz
: Opóz
nienie (T) oblicz osobno dla obu funkcji.
9. Sumator 1-bitowy realizuje funkcje logiczne sumy s = f (x, y, z) i przeniesienia c = h (x, y, z) równowa\
ne
arytmetycznemu równaniu dodawania 1-bitowego x + y + z = 2c + s (x , y , z , s , c " {0, 1}) . Zaprojektuj
ogniwo inkrementera realizujÄ…cego funkcje s = f (x, 1, z) oraz c = h (x, 1, z) i oblicz charakterystyki AT.
Wskazówka: Wyznacz i zminimalizuj funkcje sumy i przeniesienia.
A. Sumator warunkowy 1-bitowy realizuje alternatywne funkcje logiczne warunkowej sumy
s0 = f (x, y, 0), s1 = f (x, y, 1) i przeniesienia c0 = h (x, y, 0), c1 = h (x, y, 1) równowa\
ne arytmetycznemu
równaniu dodawania 1-bitowego przy zało\
eniu, \
e przeniesienie wejściowe jest odpowiednio równe
0 albo 1. Podaj tabelÄ™ prawdy sumatora i wyznacz te funkcje.
Wskazówka: Wyznacz i zminimalizuj funkcje sumy i przeniesienia.
B* Narysuj schemat logiczny sumatora 1-bitowego, którego wyjścia sumy i przeniesienia są wytwarzane
z u\
yciem multiplekserów sterowanych przeniesieniem wejściowym na podstawie funkcji sumy i
przeniesienia zerowego i jedynkowego s0 , s1 , c0 , c1 . Wyznacz charakterystyki AT tego układu.
Wskazówka: Wyznacz i zminimalizuj funkcje sumy i przeniesienia.
C* Poka\
, \
e charakterystyki AT sieci realizujÄ…cych funkcjÄ™ dualnÄ… i komplementarnÄ… sÄ… jednakowe.
Wskazówka: Wykorzystaj prawa de Morgana i równowa\
ność charakterystyk AT dla sumy logicznej
i iloczynu logicznego.
©Janusz Biernat, ARYT-ZADANIA-schematy 02 3 kwietnia 2004
22
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
Lista nr 5
1. Oblicz charakterystyki AT sumatorów uniwersalnych RCA dla kodów k-bitowych:
a) uzupełnieniowego pełnego (U2) b) uzupełnieniowego niepełnego (U1) c) znak-moduł,
d) spolaryzowanego ujemnie  +2k 1 e) spolaryzowanego dodatnio  +2k 1 1
Wskazówka: Wykorzystaj charakterystyki AT sumatora 1-bitowego.
2. Zaproponuj sposób kodowania cyfr i zaprojektuj sumator jedno- i cztero-pozycyjny dla systemu
a) U10 z kodowaniem cyfr w kodzie  +3 i kodzie BCD
b) dwójkowego negabazowego (² =  2),
c)* naturalnego trójkowego (² = 3) i dwójkowego z cyfrÄ… znakowanÄ… SD, (D={ 1,0,+1})
Wskazówka: a), b) wykorzystaj związki z sumatorem dwójkowym; c) wyznacz tabele prawdy.
3. Oblicz charakterystyki AT sumatora 24-bitowego z przeniesieniami przeskakującymi (carry-skip) jeśli
ma on strukturÄ™ a) 3-4-4-3-4-4-2, b) 3-3-4-4-4-3-3, c) 4-4-4-4-4-4, d) 6-6-6-6, e) optymalnÄ….
Wskazówka: Area: Oblicz liczbę ogniw sumatora i liczbę ogniw łańcucha przeskoku przeniesienia,
Time:Wyznacz ście\
ki krytyczne i oblicz opóz
nienie.
4. Zaprojektuj 8-bitowe układy inkrementacji i dekrementacji i wyznacz ich charakterystyki AT.
Wskazówka: Wykorzystaj charakterystyki 1-bitowego ogniwa inkrementera/dekrementera, wyznacz
najdłu\
sza scie\
kÄ™ propagacji przeniesienia.
5. Zaprojektuj 4- i 8-bitowy sumator sum warunkowych i wyznacz ich charakterystyki AT.
Wskazówka: Zauwa\
, \
e sumatory wejściowe są uproszczone, oblicz liczbę multiplekserów.
6. Zaprojektuj 4- i 8-bitowy sumator prefiksowy PPA i wyznacz ich charakterystyki AT.
Wskazówka: Oceń charakterystyki AT stopnia wejściowego, poziomu sieci PPA i stopnia wyjściowego.
7. W celu dodania n operandów k-bitowych u\
yto sumatora CSA (carry-save). Ile bitów zawiera suma?
Jakie jest opóz
nienie (T) podczas obliczania sumy, jeśli sumę końcową wytwarza
a) sumator ze skrośną propagacją przeniesień RCA, b) sumator sum warunkowych COSA.
Obliczenia wykonaj dla n = 7, 15, 31 oraz k = 8, 16, 32.
Wskazówka: Liczbę bitów sumy wyznacza jej zakres [0, n (2k  1)]. Liczba poziomów s d" (lg n/2) / lg 3/2.
Opóz
nienie jednego poziomu T=4 (do obu wyjść)
8. Ile poziomów musi zawierać sumator CSA u\
yty do redukcji iloczynów częściowych tworzonych
w mno\
eniu liczb 32-bitowych w kodzie naturalnym (NB)? Ile sumatorów elementarnych (3,2)
zawiera najbardziej skomplikowana gałąz
CSA odpowiadajÄ…ca bitom o tej samej wadze.
Wskazówka: Patrz poprzednie zadanie.
©Janusz Biernat, ARYT-ZADANIA-schematy 02 3 kwietnia 2004
23
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
9. Zaprojektuj sumator CSA dodający odpowiednio 3, 4 i 8 operandów 4-bitowych w kodzie U2.
Wskazówka: Nie zapomnij o bitach rozszerzenia. Sprawdz
skutki, jeśli bity te zostaną pominięte.
A. Wyznacz, uwzględniając czas końcowego dodawania, najkrótszy czas dodawania 32 operandów 64-
bitowych w sumatorze CSA jeśli dysponujesz:
c) reduktorami (3,2) generującymi przeniesienia 1-bitowe, wnoszące opóz
nienia T = 4 ka\
dy
d) *reduktorami (4,2) generującymi przeniesienia 2-bitowe, wnoszące opóz
nienia T = 6 ka\
dy
Wskazówka: *Oblicz liczbę poziomów i liczbę bitów końcowego dodawania.
D* Opracuj i uzasadnij algorytmy konwersji dwójkowo dziesiętnej liczb całkowitych dodatnich, bez
wykonywania dzielenia, jeśli cyfry dziesiętne są kodowane: a) w kodzie BCD, b) w kodzie BCD+3.
Wskazówka: Konwersja BCD na dwójkowy: Zbadaj skutki przesunięcia o jeden bit w prawo liczby k e" 2-
pozycyjnej w kodzie BCD. Konwersja dwójkowy na BCD/BCD+3: Wykorzystaj dodawanie.
E* Zaprojektuj generator reprezentacji resztowej liczby całkowitej 8- i 16-bitowej w kodzie NB
a) mod 11112 b) mod 100012 c) mod 1112 d) mod 10012
Uwaga: *Jest wiele argumentów wejściowych, które mają (b) i d)) ró\
ne znaki. Konieczne mo\
e być
u\
ycie bitów rozszerzenia.
F* Zaprojektuj generator reprezentacji resztowej liczby całkowitej 8- i 16-bitowej w kodzie U2
a) mod 11112 b) mod 100012 c) mod 1112 d) mod 10012
Wskazówka: Rozwa\
kongruencje w zbiorze liczb całkowitych. Zauwa\
, \
e najwy\
sz grupa bitów ma
k -2 k -2 s-1
znak - xk -12k -1 + xi 2i =2s (-xk -12k -1-s + xi 2i-s ) + xi 2i
" " "
i=0 i=s i=0
H. Zaprojektuj sumator mod (28 1) dwóch liczb całkowitych 8-bitowych w kodzie U2.
Wskazówka: Rozwa\
kongruencje w zbiorze liczb całkowitych.
G* Zaprojektuj sumatory mod (24 1) i mod (24+1) 4 liczb całkowitych 4-bitowych w kodzie U2.
Wskazówka: Rozwa\
kongruencje w zbiorze liczb całkowitych. Przeanalizuj struktury PPA.
©Janusz Biernat, ARYT-ZADANIA-schematy 02 3 kwietnia 2004
24
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
Lista nr 6
1. Zakoduj na 8 bitach według prostej i odwrotnej reguły Booth a w bazie 2 oraz w bazie 4 liczby:
a)  8710 b) +12110 c) 1011012 c) 1011101U2
Wskazówka: Zapisz liczby w systemie U2.
2. PrzyjmujÄ…c, \
e 6-bitowe operandy są dane w dwójkowym kodzie uzupełnieniowym a) pełnym (U2),
b) niepełnym (U1) i u\
ywajÄ…c mno\
nika przekodowanego wg reguły Booth a w bazie 2 i 4 wykonaj
mno\
enia: i) 110101×011011 ii) 011101×110111 iii) 101001×111111
Wskazówka: Nie zapomnij o bitach rozszerzenia iloczynów częściowych.
3. Oblicz charakterystyki AT matrycy mno\
Ä…cej dwa operandy: a) 4-bitowe, b) 8-bitowe c)* n-bitowe
Wskazówka: Policz liczbę elementarnych sumatorów oraz liczbę poziomów akumulacji.
4* Zaprojektuj matrycÄ™ mno\
Ä…cÄ… operandy 4-bitowe w kodzie U2 z wykorzystaniem przekodowania
mno\
nika wg reguły Bootha w bazie 4. Porównaj z innymi układami matrycowymi.
Wskazówka: Zaprojektuj element podstawowy matrycy.
5. Oblicz charakterystyki AT sumatora CSA u\
ytego do redukcji iloczynów częściowych w mno\
eniu
operandów 4-, 8- bitowych danych: a) w kodzie NB, b) w kodzie U2 z eliminacją bitów rozszerzenia.
*Podaj oszacowanie charakterystyk AT dla mno\
enia operandów n-bitowych.
Wskazówka: Ad b) zauwa\
, \
e ka\
dy operand ma innÄ… wagÄ™.
6. W dzieleniu w systemie naturalnym w bazie 4 skalowana reszta częściowa ma wartość 2,2D. Wyznacz:
analitycznie i na podstawie parametrycznego wykresu dzielenia, kolejne dwie cyfry ilorazu.
Wskazówka: a) rozwią\
dwa kolejne równania dzielenia; b) zaznacz resztę na osi odciętych i graficznie
znajdz
kolejną resztę (pierwsze odwzorowanie wg odcinka  q=2 ), przeskaluj ją i powtórz czynności.
7. W dzieleniu w systemie U2 przeskalowana reszta częściowa ma wartość: i)  0,2D, ii) +0,7D.
Wyznacz: analitycznie i na podstawie parametrycznego wykresu dzielenia kolejne dwie cyfry ilorazu,
zakładając, \
e dzielnik D jest: a) ujemny, b) dodatni.
Wskazówka: Patrz poprzednie zadanie.
8. Wykonaj bezpośrednio w kodzie U2 dzielenia z dokładnością do 4 cyfr znaczących ilorazu:
a) 110101 : 011011 b) 011101 : 110111 c) 101001 : 11111 d) 101001 : 10011
e) 1,10101 : 01101,1 f) 0,11101 : 110,111 g) 1010,01 : 111,11 h) 101001 : 100,11
Sprawdz
, wykonujÄ…c mno\
enie, poprawność otrzymanych wyników.
Wskazówka: Nie zapomnij przeskalować dzielnej (i/lub dzielnika)
©Janusz Biernat, ARYT-ZADANIA-schematy 02 3 kwietnia 2004
25
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
9. Wykonaj wykres P-D dla dzielenia w bazie 4 i dzielnika z zakresu [1,2). Podaj ile bitów musi być
porównywanych w celu wyznaczenia cyfr ilorazu.
Wskazówka:
A. Oblicz charakterystyki AT matryc dzielÄ…cych operandy 8-bitowe w kodzie NB i U2
Wskazówka: Przeanalizuj pełną ście\
kÄ™ propagacji przeniesienia.
B. Oblicz metodÄ… Newtona iloraz 3,1416 :2,7183.
Wskazówka: Wybierz pierwsze przybli\
enie
C. Oceń czas obliczania pierwiastka kwadratowego z liczby całkowitej metodą sekwencyjną ( kolejnych
reszt ) oraz na podstawie to\
samości:  suma n kolejnych nieparzystych liczb naturalnych jest równa
kwadratowi z ich liczby (np. 1+3+5=32 1+3+5+7=42, 1+3+5+7+9=52 itd.)
*Określ minimalny czas obliczeń, jeśli liczba jest zakodowana odpowiednio na 8, 16, 32 bitach.
i=k i=k -1
Wskazówka: Zauwa\
, \
e "k = X - (2i +1) = [X - (2i +1)] - (2k +1) = "k -1 - (2k +1) , więc
" "
i=0 i=0
oszacowaniem pierwiastka jest takie k, przy którym odstęp sumy od X zmienia znak.
D* Oszacuj liczbę kroków algorytmu CORDIC potrzebnych do obliczenia wartości funkcji exp, ln, sin,
cos, arctg dla argumentu z przedziału [ 1,1] z dokładnością do 32 bitów części ułamkowej.
Wskazówka: Zastosuj odpowiednio wzory.
E* Oceń czas obliczania pierwiastka trzeciego stopnia na podstawie algorytmu opartego na zale\
ności:
n n n j-1 n-1 j
2
n3 - n =
"(3Å"i - 3Å"i) = 3"(i Å" (i -1)) = 3""2i = 6""i
i=1 i=1 j=1 i=0 j=1 i=1
Wskazówka: Zauwa\
związek sumy zewnętrznej z wewnętrzną.
©Janusz Biernat, ARYT-ZADANIA-schematy 02 3 kwietnia 2004
26