Kódolás

(1)

(2)

Az információ kódolása

•

Kódolás – közölnivalónknak a szokásostól eltérő ábrázolása,

kifejezési formája. Információ tárolása számítógépen – a gép

számára érthető, olvasható formában kell megadni. A gépek

stabilan csak két állapotot tudnak tárolni – a számítógépnek

szánt információt két jelből álló, bináris kódkészlettel kell

kifejezni.

(3)

Kódolás

• S = {s₁,s₂,K,s_p}– az elsődleges szimbólumok halmaza.

• A ={a₁,a₂,K,a_q} – a kódok ábécéje, elemei a „betűk”.

• Aⁿ = A× A×K× A ={w | w = a₁a₂a₃Ka_n, a_j ∈ A, j =1,n} – az összes n hosszúságú, A elemeiből képzett szavak halmaza.

• A⁺ = A ∪ A² ∪ A³ ∪K∪ Aⁿ – az A-n képezhető összes szavak halmaza.

• Kód – C :S → A⁺ injektív leképezés.

• C injektiv: C(s_k ) = C(s_l ) ⇒ s_k = s_l.

• Egyenletes kód – C : S → Aⁿ injektív függvény (az összes kódszó n hosszúságú).

(4)

Kódolás

Példák:

A 0-9 számjegyek bináris ábrázolása egyenletes kód.

4 },

1 , 0 { },

9 , 8 , 7 , 6 , 5 , 4 , 3 , 2 , 1 , 0

{ = =

= A n

S ,

0000 )

0 ( =

C , C(1) = 0001, C(2) = 0010, _K, C(9) =1001. A Morse ábécé nem egyenletes.

S = {kisbetűk, számjegyek, különleges jelek}

A = { • (ti), — (tá)}

C(e)= • , C(a)= • — , C(s)= • • •, C(b)= — • • • , C(é)= • • — • • , stb.

(5)

Dekódolás

• C : S → A⁺ injektív függvény ﬂ C :S ^→ C(S) ^⊆ A⁺ bijektív.

• C inverz függvényeC⁻¹ :C(S) → S .

• w∈ A⁺ kódszó – határozzuk meg s∈S -et úgy, hogyC(s) = w, vagy azt a választ kapjuk, hogy nem létezik ilyen s .

• Az egyenletes kódok dekódolása egyszerű.

• A nem egyenletes kódok esetén külön elválasztási szimbólumra lehet szükség két egymásután következő C(s₁) és C(s₂) sorozat között

• Egyes nem egyenletes kódok elválasztási szimbólum nélkül is dekódolhatók.

• Egy C kód egyértelműen dekódolható függvény, ha bármely két S-beli s_i és s_j szimbólumra a C(s_i) és C(s_j) kódszakaszok egyike sem előtagja a másiknak.

(6)

Dekódolás

Példa:

Nem egyenletes kód, amely esetén nincs szükség elválasztási szimbólumra a dekódolásnál.

S = {0, 1, 2, …, 9} és A = {1, 2, 3}

C(0) = 11 C(1) = 12 C(2) = 212 C(3) = 222 C(4) = 31 C(5) = 321 C(6) = 322 C(7) = 211 C(8) = 3321 C(9) = 3312

C(2004) = 212111131, C(1848) = 123321313321

(7)

Adatábrázolás a számítógépben

• A kódolás alapja a kettes számrendszer

• Minden elem ugyanannyi bináris számjegyet tartalmaz.

(8)

Alfanumerikus adatok ábrázolása

ASCII (American Standard Code for Information Interchange)

• Eredetileg 7 bites kód

• 8 bites változat – kiterjesztett ASCII kód

• 0 – 1F vezérlő karakterek

pl. 0A – LF 07 – BEL 1B – ESC 0D – CR 08 – BS

• 20 – 2F speciális karakterek pl. 20 – szóköz

• 30 – 39 számjegyek „0” – „9”

• 41 – 5A „A” – „Z”

• 61 – 7A „a” – „z”

• 80 – FF különböző, a kiválasztott készlet szerint pl. 160 – „á” 130 – „é”

(9)

ASCII

(10)

Unicode

• megfeleltetés nem byte-ok és karakterek között, hanem nemnegatív egész számok és karakterek között

• különböző nyelvekben, szakterületeken használt összes karakter egységes kódolása

• kezdetben 2¹⁶ karakter (2 byte), nem elegendő

• 2³² karakter, valószínűleg 2²¹ elegendő

• nem ad útmutatást az ábrázolásra, csak a kódokat adja meg Bővebb információ:

http://www.unicode.org/

(11)

Néhány karakter Unicode kódja

á U+00E1 Á U+00C1 ă U+0103 Ă U+0102

é U+00E9 É U+00C9 â U+00E2 Â U+00C2 í U+00ED Í U+00CD î U+00EE Î U+00CE ó U+00F3 Ó U+00D3 ş U+015F Ş U+015E ö U+00F6 Ö U+00D6 ţ U+0163 Ţ U+0162 ő U+0151 Ő U+0150

ú U+00FA Ú U+00DA ü U+00FC Ü U+00DC ű U+0171 Ű U+0170

„ U+201E ” U+201D – U+2013

(12)

The Unicode Character Code Charts By Script

SYMBOLS AND PUNCTUATION | NAME INDEX | HELP AND LINKS

European

Alphabets African Scripts Indic

Scripts East Asian Scripts Central Asian Scripts

(see also Comb.

Marks) Ethiopic Bengali Han Ideographs Kharoshthi Armenian Ethiopic Devanagari Unified CJK Ideographs

(5MB) Mongolian

Armenian Ethiopic

Supplement Gujarati CJK Ideographs Ext. A

(2MB) Phags-Pa

Armenian Ligatures Ethiopic Extended Gurmukhi CJK Ideographs Ext. B

(13MB) Tibetan

Coptic Other African

scripts Kannada Compatibility Ideographs

(.5MB)

Coptic N'Ko Limbu ... Supplement (.5MB)

Coptic in Greek

block Tifinagh Malayalam Kanbun

(13)

Cyrillic Middle Eastern

Scripts Oriya (see also Unihan

Database) Ancient Scripts Cyrillic Arabic Sinhala Radicals and Strokes Ancient Greek Cyrillic

Supplement Arabic Syloti Nagri CJK Radicals Ancient Greek Numbers

Georgian Arabic Supplement Tamil KangXi Radicals Ancient Greek Musical

Georgian Arabic Presentation

Forms A Telugu CJK Strokes Cuneiform

Georgian Supplement

Arabic Presentation

Forms B Ideographic

Description Cuneiform

Greek Hebrew Philippine

Scripts Chinese-specific Cuneiform Numbers

Greek Hebrew Buhid Bopomofo Old Persian

Greek Extended Hebrew Presentation

Forms Hanunoo Bopomofo Extended Ugaritic

(14)

(see also Ancient

Greek) Syriac Tagalog Japanese-specific Linear B

Latin Syriac Tagbanwa Hiragana Linear B Syllabary

Basic Latin Thaana Katakana, Linear B Ideograms

Latin-1 Thaana South East

Asian

Katakana Phonetic Ext.

Other Ancient Scripts

Latin Extended A American

scripts Buginese Halfwidth Katakana Aegean Numbers Latin Extended B Canadian

Syllabics Balinese Korean-specific Counting Rod Numerals Latin Extended C Cherokee Khmer Hangul Syllables

(4MB) Cypriot Syllabary

Latin Extended D Deseret Khmer Symbols Hangul Jamo Gothic Latin Extended

Additional Other Scripts Lao Hangul Compatibility

Jamo Old Italic

Latin Ligatures Shavian Myanmar Halfwidth Jamo Ogham Fullwidth Latin Letters Osmanya New Tai Lue Yi Runic

Small Forms Glagolitic Tai Le Yi (.6MB) Phoenician

(see also Phonetic

Symbols) Thai Yi Radicals

(15)

Code Charts for Symbols and Punctuation

SCRIPT CHARTS | NAME INDEX | HELP AND LINKS Punctuation Mathematical

Symbols Symbols Private Use

General Punctuation Numbers and Digits Miscellaneous Symbols Private Use Area ASCII Punctuation (see also specific

scripts) Dingbats Suppl. Private Use Area A

Latin-1 Punctuation ASCII Digits Miscellaneous Symbols Suppl. Private Use Area B General Punctuation Fullwidth ASCII Digits Tai Xuan Jing Symbols Surrogates

Supplemental Punctuation Number Forms Yijing Hexagrams High Surrogates CJK Punctuation Super and Subscripts Braille Patterns High Private Use

Surrogates

CJK Punctuation Letterlike Symbols Musical Notation Low Surrogates Fullwidth ASCII

Punctuation Letterlike Symbols Ancient Greek Musical... Noncharacters in Charts Vertical Forms Math Alphanumeric

Symbols

Byzantine Musical

Symbols Reserved range

Enclosed and Square Arrows and

Operators Western Musical SymbolsAt End of BMP Enclosed Alphanumerics Arrows Currency Symbols At End of Plane 1 .... CJK Letters and

Months

Mathematical Operators

(see also specific

scripts) At End of Plane 2 CJK Compatibility Suppl. Math Operators Dollar Sign, Euro Sign At End of Plane 3

(16)

(see also Letterlike

Symbols) Misc. Math Symbols A Yen, Pound and Cent At End of Plane 4 Combining Diacritical

Marks Misc. Math Symbols B Currency Symbols At End of Plane 5 Combining Diacritical

Marks Supplemental Arrows A Fullwidth Currency

Symbols At End of Plane 6

.... for Symbols Supplemental Arrows B Mark and Pfennig

(historic) At End of Plane 7

.... Supplement Misc. Symbols and

Arrows Rial Sign At End of Plane 8

Combining Half Marks Geometrical Symbols Specials At End of Plane 9 Phonetic Symbols Geometrical Shapes Controls: C0, C1 At End of Plane 10 IPA Extensions Box Drawing Layout Controls At End of Plane 11 Phonetic Extensions Block Elements Invisible Operators At End of Plane 12 Phonetic Extensions

Supplement Technical Symbols Specials At End of Plane 13 Modifier Tone Letters Control Pictures Tags At End of Plane 14 Spacing Modifier Letters Miscellaneous

Technical Variation Selectors At End of Plane 15 (see also Super and

Subscript) OCR Variation Selectors

Supplement At End of Plane 16

(17)

UTF-8

• Unicode ábrázolásmódja

• egy karakter kódja változó hosszúságú lehet (max. 6 byte)

• az ASCII karakterek kódja 1 byte, megegyezik az ASCII kóddal (<128)

• 128-nál nagyobb vagy egyenlő kódú Unicode karaktereket több 128-nál nagyobb byte ábrázol

Unicode érték UTF-8 bytesorozat

1. byte 2. byte ...

30 0 7 0 7 0 ...

| | | | | | 00000000 00000000 00000000 0xxxxxxx <-> 0xxxxxxx

00000000 00000000 00000xxx xxxxxxxx <-> 110xxxxx 10xxxxxx

00000000 00000000 xxxxxxxx xxxxxxxx <-> 1110xxxx 10xxxxxx 10xxxxxx

00000000 000xxxxx xxxxxxxx xxxxxxxx <-> 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

...

(18)

Számok ábrázolása

Fixpontos ábrázolás

az utolsó bit után – egész számok – a törtrészt jelölő képzeletbeli vessző az első bit előtt

az utolsó n bit előtt – nincs kerekítés

Lebegőpontos ábrázolás

– kerekített értékek

– nagy ábrázolható számtartomány

(19)

Fixpontos ábrázolás

– a kódszó hossza adott (általában szóhossz) – az első bit előjelbit (0 pozitív, 1 negatív)

– a törtrészt jelző pont nem szerepel az ábrázolásban, helye fix

(20)

Fixpontos ábrázolás – |x| < 1, 2-es számrendszerben

Direkt kód

⎩⎨

⎧

≤

−

= ≥

0 ,

1

0 ] ,

[ _D

x ha x

x ha x x

Inverz kód

⎩⎨

⎧

<

+

−

= ₋ ₊ ≥

0 ,

) 10 ( )

10 (

0 ] ,

[ ₁

2 2

I x ha x

x ha

x x _n

Komplementer kód

⎩⎨

⎧

<

+

= ≥

0 ,

) 10 (

0 ] ,

[

2

C x ha x

x ha x x

(n a törtrész számjegyeinek száma).

(21)

Fixpontos ábrázolás – |x| < 1

Megjegyzések:

– ha x ≥ 0 : [x] _D =[x] _I = [x] _C – ha x < 0 , x = −0,x₋1x₋2Kx₋_n :

3 2 K 1K

K K

n n

x x

01 0

. 0 ,

1 ]

[

, 1 ]

[

, 1 ]

[

2 1 C

2 1 I

2 1 D

+

=

−

, ahol

⎩⎨

⎧

=

= =

1 ha

, 0

0 ha

, 1

i i

i x

x x .

– direkt kód:

– különböző ábrázolás +0, illetve –0;

– összeadás algoritmusban külön kell tárgyalni előjel szerint a lehetséges eseteket;

– inverz kód:

– összeadás algoritmusban külön kell tárgyalni előjel szerint a lehetséges eseteket;

(22)

Összeadás komplementer kódban

Definíció

Legyen a,b∈[0,(10)₂) (komplementer kódok)

⎩⎨

⎧

≥ +

− +

<

+

= +

⊕

2 2

2

) 10 ( ha

, )

10 (

) 10 ( ha

,

b a

b b a

a

Tétel

Legyen x, y ∈(−1, 1) . Akkor

C C

C [ ] [ ]

]

[x ⊕ y = x + y

(23)

Bizonyítás

a. x, y ≥ 0 ⇒ x + y ≥ 0 ( x + y <1, ha nincs túlcsordulás)

C C

C [ ] [ ]

]

[x ⊕ y = x + y = x + y

b. x ≥ 0, y < 0, x + y ≥ 0 ⇒ x + y + (10)₂ ≥10

C 2

2 C

C [ ] (10) (10) [ ]

]

[x ⊕ y = x + + y − = x + y = x + y

c. x ≥ 0, y < 0, x + y < 0 ⇒ x + y + (10)₂ <10

C 2

2 C

C [ ] (10) (10) ( ) [ ]

]

[x ⊕ y = x + + y = + x + y = x + y

d. x < 0, y < 0 ⇒ x + y < 0 ⁽| x + y |<1^,ha nincs túlcsordulás)

C 2

2 2

2 C

C [ ] (10) (10) (10) (10) ( ) [ ]

]

[x ⊕ y = + x + + y − = + x + y = x + y

(24)

Egész számok ábrázolása – komplementer kód

n bináris számjegy⁽n∈{8,16, 32}⁾ 2 1

|

, < ⁻

∈ x ⁿ

x Z

⎩⎨

⎧

<

+

= ≥

0 ha

, )

10 (

0 ha

] , [

2

C x x

x

x x_n

Túlcsordulás összeadásnál

Az összeadás eredménye helyes, ha bináris ábrázolásban:

– nincs átvitel az előjelbitre és nincs kifutó bit – van átvitel az előjelbitre és van kifutó bit

(25)

Példák – 8 bites ábrázolás

000010102

10 =

2 2

8 2

C (10 ) 00001010 100000000 00001010 11110110 ]

10

[− = − = − =

egyszerűbben:

00001010 bitenként invertáljuk 11110101+ hozzáadunk 1-et 1

11110110

–10 + (–7) –15 + 7 65+70 11110110+ 11110001+ 01000001+

11111001 00000111 01000110

1|11011111 11111000 10000111 túlcsordulás

(26)

Valós számok lebegőpontos ábrázolása (1)

–∀x ∈ x ≠ 0 x = ± m × 10 ^k , ahol m – mantissza, k – exponens – normalizált alak egység alatti mantisszával: 1

10

1 <= m <

– kettes számrendszerben normalizált alak: x = (−1)^S ⋅1,m₂ ⋅10^k₂ Példa: 128,25₁₀ =10000000,01₂ =1,000000001₂ ⋅(2⁷)₁₀

10 2 2

2

10 0,011 1,1 (2 ) 375

,

0 = = ⋅ ⁻

(27)

Valós számok lebegőpontos ábrázolása (2)

– két előjel szerepel: a szám illetve a kitevő előjele

– a kitevőt eltolt nullapontú formában ábrázoljuk, azaz az ábrázolható legkisebb értéket tekintjük nullának

– ábrázolandó: előjel, eltolt kitevő, mantissza

– minden formátumra jellemző az e eltolás értéke – általános alakban az x = (−1)^S ⋅1,m₂ ⋅10^k₂ :

S e+k m

(28)

Egyszerű pontosság – single

31 30 23 22 0

S e+k m

– 4 byte

– e = 127₁₀ = 0111 1111₂

– értékes tízes alapú számjegyek száma = 6 – legkisebb ábrázolható tízes hatvány: –37 – legnagyobb ábrázolható tízes hatvány: 38

(29)

Dupla pontosság – double

63 62 52 51 0

S e+k m

– 8 byte

– e = 1023₁₀ = 011 1111 1111₂

(30)

Kiterjesztett pontosság – extended

79 78 64 63 62 0

S e+k 1 m

– 10 byte

– e = 16383₁₀ = 011 1111 1111 1111₂

(31)

Megjegyzések

– a legkisebb és a legnagyobb exponenst hibakezelésre használja, ezért −126 ≤ k ≤127

– az egyszerű és dupla pontosságú formátumnál az egészeket jelentő 1-es bitet nem ábrázoljuk

(32)

Példák – 4 byte-os ábrázolás

1. −128,25₁₀ = −10000000,01₂= −1,000000001₂⋅(2⁷)₁₀ S = 1

k = 7

2 10

10

10 7 134 1000 0110

127 + = =

= + k e

11000011 00000000 01000000 00000000 azaz C3004000 2. 0,375₁₀ = 0,011₂ =1,1₂ ⋅(2⁻²)₁₀

S = 0 k = –2

2 10

10

10 2 125 0111 1101

127 − = =

= + k e

00111110 11000000 00000000 00000000 azaz 3EC00000

(33)

Egész számok – BCD formátum

– BCD – Binary Coded Decimal

– minden 10-es számrendszerbeli számjegyet 4 biten ábrázolunk – a koprocesszor BCD formátuma:

– 10 byte

– 1. byte előjel ( 1000 0000 negatív, 0000 0000 pozitív) – 18 számjegy