Adatok kódolása

A titkosító algoritmusok részletezése előtt még egy fontos témát kell áttekinteni. Ez az adatok kódolása. Informatikában a kódolás szó nem azonos a titkosítás fogalmával. A kódolás egy olyan eljárást jelez, amely segítségével az emberek által érthető információkat egy olyan formában kódoljuk, amivel a gép már kezdeni is tud valamit.

Számok és bit sorrend

Azt sokan tudják, hogy a számítógép kettes számrendszerben dolgozik, azonban a számok ábrázolásának is vannak különféle módjai a bináris felépítésen belül. Az egész számok tárolódhatnak előjel segítségével és előjel nélkül. Informatika órákon általában csak az előjel nélküli ábrázolás kerül elő. Ennek lényege, hogy a számot, amit átváltunk, leírjuk egyszerűen. Ebből adódóan az 1372 szám bináris alakja a 1010 1011 100 lesz. A bináris átváltás módját nem részletezném külön, mivel számos kiváló szakirodalom lelhető fel a Google segítségével a témában.

Ez az ábrázolási mód kicsit sántít. Mivel a számítógép csak fix bithosszúságokban tud gondolkodni. Ez azt jelenti, hogy egy számot 8, 16, 32, 64 vagy 128 biten tud ábrázolni. 128 bit felett is lehetséges egész számok ábrázolása, de gyakorlatban nem igen van rá szükség, mivel a 128 biten a legnagyobb ábrázolható szám 340 282 366 920 938 463 463 374 607 431 768 211 456. Ez egy akkora szám, hogy kimondani sem egyszerű. Éppen ezért gyakorlatban nem is nagyon alkalmaznak ekkora számábrázolást, csak speciális esetekben.

Ha a szám, amit ábrázolni szeretnénk, nem fér bele az ábrázolási tartományba, akkor túlcsordulás keletkezik. Ez azt jelenti, hogy a szám visszaáll a legkisebb ábrázolható számra és egy speciális bit jelzi a processzornak, hogy valami számítási hiba történt. A számítási hibát a felhasználónak kell kezelnie a programjában. Súlyos gondokat tud okozni, ha ilyen apróságokat nem vesz figyelembe az ember.

A való élettől igen messze áll, hogy csak pozitív számokat használjunk, ezért meg kellett oldani azt, hogy a számítógép képes legyen negatív számokat is kezelni. Ezt úgy oldották meg, hogy az alkalmazott bit hosszból a legnagyobb helyi értékű bitet kinevezték előjel bitnek. Ha ez 0, akkor a szám pozitív, ha pedig 1, akkor a szám negatív. Hátránya a megoldásnak, hogy előjellel 8 biten csak egy 7 bites szám ábrázolható, ami 127. Ez pont a fele annak a számnak, amit előjel nélkül tudnánk ábrázolni. Itt is érvényes a valamit valamiért elv. Az ábrázolható számok darabra nem változtak, mivel -127-et is tudunk ábrázolni, csak a tartomány változott.

Az előjeles számoknál, ha a szám negatív, van még egy ábrázolási turpisság, amit kettes komplemensnek neveznek. Erre a kódolásra azért van szükség, mert így a processzorban található összeadó egység képes kivonás elvégzésére is. Ez azért jó és hasznos, mert a szorzást vissza tudjuk vezetni összeadások sorozatára. Az osztást pedig kivonások sorozatára. Ha nem kell külön kivonó áramkört fejleszteni, akkor az összeadó képes megvalósítani a négy alapműveletet. A kettes komplemens az egyes komplemensnél eggyel nagyobb szám, ahol az egyes komplemens egyszerűen a szám bitenkénti negáltja.

A tört számok ábrázolása az IEEE 754 szabvány szerint történik. Ezt 1984-ben vezették be. Ezen ábrázolási szabványból a 32 bites és 64 bites változat alkalmazása a leginkább elterjedt. Ilyen számoknál beszélhetünk számábrázolási hibákról. Számábrázolási hiba akkor keletkezik, ha egy olyan számot próbálunk meg kettes számrendszerbe átváltani, amely nem ábrázolható megfelelő pontossággal. Ekkor valamekkora kerekítés történik. Ezen kerekítési hibák a bitszám növelésével ugyan csökkennek, de a szükséges számítási idő pedig növekszik. 32 biten ábrázolt tört számok esetén az eredmény nagyon extrém esetekben is 3-4 tizedes jegyig pontosnak tekinthető, ami a legtöbb alkalmazási területen elfogadható pontosság.

Ezen formátum bevezetése előtt a számítógépek a számokat BCD kódolással tárolták a legtöbb esetben. Ennek a kódolásnak az a lényege, hogy a tízes számrendszerbeli szám számjegyeit egyesével 4 vagy 8 biten kódolva tároljuk. A 4 bites változatot nevezik pakolt formátumnak, mivel ekkor 8 biten 2db számjegy ábrázolható. A 8 bites formátumban 4 bit mindig 0, 4 pedig a számjegyet írja le. A korai számítógépekben azért alkalmazták ezt a módszert, mert így elkerülhetőek voltak a kerekítési hibák. Hátránya az, hogy ha a fenti 128 bites számot szeretnénk BCD kódban ábrázolni, akkor 156 bit kellene a szám ábrázolásához. Ez ebben a konkrét esetben ~21,87% plusz információ a rendszerben. Ha kisebb számokról vagy több tizedesjegyből álló számokról, akkor a hatékonyság még problémásabb. És akkor arról még nem beszéltünk, hogy egy BCD kódban működő processzort sokkal bonyolultabb megtervezni, mintha pusztán bináris lenne a rendszer.

A bitsorrend kérdése azért fontos, mert léteznek olyan számítógépek amelyek eltérően értelmezik. A tízes számrendszer esetén az van megszokva számunkra, hogy a szám bal oldalán található a legnagyobb helyi érték. Ezt a kódolási sémát nevezzük Big Endian kódolásnak. Ha azonban a legkisebb helyi értékű bit a bal oldalán található a számnak, akkor a rendszer Little Endian. Az, hogy a számítógép miként tárolja a számokat a memóriában, nincs hatással a műveletvégzési sebességre. Pontosabban, nem sikerült még senkinek mérésekkel alátámasztani. Azt hihetnénk, hogy a Big Endian tárolást alkalmazzák legtöbb esetben, mivel ez lenne a logikus. A valóság azonban az, hogy a legtöbb számítógép Little Endian kódolást alkalmaz, mivel az Intel anno ezt a kódolási sémát választotta. Így az összes X86/X64 alapú számítógép Little Endian. Az ARM processzorok esetén utasítás segítségével megváltoztatható.

Szövegek

A szövegek lényegében karakterek sorozatai. Az egyes karakterek kódolása megtörténhet számokkal. Például azt mondjuk, hogy a 15-ös szám jelentse az A betűt. Erre írunk egy programot, amely ha 15-ös kódot olvas kirajzoljon egy betűt a képernyőre. Ha ezt minden karakterre megtesszük, akkor kész a kódolási rendszerünk.

A számítógépek kitalálásának idején nem volt egységes szabvány a betűk kódolásáról. Minden gyártó mást alkalmazott, így volt rendesen káosz. Mivel az adott program, információ hordozhatatlan volt a különböző géptípusok között. Ez még bőven az internet előtt volt, mivel ha ez még ma is így lenne, nem lenne internet.

Az ASCII szabvány 1963-ban született meg. A mozaikszó az American Standard Code for Information Interchange szavakból van képezve. Mint ahogy a neve mutatja, ez egy amerikai szabvány. Eredetileg a kódolás 7 bites volt. 95 nyomtatható karaktert és 32 vezérlő karaktert tartalmazott. A vezérlő karakterek szövegek végének jelölésre, sortörések és egyéb funkciók miatt lettek bevezetve. Nagy részük ezeknek már nem használatos. A vezérlő karakterek a táblázat elején helyezkednek el.

ASCII tábla

Mivel amerikai eredetű a szabvány, ezért csak az angol ABC betűit, számokat és mondatvégi jeleket tartalmazott a kódrendszer. A számítástechnika fejlődésével azonban ez a megközelítés nem bizonyult a legjobbnak, mivel a többi nyelv írásjeleit és speciális betűit is kódolni kellett valahogy. Erre azt a megoldást találták ki, hogy felbővítették a kódolást 8 bitesre. Az első 127 karakter maradt változatlan, az új 128 karaktert pedig kódlapokkal lehetett cserélni. Így minden nyelvnek meglehetett a saját kódlapja.

Ezzel pont azt sikerült elérni, hogy ne legyen egységes az ASCII. Mivel egy orosz nyelven írt szöveget nem tudott megjeleníteni automatikusan jól egy angol operációs rendszer, ha nem a megfelelő kódlap volt betöltve. Messze nem volt ez ideális helyzet. Továbbá a kódolás nem vette figyelembe az olyan nyelveket, mint a kínai vagy a japán, ahol egy-egy írásjel egy egész szót jelent. Ezekből bőven több létezik, mint 128.

A problémát megkerülendő létrehoztak egy új szabványt, amely a Unicode nevet kapta. Ez eredetileg egy 16 bites kódolás, minden karakter 2 byte-ból áll. Így összesen 65 535 karakter ábrázolása lehetséges. Ez a kódolás nem használ kódlapokat és kompatibilis az ASCII-vel, mivel az első 128 karakter azonos.

Az Unicode szabványból több formátum létezik. Van UTF-8, UTF-16 és UTF-32. Unicode alatt ma az UTF-32 értendő. Ez egy 32 bites kódolás. Ez közel 4 milliárd írásjel ábrázolását teszi lehetővé, de jelenleg “csak” 1 114 112 kód használt, ami a világon ismert összes írásjelet lefedi. Az UTF-16 változat volt az eredeti kódolás. Ennek a gyökerei 1987-ig nyúlnak vissza. Ezt váltotta le az UTF-32, mivel több írásjel tárolására volt szükség.

Az UTF-8 formátum a legjobban elterjedt. Ez egy váltakozó bitsűrűségű kódolás. Az UTF-16 és UTF-32 jó, ha memóriában kell tárolni az adatot, de veszteséges, ha lemezen, illetve nagyon nem ideális ezeket hálózaton átvinni sem. Ezért ebben a kódolásban, ha egy karakter leírható 7 biten, akkor egy byte-on kerül ábrázolásra a karakter. Ha leírható 16 biten, akkor 2 byte-on, ha pedig csak 32 biten ábrázolható, akkor 4 byte-ot foglal el egy karakter. Ennek köszönhetően jól csökkenthető a szükséges tárterület, mivel egy magyar szövegben csak az ékezetes és speciális betűk, mint az ó, ö, ő, ú, ü, ű betűk fognak 2 byte-os karakterek lenni.

Annak ellenére, hogy van UTF kódolás jó régóta, csak 2007-ben váltotta le az ASCII kódot a weben hivatalosan az UTF. A Windows XP óta minden Windows rendelkezik UTF-8 támogatással, de a fájlnevek tárolása még mindig ASCII és kódlapjai segítségével történik.

Képek

A képek a képpontok színének tárolásával kódolhatóak. Kérdés az, hogy hogyan írjuk le a színeket. Számítástechnikában az RGB színmodellt alkalmazzák a legtöbb helyen. Ennek segítségével bármilyen szín három alapszín megfelelő keverékeként áll elő: piros, zöld és kék. A modell sajátossága, hogy ha ezeket mind 100% intenzitásban összekeverjük, akkor fehér fényt kapunk. Ha pedig 0% intenzitással szerepelnek a komponensek, akkor feketét. Mivel a festékek esetén ez a megközelítés használhatatlan nyomdában a CMYK modellt alkalmazzák, amely négy színnel dolgozik.

Képek esetén számos képformátumot alkottunk meg. A legegyszerűbb tárolási mód, ha tömörítés nélkül tároljuk a képeket. Ebben az esetben több tárolási mód adódik, attól függően, hogy hány színt szeretnénk ábrázolni pixelenként. Az alábbi formátumok terjedtek el:

  • 1 bit pixelenként
    Fekete-fehér képeket eredményez, 8 pixel információja tárolható egy byte-on.
  • 16 bit pixelenként
    Színes képet eredményez, de a 16 nem osztható 3 felé maradék nélkül. Ebből adódóan az első megközelítés az volt, hogy 5 bitet alkalmaznak csatornánként, és egy bit pedig használatlan marad. Ezt később felváltotta az 5-6-5 bit elrendezés, ahol a piros és a kék szín 5 biten van ábrázolva, a zöld pedig 6 biten. Erre azért volt szükség, mert az emberi szem jobban érzékeny a zöld szín árnyalataira, mint bármelyik másikra.
  • 24 bit pixelenként
    Ma a leggyakrabban alkalmazott színkódolás. 8 bit jut minden alapszínre.
  • Fix palettás képek
    A fix palettás képek a 16 bites színmélység megjelenése előtt voltak használva. Ezen tárolás lényege, hogy definiálunk 8, 16, 32, vagy 256 színt, amely segítségével felépítjük a képünket. A színek tárolása történhet 16 vagy 24 biten. Ezután minden pixel csak egy byte adatot foglal és a palettában hivatkozik a színre, amely segítségével helyettesíthető. Ezen tárolási mód abban az időben volt nagyon népszerű, mikor még a számítógépek nem rendelkeztek végtelen mennyiségű memóriával.

A képek tárolása tömörítetlen formátumban igen nagy helyet tud elfoglalni. Egy full HD felbontású képkocka tárolása tömörítetlenül 24 bit színmélységgel 5,9MB adatot jelent. Ez ma már nem számít annyira nagy méretnek, de még mindig nem kényelmes interneten küldözgetni ekkora fájlokat. Éppen ezért megalkottak különböző képtömörítési eljárásokat. Ezek közül a legnépszerűbb a JPEG és a PNG

A JPEG formátum veszteséges. Úgy éri el a tömörítést, hogy az egymáshoz közel álló pixeleket, ha közel állnak színben, helyettesíti egy, az adott környezetre jellemző színnel. Ez a legtöbb esetben nem feltűnő, mivel az emberi szemet nem arra tervezték, hogy egy-egy pixel színét külön-külön meg tudja különböztetni. Magas tömörítési beállítás mellett azonban igencsak rontja a képminőséget nagyon észrevehetően.

A PNG formátum veszteségmentes tömörítést alkalmaz, ebből adódóan a kimeneti fájlok mérete nagyobb lesz, mint a JPEG képek esetén. Ezt a formátumot leginkább ábrák, pár színt tartalmazó képek tömörítésére találták ki.

Hangok

A hangok tömörítés nélkül úgy tárolódnak, hogy a mintavételezési frekvencia által meghatározott darabszámú mintát rögzítünk adott intenzitással. Az intenzitás 16 bites szám, a mintavételezési frekvencia a legtöbb esetben 44100Hz. Ezt nevezzük CD minőségnek. Az audio CD lemezek esetén 1 perc tárolásához ~10Mb hely kell. Ezt a fajta kódolás a PCM.

Ebből csinálnak a különböző tömörítők tömörített hangot, amelyek közül a legnépszerűbb az MP3. Ez igencsak veszteséges tömörítés, fejlettebb változata az MP4, amely jóval fejlettebb, viszont nem tudott elterjedni olyan szinten, mint elődje.

Léteznek veszteségmentes tömörítési eljárások is, mint a WavPack, FLAC és ALAC. Ezek az eredeti hang anyagot nem változtatják meg, viszont a fájlméretet csökkentik valamennyire. A tömörítés mértéke a hanganyagtól függ. Van ami jobban tömöríthető, van ami kevésbé.

Az MP3, MP4 formátumról és a veszteségmentes formátumokról korábban készítettem részletes írásokat.