/40

Imię

Nazwisko

nr indeksu

pkt

ocena

0.(1p) Przeprowad konwersj liczby –55378 = | | | | | | | | | | | | | U2

ź

ę

1.(4p) Ciag 12 bitów w notacji 553,78 jest zapisem kodu liczby, której 3 bity stanowi cz ułamkow .

ą

ę

ś

ć

ą

Podaj warto liczby i zapis 16-bitowy w notacji ( )16 z 4 bitami ułamka, je li podano j w kodzie: ś

ć

ś

ą

warto (dziesi tnie)

rozszerzenie 16-bitowe w notacji (...)

16

ś

ć

ę

znak

całkowita, ułamkowa

całkowita, ułamkowa

uzupełnieniowym pełnym (U2):

,

,

znak-moduł (SM):

,

,

2.(4p) Stosuj c reguły arytmetyki resztowej oblicz reszty całkowite (dodatnie lub ujemne) ą

55378 mod 778 =

55378 mod 1018 =

55378 mod 6310 =

55378 mod 0F16 =

3.(6p) Dane s liczby 48-bitowe { x 47 x 46 ... x 1 x 0} oraz { y 47 y 46 ... y 1 y 0} w kodzie uzupełnieniowym U2: ą

0101 0111 1010 1010 0110 0101 1010 1111 0110 0101 1010 1111

0101 0010 1111 0111 1010 1010 0110 0101 1010 1010 0110 0101

W dodawaniu najdłu szy ła cuch propagacji przeniesienia obejmuje ......... pozycji ż

ń

Poniewa c

=

47 = ..... , c48 = ....., wi c c47 ..... c48 ( oraz s47

/ ≠ s...... ) zatem nie* wyst pi nadmiar.

ż

ę

ą

4.(4p) Oblicz z dokładno ci do 2 pozycji cz ci ułamkowej 11111 0

, 01 = | | | |,| | |

ś

ą

ę

ś

2

5.(4p) Zgodnie z reguł Booth’a w bazie 4 1010 1001U2 = | | | | | | | | |SD +1*

ą

6.(6p) Wykonaj dwoma sposobami mno enie liczb dwójkowych w kodzie uzupełnieniowym (U2) ż

1 1 0 1 1

1 1 0 1 1

×

1 1 0 1

×

1 1 0 1

1 1 0 1 1

0 1 0 1 1

7.(6p) Dodanie 24 liczb 24-bitowych w kodzie naturalnym wymaga ....-poziomowego sumator CSA.

Wynik b dzie .....-bitowy, a ko cowe dodawanie obejmie ..... bitów. Całkowity czas sumowania ę

ń

przy u yciu sumatora sum warunkowych jest ...... razy wi kszy od czasu dodawania 1-bitowego ż

ę

( T=4), a przy u yciu sumatora z przeskokiem przeniesie ( T = 2 ⋅ 2 n ) ....... razy wi kszy.

ż

ń

ę

8.(5p) Stosuj c metod dzielenia nieodtwarzaj cego oblicz 3 pierwsze reszty i 3 pierwsze cyfry ilorazu ą

ę

ą

=– D k =

X : D

1, 1

0 0 0

:

0, 1

0

0 1

– / + D

q 0 =

q 1 =

q 2 =

ARYTMETYKA – EGZAMIN 0

2003

 Janusz Biernat

*) niepotrzebne skre li

ś

ć

/40

Imię

Nazwisko

nr indeksu

pkt

ocena

0.(1p) Przeprowad konwersj liczby 72,659 = | | | | | | | | | | | | | U2

ź

ę

1.(4p) Zapisz w postaci kodu 16-bitowego z 6 bitami cz ci ułamkowej wynik działania 7,(26)8 – 108

ę

ś

w systemie :

uzupełnieniowym pełnym (U2):

znak-moduł (SM):

2.(4p) Stosuj c reguły arytmetyki resztowej oblicz reszty całkowite (dodatnie lub ujemne) ą

72658 mod 1018 =

72658 mod 10012 =

72658 mod 1710 =

72658 mod 01F16 =

3.(6p) Dane s liczby 48-bitowe { x 47 x 46 ... x 1 x 0} oraz { y 47 y 46 ... y 1 y 0} w kodzie uzupełnieniowym U2: ą

0111 0110 1010 0111 1010 1010 0110 0101 1010 1010 0110 0101

1101 0111 1010 1010 0110 0101 0010 1111 0110 0101 0010 1111

W dodawaniu najdłu szy ła cuch propagacji przeniesienia obejmuje ......... pozycji ż

ń

Poniewa c

=

47 = ..... , c48 = ....., wi c c47 ..... c48 ( oraz s47

/ ≠ s...... ) zatem nie* wyst pi nadmiar.

ż

ę

ą

4.(4p) Oblicz z dokładno ci do 5 cyfr znacz cych

0

,

0 00010011 1

1

= ,| | | | | |

ś

ą

ą

2

5.(4p) Zgodnie z reguł Booth’a w bazie 4 1011 0110U2 = | | | | | | | | |SD +1*

ą

6.(6p) Wykonaj dwoma sposobami mno enie liczb dwójkowych w kodzie uzupełnieniowym (U2) ż

1 0 1 1 1

1 0 1 1 1

× 1 0 1 1 1

× 1 0 1 1 1

1 0 1 1 1

0 0 1 1 1

7.(6p) Dodanie 24 liczb 16-bitowych w kodzie naturalnym wymaga ....-poziomowego sumator CSA.

Wynik b dzie .....-bitowy, a ko cowe dodawanie obejmie ..... bitów. Całkowity czas sumowania ę

ń

przy u yciu sumatora sum warunkowych jest ...... razy wi kszy od czasu dodawania 1-bitowego ż

ę

( T=4), a przy u yciu sumatora z przeskokiem przeniesie ( T = 2 ⋅ 2 n ) ....... razy wi kszy.

ż

ń

ę

8.(5p) Stosuj c metod dzielenia nieodtwarzaj cego oblicz 3 pierwsze reszty i 3 pierwsze cyfry ilorazu ą

ę

ą

=– D k =

X : D

0, 1

0 0 0

:

1, 0

0

0 1

– / + D

q 0 =

q 1 =

q 2 =

ARYTMETYKA – EGZAMIN 0

2003

 Janusz Biernat

*) niepotrzebne skre li

ś

ć

Zadania kolokwialne – schematy rozwi za

ą

ń

0.(1p) Przeprowad konwersj liczby

–

p

q

,

r

t

ź

ę

– N 2 =

– 0 b b b b b b , b b b b b b

2

0– N 2 = (– N)U2 =

1 1

,

0 0 U2

X

y

,

z

v

U16

Konwersja ( X) →

→

→

→

→

a

( Z)U b przebiega nast puj co ±( X) a

± ( Z) b

± (0| Z)U b

0± (0| Z)U b

( Z*)U b

ę

ą

1.(4p) Ciag 12 bitów w notacji p q r , t 8 jest zapisem kodu liczby, której 3 bity stanowi cz ułamkow .

ą

ę

ś

ć

ą

Podaj warto liczby i zapis 16-bitowy w notacji ( )16 z 4 bitami ułamka, je li podano j w kodzie: ś

ć

ś

ą

rozszerzenie U2

s s s s b b b b b b b b b b b 0

…

rozszerzenie – notacja (..)16

(U2)↑X↓(SM)

Y

W ,

Z

rozszerzenie SM

s 0 0

0 b b b b b b b b, b b b 0

…

(s=1 ⇒ liczba ujemna, suma warto ci liczb ujemnych o m bitach cz ci całkowitej interpretowanych ś

ę

ś

jako U2 i SM wynosi –2 m–1), wi c warto liczby wynosi odpowiednio w tych kodach: ę

ś

ć

L1 + L2 = –256 !! ( m=9)

warto (dziesi tnie)

rozszerzenie 16-bitowe w notacji (...)

16

ś

ć

ę

znak

całkowita, ułamkowa

całkowita, ułamkowa

uzupełnieniowy pełny (U2): (L1) –

, 1– t/8

XU2

Y

W,

Z

znak-moduł (SM): (L2)

–

, t/8

XSM Y

W,

Z

Liczby z okresem ułamkowym – najpierw oblicz wynik działania w systemie znak-moduł

• pami taj, e 1 – 0,( xy)β= 0,((β – 1 ) – x, (β – 1 ) – y)β

ę

ż

• przekonwertuj warto bezwzgl dn wyniku na system docelowy (np. dwójkowy)

ś

ć

ę

ą

• wyznacz reprezentacj uzupełnieniow

ę

ą

2.(4p) Stosuj c reguły arytmetyki resztowej oblicz reszty całkowite (dodatnie lub ujemne) ą

p q r t β mod m = p q r t β mod (βk ± 1) = …

p q r t α mod m = p q r t α mod (βk ± 1) = x y … z v β mod (βk ± 1) =

p q r t 8 [= XYZ16 = sbb...bb2] mod (βk–1) [= 0FF..F16 | lub = 77..78 | lub = 111..12] = …

p q r t 8 [= XYZ16 = sbb...bb2] mod (βk+1) [= 100..0116 | lub = 100..018 | lub = 100..012] =

3.(6p) Dane s liczby 48-bitowe {x47 x46 ... x1 x0} oraz {y47 y46 ... y1 y0} w kodzie uzupełnieniowym U2: ą

0 11 1 00 10 11 11 01 10 0 110 10 10 1101 0 110 0 110 1010 1101 0 110

0 10 1 01 10 10 10 00 10 1 111 01 10 1010 1 111 1 111 0110 1010 1 111

ła cuch propagacji przeniesienia w dodawaniu – kolejne pozycje takie, e xi ≠ yi. (podkre lone) ń

ż

ś

generacja przeniesienia w dodawaniu – pary pozycji takich, e xi =yi.=1 (kursywa) ż

0111 0 010 1111 0110 0110 1010 11 01 011 0 011 0 1 010 11 01 011 0

0101 0 110 1010 0010 1111 0110 10 10 111 1 111 1 0 110 10 10 111 1

ła cuch propagacji przeniesienia w odejmowaniu – kolejne pozycje takie, e xi =yi. (podkre lone) ń

ż

ś

generacja przeniesienia w odejmowaniu – pary pozycji takich, e xi =0 yi.=1 (kursywa) ż

( n = 48) nie* wyst pi nadmiar, bo cn = cn–1 (oraz sn = sn–1 ) ą

albo nie* wyst pi nadmiar, bo cn ≠ cn–1 (oraz sn ≠ sn–1 ) ą

4.(4p) Oblicz z dokładno ci do 2 pozycji cz ci ułamkowej 101011

, 11 = | 1 | 0 | x |,| y | z |

ś

ą

ę

ś

2

5.(4p) Reguła Booth’a w bazie 4 |{x7... x1x0}|U2 = |{y7... y1y0}|SD+1* i [2*y2i+1+y2i= (–2x2i+1+x2i+x2i–1)]

( w algorytmie odwrotnym |{x7... x1x0}|U2 = 2*|{y7... y1y0}|SD–x0 i [2*y2i+1+y2i= (–2x2i+2+x2i+1+y2i)]

– w obu przypadkach y2i+1*y2i = 0 – przynajmniej jedna z cyfr pary jest zerem) ARYTMETYKA – EGZAMIN 0

schemat rozwi zania

 Janusz Biernat

ą

Zadania kolokwialne – schematy rozwi za

ą

ń

6.(6p) Dwoma sposobami mno enie liczb w kodzie U2 (0zz...zz – uzupełnienie 1xx...xx) ż

1 x x x x

1 x x x x

× 1 ... 0 ... 1

× 1 ... 0 ... 1

1 1 1 1 1 1 x x x x

× 1

0 x x x x

... ... ... ... ... ...

...

... ...

...

0 0 0 0 ...

× 0 (0)

1 0 0 0 0

... ... ... ...

...

... ...

...

0 0 z z z z

× –1

1 z z z z

b b

1 0 0 0 0 1

b

b

Uwaga: Je li mno nik ma mniej bitów ni mno na, nie ma potrzeby rozszerzania mno nika.

ś

ż

ż

ż

ż

W mno eniu bez rozszerze korekcyjna „ 1 ” jest zawsze na pozycji najwy szego bitu mno nej!

ż

ń

ż

ż

7.(6p) Dodanie N liczb m-bitowych w kodzie naturalnym wymaga ....-poziomowego sumator CSA.

Wynik b dzie .....-bitowy, a ko cowe dodawanie obejmie ..... bitów. Całkowity czas sumowania ę

ń

przy u yciu sumatora sum warunkowych jest ...... razy wi kszy od czasu dodawania 1-bitowego ż

ę

( T=2), a przy u yciu sumatora z przeskokiem przeniesie ( T = 2 ⋅ 2 n ) ....... razy wi kszy.

ż

ń

ę

Liczba sumatorów elementarnych w drzewie CSA – m×( N–2) → A = 7 m×( N–2) + ACPA Liczba poziomów p – odpowiednio do skali redukcji ( k 0=2): ks– 1 < N ≤ ks, gdzie ki= ki–1+  ki/2

czyli k

p

3

≤

≤

1– k 2– k 3–... = 3–4–6–9–13–19–18–42–... lub z oszacowania

p

(

2

2)

N

(

2 )

2

Liczba bitów wyniku d = log2 N + m (dokładniej d = log2 [ N*(2 m–1)]

Liczba bitów ko cowego sumowania r ≈ m (wyniki na pozycjach najni szych s gotowe po redukcji ń

ż

ą

na pozycjach najwy szych pojawiaj si dodatkowe bity znacz ce w tej samej liczbie)

ż

ą

ę

ą

Czas dodawania ko cowego (znormalizowany czas dodawania 1 -bitowego wynosi T = 4) ń

• w sumatorze sum warunkowych – T

( r) = 2 ⋅ log r

COSA

2

• w sumatorze z przeskokiem przeniesie – T

( r) = 2 ⋅ 2 r

ń

CSKA

Całkowity czas sumowania = czas redukcji na p poziomach + czas ko cowego dodawania CPA: i ń

T= 4 p+ TCPA( r) tzn. T/4 razy wi kszy od czasu dodawania 1-bitowego ę

8.(5p) Stosuj c metod dzielenia nieodtwarzaj cego oblicz 3 pierwsze reszty i 3 pierwsze cyfry ilorazu ą

ę

ą

– D

k =

X : D

0, x

x x x

: 0, d d d d

–/+ D

0

q 0 =

0

q 1 =

q 2 =

Komentarz:

• sprawdzamy warunek | X| < | D| – je li nie jest spełniony skalujemy dzieln ( k = ....) ś

ą

• je li XD > 0 obliczamy reszt zerow r 0 = X– D, w przeciwnym razie r 0 = X+ D, ś

ę

ą

• je li ri D > 0, cyfr ilorazu jest qi = 1 i od przeskalowanej reszty 2 ri odejmujemy D, ś

ą

w przeciwnym razie ( ri D > 0), cyfr ilorazu jest qi = 0 i do reszty 2 ri dodajemy D

ą

• otrzymany iloraz (1, xx... lub 0, xx... ) skalujemy odwrotnie ni dzieln ż

ą

ARYTMETYKA – EGZAMIN 0

schemat rozwi zania

 Janusz Biernat

ą