Rok I
ARYTMETYKA KOMPUTERÓW
Lista nr
0
©Janusz Biernat, ARYT-ZADANIA-schematy’02
3 kwietnia 2004
0
1. Znajd
ź podstawę x systemu naturalnego, w którym: a)
5
41
=
x
, b)
4
22
=
x
c) a
2
=301
x
, d) b
2
=562
x
2. Znajd
ź podstawę
β
systemu naturalnego, w którym liczby naturalne x
1
oraz x
2
s
ą rozwiązaniami
równania ax
2
+ bx+c = 0. Wykonaj obliczenia dla x
1
= 5
β
, x
2
= 8
β
i równania 5
β
x
2
– 50
β
x+125
β
= 0
3* Znajd
ź podstawę systemu naturalnego, w którym x
1
, x
2
∈
s
ą rozwiązaniami równania ax
2
+ bx+c = 0
gdzie a,b,c
∈
(całkowite).**Rozwi
ąŜ zadanie jeśli wiadomo, Ŝe w tym systemie a,x
1
,x
2
s
ą liczbami
jednocyfrowymi, b jest liczb
ą dwucyfrową b = b
1
β
+b
0
, za
ś c jest liczbą o postaci c = c
2
β
2
+ c
1
β
+c
0
,
c
2
= 0 lub 1. Wykonaj obliczenia dla x
1
= 5
β
, x
2
= 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. Przeprowad
ź konwersje podstawy (bazy), z dokładnością do 4 cyfr części ułamkowej wyniku:
a) 674,581
10
= (…)
16
= (…)
4
b) 0CD,12
16
= (…)
2
= (…)
10
c) 3,012
8
= … (…)
2
…= (…)
16
d) 34,56
10
×
2
–5
= (…)
2
= (…)
16
e) 102,21
3
×
5
–2
= (…)
5
f) 0BACA
16
×
5
–3
= (…)
10
g) 6745,81
9
= (…)
7
= (…)
10
h) 0AA,12
11
= (…)
10
= (…)
9
i) 102,21
3
×
15
–2
= (…)
5
j) 34
7
/56
7
= (…)
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
źródłowej, który nie jest podzielnikiem podstawy
docelowej.
9. Przeprowad
ź 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
Rok I
ARYTMETYKA KOMPUTERÓW
Lista nr
1
©Janusz Biernat, ARYT-ZADANIA-schematy’02
3 kwietnia 2004
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”.
Rok I
ARYTMETYKA KOMPUTERÓW
Lista nr
2
©Janusz Biernat, ARYT-ZADANIA-schematy’02
3 kwietnia 2004
2
1. Zapisz w systemie uzupełnieniowym do 2 (U2) z czterema bitami cz
ęści ułamkowej liczby:
a) – 674,581
10
b) – 0A,12
16
c) – 3,012
8
d) + 34,56
10
e) 4,56
10
– 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
mo
Ŝna wykonać przez grupowanie (
β
→
β
S
) lub dekompozycj
ę cyfr (
β
S
→
β
).
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 „+2
k–1
–1”
f) spolaryzowanym „+2
k–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..?? Sprawd
ź, czy w ich dodawaniu i odejmowaniu wystąpi nadmiar.
7. Korzystaj
ąc z zaleŜności
Y
X
Y
X
+
=
−
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) 10011101
2
– 01111001
2
Sprawd
ź 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) 6745
U10
×
8123
U10
b) 9745
U10
×
0823
U10
c) 3156
U10
×
8423
U10
d) 9994
U10
×
9916
U10
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
©Janusz Biernat, ARYT-ZADANIA-schematy’02
3 kwietnia 2004
4
1. Oblicz iloczyn liczb 4-cyfrowych podanych w ósemkowym uzupełnieniowym systemie pełnym (U8):
a) 5745
U8
×
7123
U8
b) 7745
U8
×
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) 01010011
U2
: 1011
U2
b) 1010011
U2
: 01011
U2
c) 876
U10
: 176
U10
d) 876
U10
: 761
U10
.
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
Sprawd
ź, 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
Sprawd
ź, 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) 123456
7
, b) 1010 0010 0111 1100
2
, c) 987654321
10
d) 123,456
7
, e) 10100 0100,1111 100
2
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) Q
3
=123
7
, r
3
=3456
7
, b) Q
3
=123
10
, r
3
= 3456
10
, c) Q
3
=101
2
, r
3
=11101
2
,
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) Q
4
=12,34
7
, b) Q
4
=1,234
10
, c) Q
4
=1101
2
.
9. Oblicz metod
ą nieodtwarzającą pierwiastek kwadratowy z liczb:
a) 1010 0010 0111 1100
2
, b) 123,456
8
, c) 10100 0100,1111 100
2
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.
Rok I
ARYTMETYKA KOMPUTERÓW
Lista nr
5
©Janusz Biernat, ARYT-ZADANIA-schematy’02
3 kwietnia 2004
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 znajdź największy wspólny podzielnik liczb:
a) 6745 i 8123
b) 9994, 92 i 9916
c) 375, 243, 345 i 126
d) 2
20
–1 oraz 2
5
+1
3. Poka
Ŝ, Ŝe liczby 2
k
+ 1 i 2
k + 1
+ 1 s
ą względnie pierwsze (k
∈
N – jest liczb
ą naturalną)
*Czy prawdziwe jest twierdzenie,
Ŝe liczby 2
k
+ 1 i 2
r
+ 1 (k , r
∈
N ) s
ą względnie pierwsze?
4* Wyka
Ŝ, Ŝe liczby
)
1
2
(
2
+
n
oraz
)
1
2
(
+
n
i
)
2
2
(
1
2
+
+
n
i
)
1
2
(
−
n
(n
∈
N ) s
ą względnie pierwsze.
5. Nie wykonuj
ąc dzielenia wyznacz resztę z dzielenia liczby 1011 0011 0111 1101
2
przez
a) 1111
2
b) 10001
2
c) 11111
2
d) 10000001
2
.
6. Stosuj
ąc reguły arytmetyki resztowej oblicz reszty całkowite (dodatnie lub ujemne) wobec modułów:
257
10
, 7
8
, 65
10
, 3F
16
, 11
16
, 0FF
16
dla liczb 4652
8
i 0ABCD
16
, oraz ich sumy, ró
Ŝnicy i iloczynu.
7. Podaj reprezentacj
ę resztową liczby 23456
10
w bazie: a) (29, 30, 31), b) (99, 100, 101), a) (63, 64, 65).
8* Znajd
ź 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). Znajdź 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:
a) 674,531
8
b) 0,12
8
⋅
8
-51
c) – 0ABC,DE
16
d) 10,1010101010
U2
⋅
4
-61
B. Zapisz w 32-bitowym formacie zmiennoprzecinkowym IEEE 754 pierwiastki kwadratowe z liczb:
a) 1010 0010, 0111 1100
2
, b) 123,456
8
, c) 10100 0100, 1111 100
2
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 100
2
c) 0 0100 0101 111 1100 1010 0010 0111 1100, d) 0 1010 0100 1111 1010 0100 1111 1111 100
2
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).
Rok I
ARYTMETYKA KOMPUTERÓW
Lista nr
6
©Janusz Biernat, ARYT-ZADANIA-schematy’02
3 kwietnia 2004
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 f
1
i f
2
(tzw. tabel prawdy) podaj ich wszystkie
mintermy (konstytuenty iloczynu) i maxtermy (konstytuenty sumy) oraz postaci formalne
x
3
x
2
x
1
f
1
(x)
x
3
x
2
x
1
f
2
(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
2
3
1
2
1
)
(
x
x
x
x
f
+
=
x
i
)
(
)
(
1
2
3
1
3
2
x
x
x
x
x
f
+
+
=
x
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 x
3
.
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 s
0
= f (x, y, 0), s
1
= f (x, y, 1)
i przeniesienia c
0
= h (x, y, 0), c
1
= 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 s
0
, s
1
, c
0
, c
1
. Wyznacz charakterystyki AT tego układu.
C* Poka
Ŝ, Ŝe charakterystyki AT sieci realizujących funkcję dualną i komplementarną są jednakowe.
Rok I
ARYTMETYKA KOMPUTERÓW
Lista nr
7
©Janusz Biernat, ARYT-ZADANIA-schematy’02
3 kwietnia 2004
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 „+2
k–1
”
e) spolaryzowanego dodatnio „+2
k–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ó
ź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ł
ąź 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óźnienia T = 4
ka
Ŝdy
b) *reduktorami (4,2) generuj
ącymi przeniesienia 2-bitowe, wnoszące opóź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 1111
2
b) mod 10001
2
c) mod 111
2
d) mod 1001
2
D* Zaprojektuj generator reprezentacji resztowej liczby całkowitej 8- i 16-bitowej w kodzie U2
a) mod 1111
2
b) mod 10001
2
c) mod 111
2
d) mod 1001
2
E. Zaprojektuj sumator mod (2
8
–1) dwóch liczb całkowitych 8-bitowych w kodzie U2.
F* Zaprojektuj sumatory mod (2
4
–1) i mod (2
4
+1) 4 liczb całkowitych 4-bitowych w kodzie U2.
Rok I
ARYTMETYKA KOMPUTERÓW
Lista nr
8
©Janusz Biernat, ARYT-ZADANIA-schematy’02
3 kwietnia 2004
8
1. Zakoduj na 8 bitach według prostej i odwrotnej reguły Booth’a w bazie 2 oraz w bazie 4 liczby:
a) –87
10
b) +121
10
c) 101101
2
c) 1011101
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
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
Sprawd
ź, 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=3
2
1+3+5+7=4
2
, 1+3+5+7+9=5
2
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:
∑∑
∑∑
∑
∑
−
=
=
=
−
=
=
=
=
=
−
⋅
=
⋅
−
⋅
=
−
1
1
1
1
1
0
1
1
2
3
6
2
3
))
1
(
(
3
)
3
3
(
n
j
j
i
n
j
j
i
n
i
n
i
i
i
i
i
i
i
n
n
Rok I
ARYTMETYKA KOMPUTERÓW
Lista nr
9
©Janusz Biernat, ARYT-ZADANIA-schematy’02
3 kwietnia 2004
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. Przeprowad
ź konwersję na system o podstawie
β
= 7 wyniku działania X
+
Y, X
−
Y, Y
−
X, 2X
−
Y, je
śli
X = 10101,011
U2
oraz Y = 0 1011,101
U2
.
Rok I
ARYTMETYKA KOMPUTERÓW
rozwi
ązania
©Janusz Biernat, ARYT-ZADANIA-schematy’02
3 kwietnia 2004
10
Lista nr 0
1. Znajd
ź podstawę x systemu naturalnego, w którym: a)
5
41
=
x
, b)
4
22
=
x
c) a
2
=301
x
, d) b
2
=562
x
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 5
x
×
5
x
=41
x
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–z
2
)
=
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–z
2
)).
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ą
liczby b jest 2. Mamy st
ąd równanie (2
β
+z
)
2
=
5
β
2
+6
β
+2, czyli
β
2
+(6–4z)
β
+(2–z
2
)
=
0 z warunkiem
β
> 6 , a poniewa
Ŝ z nie moŜe być równe 1 (bo wtedy
β
=
–1), iloczyn pierwiastków (2–z
2
) 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. Znajd
ź podstawę
β
systemu naturalnego, w którym liczby naturalne x
1
oraz x
2
s
ą rozwiązaniami
równania ax
2
+ bx+c = 0. Wykonaj obliczenia dla x
1
= 5
β
, x
2
= 8
β
i równania 5
β
x
2
– 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
β
(
x
1
+x
2
) =
50
β
, sk
ąd natychmiast wynika (5
β
×
10
β
=50
β
)
Ŝe x
1
+x
2
= 10
β
=
β
. Trzeba jeszcze sprawdzi
ć, czy 5
13
×
(5
13
×
8
13
) = 125
13
(OK., bo 13
2
+2
×
13+1 = 200).
*Je
śli rozwiązania równania x
2
– 15
β
x+53
β
= 0 s
ą naturalne, to x
1
+ x
2
=
β
+ 5 oraz
=
x
1
x
2
=
5
β
+ 3.
Musi wi
ęc być x
1
> 5 oraz x
2
<
β
(w przeciwnym razie jeden musi by
ć ujemny) Jeśli x
1
= 6 , x
2
=
β
− 1
,
to
β
=
9
.
(powinny by
ć dwa symetryczne rozwiązania dla x
1
oraz x
2
– jedno rozwi
ązanie dla
β
).
3* Znajd
ź podstawę systemu naturalnego, w którym x
1
, x
2
∈
s
ą rozwiązaniami równania ax
2
+ bx+c = 0
gdzie a,b,c
∈
(całkowite).**Rozwi
ąŜ zadanie jeśli wiadomo, Ŝe w tym systemie a,x
1
,x
2
s
ą liczbami
jednocyfrowymi, b jest liczb
ą dwucyfrową b = b
1
β
+b
0
, za
ś c jest liczbą o postaci c = c
2
β
2
+ c
1
β
+c
0
,
c
2
= 0 lub 1. Wykonaj obliczenia dla x
1
= 5
β
, x
2
= 8
β
oraz a = 1 lub 3.
Rok I
ARYTMETYKA KOMPUTERÓW
rozwi
ązania
©Janusz Biernat, ARYT-ZADANIA-schematy’02
3 kwietnia 2004
11
Wskazówka: *Na podstawie wzorów Viete’y uło
Ŝyć układ równań względem nieznanej podstawy
β
i nieznanego drugiego pierwiastka x
2
: – a
(
x
1
+ x
2
) =
b oraz a x
1
x
2
=
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,53
9
= 0,1210
3
7. Przeprowad
ź konwersje podstawy (bazy), z dokładnością do 4 cyfr części ułamkowej wyniku:
a) 674,581
10
= (…)
16
= (…)
4
b) 0CD,12
16
= (…)
2
= (…)
10
c) 3,012
8
= … (…)
2
…= (…)
16
d) 34,56
10
×
2
–5
= (…)
2
= (…)
16
e) 102,21
3
×
5
–2
= (…)
5
f) 0BACA
16
×
5
–3
= (…)
10
g) 6745,81
9
= (…)
7
= (…)
10
h) 0AA,12
11
= (…)
10
= (…)
9
i) 102,21
3
×
15
–2
= (…)
5
j) 34
7
/56
7
= (…)
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 ź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
Rok I
ARYTMETYKA KOMPUTERÓW
rozwi
ązania
©Janusz Biernat, ARYT-ZADANIA-schematy’02
3 kwietnia 2004
12
istnieje nierozkła-dalny podzielnik podstawy
źródłowej, który nie jest podzielnikiem podstawy
docelowej.
Wskazówka: Znajd
ź 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,5
10
= 0,1
2
, ale np. 0,1
10
= 0,(00011)
2
.
9. Przeprowad
ź 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
=
0,3 + 0,03 + … = = 0,3 / ( 1 – 0,1 ) =
1
/
3
= 0,1
3
, 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: Sprawd
ź, 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”.
Odpowied
ź: 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.
Rok I
ARYTMETYKA KOMPUTERÓW
rozwi
ązania
©Janusz Biernat, ARYT-ZADANIA-schematy’02
3 kwietnia 2004
13
Rok I
ARYTMETYKA KOMPUTERÓW
rozwi
ązania
©Janusz Biernat, ARYT-ZADANIA-schematy’02
3 kwietnia 2004
14
Lista nr 1
1. Zapisz w systemie uzupełnieniowym do 2 (U2) z czterema bitami cz
ęści ułamkowej liczby:
a) – 674,581
10
b) – 0A,12
16
c) – 3,012
8
d) + 34,56
10
e) 4,56
10
– 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
mo
Ŝna wykonać przez grupowanie (
β
→
β
S
) lub dekompozycj
ę cyfr (
β
S
→
β
).
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 „+2
k–1
–1”
f) spolaryzowanym „+2
k–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.
Rok I
ARYTMETYKA KOMPUTERÓW
rozwi
ązania
©Janusz Biernat, ARYT-ZADANIA-schematy’02
3 kwietnia 2004
15
6. Znanych jest kilka najbardziej znacz
ących bitów liczb 48-bitowych w kodzie uzupełnieniowym U2.
11101010..?? oraz 10011110..?? Sprawd
ź, czy w ich dodawaniu i odejmowaniu wystąpi nadmiar.
Wskazówka: Nale
Ŝy znaleźć 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
Y
X
Y
X
+
=
−
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) 10011101
2
– 01111001
2
Sprawd
ź 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,
β
2
m
–2
β
m
+1<
β
2
m
–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 [–2
m–1
×
(2
m–1
–1), (–2
m–1
)
2
]= [–2
2m–2
+2
m–1
, 2
2m–2
]. Liczba 2
2m–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) 6745
U10
×
8123
U10
b) 9745
U10
×
0823
U10
c) 3156
U10
×
8423
U10
d) 9994
U10
×
9916
U10
Rok I
ARYTMETYKA KOMPUTERÓW
rozwi
ązania
©Janusz Biernat, ARYT-ZADANIA-schematy’02
3 kwietnia 2004
16
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
).
Rok I
ARYTMETYKA KOMPUTERÓW
rozwi
ązania
©Janusz Biernat, ARYT-ZADANIA-schematy’02
3 kwietnia 2004
17
Lista nr 2
1. Oblicz iloczyn liczb 4-cyfrowych podanych w ósemkowym uzupełnieniowym systemie pełnym (U8):
a) 5745
U8
×
7123
U8
b) 7745
U8
×
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) 01010011
U2
: 1011
U2
b) 1010011
U2
: 01011
U2
c) 876
U10
: 176
U10
d) 876
U10
: 761
U10
.
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
Sprawd
ź, 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
Sprawd
ź, 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) 123456
7
, b) 1010 0010 0111 1100
2
, c) 987654321
10
d) 123,456
7
, e) 10100 0100,1111 100
2
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) Q
3
=123
7
, r
3
=3456
7
, b) Q
3
=123
10
, r
3
= 3456
10
, c) Q
3
=101
2
, r
3
=11101
2
,
Rok I
ARYTMETYKA KOMPUTERÓW
rozwi
ązania
©Janusz Biernat, ARYT-ZADANIA-schematy’02
3 kwietnia 2004
18
Wskazówka: Przeanalizuj nierówno
ść, która jest podstawą obliczenia czwartej cyfry ilorazu – występuje
w niej podwojone skalowane trzecie przybli
Ŝenie Q
3
oraz reszta r
3
:
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) Q
4
=12,34
7
, b) Q
4
=1,234
10
, c) Q
4
=1101
2
.
Wskazówka: Przeanalizuj nierówno
ść, która jest podstawą obliczenia piątej cyfry ilorazu – występuje
w niej podwojone skalowane czwarte przybli
Ŝenie Q
4
oraz reszta r
4
. 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 1100
2
, b) 123,456
8
, c) 10100 0100,1111 100
2
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 2
m–1
±
1. Zauwa
Ŝ, Ŝe wtedy X = (2
m–1
±
1)Q, sk
ąd
wynika,
Ŝe Q =
±
(X–2
m–1
Q), 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.
Rok I
ARYTMETYKA KOMPUTERÓW
rozwi
ązania
©Janusz Biernat, ARYT-ZADANIA-schematy’02
3 kwietnia 2004
19
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– kY<Y)
2. Korzystaj
ąc z twierdzenia Euklidesa znajdź największy wspólny podzielnik liczb:
a) 6745 i 8123
b) 9994, 92 i 9916
c) 375, 243, 345 i 126
d) 2
20
–1 oraz 2
5
+1
Wskazówka: Zastosuj twierdzenie Euklidesa b) NWD(a,b,c)= NWD(NWD(a,b), NWD(b,c))
3. Poka
Ŝ, Ŝe liczby 2
k
+ 1 i 2
k + 1
+ 1 s
ą względnie pierwsze (k
∈
N – jest liczb
ą naturalną)
*Czy prawdziwe jest twierdzenie,
Ŝe liczby 2
k
+ 1 i 2
r
+ 1 (k , r
∈
N ) s
ą względnie pierwsze?
Wskazówka: Zastosuj twierdzenie Euklidesa. Zauwa
Ŝ, Ŝe 2
k + 1
= 2
×
2
k
= 2
k
+ 2
k
*Poka
Ŝ kontrprzykład – (2
1
+1,2
3
+1) = 3. Udowodnij,
Ŝe gdy k jest nieparzyste, to (2
k
+ 1 , 2
k + 2
) = 3 .
4* Wyka
Ŝ, Ŝe liczby
)
1
2
(
2
+
n
oraz
)
1
2
(
+
n
i
)
2
2
(
1
2
+
+
n
i
)
1
2
(
−
n
(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 1101
2
przez
a) 1111
2
b) 10001
2
c) 11111
2
d) 10000001
2
.
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:
257
10
, 7
8
, 65
10
, 3F
16
, 11
16
, 0FF
16
dla liczb 4652
8
i 0ABCD
16
, 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 23456
10
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* Znajd
ź 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). Znajdź tę liczbę w zbiorze
kongruencji naturalnych (x
∈
[0, M=29
⋅
30
⋅
31)) i całkowitych (x
∈
–(M–1) /2, M–1 /2)).
Rok I
ARYTMETYKA KOMPUTERÓW
rozwi
ązania
©Janusz Biernat, ARYT-ZADANIA-schematy’02
3 kwietnia 2004
20
Wskazówka: Wykorzystuj
ąc zaleŜność (m
±
1) mod m =
±
1 znajd
ź odwrotności multyplikatywne
niepełnych iloczynów modułów bazy i zastosuj chi
ńskie twierdzenie o resztach. ZauwaŜ, Ŝe jeśli m
0
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 (m
1
–1, m
2
– 1,
m
3
– 1, … , m
k
– 1) = M –1 = –1.
A. Zapisz w 32-bitowym formacie zmiennoprzecinkowym standardu IEEE 754 liczby o warto
ściach:
a) 674,531
8
b) 0,12
8
⋅
8
-51
c) – 0ABC,DE
16
d) 10,1010101010
U2
⋅
4
-61
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 1100
2
, b) 123,456
8
, c) 10100 0100, 1111 100
2
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 100
2
c) 0 0100 0101 111 1100 1010 0010 0111 1100, d) 0 1010 0100 1111 1010 0100 1111 1111 100
2
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
Rok I
ARYTMETYKA KOMPUTERÓW
rozwi
ązania
©Janusz Biernat, ARYT-ZADANIA-schematy’02
3 kwietnia 2004
21
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 f
1
i f
2
podaj ich wszystkie mintermy
(konstytuenty iloczynu) i maxtermy (konstytuenty sumy) oraz postaci formalne
x
3
x
2
x
1
f
1
(x)
x
3
x
2
x
1
f
2
(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(x
1
, … , x
i–1
,
φ
, x
i+1
, … , x
n
) = f(x
1
, … , x
i–1
,
0
, x
i+1
, … , x
n
) + f(x
1
, … , x
i–1
,
1
, x
i+1
, … , x
n
) .
3. Wyznacz funkcje dualne i komplementarne do funkcji
2
3
1
2
1
)
(
x
x
x
x
f
+
=
x
i
)
(
)
(
1
2
3
1
3
2
x
x
x
x
x
f
+
+
=
x
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 x
3
.
Wskazówka: Oblicz f(x
3
= 0) oraz f(x
3
= 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
Odpowied
ź: Wyznacz najdłuŜszą ścieŜkę, policz bramki przeliczeniowe na tej ścieŜce (T) i wszystkie (A).
Rok I
ARYTMETYKA KOMPUTERÓW
rozwi
ązania
©Janusz Biernat, ARYT-ZADANIA-schematy’02
3 kwietnia 2004
22
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.
Odpowied
ź: Opóź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
s
0
= f (x, y, 0), s
1
= f (x, y, 1) i przeniesienia c
0
= h (x, y, 0), c
1
= 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 s
0
, s
1
, c
0
, c
1
. 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.
Rok I
ARYTMETYKA KOMPUTERÓW
rozwi
ązania
©Janusz Biernat, ARYT-ZADANIA-schematy’02
3 kwietnia 2004
23
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 „+2
k–1
”
e) spolaryzowanego dodatnio „+2
k–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óź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ó
ź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 (2
k
–1)]. Liczba poziomów s
≤
(lg n/2) / lg 3/2.
Opó
ź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ł
ąź CSA odpowiadająca bitom o tej samej wadze.
Wskazówka: Patrz poprzednie zadanie.
Rok I
ARYTMETYKA KOMPUTERÓW
rozwi
ązania
©Janusz Biernat, ARYT-ZADANIA-schematy’02
3 kwietnia 2004
24
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. Sprawd
ź 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óźnienia T = 4
ka
Ŝdy
d) *reduktorami (4,2) generuj
ącymi przeniesienia 2-bitowe, wnoszące opóź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
≥
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 1111
2
b) mod 10001
2
c) mod 111
2
d) mod 1001
2
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 1111
2
b) mod 10001
2
c) mod 111
2
d) mod 1001
2
Wskazówka: Rozwa
Ŝ kongruencje w zbiorze liczb całkowitych. ZauwaŜ, Ŝe najwyŜsz grupa bitów ma
znak
∑
∑
∑
−
=
−
=
−
−
−
−
−
=
−
−
+
+
−
=
+
−
1
0
2
1
1
2
0
1
1
2
)
2
2
(
2
2
2
s
i
i
i
k
s
i
s
i
i
s
k
k
s
k
i
i
i
k
k
x
x
x
x
x
H. Zaprojektuj sumator mod (2
8
–1) dwóch liczb całkowitych 8-bitowych w kodzie U2.
Wskazówka: Rozwa
Ŝ kongruencje w zbiorze liczb całkowitych.
G* Zaprojektuj sumatory mod (2
4
–1) i mod (2
4
+1) 4 liczb całkowitych 4-bitowych w kodzie U2.
Wskazówka: Rozwa
Ŝ kongruencje w zbiorze liczb całkowitych. Przeanalizuj struktury PPA.
Rok I
ARYTMETYKA KOMPUTERÓW
rozwi
ązania
©Janusz Biernat, ARYT-ZADANIA-schematy’02
3 kwietnia 2004
25
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) –87
10
b) +121
10
c) 101101
2
c) 1011101
U2
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
znajd
ź 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
Sprawd
ź, wykonując mnoŜenie, poprawność otrzymanych wyników.
Wskazówka: Nie zapomnij przeskalowa
ć dzielnej (i/lub dzielnika)
Rok I
ARYTMETYKA KOMPUTERÓW
rozwi
ązania
©Janusz Biernat, ARYT-ZADANIA-schematy’02
3 kwietnia 2004
26
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=3
2
1+3+5+7=4
2
, 1+3+5+7+9=5
2
itd.)
*Okre
śl minimalny czas obliczeń, jeśli liczba jest zakodowana odpowiednio na 8, 16, 32 bitach.
Wskazówka: Zauwa
Ŝ, Ŝe
)
1
2
(
)
1
2
(
]
)
1
2
(
[
)
1
2
(
1
1
0
0
+
−
∆
=
+
−
+
−
=
+
−
=
∆
−
−
=
=
=
=
∑
∑
k
k
i
X
i
X
k
k
i
i
k
i
i
k
, wi
ęc
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:
∑∑
∑∑
∑
∑
−
=
=
=
−
=
=
=
=
=
−
⋅
=
⋅
−
⋅
=
−
1
1
1
1
1
0
1
1
2
3
6
2
3
))
1
(
(
3
)
3
3
(
n
j
j
i
n
j
j
i
n
i
n
i
i
i
i
i
i
i
n
n
Wskazówka: Zauwa
Ŝ związek sumy zewnętrznej z wewnętrzną.