KODOWANIE LICZB I
KODOWANIE LICZB I
TEKSTÓW
TEKSTÓW
Kody binarne
Kody binarne
kod naturalny NKB
kod naturalny NKB
kod BCD
kod BCD
kod Gray’a
kod Gray’a
inne kody
inne kody
Kodowanie znaków (tekstów)
Kodowanie znaków (tekstów)
KODOWANIE LICZB I
KODOWANIE LICZB I
TEKSTÓW
TEKSTÓW
Kody binarne
Kody binarne
kod naturalny NKB
kod naturalny NKB
kod BCD
kod BCD
kod Gray’a
kod Gray’a
inne kody
inne kody
Kodowanie znaków (tekstów)
Kodowanie znaków (tekstów)
Zbiorem
Zbiorem
kodowanym może
kodowanym może
być zbiór
być zbiór
dowolnych
dowolnych
obiektów (cyfr,
obiektów (cyfr,
liter, symboli
liter, symboli
graficznych,
graficznych,
stanów
stanów
logicznych,
logicznych,
poleceń do
poleceń do
wykonania itp.)
wykonania itp.)
Kodowaniem nazywamy przyporządkowanie poszczególnym
obiektom zbioru kodowanego odpowiadających im elementów
zwanych słowami kodowymi, przy czym każdemu słowu
kodowemu
musi
odpowiadać
dokładnie
jeden
element
kodowany
Kodowaniem nazywamy przyporządkowanie poszczególnym
obiektom zbioru kodowanego odpowiadających im elementów
zwanych słowami kodowymi, przy czym każdemu słowu
kodowemu
musi
odpowiadać
dokładnie
jeden
element
kodowany
A
A
B
B
C
C
010
010
111
111
100
100
001
001
Proces kodowania może być
Proces kodowania może być
opisem słownym, wzorem
opisem słownym, wzorem
(zależnością matematyczną),
(zależnością matematyczną),
tabelą kodową itp.
tabelą kodową itp.
Kodem liczbowym nazywamy taki kod, który liczbom dowolnego
systemu będzie przyporządkowywał słowa kodowe w postaci
zerojedynkowej (binarnej)
Kodem liczbowym nazywamy taki kod, który liczbom dowolnego
systemu będzie przyporządkowywał słowa kodowe w postaci
zerojedynkowej (binarnej)
Zbiór słów
Zbiór słów
kodowych
kodowych
KODOWANIE
KODOWANIE
Jeżeli
dowolnej
liczbie
dziesiętnej
przyporządkujemy
odpowiadająca jej liczbę binarną, to otrzymamy naturalny kod
binarny (NKB)
Jeżeli
dowolnej
liczbie
dziesiętnej
przyporządkujemy
odpowiadająca jej liczbę binarną, to otrzymamy naturalny kod
binarny (NKB)
Minimalna długość k słowa binarnego reprezentującego liczbę dziesiętną A
Minimalna długość k słowa binarnego reprezentującego liczbę dziesiętną A
musi spełniać warunek:
musi spełniać warunek:
1
2A
2
A
k
Oznacza to, że możemy przedstawiać:
Oznacza to, że możemy przedstawiać:
za pomocą 2 bitów liczby w zakresie 0
za pomocą 2 bitów liczby w zakresie 0
÷
÷
3
3
za pomocą 3 bitów liczby w zakresie 0
za pomocą 3 bitów liczby w zakresie 0
÷
÷
7
7
za pomocą 4 bitów liczby w zakresie 0
za pomocą 4 bitów liczby w zakresie 0
÷
÷
15
15
……
……
.
.
NATURALNY KOD BINARNY (NKB)
NATURALNY KOD BINARNY (NKB)
Innymi słowy
Innymi słowy
przy pomocy
przy pomocy
k
k
bitów możemy przedstawiać liczby naturalne w
bitów możemy przedstawiać liczby naturalne w
zakresie
zakresie
<0, 2
<0, 2
k
k
-1>
-1>
Gdy w systemie wygodnie jest operować liczbami dziesiętnymi
Gdy w systemie wygodnie jest operować liczbami dziesiętnymi
stosowany jest kod BCD. Liczba terad kodu BCD jest bowiem
stosowany jest kod BCD. Liczba terad kodu BCD jest bowiem
równa liczbie pozycji dziesiętnych reprezentowanej liczby. Np.
równa liczbie pozycji dziesiętnych reprezentowanej liczby. Np.
dziesiętna liczba 6-pozycyjna (000000-999999) jest kodowana
dziesiętna liczba 6-pozycyjna (000000-999999) jest kodowana
na 24 bitach
na 24 bitach
Konstrukcja:
Konstrukcja:
•
każdej cyfrze dziesiętnej przyporządkowujemy czterocyfrową
każdej cyfrze dziesiętnej przyporządkowujemy czterocyfrową
liczbę dwójkową w kodzie NKB
liczbę dwójkową w kodzie NKB
*)
*)
;
;
•
słowo kodowe w kodzie prostym BCD otrzymujemy zapisując
słowo kodowe w kodzie prostym BCD otrzymujemy zapisując
każdą cyfrę liczby dziesiętnej w postaci tetrady binarnej
każdą cyfrę liczby dziesiętnej w postaci tetrady binarnej
463
463
D
D
= 010001100011
= 010001100011
BCD
BCD
67
67
D
D
= 01100111
= 01100111
BCD
BCD
*)
*)
gdybysmy zamiast kodu NKB użyli kodu np. Gray’a wówczas
gdybysmy zamiast kodu NKB użyli kodu np. Gray’a wówczas
otrzymalibysmy kod BCD Gray’a
otrzymalibysmy kod BCD Gray’a
KOD PROSTY BCD
KOD PROSTY BCD
Kod Gray’a tworzy się z kodu naturalnego NKB biorąc pod
Kod Gray’a tworzy się z kodu naturalnego NKB biorąc pod
uwagę:
uwagę:
Kod Gray’a to taki kod, którego kolejne słowa różnią się tylko na
jednej pozycji
Kod Gray’a to taki kod, którego kolejne słowa różnią się tylko na
jednej pozycji
1
n
2
n
2
n
n
1
n
1
n
n
n
b
b
g
b
b
g
b
g
NKB
Kod Gray’a
000
000
001
001
010
011
011
010
100
110
101
111
110
101
111
100
g
g
n
n
g
g
n-1
n-1
g
g
n-2
n-2
...g
...g
n-k
n-k
- kod Gray’a
- kod Gray’a
b
b
n
n
b
b
n-1
n-1
b
b
n-2
n-2
...b
...b
n-k
n-k
- kod NKB
- kod NKB
KOD GRAY’A
KOD GRAY’A
suma modulo 2
suma modulo 2
NKB BCD Kod Gray’a
1 z 10
J ohnsona
0
0000
0000
0000
0000000001
00000
1
0001
0001
0001
0000000010
00001
2
0010
0010
0011
0000000100
00011
3
0011
0011
0010
0000001000
00111
4
0100
0100
0110
0000010000
01111
5
0101
0101
0111
0000100000
11111
6
0110
0110
0101
0001000000
11110
7
0111
0111
0100
0010000000
11100
8
1000
1000
1100
0100000000
11000
9
1001
1001
1101
1000000000
10000
Długość słowa kodu „1 z n” (w tabeli „1 z 10”)
jest równa n, tj. liczności zbioru kodowanego
(liczbie kodowanych słów)
Kod 5-bitowy stosowany do
kodowania
cyfr
dziesiętnych
Są to kody nadmiarowe (redundancyjne), w których liczba pozycji binarnych jest
większa niż wynika to z ogólnej zależności
Redundancję można wykorzystać do zwiększenia niezawodności operacji
wykonywanych na liczbach
1
2A
2
A
k
INNE KODY BINARNE
INNE KODY BINARNE
Do
reprezentacji
liczb
całkowitych
stosowane
są
kody
stałopozycyjne
• zapis znak-moduł
• zapis U1
• zapis U2
• zapis polaryzowany (BIAS)
Zapis U2 (uzupełnień do 2) jest podobny do U1 ale dla liczb ujemnych.
Moduł liczby ujemnej powstaje tak, że do zanegowanych pozycji słowa jest
arytmetycznie dodawana jedynka i dopiero tak utworzone słowo odpowiada
w NKB modułowi tej liczby.
„0” ma pojedynczą reprezentację: 0000...000
Zapis U2 (uzupełnień do 2) jest podobny do U1 ale dla liczb ujemnych.
Moduł liczby ujemnej powstaje tak, że do zanegowanych pozycji słowa jest
arytmetycznie dodawana jedynka i dopiero tak utworzone słowo odpowiada
w NKB modułowi tej liczby.
„0” ma pojedynczą reprezentację: 0000...000
Zapis BIAS (polaryzowany) przedstawia liczby w taki sposób, że „0” jest
reprezentowane przez n-bitowe słowo 1000..000 czyli przez liczbę 2
n-1
kodu
NKB. Wszystkie inne liczby A są przedstawione na n pozycjach jako binarne
wartości liczby 2
n-1
+A
Zapis BIAS (polaryzowany) przedstawia liczby w taki sposób, że „0” jest
reprezentowane przez n-bitowe słowo 1000..000 czyli przez liczbę 2
n-1
kodu
NKB. Wszystkie inne liczby A są przedstawione na n pozycjach jako binarne
wartości liczby 2
n-1
+A
Zapis znak-moduł tworzy się przez dodanie przed MSB dodatkowego bitu
znaku do zapisu NKB: 0 - liczba dodatnia; 1 - liczba ujemna;
„0” ma podwójną reprezentację: 1000...000 lub 0000...000
Zapis znak-moduł tworzy się przez dodanie przed MSB dodatkowego bitu
znaku do zapisu NKB: 0 - liczba dodatnia; 1 - liczba ujemna;
„0” ma podwójną reprezentację: 1000...000 lub 0000...000
W zapisie U1 (uzupełnień do 1) MSB jest także bitem znaku : 0 - liczba
dodatnia; 1 - liczba ujemna; ale w zależności od jego wartości dalsze bity
mają różne znaczenie.
Dla „0” (l.dodatnia) dalsze bity reprezentują liczbę w NKB.
Dla „1” (l.ujemna) dalsze bity reprezentują moduł liczby ujemnej, w taki
sposób, że zanegowane ich wartości odpowiadają modułowi tej liczby w NKB.
„0” ma podwójną reprezentację: 1111...111 lub 0000...000
W zapisie U1 (uzupełnień do 1) MSB jest także bitem znaku : 0 - liczba
dodatnia; 1 - liczba ujemna; ale w zależności od jego wartości dalsze bity
mają różne znaczenie.
Dla „0” (l.dodatnia) dalsze bity reprezentują liczbę w NKB.
Dla „1” (l.ujemna) dalsze bity reprezentują moduł liczby ujemnej, w taki
sposób, że zanegowane ich wartości odpowiadają modułowi tej liczby w NKB.
„0” ma podwójną reprezentację: 1111...111 lub 0000...000
STAŁOPOZYCYJNA REPREZENTACJA
STAŁOPOZYCYJNA REPREZENTACJA
LICZB
LICZB
Przykład zapisu liczb:
• zapis znak-moduł
• zapis U1
• zapis U2
57 = 0 1 1 1 0 0 1
57 = 0 1 1 1 0 0 1
kod NKB
kod NKB
-57 = 1 1 1 1 0 0 1
-57 = 1 1 1 1 0 0 1
znak-moduł
znak-moduł
= 1 0 0 0 1 1 0
= 1 0 0 0 1 1 0
uzupełnienie do 1
uzupełnienie do 1
+ 1
+ 1
= 1 0 0 0 1 1 1
= 1 0 0 0 1 1 1
uzupełnienie do 2
uzupełnienie do 2
Bit znaku
Bit znaku
powstaje przez dopisanie
1 na MSB
powstaje przez dopisanie
zanegowanie wszystkich
bitów modułu liczby
powstaje przez dopisanie
zanegowanie wszystkich
bitów modułu liczby oraz
dodanie 1
STAŁOPOZYCYJNA REPREZENTACJA
STAŁOPOZYCYJNA REPREZENTACJA
LICZB
LICZB
Liczba
ZM
U1
U2
BIAS
BCD
-127
11111111
10000000
10000001
00000001 1000100100111
-126
11111110
10000001
10000010
00000010 1000100100110
...
...
...
...
...
...
...
...
...
...
...
...
-2
10000010
11111101
11111110
11111110 1000000000010
-1
10000001
11111110
11111111
11111111 1000000000001
0
10000000
11111111
00000000
10000000 0000000000000
0
00000000
00000000
00000000
10000000 0000000000000
1
00000001
00000001
00000001
10000001 0000000000001
2
00000010
00000010
00000010
10000010 0000000000010
3
00000011
00000011
00000011
10000011 0000000000011
...
...
...
...
...
...
...
...
...
...
...
...
126
01111110
01111110
01111110
11111110 0000100100110
127
011111111 011111111 011111111 11111111 0000100100111
STAŁOPOZYCYJNA REPREZENTACJA
STAŁOPOZYCYJNA REPREZENTACJA
LICZB
LICZB
animacje pokazujące:
animacje pokazujące:
ĆWICZENIE Z ZAPISU LICZB
ĆWICZENIE Z ZAPISU LICZB
animacje pokazujące:
animacje pokazujące:
ĆWICZENIE Z DODAWANIA LICZB BEZ
ĆWICZENIE Z DODAWANIA LICZB BEZ
ZNAKU (DODATNICH)
ZNAKU (DODATNICH)
Wartości w zapisach
Wartości
dziesiętne
ZM
U1
U2
BCD
89
+45
0 1011001
0 0101101
0 1011001
0 0101101
0 1011001
0 0101101
0 1000 1001
0 0100 0101
+134
(1) 0 0000110 (1) 0 0000110 (1) 0 0000110
0 1100 1110
Korekcja + 0110 0110
0010 0100
+ (1)
(1) 0011 0100
Wartości w zapisach
Wartości
dziesiętne
ZM
U1
U2
BCD
+9
-7
0 1001
+ 1 0111
0 1001
+ 1 1000
0 1001
+ 1 1001
0 1001
+ 1 0111
+2
0 0010
(1) 0 0001
+ 1
(1) 0 0010
0 0010
0 0010
STAŁOPOZYCYJNA REPREZENTACJA
STAŁOPOZYCYJNA REPREZENTACJA
LICZB-dodawanie i odejmowanie
LICZB-dodawanie i odejmowanie
W zapisie U2 (uzupełnień do 2) liczbę binarną można przedstawić jako:
a
n-1
...a
0
= -a
n-1
.
2
n-1
+a
n-2
.
2
n-2
+
...
+a
0
.
2
0
Najstarszy bit nie jest tylko bitem znaku ale niesie wraz ze swoją wagą wartość
ujemną
W zapisie U2 (uzupełnień do 2) liczbę binarną można przedstawić jako:
a
n-1
...a
0
= -a
n-1
.
2
n-1
+a
n-2
.
2
n-2
+
...
+a
0
.
2
0
Najstarszy bit nie jest tylko bitem znaku ale niesie wraz ze swoją wagą wartość
ujemną
1101
1101
U2
U2
= -1
= -1
.
.
2
2
3
3
+1
+1
.
.
2
2
2
2
+0
+0
.
.
2
2
1
1
+1
+1
.
.
2
2
0
0
= -8+4+1 =
= -8+4+1 =
-3
-3
D
D
0111
0111
U2
U2
= -0
= -0
.
.
2
2
3
3
+1
+1
.
.
2
2
2
2
+1
+1
.
.
2
2
1
1
+1
+1
.
.
2
2
0
0
= 4+2+1 =
= 4+2+1 =
7
7
D
D
Ponieważ: a-b=a+(-b); -a+b=(-a)+b; -a-b=(-a)+(-b) to korzystnie jest
Ponieważ: a-b=a+(-b); -a+b=(-a)+b; -a-b=(-a)+(-b) to korzystnie jest
stosować liczbę przeciwną (oznaczanej symbolem ~) do danej
stosować liczbę przeciwną (oznaczanej symbolem ~) do danej
~0111
~0111
U2
U2
1000
1000
+ 1
+ 1
1001
1001
U2
U2
negacja wszystkich bitów i dodanie 1
negacja wszystkich bitów i dodanie 1
-7
-7
D
D
7
7
D
D
Zakresy liczb w kodzie U2: -2
Zakresy liczb w kodzie U2: -2
n-1
n-1
X
X
2
2
n-1
n-1
-1
-1
np. dla n=5 liczby od -16
np. dla n=5 liczby od -16
D
D
(10000
(10000
U2
U2
) do +15
) do +15
D
D
(01111
(01111
U2
U2
). W zakresie
). W zakresie
tym muszą się znaleźć nie tylko argumenty ale i wynik.
tym muszą się znaleźć nie tylko argumenty ale i wynik.
10111
10111
+11000
+11000
1 01111
1 01111
-9
-9
D
D
=
=
-1
-1
.
.
16+0
16+0
.
.
8+1
8+1
.
.
4+1
4+1
.
.
2+1
2+1
.
.
1
1
-8
-8
D
D
=
=
-1
-1
.
.
16+1
16+1
.
.
8+0
8+0
.
.
4+0
4+0
.
.
2+0
2+0
.
.
1
1
-17
-17
D
D
=
=
-1
-1
.
.
32+0
32+0
.
.
16+1
16+1
.
.
8+1
8+1
.
.
4+1
4+1
.
.
2+1
2+1
.
.
1
1
bit poza zakresem - nie
bit poza zakresem - nie
odrzucamy
odrzucamy
110111
110111
+111000
+111000
1 101111
1 101111
-9
-9
D
D
=
=
-1
-1
.
.
32+1
32+1
.
.
16+0
16+0
.
.
8+1
8+1
.
.
4+1
4+1
.
.
2+1
2+1
.
.
1
1
-8
-8
D
D
=
=
-1
-1
.
.
32+1
32+1
.
.
16+1
16+1
.
.
8+0
8+0
.
.
4+0
4+0
.
.
2+0
2+0
.
.
1
1
-17
-17
D
D
=
=
-1
-1
.
.
32+0
32+0
.
.
16+1
16+1
.
.
8+1
8+1
.
.
4+1
4+1
.
.
2+1
2+1
.
.
1
1
bit poza zakresem -
bit poza zakresem -
odrzucamy
odrzucamy
STAŁOPOZYCYJNA REPREZENTACJA
STAŁOPOZYCYJNA REPREZENTACJA
LICZB-dodawanie i odejmowanie (kod
LICZB-dodawanie i odejmowanie (kod
U2)
U2)
animacje pokazujące:
animacje pokazujące:
ĆWICZENIE Z DODAWANIA LICZB ZE
ĆWICZENIE Z DODAWANIA LICZB ZE
ZNAKIEM
ZNAKIEM
Początki:
Początki:
•
Harald C. M. Morse (kropka - kreska - ....);
Harald C. M. Morse (kropka - kreska - ....);
•
Anatol de Baudot (dalekopis);
Anatol de Baudot (dalekopis);
•
w pierwszych maszynach cyfrowych - kod dalekopisowy 5-
w pierwszych maszynach cyfrowych - kod dalekopisowy 5-
bitowy, a potem 8-bitowy (EBCDIC);
bitowy, a potem 8-bitowy (EBCDIC);
W 1977 roku kiedy to ANSI (
W 1977 roku kiedy to ANSI (
American National Standards Institute
American National Standards Institute
)
)
zatwierdził
zatwierdził
kod ASCII
kod ASCII
(
(
The American Standard Code for Information
The American Standard Code for Information
Interchange
Interchange
).
).
Jest to 7-bitowy kod (8 bit do kontroli parzystości), definiujący
Jest to 7-bitowy kod (8 bit do kontroli parzystości), definiujący
128-elementowy zestaw znaków (
128-elementowy zestaw znaków (
character set
character set
) o wartościach
) o wartościach
kodowych od 0 do 127. Zestaw zawiera litery łacińskie (duże i
kodowych od 0 do 127. Zestaw zawiera litery łacińskie (duże i
małe), cyfry i znaki interpunkcji oraz różne znaki specjalne.
małe), cyfry i znaki interpunkcji oraz różne znaki specjalne.
Międzynarodowa Organizacja Standaryzacji - ISO, nadała
Międzynarodowa Organizacja Standaryzacji - ISO, nadała
amerykańskiemu systemowi kodowania status standardu
amerykańskiemu systemowi kodowania status standardu
międzynarodowego oznaczonego jako ISO 646.
międzynarodowego oznaczonego jako ISO 646.
Kod ASCII rozszerzony
Kod ASCII rozszerzony
wprowadza dodatkowe 128 znaków wykorzystując
wprowadza dodatkowe 128 znaków wykorzystując
mało używany bit parzystości:
mało używany bit parzystości:
IBM wprowadza
IBM wprowadza
•
Code Page 474 dla USA
Code Page 474 dla USA
•
Code Page 852 dla Europy Wschodniej
Code Page 852 dla Europy Wschodniej
KODOWANIE ZNAKÓW
KODOWANIE ZNAKÓW
8
Bit kontroli parzystości
7
0
0
0
0
1
1
1
1
6
0
0
1
1
0
0
1
1
Numery bitów słowa
5
0
1
0
1
0
1
0
1
4
3
2
1
0
0
0
0
NUL
DEL
SP
0
@
P
‘
p
0
0
0
1
SOH DC1
!
1
A
Q
a
q
0
0
1
0
STX
DC2
„
2
B
R
b
r
0
0
1
1
ETX
DC3
3
C
S
c
s
0
1
0
0
EOT DC4
$
4
D
T
d
t
0
1
0
1
ENQ NAK
%
5
E
U
e
u
0
1
1
0
ACK SYN
&
6
F
V
f
v
0
1
1
1
BEL
ETB
`
7
G
W
g
w
1
0
0
0
BS
CAN
(
8
H
X
h
x
1
0
0
1
HT
EM
)
9
I
Y
i
y
1
0
1
0
LF
SUB
*
:
J
Z
j
z
1
0
1
1
VT
ESC
+
;
K
[
k
{
1
1
0
0
FF
FS
,
<
L
\
l
|
1
1
0
1
CR
GS
-
=
M
]
m
}
1
1
1
0
SO
RS
.
>
N
n
~
1
1
1
1
SI
US
/
?
O
o
DEL
KODOWANIE ZNAKÓW-kod ASCII
KODOWANIE ZNAKÓW-kod ASCII
1. W 1987 roku ISO tworzy standard ISO 8859 (rozszerzone ASCII):
• ISO 8859-1 (Latin-1) - Europa zachodnia
• ISO 8859-2 (Latin-2) - Europa wschodnia
• ...............................
• ISO 8859-5 (cyrlica)
• ...............................
• ISO 8859-7 (greka)
• ...............................
2. W 1990 roku Instytut Maszyn Matematycznych tworzy kod
Mazovia (rozpowszechniony w dobie kart graficznych Hercules)
3. Firma Microsoft tworzy własny zestaw znaków dla Europy
wschodniej Windows CP 1250
KODOWANIE ZNAKÓW-problem
KODOWANIE ZNAKÓW-problem
polskich liter
polskich liter
Litera Mazovia IBM Latin-2 Windows1250 ISO Latin-2
Ą
143
164
165
161
Ć
149
143
198
198
Ę
144
168
202
202
Ł
156
157
163
163
Ń
165
227
209
209
Ó
163
224
211
211
Ś
152
151
140
166
Ź
160
141
143
172
Ż
161
189
175
175
ą
134
165
185
177
ć
141
134
230
230
ę
145
169
234
234
ł
146
136
179
179
ń
164
228
241
241
ó
162
162
243
243
ś
158
152
156
182
ź
166
171
159
188
ż
167
190
191
191
KODOWANIE ZNAKÓW-problem
KODOWANIE ZNAKÓW-problem
polskich liter
polskich liter
DZIĘKUJĘ ZA UWAGĘ !
DZIĘKUJĘ ZA UWAGĘ !
KOD GRAY’A
KOD GRAY’A
Tabela prawdy sumy modulo 2
Tabela prawdy sumy modulo 2