Systemy liczbowe i kodowanie
1. Wprowadzenie
Informatyka - zespół dyscyplin nauki i techniki, które zajmują się przetwarzaniem informacji.
Informacja  pojęcie o ró\
nych definicjach w ró\
nych dziedzinach. Np. w naukach ścisłych
(ogólnie) oznacza pewną własność rozpatrywanych obiektów.
- wartość liczbowa,
- kolor,
- stan układu sterowania.
Zapis informacji  przedstawienie informacji w postaci ciÄ…gu ustalonych symboli.
- informacja alfanumeryczna  zawierajÄ…ca cyfry i takie symbole jak: !, @, #, $, %, &, *, (, +,
:,  , <, itp.
- informacja cyfrowa  składająca się z ustalonych cyfr.
Alfabet  skończony niepusty zbiór symboli słu\
Ä…cych do zapisu informacji.
- alfabet języka pisanego,
- alfabet binarny (dwójkowy)  zawiera dwa symbole: 0 i 1.
Słowo  skończony ciąg symboli danego alfabetu.
SÅ‚owa binarne:
- bit  słowo dwójkowe zawierające jeden symbol (alfabetu binarnego),
- tetrada  słowo dwójkowe zawierające cztery symbole (alfabetu binarnego),
- bajt  słowo dwójkowe zawierające osiem symboli (alfabetu binarnego).
Kodowanie - przyporządkowanie poszczególnym informacjom (obiektom zbioru kodowanego)
odpowiadających im słów kodowych, przy czym ka\
demu słowu kodowemu odpowiada
dokładnie jeden element kodowany (informacja).
- kody alfanumeryczne  odwzorowanie symboli alfanumerycznych w słowa binarne (CCITT,
ISO-7, ISO-8859-2, ...),
- kody liczbowe,
- kody kontrolne (detekcyjne i korekcyjne),
- ...
Systemy liczbowe  zestaw reguł umo\
liwiających przedstawienie liczb za pomocą określonych
symboli (cyfr) oraz wykonywanie na tych liczbach określonych działań (operacji
arytmetycznych).
- pozycyjne systemy liczbowe  znaczenie cyfry (wartość) jest uzale\
nione od pozycji, które
zajmuje w liczbie (przykład: system dziesiątkowy, np. 7744)
- niepozycyjne systemy liczbowe  znaczenie cyfry jest niezale\
ne od zajmowanej pozycji w
liczbie (przykład: system rzymski, np. XVIII (wiek)).
" Ogólnie, dowolna liczba rzeczywista R:
R = a1Å"Ä…1+ ... + aiÅ"Ä…i + akÅ"Ä…k
gdzie: ai  cyfra i-tej pozycji, Ä…i  waga i-tej pozycji.
Przedstawienie (rozwinięcie) liczby R:
(R)Ä…1,..., Ä…i,..., Ä…k = (a1,...,ai,...,ak) Ä…1,..., Ä…i,..., Ä…k
1
2. Pozycyjne systemy liczbowe
W systemach pozycyjnych ka\
da pozycja ma jednoznacznie określoną, stałą wagę liczbową i dla
wszystkich wag prawdziwe jest:
Ä…i+1
= p , i=1,...,k.
Ä…i
p  podstawa (baza, rzÄ…d, zasada) systemu pozycyjnego.
Przedstawienie liczby R w systemie o podstawie p:
(R)p = Ä…(a1 a2 ... ak-1 ak)p
Jeśli nie ma wątpliwości jaka jest podstawa wtedy często nie oznacza się jej.
" W technice komputerowej wykorzystywane są głównie systemy: dwójkowy, ósemkowy
dziesiątkowy (dziesiętny) i szesnastkowy (heksadecymalny).
- układ dwójkowy: p=2, ai " {0, 1},
- układ ósemkowy: p=8, ai " {0, 1, 2, 3, 4, 5, 6, 7},
- układ dziesiętny: p=10, ai " {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
- układ szesnastkowy: p=16, ai " {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F }  (A=10, B=11,
C=12, D=13, E=14, F=15),
Poni\
ej przedstawiono przykładowe wartości liczb całkowitych zapisanych w ró\
nych
systemach.
| System dziesiętny | System dwójkowy | System ósemkowy | System szesnastkowy |
--------------------------------------------------------
0 0 0 0
1 1 1 1
2 10 2 2
3 11 3 3
4 100 4 4
5 101 5 5
6 110 6 6
7 111 7 7
8 1000 10 8
9 1001 11 9
10 1010 12 A
11 1011 13 B
12 1100 14 C
13 1101 15 D
14 1110 16 E
15 1111 17 F
16 10000 20 10
17 10001 21 11
18 10010 22 12
19 10011 23 13
20 10100 24 14
100 1100100 144 64
127 1111111 177 7F
128 10000000 200 80
255 11111111 377 FF
256 100000000 400 100
1000 1111101000 1750 3E8
--------------------------------------------------------
2
2.1. Reprezentacja liczb rzeczywistych
" DowolnÄ… liczbÄ™ rzeczywistÄ…:
- mo\
na przedstawić za pomocą skończonego, niepustego zbioru symboli zwanych cyframi.
- mo\
na przedstawić w ró\
nych systemach pozycyjnych,
- w systemie dziesiętnym liczby zapisuje się w postaci ciągu cyfr dziesiętnych,
reprezentowanych przez znaki: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9  np. 1939,17.
- w systemie dwójkowym liczby zapisuje się za pomocą alfabetu binarnego  np. liczba
101,01 reprezentuje liczbę dziesiętną o wartości 5,25.
- w językach programowania, w celu oddzielenia części całkowitej od ułamkowej, stosuje się
kropkÄ™ (np. 1939,17), w matematyce stosuje siÄ™ przecinek, np. (1939,17).
" Ogólnie: liczba rzeczywista R w układzie pozycyjnym o podstawie p > 1 jest zapisywana w
następujący sposób:
(R)p = Ä… (C, U)p = (C)p,(U)p
- C  część całkowita, U  część ułamkowa,
- zakres u\
ywanych cyfr: od 0 do p-1:
ai " {0, 1, ..., (p-1)}
" Zapis liczb na z góry ustalonej liczbie pozycji.
- na ogół liczby zapisuje się na z góry ustalonej liczbie pozycji (np. w komputerach
podstawową jednostką przetwarzania danych jest słowo maszynowe  np. 16-bitowe),
- w arytmetyce stałopozycyjnej miejsce przecinka jest ustalone  np. zakłada się, \
e część
całkowita liczby składa się (maksymalnie) z n cyfr, natomiast część ułamkowa z m cyfr,
- w stałopozycyjnym systemie liczbowym (n, m) o podstawie p liczbę R zapisujemy w postaci:
(R)p = Ä… (an-1 an-2... a1 a0 , a-1 a-2 ... a-(m-1) a-m)p
jej wartość wynosi:
(R)p = Ä… (an-1Å"pn-1+ an-2Å"pn-2+ ... + a1Å"p1+ a0Å"p0+ a-1Å"p-1+ a-2Å"p-2+ ... + a-(m-1)Å"p-(m-1) + a-mÅ"p-m)
równowa\
ny zapis ma postać:
n-1
R = Ä… pi
"ai
i=-m
- wartość maksymalna: Rmax = pn - p-m ,
- dodatnia wartość minimalna: Rmin = p-m ,
- liczba ró\
nych liczb: L = pn+m ,
- bezwzględny błąd przedstawienia liczby: " = min(Ri, Rj) = p-m , gdzie: Ri `" Rj .
Przykłady:
" Liczba R = 123,75(10) jest reprezentowana w układzie dziesiętnym w postaci:
123,75(10) = (1Å"102 + 2Å"101 + 3Å"100 + 7Å"10-1 + 5Å"10-2 ).
" W układzie dwójkowym liczba R = 1111011,11(2) ma następującą reprezentację:
1111011,11(2) = 1Å"26 + 1Å"25 + 1Å"24 + 1Å"23 + 0Å"22 + 1Å"21 + 1Å"20 + 1Å"2-1 + 1Å"2-2 =
= 64 + 32 + 16 + 8 + 0 + 2 + 1 + 0,5 + 0,25 = 123,75.
3
" Dla słów 4-bitowych (p=2), w których 2 bity są przeznaczone na kodowanie części
całkowitej i dwa bity na kodowanie części ułamkowej wartości maksymalna, minimalna,
liczba wartości i dokładność kodowania wynoszą:
Rmax = 2-2 - 2-2 = 4  0,25 = 3,75
Rmin = 2-2 = ź = 0,25
L = 22+2 =24 = 16
" = 2-2 = ź = 0,25
Dopuszczalne słowa kodowe to:
00,00(2) = 0,00(10),
00,01(2) = 0,25(10),
00,10(2) = 0,50(10),
00,11(2) = 0,75(10),
01,00(2) = 1,00(10),
...
11,00(2) = 3,00(10),
11,01(2) = 3,25(10),
11,10(2) = 3,50(10),
11,11(2) = 3,75(10).
4
2.2. Konwersja liczb
" Określanie dla liczby
(X)p=(C)p,(U)p=(xn-1 xn-2... x1 x0 , x-1 x-2 ... x-m+1 x-m)p
w systemie liczbowym o podstawie p jej odpowiednika
(X)s=(C)s,(U)s=(x2 x2 ... x2 x2 , x2 x2 ... x2 x2 )s
u-1 u-2 1 0 -1 -2 -(v-1) -v
w systemie liczbowym o podstawie s.
" Zakładamy znajomość operacji arytmetycznych w systemie liczbowym o podstawie p.
Metoda bezpośrednia I
" Cyfry xi liczby (X)p i podstawÄ™ p wyra\
amy przez odpowiedniki w systemie o podstawie s:
(xi)s, (p)s.
" Realizujemy działania w systemie o podstawie s:
n-1
(X )s = )s Å" ( p)i
"(xi s
i=-m
Przykład  konwersja dwójkowo-dziesiętna.
Liczba w systemie dwójkowym (X)2=(10101,0101)2.
(X)10 = 1Å"24 + 0Å"23 +1Å"22 + 0Å"21 + 1Å"20 + 0Å"2-1 + 1Å"2-2 + 0Å"2-3 + 1Å"2-4 +
= 16 + 0 + 4 + 0 + 1 + 0 + 0,25 + 0 + 0,0625 = 21,3125
Metoda bezpośrednia II
" Działania realizujemy w systemie o podstawie s wyra\
ajÄ…c cyfry xi i podstawÄ™ p w systemie
o podstawie s, i korzystajÄ…c z zale\
ności:
n-1
xi Å" pi = (...((xn-1 Å" p + xn-2 ) Å" p + xn-3) Å" p + ... + x1) Å" p + x0 +
"
i=-m
+ p-1 Å" (x-1 + p-1 Å" (x-2 + ... + p-1 Å" (x-(m-1) + p-1 Å" x-m )...))
Przykład 1  konwersja dwójkowo-dziesiętna.
Liczba w systemie dwójkowym (X)2=(10101,0101)2.
(C)2 = 1 0 1 0 1
| | | | |
(C)10 = (1Å"2+0)Å"2+1)Å"2+0)Å"2+1 = 21
(U)2 = 0, 0 1 0 1
| | | |
(C)10 = 2-1Å"(0+2-1Å"(1+2-1Å"(0+2-1Å"1))) = 0,5Å"(0,5Å"(1+0,5Å"(0,5))) = 0,5Å"0,5Å"1,25 = 0,3125
(X)10 = 21,3125
Przykład 2  konwersja dwójkowo-szesnastkowa.
Liczba w systemie dwójkowym (X)2=(10101,0101)2.
(C)2 = 1 0 1 0 1
| | | | |
(C)16 = (116Å"216+016)Å"216+116)Å"216+016)Å"216+116 = (216Å"216+116)Å"216Å"216+116 = 516Å"216Å"216+116 =
A16Å"216+116 = 1416 + 116 = 1516
5
(U)2 = 0, 0 1 0 1
| | | |
(C)10 = 0,816 Å" (016 + 0,816 Å" (116 + 0,816 Å" (016 + 0,816 Å" 116))) =
| | | |
× 0,A16 × 1,416 × 0,816 × 116
0,516 2 0 = 0,416 = 0,816
+ 0,8
0,A0
(X)16 = 15,516
Metoda ilorazowo-iloczynowa
" Cyframi x2 (x2 " {0, 1, ..., s-1}) części całkowitej (C)s są reszty ri z dzielenia całkowitego
i i
przez s w systemie o podstawie p części całkowitej (C)p i kolejnych ilorazów Ii a\
do uzyskania
wartości ilorazu Ik-1=0.
(C)p : s = I0 reszta r0 x2 =r0 ,



0
I0 : s = I1 reszta r1 x2 =r1 ,



1
...
Ik-3 : s = Ik-2 reszta rk-2 x2 =rk-2 ,



k-2
Ik-2 : s = 0 reszta rk-1 x2 =rk-1 ,



k-1
" Cyframi x2 (x2 " {0, 1, ..., s-1}) części ułamkowe (U)s są cyfry przeniesienia ci
-i -i
przenoszone na część całkowitą otrzymywane w wyniku mno\
enia przez s w systemie o
podstawie p części ułamkowej (U)p i kolejno uzyskiwanych części ułamkowych Ii a\
do
uzyskania wartości części ułamkowej Iv=0 lub maksymalnej liczby cyfr części ułamkowej (U)s.
(U)p Å"
Å" s = I1 + c1 x2 =c1 ,
Å"
Å"
-1
I1 Å"
Å" s = I2 + c2 x2 =c2 ,
Å"
Å"
-2
...
Iv-1 Å"
Å" s = Iv + cv x2 =cv ,
Å"
Å"
-v
(U)s = (x2 x2 ... x2 x2 )s + µv
-1 -2 -(v-1) -v
" µv  bÅ‚Ä…d zaokrÄ…glenia: µv = IvÅ"s-v .
Å"
Å"
Å"
Przykład  konwersja dziesiętno-binarna.
Liczba w systemie dziesiętnym X=35,6875(10).
a) Określamy (C)2 z (C)10 = 35(10) :
35 : 2 = 17 reszta 1 = a0
17 : 2 = 8 reszta 1 = a1
8 : 2 = 4 reszta 0 = a2
4 : 2 = 2 reszta 0 = a3
2 : 2 = 1 reszta 0 = a4
1 : 2 = 0 reszta 1 = a5
0 - koniec dzielenia
(C) = 35(10) = 100011(2).
b) Określamy (U)2 z (U)10 = 0,6875(10) :
0,6875 Å" 2 = 1,375 = 0,375 nadmiar 1 = a-1
0,375 Å" 2 = 0,75 = 0,75 nadmiar 0 = a-2
0,75 Å" 2 = 1,5 = 0,5 nadmiar 1 = a-3
0,5 Å" 2 = 1,0 = 0,0 nadmiar 1 = a-4
0,0 - koniec mno\
enia
(U) = 0,6875(10) = 0,1011(2).
Ostatecznie: X = 35,6875(10) = 100011,1011(2)
6
Przykład  konwersja dziesiętno-ósemkowa
Liczba w systemie dziesiętnym X=35,6875(10).
Dopuszczalne cyfry : { 0, 1, 2, 3, 4, 5, 6, 7 }.
35 : 8 = 4 reszta 3 = a0
4 : 8 = 0 reszta 4 = a1
0  koniec dzielenia
0,6875 Å" 8 = 5,5 = 0,5 nadmiar 5 = a-1
0,5 Å" 8 = 4,0 = 0,0 nadmiar 4 = a-2
0,0  koniec mno\
enia
X = 35,6875(10) = 43,54(8).
Przykład  konwersja dziesiętno-szesnastkowa.
Liczba w systemie dziesiętnym X=35,6875(10).
Dopuszczalne cyfry : { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F }.
35 : 16 = 2 reszta 3 = a0 (cyfra najmniej znaczÄ…ca LSD)
2 : 16 = 0 reszta 2 = a1
0  koniec dzielenia
0,6875 Å" 16 = 11,0 = 0,0 nadmiar 11 = a-1 = B
0,0  koniec mno\
enia
X = 35,6875(10) = 23,B(16).
Metoda ró\
nicowa
" Liczbę (X)s otrzymujemy z (X)p odejmując od niej (i od tak otrzymanych ró\
nic) kolejne
potęgi podstawy s systemu, w której ma być wyra\
ona, rozpoczynając od największej z
potęg, która jest mniejsza lub równa tej liczbie.
" Odjęcie lub nie potęgi r podstawy s wyznacza cyfrę x2 liczby (X)s  1 gdy odjęcie jest
r
mo\
liwe (sr jest mniejsze lub równe wcześniej otrzymanej ró\
nicy), 0 gdy odjęcie nie jest
mo\
liwe.
" Konwersja jest realizowana a\
otrzymuje się ró\
nicę równą zero lub uzyskuje się wymaganą
dokładność.
Przykład  konwersja dziesiętno-dwójkowa.
Liczba w systemie dziesiętnym X=21,3125(10).
21,3125 - 24 = 5,3125 x2 = l
4
5,3125 - 23 < 0 x2 = 0
3
5,3125 - 22 = 1,3125 x2 = l
2
1,3125 - 21 < 0 x2 = 0
1
1,3125 - 20 = 0,3125 x2 = l
0
0,3125 - 2-1 < 0 x2 = 0
-1
0,3125 - 2-2 = 0,0625 x2 = l
-2
0,0625 - 2-3 < 0 x2 = 0
-3
0,0625 - 2-4 = 0 x2 = l
-4
(X)2 = 10101,01012
7
Konwersja z systemu binarnego do systemu o podstawie p=2k (k=2, 3, ...)  metoda
podziału
" Podział cyfr (bitów) zaczynając od przecinka w lewo a następnie w prawo na grupy
pozwalające określić wartości cyfr liczby przedstawionej w systemie o podstawie p=2k. Jeśli
grupa nie jest pełna to dopisuje się zera.
" Konwersja dwójkowo-ósemkowa  podział na grupy trzybitowe (triady).
" Konwersja dwójkowo-szesnastkowa  podział na grupy czterobitowe (tetrady).
Przykład  konwersja dwójkowo-ósemkowa i dwójkowo-szesnastkowa
a) Liczba X = 35,6875(10) = 100011,1011(2).
d.-ósemkowa: 100011,1011(2) = 100 011, 101 100(2) = 43,54(8)
d-szesnastkowa: 100011,1011(2) = 0010 0011, 1011(2) = 23,B(16) .
b) Liczba X = 1964,18359375(10) = 11110101100,00101111(2).
d.-ósemkowa: 11110101100,00101111(2) = 011 110 101 100 , 001 011 110(2) = 3654,136(8)
d-szesnastkowa: 11110101100,00101111(2) = 0111 1010 1100 , 0010 1111(2) = 7AC,2F(16) .
8