/40

Imi Nazwisko

nr indeksu

pkt

ocena

ARYTMETYKA – KOLOKWIUM 2

27 stycznia 2006



Janusz Biernat

Errata rozwi

ązań opublikowanych 27.01.2006 (poprawki naniesione w tekście na następnych stronach)

G2/4: Jest 15 ma by

ć 13

G4/6: Jest 1,643

7

ma by

ć 1,656

2

G5/6: Jest 2

–54

ma by

ć 2

54

G5/7a: Skutkiem „literówki” był bł

ędny zapis przekodowanego mnożnika i całego mnożenia.

Wszystkie sensowne rozwi

ązania zadania 2a i 2b były akceptowane (choć niekoniecznie ocenione na

maksymaln

ą liczbę punktów). Poniżej rozwiązania podane 27.01, alternatywne rozwiązania w tekście.

Zad. G1/2

(inne rozwi

ązanie)

Zad. G2/2

(inne rozwi

ązanie)

Zad. G3/2

(inne rozwi

ązanie)

/40

Imi Nazwisko

nr indeksu

pkt

ocena

1

ARYTMETYKA – KOLOKWIUM 2

27 stycznia 2006



Janusz Biernat

1.(4p) Dodanie 53 liczb 64-bitowych w kodzie NB wymaga

.

9-poziomowego drzewa CSA. Zawiera ono 3264

(51x64) sumatorów, a minimalny całkowity czas dodawania wynosi T

CSA

+2log

2

n=48 (9x4+2x6)

2.

(5p) Uzupełnij schemat drzewa CSA zliczaj

ącego jedynki

sumator ko cowy

(4p) Uzupełnij poni

ższy graf prefiksowy.

Zaznacz w

ęzeł wytwarzający G

0,8

(0)

(9)

3.(4p) W systemie RNS (4, 5, 7) warto

ścią liczby {1, 1, 2}+{1, 2, 3}*{1, 2, 4}={2, 0, 0}jest 70

4.(4p) Oblicz: 64

124

mod 33 = (2

⋅

33–2)

124 mod (2

⋅

10)

mod 33 = (–2)

4

mod 33 = 16

6

–1

mod 37 = 31 (–6)

5.(3p) W 8-bitowym dodawaniu liczb 11010100

U2

+ 01010111

U2

nadmiar nie wyst

ąpi, a logiczne warto

ści

funkcji generacji przeniesienia wynosz

ą G

3,6

=1 oraz G

0,7

= 1.

6.(6p) Ci

ąg 0 1010 1110 0111 0101 1110 1101 0101 111 jest zmiennoprzecinkową znormalizowaną

reprezentacj

ą liczby x (wykładnik w kodzie „+127”). Oblicz x i zapisz go w tym samym formacie

z zaokr

ągleniem do 5. cyfry ułamka. Wartość dziesiętna pierwiastka wynosi około 1,| 6 | 8 | 7

5

|

×

2

23

.

| 0 | | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | | 1 | 0 | 1 | 1 | 0 | 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

:

0 1, 0 1 0 1

====

++++

D

k=-2

-D

1 0, 1 0 1 1

1

1

1

0

1

0

q

0

= 0

0

1

0

1

0

1

0

0

1

1

1

1

0

q

1

= 1

1 0, 1 0 1 1

0

0

1

0

0

1

q

2

= 1

Iloraz jest równy Q = 0,11...

2

⋅

2

2

/40

Imi Nazwisko

nr indeksu

pkt

ocena

2

ARYTMETYKA – KOLOKWIUM 2

27 stycznia 2006



Janusz Biernat

1.(4p) Dodanie 64 liczb 32-bitowych w kodzie NB wymaga 10-poziomowego drzewa CSA. Zawiera 1984

(62x32)

sumatorów, a minimalny całkowity czas dodawania wynosi T

CSA

+2log

2

n= 50 (10x4+5x2).

2.

(5p) Uzupełnij schemat drzewa CSA zliczaj

ącego jedynki

sumator ko cowy

(4p) Uzupełnij poni

ższy graf prefiksowy.

Zaznacz w

ęzeł wytwarzający G

0,7

(0)

(8)

3.(4p) W systemie RNS (5, 6, 7) warto

ścią liczby {3, 2, 3}+{2, 2, 3}*{1, 2, 2}={0, 0, 2} jest

.

30

4.(4p) Oblicz: 40

159

mod 21 = (2

⋅

21–2)

159 mod (2

⋅

6)

mod 21 = (–2)

3

mod 21 = 13 (–8)

5

–1

mod 41 = 33 (–8)

5.(3p) W 8-bitowym dodawaniu liczb 11010100

U2

+ 10010001

U2

nadmiar nie wyst

ąpi, a logiczne warto

ści

funkcji generacji przeniesienia wynosz

ą G

2,5

= 0 oraz G

0,6

=.0.

6.(6p) Ci

ąg 0 1110 1100 0100 0101 1110 1101 0101 111 jest zmiennoprzecinkową znormalizowaną

reprezentacj

ą liczby x (wykładnik w kodzie „+127”). Oblicz x i zapisz go w tym samym formacie

z zaokr

ągleniem do 5. cyfry ułamka. Wartość dziesiętna pierwiastka wynosi około 1,| 5 | 9 | 3

7

|

×

2

54

.

| 0 | | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | | 1 | 0 | 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 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

:

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

0

q

1

= 1

1

0

1

1

1

1

1

1

1

0

0

1

q

2

= 0

Iloraz jest równy Q =

.

0,10...

2

⋅

2

–2

/40

Imi Nazwisko

nr indeksu

pkt

ocena

3

ARYTMETYKA – KOLOKWIUM 2

27 stycznia 2006



Janusz Biernat

1.(4p) Dodanie 72 liczb 16-bitowych w kodzie NB wymaga

.

10-poziomowego drzewa CSA. Zawiera 1120

(70x16) sumatorów, a minimalny całkowity czas dodawania wynosi T

CSA

+2log

2

n= 48 (4x10+2x4).

2.

(5p) Uzupełnij schemat drzewa CSA zliczaj

ącego jedynki

sumator ko cowy

(4p) Uzupełnij poni

ższy graf prefiksowy.

Zaznacz w

ęzeł wytwarzający G

0,9

(!!brak)

(0)

(8)

3.(4p) W systemie RNS (3, 5, 7) warto

ścią liczby {2, 1, 3}+{1, 4, 3}*{1, 3, 6}={0, 3, 0} jest

.

63

4.(4p) Oblicz: 67

243

mod 35 = (2

⋅

35–3)

243 mod (4

⋅

6)

mod 35 = (–3)

3

mod 35 = 8 (–27)

6

–1

mod 43 = 36 (–7)

5.(3p) W 8-bitowym dodawaniu liczb 01100100

U2

+ 10111111

U2

nadmiar nie wyst

ąpi, a logiczne warto

ści

funkcji generacji przeniesienia wynosz

ą G

1,7

= 1 oraz G

0,5

= 1.

6.(6p) Ci

ąg 0 0010 1100 1110 0101 1110 0101 1101 111 jest zmiennoprzecinkową znormalizowaną

reprezentacj

ą liczby x (wykładnik w kodzie „+127”). Oblicz x i zapisz go w tym samym formacie

z zaokr

ągleniem do 5. cyfry ułamka. Wartość dziesiętna pierwiastka wynosi około 1,| 9 | 3 | 7

5

|

×

2

–42.

.

| 0 | | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | | 1 | 1 | 1 | 1 | 0 | 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

:

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

0

q

1

= 1

1

0

1

0

1

1

1

1

1

1

0

1

q

2

= 0

Iloraz jest równy Q =

.

0,10...

2

⋅

2

3

/40

Imi Nazwisko

nr indeksu

pkt

ocena

4

ARYTMETYKA – KOLOKWIUM 2

27 stycznia 2006



Janusz Biernat

1.(4p) Dodanie 42 liczb 64-bitowych w kodzie NB wymaga 8-poziomowego drzewa CSA. Zawiera ono 2560

(40x64) sumatorów, a minimalny całkowity czas dodawania wynosi T

CSA

+2log

2

n= 44 (8x4+2x6).

2.

(5p) Uzupełnij schemat poni

ższego sumatora CSA (7x2b)

(4p) Uzupełnij poni

ższy graf prefiksowy.

Zaznacz w

ęzeł wytwarzający G

0,8

(0)

(10)

3.(4p) W systemie RNS (3, 5, 8) warto

ścią liczby {1, 1, 1}+{1, 2, 3}*{1, 2, 5}={2, 0, 0} jest

.

80

4.(4p) Oblicz: 68

184

mod 33 = (2

⋅

33+2)

184 mod (2

⋅

10)

mod 33 = (+2)

4

mod 33 = 16

9

–1

mod 37 = 33 (–4)

5.(3p) W 8-bitowym dodawaniu liczb 11010100

U2

+ 01011111

U2

nadmiar nie wyst

ąpi, a logiczne warto

ści

funkcji generacji przeniesienia wynosz

ą G

1,6

=

1 oraz G

0,4

=.1

6.(6p) Ci

ąg 0 1010 1110 0110 0101 0001 0001 0101 111 jest zmiennoprzecinkową znormalizowaną

reprezentacj

ą liczby x (wykładnik w kodzie „+127”). Oblicz x i zapisz go w tym samym formacie

z zaokr

ągleniem do 5. cyfry ułamka. Wartość dziesiętna pierwiastka wynosi około 1,| 6 | 5 | 6

2

|

×

2

23

.

| 0 | | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | | 1 | 0 | 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

-1 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

1 1 1 1

1 0 0 0 1 1

9 9 9 9 3 4 8

0 0 0

0 1 1 1 0 1

9 9 9 0 2 2

0

0 1 1 1 0 1

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

:

0 1, 0 1 0 1

====

++++

D

k= -2

-D

1 0, 1 0 1 1

1

1

1

1

0

1

0

q

0

= 0

0

1

0

1

0

1

0

0

1

1

1

1

0

q

1

= 1

1

0

1

0

1

1

0

0

1

0

0

1

q

2

= 1

Iloraz jest równy Q =

.

0,11...

2

⋅

2

2

/40

Imi Nazwisko

nr indeksu

pkt

ocena

5

ARYTMETYKA – KOLOKWIUM 2

27 stycznia 2006



Janusz Biernat

1.(4p) Dodanie 63 liczb 32-bitowych w kodzie NB wymaga

.

9-poziomowego drzewa CSA. Zawiera ono 1952

(61x32) sumatorów, a minimalny całkowity czas dodawania wynosi T

CSA

+2log

2

n= 46 (9x4+2x5).

2.

(5p) Uzupełnij schemat poni

ższego sumatora CSA (9x2b)

(4p) Uzupełnij poni

ższy graf prefiksowy.

Zaznacz w

ęzeł wytwarzający G

0,8

(0)

(8)

3.(4p) W systemie RNS (5, 7, 8) warto

ścią liczby {3, 1, 2}+{2, 3, 3}*{1, 3, 2}={0, 3, 0} jest 80

4.(4p) Oblicz: 44

279

mod 21 = (2

⋅

21+2)

279 mod (2

⋅

6)

mod 33 = (+2)

3

mod 33 = 8

8

–1

mod 41 = 36 (–5)

5.(3p) W 8-bitowym dodawaniu liczb 11010100

U2

+ 10010001

U2

nadmiar nie wyst

ąpi, a logiczne warto

ści

funkcji generacji przeniesienia wynosz

ą G

2,6

=

0 oraz G

0,5

= 0.

6.(6p) Ci

ąg 0 1110 1100 0111 0111 0010 0000 0101 111 jest zmiennoprzecinkową znormalizowaną

reprezentacj

ą liczby x (wykładnik w kodzie „+127”). Oblicz x i zapisz go w tym samym formacie

z zaokr

ągleniem do 5. cyfry ułamka. Wartość dziesiętna pierwiastka wynosi około 1,| 6 | 8 | 7

5

|

×

2

54

.

| 0 | | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | | 1 | 0 | 1 | 1 | 0 | 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

:

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

0

q

1

= 1

1

0

1

1

1

1

1

1

1

0

0

1

q

2

= 0

Iloraz jest równy Q = 0,10...

2

⋅

2

–2

/40

Imi Nazwisko

nr indeksu

pkt

ocena

6

ARYTMETYKA – KOLOKWIUM 2

27 stycznia 2006



Janusz Biernat

1.(4p) Dodanie 41 liczb 16-bitowych w kodzie NB wymaga

.

8-poziomowego drzewa CSA. Zawiera ono 624

(39x16) sumatorów, a minimalny całkowity czas dodawania wynosi T

CSA

+2log

2

n= 40 (8x4+2x4).

2.

(5p) Uzupełnij schemat poni

ższego sumatora CSA (8x2b)

(4p) Uzupełnij poni

ższy graf prefiksowy.

Zaznacz w

ęzeł wytwarzający G

0,8

(0)

(9)

3.(4p) W systemie RNS (3, 7, 8) warto

ścią liczby {2, 2, 3}+{1, 4, 3}*{1, 3, 5}={0, 0, 2} jest 42

4.(4p) Oblicz: 73

267

mod 35 = (2

⋅

35+3)

267 mod (4

⋅

6)

mod 35 = (+3)

3

mod 35 = 27

7

–1

mod 43 = 37 (–6)

5.(3p) W 8-bitowym dodawaniu liczb 01100100

U2

+ 10111111

U2

nadmiar nie wyst

ąpi, a logiczne warto

ści

funkcji generacji przeniesienia wynosz

ą G

1,6

= 1 oraz G

0,3

= 1.

6.(6p) Ci

ąg 0 0010 1100 1110 0100 0001 0101 1101 111 jest zmiennoprzecinkową znormalizowaną

reprezentacj

ą liczby x (wykładnik w kodzie „+127”). Oblicz x i zapisz go w tym samym formacie

z zaokr

ągleniem do 5. cyfry ułamka. Wartość dziesiętna pierwiastka wynosi około 1,| 9 | 3 | 7

5

|

×

2

–42

.

| 0 | | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | | 1 | 1 | 1 | 1 | 0 | 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 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

:

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

0

q

1

= 1

1

0

1

0

1

1

1

1

1

1

0

1

q

2

= 0

Iloraz jest równy Q =

.

0,10...

2

⋅

2

3