Stałopozycyjna reprezentacja liczb

Kody (zapisy) stałopozycyjne (integer) - do zapisu liczb całkowitych

• Kod NKB (naturalny kod binarny - natural binary code)

• Zapis ZM (znak - moduł - sign -magnitude)

• Zapis U1 (zapis uzupełnień do 1 - 1s complement)

• Zapis U2 (zapis uzupełnień do 2 - 2s complement)

Reprezentacja liczb całkowitych (słowa 8-bitowe)

A	ZM	U1	U2	NKB
-127 -126 .... -4 -3 -2 -1 -0 +0 +1 +2 +3 +4 .... +126 +127	1 1111111 1 1111110 .... 1 0000100 1 0000011 1 0000010 1 0000001 1 0000000 0 0000000 0 0000001 0 0000010 0 0000011 0 0000100 .... 0 1111110 0 1111111	1 0000000 1 0000001 .... 1 1111011 1 1111100 1 1111101 1 1111110 1 1111111 0 0000000 0 0000001 0 0000010 0 0000011 0 0000100 .... 0 1111110 0 1111111	1 0000000 1 0000001 .... 1 1111100 1 1111101 1 1111110 1 1111111 0 0000000 0 0000000 0 0000001 0 0000010 0 0000011 0 0000100 .... 0 1111110 0 1111111	0 0000000 0 0000001 0 0000010 0 0000011 0 0000100 .... 0 1111110 0 1111111

Charakterystyka ZM, U1 i U2

Podobieństwa

1. bit najbardziej znaczący - bit znaku

2. Dla A>0 tożsame z NKB

Różnice

	ZM	U1		U2
Liczba zer	2 Moduł liczby dodatniej	2 Negacja bitów NKB	1 Negacja bitów NKB +1
Moduł (A<0)

Przykład: jak powstaje zapis liczby -3 w U1 i U2

ZM	U1	U2
1 0000011	Negacja bitów modułu 1 1111100	Negacja bitów modułu 1 1111100 Zanegowany moduł +1:1 1111101

Przedziały liczb całkowitych słowa (n-binarne)

n	ZM, U1 i U2		NKB
		Min -2^n-1+1	Max = 2^n-1-1	<0, 2^n-1>
1 2 3 4 5 6 7 8 16 32 64	0 -1 -3 -7 -15 -31 -63 -127 -32 769 -2 147 483 647 -9 223 372 036 854 780 000	0 1 3 7 15 31 63 127 32 769 2 147 483 647 9 223 372 036 854 780 000	1 3 7 15 31 63 127 255 65 535 4 294 967 295 18 446 744 073 709 600 000

Algorytm dodawania dwóch dodatnich liczb a i b (słowa n-binarne)

(zapisy: ZM, U1 i U2)

START

c =0

i = 0

y[i] = a[i] XOR (b[i] XOR c

c= (a[i] AND b[i] OR (a[i] AND c) OR b[i] AND c)

NIE

i = n-1 i = i +1

TAK

TAK c =1 NIE

Wynik y i c Wynik y

STOP

Funkcje logiczne Boole'a w algorytmie

A	B	A AND B	A OR B	A XOR B
0 0 1 1	0 1 0 1	0 0 0 1	0 1 1 1	0 1 1 0

Tabela prawdy definiujaca sumowanie dwóch bitów

a[i]	b[i]	c[i]	y[i]	c[i+1]
0 1 0 1 0 1 0 1	0 0 1 1 0 0 1 1	0 0 0 0 1 1 1 1	0 1 1 0 1 0 0 1	0 0 0 1 0 1 1 1

Dwa przypadki wyniku dodawania

Wynik dodawania bez przeniesienia		Wynik dodawania z przeniesieniem
Wartości dziesiętne	Wartości ZM, U1, U2	Wartości dziesiętne	Wartości ZM, U1, U2
100 + 27 = 127 Czytaj:	0 1100100 + 0 0011011 = (0) 0 0111111 6 i przeniesienie 0	89 + 45 = 134 Czytaj:	0 1011001 + 0 0101101 = (1) 0 0000110 6 i przeniesienie 128

Algorytm odejmowania dwóch liczb: a i b (słowa n-binarne)

(zapis ZM)

START

1 =0

y[i] = a[i] XOR b[i]

c= (a[i] AND b[i] OR (a[i] AND c) OR b[i] AND c)

1

NIE

a[i] < b[i] i = i +1

TAK NIE

j = i +1 i = n-1

a[j] = NOT a[j] TAK

TAK a[j] = 0 STOP

1

NIE

j = j+1

Algorytm odejmowania w U1

1. Łatwiejszy w porównaniu z ZM.

2. Dodawanie wszystkich pozycji bitowych wraz z bitem znaku.

3. Korekta wyniku uwzględniająca powstałe przeniesienie.

4. Korekta polega na dodaniu przeniesienia (jedynki) do najmniej znaczącej pozycji bitowej wyniku

Algorytm odejmowania w U2

1. Łatwiejszy w porównaniu z U1.

2. Dodawanie wszystkich pozycji bitowych wraz z bitem znaku.

3. Ignorowanie powstałego przeniesienia.

Odejmowanie liczb o różnych zapisach

Liczby dziesiętne	ZM	U1	U2
Odjemna Odjemnik Różnica Korekta (U1) Różnica (U1)	+9 -7 +2	0 1001 - 1 0111 0 0010	0 1001 + 1 1000 (1) 0 0001 + 1 0 0010	0 1001 + 1 1001 (1) 0 0010

Mnożenie stałopozycyjne

Zasada ogólna: Jeśli mnożna i mnożnik są słowami n-binarnymi, to iloczyn jest słowem 2n-binarnym

Mnożenie w zapisie ZM

1^o. Porównanie bitów znaków: przyjęcie jako znaku wyniku SUMA MOD2.

2^o. Właściwe mnożenie: podobne do mnożenia dwóch liczb dziesiętnych na papierze

Przykład: Mnożenie liczb o modułach 4-bitowych (a=5, b=6)

0101

x 0110

0000

0101

0101

0000

= 00011110

Sumator z dwoma rejestrami robi to tak:

Rejestr mnożnika (M) ← 0110

R - rejestr mnożnej
Dzielenie	RH	RL
Wpisanie danych + = SHR + = SHR + = SHR + = SHR	0000 0110 0110 0011 0000 0011 0001 0110 0111 0011 0000 0011 0001	0101 0101 0010 0010 1001 1001 1100 1100 1110

Mnożenie w zapisie U1

1^o. Porównanie bitów znaków: przyjęcie jako znaku wyniku SUMA MOD 2.

2^o.Właściew mnożenie:

• jeżeli obie liczby dodatnie - jak w ZM;

• jeżeli obie ujemne - jak w ZM, ale zanegowane bity modułów;

• jeżeli są przeciwnych znaków to, to mnożna - liczba dodatnia, mnożnik liczba ujemna.

Przykład: Mnożenie liczb o modułach 4-bitowych (a = 5, b = -6)

Rejestr mnożnika (M) ← 1001

R- rejestr mnożnej			R- rejestr mnożnej
Dzielenie	RH	RL	Dzielenie	RH	RL
Wpisanie danych + = SHR + = Korekta + = SHR	0000 1001 1001 1100 1111 (1) 1011 1 1100 1110	0101 0101 1010 1010 1010 0101	(c. d.) + = Korekta + = SHR + = Korekta + = SHR	1110 1001 (1) 0111 1 1000 1100 1111 1011 1 1100 1110	0101 0101 0101 0010 0010 0010 0001

Dzielenie stałopozycyjne:

Uwagi ogólne:

1. Wynik (iloraz) składa się z dwóch części: część całkowita i reszta.

2. Jeśli żądana długość ilorazu (część całkowita) wynosi k bitów a dzielnik ma długość m bitów, to wymagana minimalna długość dzielnej wynosi n = k + m - 1 bitów.

Dzielenie w zapisie ZM

1^o. Porównanie bitów znaków: przyjęcie jako znaku wyniku SUMA MOD2.

2^o. Właściwe mnożenie: podobne do dzielenia dwóch liczb dziesiętnych na „papierze”.

3^o. Liczba iteracji: n - m +1

Przykład: a = +14 -dzielna 4-bitowa, b = +3 -dzielnik 2-bitowy

Iteracja Komentarz Bity ilorazu 1 0 0

1 odejmujemy 1 1 1 1 0 : 1 1

1 1

2 nie odejmujemy 0 0 1

1 1

3 nie odejmujemy 0 0 1 0

1 1

Reszta: 1 0

4-bitowy rejestr dzielnika (M) ← 0011

R - rejestr dzielnej (8-bitowy)
Dzielenie	RH	RL
Wpisanie danych SHL Nie odejmujemy (0) SHL Odejmójemy (1) = SHL Nie odejmujemy (0) SHL Wynik:	0000 0001 0011 0011 0011 0000 0001 0011 0010 (reszta)	1110 1100 1100 1000 1001 1001 0010 0010 0100 (część całkowita)

---