Kódolás
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.
Kódolás •
S = {s1 , s 2 , K , s p } – az elsődleges szimbólumok halmaza.
•
A = {a1 , a 2 , K , a q } – a kódok ábécéje, elemei a „betűk”.
•
An = A × A × K × A = {w | w = a1a2 a3 K an , a j ∈ A, j = 1, n} – az összes n hosszúságú, A elemeiből képzett szavak halmaza.
•
A + = A ∪ A 2 ∪ A3 ∪ K ∪ A n
– az A-n képezhető összes szavak
halmaza. •
Kód – C : S → A + injektív leképezés.
•
C injektiv: C ( s k ) = C ( sl ) ⇒ s k = s l .
•
Egyenletes kód – C : S → A n injektív függvény (az összes kódszó n hosszúságú).
Kódolás Példák: A 0-9 számjegyek bináris ábrázolása egyenletes kód. S = {0,1,2,3,4,5,6,7,8,9},
A = {0,1}, n = 4 ,
C (0) = 0000 , 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.
Dekódolás • C : S → A + injektív •
C inverz függvénye C −1 : C ( S ) → S .
• w ∈ A + kódszó • • • •
függvény fl C : S → C ( S ) ⊆ A + bijektív.
– határozzuk meg s ∈ S -et úgy, hogy C ( 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(s1) és C(s2) 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 si és sj szimbólumra a C(si) és C(sj) kódszakaszok egyike sem előtagja a másiknak.
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
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.
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 – „é”
ASCII
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 216 karakter (2 byte), nem elegendő 232 karakter, valószínűleg 221 elegendő nem ad útmutatást az ábrázolásra, csak a kódokat adja meg
Bővebb információ: http://www.unicode.org/
Néhány karakter Unicode kódja á é í ó ö ő ú ü ű „ –
U+00E1 U+00E9 U+00ED U+00F3 U+00F6 U+0151 U+00FA U+00FC U+0171 U+201E U+2013
Á É Í Ó Ö Ő Ú Ü Ű ”
U+00C1 U+00C9 U+00CD U+00D3 U+00D6 U+0150 U+00DA U+00DC U+0170 U+201D
ă â î ş ţ
U+0103 U+00E2 U+00EE U+015F U+0163
Ă Â Î Ş Ţ
U+0102 U+00C2 U+00CE U+015E U+0162
The Unicode Character Code Charts By Script SYMBOLS AND PUNCTUATION | NAME INDEX | HELP AND LINKS European Alphabets (see also Comb. Marks)
African Scripts
Indic Scripts
East Asian Scripts
Central Asian Scripts
Ethiopic
Bengali
Han Ideographs
Kharoshthi
Armenian
Ethiopic
Devanagari
Armenian
Ethiopic Supplement
Gujarati
Limbu
Unified CJK Ideographs (5MB) CJK Ideographs Ext. A (2MB) CJK Ideographs Ext. B (13MB) Compatibility Ideographs (.5MB) ... Supplement (.5MB)
Malayalam
Kanbun
Armenian Ligatures Ethiopic Extended Gurmukhi Coptic Coptic Coptic in Greek block
Other African scripts N'Ko Tifinagh
Kannada
Mongolian Phags-Pa Tibetan
Cyrillic Cyrillic Cyrillic Supplement Georgian
Middle Eastern Scripts Arabic
Syloti Nagri
Arabic Supplement
Tamil
Georgian Supplement Greek
Hebrew
Greek
Hebrew Hebrew Presentation Forms
Greek Extended
Sinhala
Arabic
Arabic Presentation Forms A Arabic Presentation Forms B
Georgian
Oriya
Telugu
Philippine Scripts Buhid Hanunoo
(see also Unihan Ancient Scripts Database) Radicals and Strokes Ancient Greek Ancient Greek CJK Radicals Numbers Ancient Greek KangXi Radicals Musical CJK Strokes
Cuneiform
Ideographic Description
Cuneiform
Bopomofo
Cuneiform Numbers Old Persian
Bopomofo Extended
Ugaritic
Chinese-specific
(see also Ancient Greek) Latin Basic Latin Latin-1 Latin Extended A Latin Extended B
Syriac
Tagalog
Japanese-specific
Linear B
Syriac Thaana
Tagbanwa South East Asian
Hiragana Katakana, Katakana Phonetic Ext.
Linear B Syllabary Linear B Ideograms Other Ancient Scripts
Buginese
Halfwidth Katakana
Aegean Numbers
Balinese
Korean-specific
Counting Rod Numerals
Thaana American scripts Canadian Syllabics
Latin Extended C
Cherokee
Latin Extended D Latin Extended Additional Latin Ligatures Fullwidth Latin Letters Small Forms (see also Phonetic Symbols)
Deseret Other Scripts Shavian Osmanya Glagolitic
Hangul Syllables (4MB) Khmer Symbols Hangul Jamo Hangul Compatibility Lao Jamo Myanmar Halfwidth Jamo New Tai Lue Yi Tai Le Yi (.6MB) Khmer
Thai
Yi Radicals
Cypriot Syllabary Gothic Old Italic Ogham Runic Phoenician
Code Charts for Symbols and Punctuation SCRIPT CHARTS | NAME INDEX | HELP AND LINKS Mathematical Punctuation Symbols Private Use Symbols General Punctuation Numbers and Digits Miscellaneous Symbols Private Use Area (see also specific ASCII Punctuation Dingbats Suppl. Private Use Area A scripts) 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 High Private Use CJK Punctuation Super and Subscripts Braille Patterns Surrogates CJK Punctuation Letterlike Symbols Musical Notation Low Surrogates Fullwidth ASCII Letterlike Symbols Ancient Greek Musical... Noncharacters in Charts Punctuation Math Alphanumeric Byzantine Musical Vertical Forms Reserved range Symbols Symbols Arrows and Enclosed and Square Western Musical Symbols At End of BMP Operators Enclosed Alphanumerics Arrows Currency Symbols At End of Plane 1 .... CJK Letters and Mathematical (see also specific At End of Plane 2 Months Operators scripts) CJK Compatibility Suppl. Math Operators Dollar Sign, Euro Sign At End of Plane 3
(see also Letterlike Symbols) Combining Diacritical Marks Combining Diacritical Marks .... for Symbols .... Supplement Combining Half Marks Phonetic Symbols IPA Extensions Phonetic Extensions Phonetic Extensions Supplement Modifier Tone Letters Spacing Modifier Letters (see also Super and Subscript)
Misc. Math Symbols A Yen, Pound and Cent
At End of Plane 4
Misc. Math Symbols B Currency Symbols
At End of Plane 5
Fullwidth Currency Symbols Mark and Pfennig Supplemental Arrows B (historic) Misc. Symbols and Rial Sign Arrows Geometrical Symbols Specials Geometrical Shapes Controls: C0, C1 Box Drawing Layout Controls Block Elements Invisible Operators Supplemental Arrows A
At End of Plane 6 At End of Plane 7 At End of Plane 8 At End of Plane 9 At End of Plane 10 At End of Plane 11 At End of Plane 12
Technical Symbols
Specials
At End of Plane 13
Control Pictures Miscellaneous Technical
Tags
At End of Plane 14
Variation Selectors
At End of Plane 15
Variation Selectors Supplement
At End of Plane 16
OCR
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 30 | 00000000 00000000 00000000 00000000
00000000 00000000 00000000 000xxxxx
...........
UTF-8 bytesorozat
00000000 00000xxx xxxxxxxx xxxxxxxx
0 | 0xxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx
<-> <-> <-> <->
1. byte 7 0 | | 0xxxxxxx 110xxxxx 1110xxxx 11110xxx
2. byte ... 7 0 ... | | 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
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
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
Fixpontos ábrázolás – |x| < 1, 2-es számrendszerben Direkt kód , ha x ≥ 0 ⎧ x [ x] D = ⎨ ⎩1 − x , ha x ≤ 0 Inverz kód x , ha x ≥ 0 ⎧ [ x] I = ⎨ − n +1 − + x , ha x < 0 ( 10 ) ( 10 ) 2 2 ⎩ Komplementer kód , ha x ≥ 0 x ⎧ [ x] C = ⎨ ⎩(10) 2 + x , ha x < 0 (n a törtrész számjegyeinek száma).
Fixpontos ábrázolás – |x| < 1 Megjegyzések:
– ha x ≥ 0 : [ x] D = [ x] I = [ x] C – ha x < 0 , x = −0, x−1 x− 2 K x− n : [ x] D = 1, x−1 x− 2 K x− n [ x] I = 1, x−1 x− 2 K x− n K [ x] C = 1, x−1 x− 2 K x− n + 0.01 01 23
⎧1, ha xi = 0 , ahol xi = ⎨ . ⎩0, ha xi = 1
n
– 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;
Összeadás komplementer kódban Definíció
Legyen a, b ∈ [0, (10) 2 ) (komplementer kódok) ⎧ a+b a⊕b = ⎨ ⎩a + b − (10) 2 Tétel
Legyen x, y ∈ (−1, 1) . Akkor [ x] C ⊕ [ y ] C = [ x + y ] C
, ha a + b < (10) 2 , ha a + b ≥ (10) 2
Bizonyítás a.
x, y ≥ 0 ⇒ x + y ≥ 0
( x + y < 1 , ha nincs túlcsordulás)
[ x] C ⊕ [ y ] C = x + y = [ x + y ] C b.
x ≥ 0, y < 0, x + y ≥ 0 ⇒ x + y + (10) 2 ≥ 10 [ x] C ⊕ [ y ] C = x + (10) 2 + y − (10) 2 = x + y = [ x + y ] C
c.
x ≥ 0, y < 0, x + y < 0 ⇒ x + y + (10) 2 < 10 [ x] C ⊕ [ y ] C = x + (10) 2 + y = (10) 2 + ( x + y ) = [ x + y ] C
d. x < 0, y < 0
⇒
x+ y<0
( | x + y |< 1 ,
ha nincs túlcsordulás)
[ x] C ⊕ [ y ] C = (10) 2 + x + (10) 2 + y − (10) 2 = (10) 2 + ( x + y ) = [ x + y ] C
Egész számok ábrázolása – komplementer kód n bináris számjegy ( n ∈ {8, 16, 32} ) x ∈ Z, | x | < 2n −1 x , ha x ≥ 0 ⎧ [ x] C = ⎨ n ( 10 ) , ha x < 0 2 + x ⎩ 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
Példák – 8 bites ábrázolás 10 = 000010102 [−10] C = (102 )8 − 000010102 = 1000000002 − 000010102 = 111101102 egyszerűbben: 00001010
bitenként invertáljuk
11110101+ 1 11110110
hozzáadunk 1-et
–10 + (–7)
–15 + 7
11110110+ 11111001 1|11011111
11110001+ 00000111 11111000
65+70 01000001+ 01000110 10000111 túlcsordulás
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 <= m < 1 10
– kettes számrendszerben normalizált alak: x = (−1) S ⋅ 1, m2 ⋅ 10k2 Példa: 128,2510 = 10000000,012 = 1,0000000012 ⋅ (27 )10 0,37510 = 0,0112 = 1,12 ⋅ (2−2 )10
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, m2 ⋅ 10k2 : S
e+k
m
Egyszerű pontosság – single 31 30
S
23 22
e+k
0
m
– 4 byte – e = 12710 = 0111 11112 – é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
Dupla pontosság – double 63 62
S
52 51
e+k
0
m
– 8 byte – e = 102310 = 011 1111 11112 – értékes tízes alapú számjegyek száma = 15 – legkisebb ábrázolható tízes hatvány: –307 – legnagyobb ábrázolható tízes hatvány: 308
Kiterjesztett pontosság – extended 79 78
S
64 63 62
e+k
1
0
m
– 10 byte – e = 1638310 = 011 1111 1111 11112 – értékes tízes alapú számjegyek száma = 19 – legkisebb ábrázolható tízes hatvány: –4931 – legnagyobb ábrázolható tízes hatvány: 4932
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
Példák – 4 byte-os ábrázolás 1. − 128,2510 = −10000000,01 2 = −1,000000001 2⋅ (27 )10 S=1 k=7 e + k = 12710 + 710 = 13410 = 1000 01102 11000011 00000000 01000000 00000000 azaz C3004000 2. 0,37510 = 0,0112 = 1,12 ⋅ (2−2 )10 S=0 k = –2 e + k = 12710 − 210 = 12510 = 0111 11012 00111110 11000000 00000000 00000000
azaz 3EC00000
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
