KOLOS Z INFORMATYKI - LEVEL 2
1. Podać wartość minimalną (ale >0) i maksymalną liczby w kodzie
stałopozycyjnym
1
, jeśli na część stałą przeznaczono 5 lub 6 bitów, a na
część ułamkową 3.
W zasadzie powtórka z rozrywki: liczby w kodzie stałopozycyjnym to po prostu liczby
z jakimś „ogonem” po przecinku, np.: liczbę 110010,011 można podzielić na:
CZĘŚĆ STAŁĄ
CZĘŚĆ UŁAMKOWĄ
1
1
0
0
1
0
0
1
1
co daje wartość 50,375. Zatem wartość maksymalna to 11111,111 (lub 111111,111),
a minimalna: 00000,001 (lub 000000,001). Z zamianą każdy chyba sobie radę da...
2.
Liczbę zapisaną w systemie dziesiętnym zapisać w kodzie ZNAK-
MODUŁ.
W systemie tym stosujemy bardzo prostą metodę kodowania liczb ze znakiem.
Najstarszy bit liczby jest bitem znaku. Reszta bitów określa wartość bezwzględną
(moduł) liczby: Jeśli przyjmiemy do zapisu liczb format całkowity n-bitowy, to liczby w
kodzie znak-moduł mają następującą postać:
c
n-1
c
n-2
c
n-3
...c
2
c
1
c
0
znak
moduł
Wartość n-bitowej, całkowitej liczby w dwójkowym kodzie znak-moduł obliczamy wg
wzoru:
c
n-1
c
n-2
c
n-3
...c
2
c
1
c
0 =
(1 - 2 × c
n-1
) ×
n-2
i = 0
c
i
2
i
Wyrażenie (1 - 2 × bit znaku) przyjmuje odpowiednio wartość 1, gdy bit znaku jest
równy 0, a -1, gdy bit znaku ma wartość 1, czyli określa liczbę ujemną. W dalszej
części wzoru mamy obliczanie wartości pozostałych bitów, czyli modułu. Moduł jest
przemnażany przez wyrażenie znakowe i w efekcie otrzymujemy wartość dodatnią
lub ujemną w zależności od stanu bitu znaku.
1
Lub pozycyjnym, nie pamiętam już dokładnie jak dyktował.
Przykład
n = 4 bity
0
110
(z-m)
= (1 - 2 ×
0
) x (
0
× 2
0
+
1
× 2
1
+
1
× 2
2
)
0
110
(z-m)
= (1 - 2 ×
0
) x (
0
× 1 +
1
× 2 +
1
× 4)
0
110
(z-m)
= 1 × ( 2 + 4)
0
110
(z-m)
= 6
(10)
1
011
(z-m)
= (1 - 2 ×
1
) × (
1
× 2
0
+
1
× 2
1
+
0
× 2
2
)
1
011
(z-m)
= (1 - 2 ×
1
) × (
1
× 1 +
1
× 2 +
0
× 4)
1
011
(z-m)
= -1 × (1 + 2)
1
011
(z-m)
= -3
(10)
Jeśli chcemy daną wartość przedstawić w dwójkowym kodzie znak-moduł, to
najpierw znajdujemy przedstawienie dwójkowe modułu tej wartości, następnie
uzupełniamy bity do zadanego formatu i dodajemy bit znaku 0 dla wartości dodatniej
lub 1 dla ujemnej.
Przykład
Przedstawić wartość -69 w 8-bitowym kodzie znak-moduł.
1. Znajdujemy przedstawienie dwójkowe modułu
w ← 69 / 2 = 34 i reszta 1
w ← 34 /2 = 17 i reszta 0
w ← 17 / 2 = 8 i reszta 1
w ← 8 / 2 = 4 i reszta 0
w ← 4 / 2 = 2 i reszta 0
w ← 2 / 2 = 1 i reszta 0
w ← 1 / 2 = 0 i reszta 1
69
(10)
= 1000101
(2)
2. Otrzymaną liczbę dwójkową uzupełniamy bitem znaku i otrzymujemy:
-69
(10)
= 11000101
(z-m)
2
3. Liczbę zapisaną w kodzie uzupełnień do dwóch (U2) zapisać w postaci
dziesiętnej.
Budowa liczby w kodzie U2 jest podobna do kodu znak-moduł. Jednak teraz pozycja
znakowa (najstarszy bit) posiada swoją wagę i uczestniczy w wartości liczby jak każda
inna pozycja.
Waga pozycji znakowej jest ujemna:
-2
n-1
c
n-1
2
n-2
2
n-3
...2
2
2
1
2
0
c
n-2
c
n-3
...c
2
c
1
c
0
znak
moduł
2
http://edu.i-lo.tarnow.pl/inf/prg/005_pmc1/0004.php#znak-modul
Wartość n-bitowej liczby zapisanej w kodzie U2 obliczamy w standardowy sposób:
sumując kolejne iloczyny cyfr przez wagi pozycji.
Przykład
n = 4 bity
0
110
(U2)
=
0
× (-2
3
) +
0
× 2
0
+
1
× 2
1
+
1
× 2
2
0
110
(U2)
=
0
× (-8) +
0
× 1 +
1
× 2 +
1
× 4
0
110
(U2)
= 2 + 4
0
110
(U2)
= 6
(10)
1
110
(U2)
=
1
× (-2
3
) +
0
× 2
0
+
1
× 2
1
+
1
× 2
2
1
110
(U2)
=
1
× (-8) +
0
× 1 +
1
× 2 +
1
× 4
1
110
(U2)
= -8 + 2 + 4
1
110
(U2)
= -2
Proszę zwrócić uwagę na istotną różnicę w stosunku do kodu Z-M. Liczby ujemne
wyglądają inaczej niż poprzednio. Jak więc kodować liczby w kodzie U2?. Musimy
rozpatrzyć dwa przypadki:
Liczba jest dodatnia - znajdujemy jej przedstawienie binarne i uzupełniamy zerami do
przyjętego formatu. Na przykład przyjmijmy format 4-bitowy i zapiszmy w nim
wartość 3:
3
(10)
= 11
(2)
Ponieważ format ma 4 bity, to dodajemy na początku dwie cyfry 0 i otrzymujemy
liczbę dodatnią w kodzie U2:
3
(10)
= 0011
(U2)
Liczba jest ujemna. W tym przypadku bit znaku musi mieć wartość 1. Ponieważ stoi
on na pozycji o wadze -2
n-1
, a reszta liczby jest dodawana do tej wagi, to musimy
znaleźć taką wartość, która dodana do wagi bitu znaku da nam liczbę kodowaną.
Wartość tę kodujemy na pozostałych bitach. Np. zakodujmy liczbę -3 w 4-bitowym
kodzie U2. Bit znaku ma wartość -2
3
, czyli -8. Aby otrzymać -3, do -8 musimy dodać
liczbę 5 i tę wartość kodujemy na pozostałych bitach:
-8 + 5 = -3
1101
(U2)
= -3
(10)
Możemy również znaleźć przedstawienie modułu tej liczby, a następnie wyliczyć
wartość przeciwną w kodzie U2 wg przepisu:
Aby znaleźć wartość przeciwną w kodzie U2 należy wykonać następujące czynności:
1. Zamienić wszystkie bity liczby na przeciwne, tzn. 1 na 0 i 0 na 1
2. Do tak otrzymanej liczby dodać wartość 1
Czyli w naszym przykładzie najpierw znajdujemy zapis dwójkowy liczby 3:
3
(10)
= 11
(2)
Następnie uzupełniamy cyfry do 4 bitów:
3
(10)
= 0011
(U2)
Teraz postępujemy zgodnie z opisaną metodą: zamieniamy bity na przeciwne i
dodajemy 1
0011
(U2)
= 3
(10)
1100
+ 0001
1101
(2)
= -3
(10)
Otrzymaliśmy identyczną liczbę, jak poprzednio.
3
4. Na czym polega normalizacja liczb?
Normalizacja danych to skalowanie pierwotnych danych (np.: danych wejściowych)
do małego, specyficznego przedziału. Na przykład do przedziału [-1, 1] lub [0,1].
Normalizacja min-max Ta metoda przeprowadza liniową transformację pierwotnych
danych najczęściej do przedziału [0,1] według wzoru:
gdzie [min, max] jest przedziałem, w którym mieszczą się dane wejściowe, natomiast
[new_min, new_max] jest nowym przedziałem danych. Np.: Jeśli V = 73600 jest w
przedziale [12000, 98000] to V’ = 0.716 w nowym przedziale [0,1].
4
5. Tabela stanów dla operacji logicznych (algebry Boole’a) dla 3
argumentów.
5
Negacja - zaprzeczenie logiczne (NOT)
Jest to operacja jednoargumentowa, tzn. rezultat zależy tylko od jednego argumentu.
Wynikiem jest wartość logiczna przeciwna do tej, którą ma argument negacji.
Negacja
a
NOT a
0
1
1
0
Jeśli operację negacji wykonamy nad słowem binarnym, to w wyniku otrzymamy
słowo, w którym wszystkie bity mają wartości przeciwne do słowa wyjściowego.
3
http://edu.i-lo.tarnow.pl/inf/prg/005_pmc1/0004.php#u2
4
http://zsi.ii.us.edu.pl/~nowak/ed/cw4.pdf
Są tam też opisy kilku innych metod, gdyby ktoś był zainteresowany
5
Jako przykłady podałem tablice stanów dla 2 argumentów, jednak każdy opatrzyłem krótkim opisem
umożliwiającym wypisanie takich tablic dla 3 i więcej argumentów.
Alternatywa - suma logiczna (OR)
Alternatywa
a
b
a OR b
0
0
0
0
1
1
1
0
1
1
1
1
W tej operacji wynik przyjmuje wartość 0 (FAŁSZ) tylko, gdy WSZYSTKIE argumenty
mają wartość 0.
Koniunkcja - iloczyn logiczny (AND)
Koniunkcja
a
b
a AND b
0
0
0
0
1
0
1
0
0
1
1
1
Odwrotnie niż poprzednio: by wynik miał wartość 1 (PRAWDA), WSZYSTKIE
argumenty muszą mieć wartość 1 (PRAWDA)
Alternatywa wykluczająca (XOR)
Jest prawdziwa wtedy i tylko wtedy, gdy dokładnie jedno ze zdań p, q jest prawdziwe:
Tablica prawdy dla alternatywy wykluczającej:
p
q
p XOR q
0
0
0
0
1
1
1
0
1
1
1
0
Negacja alternatywy wykluczającej (XNOR)
Bramka ta neguje wynik bramki XOR czyli zwraca fałsz (0), jeśli dokładnie jedno z
wejść: A lub B jest prawdą (1), a w przeciwnym wypadku zwraca prawdę.
Tablica prawdy XNOR
A
B
Q
0
0
1
0
1
0
1
0
0
1
1
1