/33
Imi
ę
Nazwisko
nr indeksu
pkt
ocena
1
ARYTMETYKA – KOLOKWIUM 2
19 stycznia 2007
Janusz Biernat
1.(3p) Drzewo CSA u yte do redukcji argumentów w dodawaniu 63 liczb 64-bitowych w kodzie U2 ma co
najmniej 10 poziomów. Zawiera ono 61
⋅⋅⋅⋅
64+2=3906 sumatorów (T
(3,2)
=4), a minimalny czas obliczenia
sumy wynosi T
CSA
+2 log
2
n +3= 10
⋅⋅⋅⋅
4+3+2
⋅⋅⋅⋅
6 = 55. (– 63=1000001
U2
, wi c 63+1 arg – 10 poziomów)
2.
(4p) Uzupełnij schemat drzewa CSA zliczaj cego jedynki
sumator ko
ń
cowy
(3p) Uzupełnij poni szy graf prefiksowy.
Zaznacz w zeł wytwarzaj cy G
8:0
(0)
(9)
3.(3p) W RNS (3, 4, 5, 7) warto ci liczby {1, 2, 2, 6}*{2, 3, 4, 5}={2, 2, 3, 2} jest 2+|{0, 0, 1, 0}| = 338 (–82)
4.(3p) 64
197
mod 33 = (64 mod 33)
197 mod
ϕϕϕϕ
(33)
mod 33 = (–2)
197 mod 20
mod 33 = (–2)
–3
mod 33 = 4
5.(2p) W 8-bitowym dodawaniu liczb 11010100
U2
+ 01010111
U2
nadmiar nie wyst
ą
pi, a logiczne warto ci
funkcji generacji i propagacji przeniesienia wynosz G
6:0
= 1 oraz P
3:1
= 0 (tak e H
3:1
= 0).
6.(5p) Ci g 0 1010 1110 0111 1000 0000 0000 0000 000 jest zmiennoprzecinkow
ą
znormalizowan
ą
reprezentacj liczby x (wykładnik w kodzie „+127”). Oblicz x
–1
i zapisz go w tym samym formacie
z zaokr
ą
gleniem do 3. cyfry ułamka. Warto dziesi tna odwrotno ci wynosi około 1,| 3 | 1 | 2 |
×
2
–48.
.
| 0 | | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | | 0 | 1 | 0 | 1 | 1 | 0 | 0 |… …| 0 | 0 |
7.
(4p) Oblicz, stosuj c przekodowanie Booth’a-McSorley’a
(2p) oblicz w systemie U10
A
U2
1 0 1 1 0 1
X
U2
××××
1 0 0 1 0 0 1 1
9 9 9 9 9 8 3 7
X
SD
-1 0
0
1
0
1
0
-1
××××
9 7 2 3
0 0 0 0 0 0 0
0 1 0 0 1 1
9 9 9 9 9 5 1 1
1 1 1 1 1
1 0 1 1 0 1
9 9 9 9 6 7 4
1 1 1
1 0 1 1 0 1
9 9 8 8 5 9
0 1 0 0 1 1
0 0 1 6 3
0 1 0 0 0 0 0 0 1 0 1 1 1
0 0 0 4 5 1 5 1
8.(4p) Wykonaj z dokładno ci do 3 cyfr znacz cych dzielenie nieodtwarzaj ce liczb danych w kodzie NB
1 0, 1 0 1 1
====
−−−−
D
X =
0
1
0 0, 1
0
1
:
0 1, 0 1 0 1
====
++++
D
k=-2
-D
1 0, 1 0 1 1
1 1
1
0 1 1
q
0
= 0
0 1 0 1 0 1
0 1
0
0 0 0
0
q
1
= 1
1 1 0, 1 0 1 1
0 0 0 1 0 1 1
q
2
= 1
Iloraz jest równy Q = 0,11...
2
⋅
2
2
/33
Imi
ę
Nazwisko
nr indeksu
pkt
ocena
2
ARYTMETYKA – KOLOKWIUM 2
19 stycznia 2007
Janusz Biernat
1.(3p) Redukcj iloczynów cz ciowych w mno eniu 32-bitowym w kodzie NB mo na wykona w drzewie
CSA o 8
.
poziomach. Zawiera ono 32
⋅⋅⋅⋅
30=960 sumatorów (T
(3,2)
=4), a minimalny czas obliczenia
iloczynu wynosi T
CSA
+2 log
2
n +3= 8
⋅⋅⋅⋅
4+3+2
⋅⋅⋅⋅
5 = 45.
2.
(4p) Uzupełnij schemat drzewa CSA zliczaj cego jedynki
sumator ko
ń
cowy
(3p) Uzupełnij poni szy graf prefiksowy.
Zaznacz w zeł wytwarzaj cy G
7:0
(0)
(8)
3.(3p) W RNS (3, 4, 7, 13) warto ci liczby {2, 3, 4, 7}*{2, 3, 2, 8}={1, 1, 1, 4} jest 1+|{0, 0, 0, 3}|=589 (–503)
4.(3p) 43
238
mod 39 = (43 mod 39)
238 mod
ϕϕϕϕ
(39)
mod 39 = 4
238 mod 24
mod 39 = 4
–2
mod 39 = 10
2
mod 39 = 22
5.(2p) W 8-bitowym dodawaniu liczb 11010100
U2
+ 10010001
U2
nadmiar nie wyst
ą
pi, a logiczne warto ci
funkcji generacji i propagacji przeniesienia wynosz G
5:2
= 0 oraz P
2:0
= 0 (tak e H
2:0
= 0).
6.(5p) Ci g 0 1110 1100 0100 1000 0000 0000 0000 000 jest zmiennoprzecinkow
ą
znormalizowan
ą
reprezentacj liczby x (wykładnik w kodzie „+127”). Oblicz x
–1
i zapisz go w tym samym formacie
z zaokr
ą
gleniem do 3. cyfry ułamka. Warto dziesi tna odwrotno ci wynosi około 1,| 5 | 0 | 3 |
×
2
–110
| 0 | | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | | 1 | 0 | 0 | 0 | 1 | 0 | 0 |… …| 0 | 0 |
7.
(4p) Oblicz, stosuj c przekodowanie Booth’a-McSorley’a
(2p) oblicz w systemie U10
A
U2
1 0 1 0 1 1
X
U2
××××
1 0 1 1 0 0 1 1
9 9 9 9 9 8 5 3
X
SD
0 -1 0
-1 0
1
0
-1
××××
6 2 1
0 0 0 0 0 0 0
0 1 0 1 0 1
9 9 9 9 9 8 5 3
1 1 1 1 1
1 0 1 0 1 1
9 9 9 9 7 0 6
0 0 0
0 1 0 1 0 1
9 9 9 1 1 8
0
0 1 0 1 0 1
0 0 1 4 7
0 0 1 1 0 0 1 0 1 0 0 0 1
0 0 0 5 5 7 1 3
8.(4p) Wykonaj z dokładno ci do 3 cyfr znacz cych dzielenie nieodtwarzaj ce liczb danych w kodzie NB
1
0
1
1 1, 1
====
−−−−
D
X = 0
0 1, 0 1 1 0 1
:
0
1
0
0 0, 1
====
++++
D
k= 2
1
0
1
1 1, 1
1 1 1 0 1 0 0
q
0
= 0
0
1 0
0
0 1
0
0
0
1 0 1
1
q
1
= 1
1 0 1 1 1 1
1 1
1
0 1 0
q
2
= 0
Iloraz jest równy Q =
.
0,10...
2
⋅
2
–2
/33
Imi
ę
Nazwisko
nr indeksu
pkt
ocena
3
ARYTMETYKA – KOLOKWIUM 2
19 stycznia 2007
Janusz Biernat
1.(3p) Drzewo CSA u yte do redukcji argumentów w dodawaniu 72 liczb 32-bitowych w kodzie U2 ma co
najmniej 10 poziomów. Zawiera ono 71
⋅⋅⋅⋅
32+4=2276 sumatorów (T
(3,2)
=4), a minimalny czas obliczenia
sumy wynosi T
CSA
+2 log
2
n +3= 10
⋅⋅⋅⋅
4+3+2
⋅⋅⋅⋅
5 = 53. (–72=10111000
U2
, wi c 72 arg – 10 poziomów)
2.
(4p) Uzupełnij schemat drzewa CSA zliczaj cego jedynki
sumator ko
ń
cowy
(3p) Uzupełnij poni szy graf prefiksowy.
Zaznacz w zeł wytwarzaj cy G
9:0
(!!brak)
(0)
(8)
3.(3p) W RNS (4, 5, 7, 11) warto ci liczby {1, 4, 3, 2}*{3, 2, 4, 7}={3, 3, 5, 3} jest 3+|{0, 0, 2, 0}|=663 (–887)
4.(3p) 67
262
mod 35 = (67 mod 35)
262 mod
ϕϕϕϕ
(35)
mod 35 = (–3)
262 mod 24
mod 35 = (–3)
–2
mod 33 = 9
–1
mod 35 = 4
5.(2p) W 8-bitowym dodawaniu liczb 01100100
U2
+ 10111111
U2
nadmiar nie wyst
ą
pi, a logiczne warto ci
funkcji generacji i propagacji przeniesienia wynosz G
7:1
= 1 oraz P
4:3
= 1 (tak e H
4:3
= 1).
6.(5p) Ci g 0 0010 1100 1110 1000 0000 0000 0000 000 jest zmiennoprzecinkow
ą
znormalizowan
ą
reprezentacj liczby x (wykładnik w kodzie „+127”). Oblicz x
–1
i zapisz go w tym samym formacie
z zaokr
ą
gleniem do 3. cyfry ułamka. Warto dziesi tna odwrotno ci wynosi około 1,| 0 | 0 | 3 |
×
2
82
.
| 0 | | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | | 0 | 0 | 0 | 0 | 1 | 0 | 0 |… …| 0 | 0 |
7.
(4p) Oblicz, stosuj c przekodowanie Booth’a-McSorley’a
(2p) oblicz w systemie U10
A
U2
1 0 1 1 0 1
X
U2
××××
1 0 0 1 0 1 1 1
9 9 9 9 9 7 3 7
X
SD
-1 0
0
1
1
0
0
-1
××××
9 8 3 2
0 0 0 0 0 0 0
0 1 0 0 1 1
9 9 9 9 9 4 7 4
1 1 1 1
1 0 1 1 0 1
9 9 9 9 2 1 1
1 1 1
1 0 1 1 0 1
9 9 7 8 9 6
0 1 0 0 1 1
0 0 2 6 3
0 0 1 1 1 1 1 0 0 1 0 1 1
0 0 0 4 4 1 8 4
8.(4p) Wykonaj z dokładno ci do 3 cyfr znacz cych dzielenie nieodtwarzaj ce liczb danych w kodzie NB
1 0, 1 0 1 1
====
−−−−
D
X = 0
0
1
1 1, 1
0
1
:
0 1, 0 1 0 1
====
++++
D
k= -3
-D
1 0, 1 0 1 1
1 1
1
0
1
0
0
q
0
= 0
0
1
0
1 0 1
0
0
1
0 0 1
1
q
1
= 1
1 0
1
0 1 1
1 1
1
1 1 0
q
2
= 0
Iloraz jest równy Q =
.
0,10...
2
⋅
2
3
/33
Imi
ę
Nazwisko
nr indeksu
pkt
ocena
4
ARYTMETYKA – KOLOKWIUM 2
19 stycznia 2007
Janusz Biernat
1.(3p) Redukcj iloczynów cz ciowych w mno eniu 24-bitowym w kodzie NB mo na wykona w drzewie
CSA o 7 poziomach. Zawiera ono 24
⋅⋅⋅⋅
22=528 sumatorów (T
(3,2)
=4), a minimalny czas obliczenia
iloczynu wynosi T
CSA
+2 log
2
n +3= 7
⋅⋅⋅⋅
4+3+2
⋅⋅⋅⋅
5 = 41.
2.
(4p) Uzupełnij schemat poni szego sumatora CSA (7x2b)
(3p) Uzupełnij poni szy graf prefiksowy.
Zaznacz w zeł wytwarzaj cy G
8:0
(0)
(10)
3.(3p) W RNS (3, 5, 8, 11) warto ci liczby {1, 4, 6, 4}*{2, 3, 7, 4}={2, 2, 2, 5} jest 2+|{0, 0, 0, 3}|=962 (–358)
4.(3p) 41
327
mod 44 = (41 mod 44)
327 mod
ϕϕϕϕ
(44)
mod 44 = (–3)
327 mod 20
mod 44 = (–3)
7
mod 44 = 13
5.(2p) W 8-bitowym dodawaniu liczb 11010100
U2
+ 0 0101111
U2
nadmiar nie wyst
ą
pi, a logiczne warto ci
funkcji generacji i propagacji przeniesienia wynosz G
6:1
= 1 oraz P
4:2
= 1 (ale H
4:2
= 0).
6.(5p) Ci g 0 1010 1110 0110 1000 0000 0000 0000 000 jest zmiennoprzecinkow
ą
znormalizowan
ą
reprezentacj liczby x (wykładnik w kodzie „+127”). Oblicz x
–1
i zapisz go w tym samym formacie
z zaokr
ą
gleniem do 3. cyfry ułamka. Warto dziesi tna odwrotno ci wynosi około 1,| 4 | 0 | 6 |
×
2
–48
.
| 0 | | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | | 0 | 1 | 1 | 0 | 1 | 0 | 0 |… …| 0 | 0 |
7.
(4p) Oblicz, stosuj c przekodowanie Booth’a-McSorley’a
(2p) oblicz w systemie U10
A
U2
1 0 0 0 1 1
X
U2
××××
1 0 1 1 0 1 1 1
9 9 9 9 9 8 3 7
X
SD
0 -1 0
0
-1 0
0
-1
××××
9 6 4 1
0 0 0 0 0 0 0
0 1 1 1 0 1
9 9 9 9 9 8 3 7
0 0 0 0
0 1 1 1 0 1
9 9 9 9 3 4 8
0
0 1 1 1 0 1
9 9 9 0 2 2
0 0 1 6 3
0 1 0 0 0 0 1 0 0 0 1 0 1
0 0 0 5 8 5 1 7
8.(4p) Wykonaj z dokładno ci do 3 cyfr znacz cych dzielenie nieodtwarzaj ce liczb danych w kodzie NB
1 0, 1 0 1 1
====
−−−−
D
X =
0
1
0 0, 1
0
1
:
0 1, 0 1 0 1
====
++++
D
k= -2
-D
1 0, 1 0 1 1
1
1
1
1
0
1 1
q
0
= 0
0 1
0
1 0 1
0 1
0
0 0 0
0
q
1
= 1
1
0
1 0 1
1
0
0
1 0 1
1
q
2
= 1
Iloraz jest równy Q =
.
0,11...
2
⋅
2
2
/33
Imi
ę
Nazwisko
nr indeksu
pkt
ocena
5
ARYTMETYKA – KOLOKWIUM 2
19 stycznia 2007
Janusz Biernat
1.(3p) Drzewo CSA u yte do redukcji argumentów w dodawaniu 64 liczb 48-bitowych w kodzie U2 ma co
najmniej 10 poziomów. Zawiera ono 62
⋅⋅⋅⋅
48+2=2978 sumatorów (T
(3,2)
=4), a minimalny czas obliczenia
sumy wynosi T
CSA
+2 log
2
n +3= 10
⋅⋅⋅⋅
4+3+2
⋅⋅⋅⋅
6 = 55. (–64=11000000
U2
, wi c 64 arg – 10 poziomów)
2.
(4p) Uzupełnij schemat poni szego sumatora CSA (9x2b)
(3p) Uzupełnij poni szy graf prefiksowy.
Zaznacz w zeł wytwarzaj cy G
8:0
(0)
(8)
3.(3p) W RNS (4, 7, 9, 11) warto ci liczby {3,2,5,7}*{1,5,3,2}={3,3,6,3} jest 3+|{0, 0, 1, 0}|=1851 (–921)
4.(3p) Oblicz: 47
416
mod 49 = (47 mod 49)
416 mod
ϕϕϕϕ
(49)
mod 49 = (–2)
416 mod 42
mod 49 = (–2)
–4
mod 49 = 31
5.(2p) W 8-bitowym dodawaniu liczb 11010100
U2
+ 10010001
U2
nadmiar nie wyst
ą
pi, a logiczne warto ci
funkcji generacji i propagacji przeniesienia wynosz G
6:2
= 0 oraz P
4:3
= 0 (tak e H
4:3
= 0).
6.(5p) Ci g 0 1110 1100 0111 1000 0000 0000 0000 000 jest zmiennoprzecinkow
ą
znormalizowan
ą
reprezentacj liczby x (wykładnik w kodzie „+127”). Oblicz x
–1
i zapisz go w tym samym formacie
z zaokr
ą
gleniem do 3. cyfry ułamka. Warto dziesi tna odwrotno ci wynosi około 1,| 3 | 4 | 3 |
×
2
–110
.
| 0 | | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | | 0 | 1 | 0 | 1 | 1 | 0 | 0 |… …| 0 | 0 |
7.
(4p) Oblicz, stosuj c przekodowanie Booth’a-McSorley’a
(2p) oblicz w systemie U10
A
U2
1 0 1 1 1 1
X
U2
××××
1 0 1 1 0 0 1 0
9 9 9 9 9 8 5 3
X
SD
0 -1 0
-1 0
1
-1 0
××××
7 5 1
0 0 0 0 0 0
0 1 0 0 0 1
0
!
9 9 9 9 9 8 5 3
1 1 1 1 1
1 0 1 1 1 1
9 9 9 9 2 6 5
0 0 0
0 1 0 0 0 1
9 9 8 9 7 1
0
0 1 0 0 0 1
0 0 1 4 7
0 0 1 0 1 0 0 1 0 1 1 1 0
0 0 0 3 6 6 0 3
8.(4p) Wykonaj z dokładno ci do 3 cyfr znacz cych dzielenie nieodtwarzaj ce liczb danych w kodzie NB
1
0
1
1
1 1
====
−−−−
D
X = 0
0 1, 0 1 1 0 1
:
0
1
0
0 0, 1
====
++++
D
k= 2
1
0
1
1 1, 1
1 1
1
0
1
0
0
q
0
= 0
0
1
0
0 0 1
0
0
0
1 0 1
1
q
1
= 1
1 0
1
1 1 1
1 1
1
0 1 0
q
2
= 0
Iloraz jest równy Q = 0,10...
2
⋅
2
–2
/33
Imi
ę
Nazwisko
nr indeksu
pkt
ocena
6
ARYTMETYKA – KOLOKWIUM 2
19 stycznia 2007
Janusz Biernat
1.(3p) Redukcj iloczynów cz ciowych w mno eniu 56-bitowym w kodzie NB mo na wykona w drzewie
CSA o 9 poziomach. Zawiera ono 56
⋅⋅⋅⋅
54+2=3024 sumatorów (T
(3,2)
=4), a minimalny czas obliczenia
iloczynu wynosi T
CSA
+2 log
2
n +3= 9
⋅⋅⋅⋅
4+3+2
⋅⋅⋅⋅
6 = 51.
2.
(4p) Uzupełnij schemat poni szego sumatora CSA (8x2b)
(3p) Uzupełnij poni szy graf prefiksowy.
Zaznacz w zeł wytwarzaj cy G
8:0
(0)
(9)
3.(3p) W syst. RNS (4, 5, 7, 9) warto ci liczby {1, 4, 3, 7}*{2, 3, 3, 2}={2, 2, 2, 5} jest 2+|{0, 0, 0, 3}| = 842
4.(3p) 49
317
mod 51 = (49 mod 51)
317 mod
ϕϕϕϕ
(51)
mod 51 = (–2)
317 mod 32
mod 51 = (–2)
–3
mod 51 = 19
5.(2p) W 8-bitowym dodawaniu liczb 01100100
U2
+ 10111111
U2
nadmiar nie wyst
ą
pi, a logiczne warto ci
funkcji generacji i propagacji przeniesienia wynosz G
6:1
= 1 oraz P
4:3
= 1 (tak e H
4:3
= 1).
6.(5p) Ci g 0 0010 1100 1110 1000 0000 0000 0000 000 jest zmiennoprzecinkow
ą
znormalizowan
ą
reprezentacj liczby x (wykładnik w kodzie „+127”). Oblicz x
–1
i zapisz go w tym samym formacie
z zaokr
ą
gleniem do 3. cyfry ułamka. Warto dziesi tna odwrotno ci wynosi około 1,| 0 | 0 | 3 |
×
2
82
.
| 0 | | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | | 0 | 0 | 0 | 0 | 1 | 1 | 0 |… …| 0 | 0 |
7.
(4p) Oblicz, stosuj c przekodowanie Booth’a-McSorley’a
(2p) oblicz w systemie U10
A
U2
1 0 1 1 0 1
X
U2
××××
1 0 1 1 1 0 0 1
9 9 9 9 9 7 3 7
X
SD
0 -1 0
0
-1 0
0
1
××××
6 1 4
1 1 1 1 1 1 1
1 0 1 1 0 1
9 9 9 9 8 9 4 8
0 0 0 0
0 1 0 0 1 1
9 9 9 9 7 3 7
9 9 8 4 2 2
0
0 1 0 0 1 1
0 0 2 6 3
0 0 1 0 1 0 1 0 0 0 1 0 1
0 0 1 0 1 5 1 8
8.(4p) Wykonaj z dokładno ci do 3 cyfr znacz cych dzielenie nieodtwarzaj ce liczb danych w kodzie NB
1 0, 1 0 1 1
====
−−−−
D
X = 0
0
1
1 1, 1
0
1
:
0 1, 0 1 0 1
====
++++
D
k=-3
-D
1 0, 1 0 1 1
1
1
0
1
0
0
q
0
= 0
0
1
0
1 0 1
0
0
1
0 0 1
1
q
1
= 1
1 0
1
0 1 1
1 1
1
1 1 0
q
2
= 0
Iloraz jest równy Q =
.
0,10...
2
⋅
2
3
/33
Imi
ę
Nazwisko
nr indeksu
pkt
ocena
7
ARYTMETYKA – KOLOKWIUM 2
19 stycznia 2007
Janusz Biernat
Wszystkie sensowne rozwi zania zadania 2a i 2b były akceptowane (cho niekoniecznie ocenione na
maksymaln liczb punktów).
Poni ej przykładowe alternatywne rozwi zania zadania 2.
Zad. G1/2
Zad. G2/2
Zad. G3/2