Rok I
ARYTMETYKA KOMPUTERÓW
Lista nr
0
©Janusz Biernat, ARYT-ZADANIA-schematy’02
25 pa
ździernika 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
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
1
©Janusz Biernat, ARYT-ZADANIA-schematy’02
25 pa
ździernika 2004
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ł.
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 2
m
pozycjach.
9. Wynik mno
Ŝenia
m
–bitowych liczb w kodzie U2 jest kodowany na 2
m
–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
2
©Janusz Biernat, ARYT-ZADANIA-schematy’02
25 pa
ździernika 2004
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
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
3
©Janusz Biernat, ARYT-ZADANIA-schematy’02
25 pa
ździernika 2004
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.
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
4
©Janusz Biernat, ARYT-ZADANIA-schematy’02
25 pa
ździernika 2004
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) z
x
+
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
2a. Ułó
Ŝ
tabele prawdy dla funkcji nadmiaru w dodawaniu / odejmowaniu w kodzie U2 i podaj wyra
Ŝ
enie
logiczne definiuj
ą
ce t
ę
funkcj
ę
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
= – 2
d
+
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
= 2
c
+
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
5
©Janusz Biernat, ARYT-ZADANIA-schematy’02
25 pa
ździernika 2004
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”
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
6
©Janusz Biernat, ARYT-ZADANIA-schematy’02
25 pa
ździernika 2004
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
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,2
D.
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,2
D
, ii) +0,7
D.
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
rozwi
ązania
©Janusz Biernat, ARYT-ZADANIA-schematy’02
25 pa
ździernika 2004
7
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
25 pa
ździernika 2004
8
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 istnieje nierozkła-
dalny podzielnik podstawy
ź
ródłowej, który nie jest podzielnikiem podstawy docelowej.
Rok I
ARYTMETYKA KOMPUTERÓW
rozwi
ązania
©Janusz Biernat, ARYT-ZADANIA-schematy’02
25 pa
ździernika 2004
9
Wskazówka: Znajd
ź
licznik ułamka danego w bazie
β
w bazie p
β
gdy (p,
β
)=1. (dowód podobnej tezy jest
w ksi
ąŜ
ce „Metody i układy arytmetyki komputerowej”). Twierdzenie kategoryczne („jest” zamiast
„mo
Ŝ
e”) jest fałszywe, bo 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
25 pa
ździernika 2004
10
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.
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.
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.
Rok I
ARYTMETYKA KOMPUTERÓW
rozwi
ązania
©Janusz Biernat, ARYT-ZADANIA-schematy’02
25 pa
ździernika 2004
11
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
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
25 pa
ździernika 2004
12
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:
Rok I
ARYTMETYKA KOMPUTERÓW
rozwi
ązania
©Janusz Biernat, ARYT-ZADANIA-schematy’02
25 pa
ździernika 2004
13
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
,
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
25 pa
ździernika 2004
14
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
25 pa
ździernika 2004
15
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
25 pa
ździernika 2004
16
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
25 pa
ździernika 2004
17
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
25 pa
ździernika 2004
18
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:
A
rea: Oblicz liczb
ę
ogniw sumatora i liczb
ę
ogniw ła
ń
cucha przeskoku przeniesienia,
T
ime: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.
Rok I
ARYTMETYKA KOMPUTERÓW
rozwi
ązania
©Janusz Biernat, ARYT-ZADANIA-schematy’02
25 pa
ździernika 2004
19
Wskazówka: Patrz poprzednie zadanie.
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
25 pa
ździernika 2004
20
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
25 pa
ździernika 2004
21
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
ą
.