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:

•

zapis liczb w systemie ZM, U1

zapis liczb w systemie ZM, U1

i U2

i U2

•

test z zapisu w systemie ZM,

test z zapisu w systemie ZM,

U1 i U2

U1 i U2

ĆWICZENIE Z ZAPISU LICZB

ĆWICZENIE Z ZAPISU LICZB

animacje pokazujące:

animacje pokazujące:

•

dodawanie

liczb

w

systemie

dodawanie

liczb

w

systemie

dwójkowym

dwójkowym

•

test z dodawania

test z dodawania

Ć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:

•

dodawanie

liczb

w

dodawanie

liczb

w

systemie ZM

systemie ZM

•

dodawanie

liczb

w

dodawanie

liczb

w

systemie U1

systemie U1

•

dodawanie

liczb

w

dodawanie

liczb

w

systemie U2

systemie U2

Ć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