/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