Ellenőrző összeg

Az ellenőrző összeg (angol kifejezéssel: checksum) egy általános informatikai és híradástechnikai fogalom, a digitális adatátvitel vagy adattárolás hibátlanságának ellenőrzését segítő módszer. Főleg régebbi szövegekben látható másik elnevezése a kontrollszumma.

Alapelv

Amikor egy elektronikus eszköz egy másik elektronikus eszköz részére adatokat küld, az átvitt adatokat különféle zavaró hatások torzíthatják. Az átvitel történhet több tízezer kilométeres távolságból is, mint egy műsorszóró műhold és a műholdvevő készülék között, vagy akár centiméteres távolságban is, például a számítógép alaplapjának két alkatrésze között. A zavaró hatás sokféle lehet, egy elektromos gép mágneses tere, egy másik, más eszközök között zajló adás, sűrű hóesés, viharfelhő, villámok, jelvisszaverődés stb. A zavaró hatások által okozott adattorzulás összefoglaló neve zaj.

Az átvitel történhet analóg vagy digitális formában is, az ellenőrző összeg az utóbbihoz kapcsolódik.

A digitális adatátvitel számjegyekre bontva továbbítja az átvinni kívánt információt. A vevőkészüléknek rendszerint nincs semmilyen előzetes elvárása az adatsorozatról, emiatt ha a számsorozatra zaj "rakódik", tehát egy-egy számjegy helyett más szám érkezik meg, azt a vevőkészülék adatként fogadja el. Ugyan az információátviteli technika igen magas fokra ért el a zajszűrés terén, mégis előfordul ilyen adattorzulás, amelyet tehát közvetlenül felfedezni nem lehet. A vevőkészülék számjegyeket vár, számjegyek érkeznek, a hiba észrevehetetlen.

A zavarforrás által okozott kár annál nagyobb lehet, minél sűrűbb az adatsor jeltartalma. Ha a zavarforrás torzító hatása 0,01 másodpercig tart, akkor egy olyan jelsorozatban, amelyben másodpercenként 100 adat halad, 1-2 számot fog eltorzítani. Ha az adatsor másodpercenként 5000 adatot tartalmaz, tehát nagyobb a jel adatsűrűsége, az átviteli csatorna sávszélessége, akkor ebben ugyanaz a zavar már 50-51 számjegyet képes egyszerre eltorzítani. A híradástechnika egyik fontos része egy átviteli csatorna várható átlagos zajterhelésének az előzetes megállapítása. Ha az adatátvitel tervezői nagy zajra számítanak, akkor ezért lassabb átviteli sebességgel is védekeznek a hibák ellen.

A hibák észlelésének legegyszerűbb módja az ellenőrző összeg használata. Bármilyen elvi módszert alkalmazunk is, annak a lényege megegyezik. Az adatküldő eszköz az átküldött adatsort egyezményes méretű szakaszokra, csomagokra osztja fel, és minden csomagból valami számítási algoritmus révén előállít egy kiegészítő számsorozatot, amelyet a csomag után téve szintén továbbít. Ez a kiegészítő számsorozat az ellenőrző összeg. A vevőkészülék fogadja a jelsorozatot, és ő is az egyezményes módon csomagokra bontja azt. Minden ilyen csomagból ő is előállítja ugyanazon elv alapján az ellenőrző összeget, majd összehasonlítja a csomag után küldött ellenőrző összeggel. Ha a kettő megegyezik, akkor adott bizonyossággal kijelenthető, hogy az átvitt adatcsomagban nincs hiba, nincs torzulás. Ha viszont a két ellenőrző összeg nem azonos, akkor tudható, hogy a jelcsomagban valamilyen torzulás történt, hibát tartalmaz. Hogy ekkor mi a teendő, azt már a rendszer megtervezői határozzák meg, például az interneten (TCP-protokoll) továbbított adatcsomagok esetében a vevőkészülék egy jelzést küld vissza, az adatcsomag megismétlését kérve.

Az elvi módszer különféle megvalósításai az ellenőrző összeg előállításának, generálásának matematikai algoritmusában különböznek, ez határozza meg azt, hogy a módszer egy csomagban hány hibát képes egyszerre felfedezni, hogy mekkora adatcsomagot lehet biztonságosan egyetlen ellenőrző összeggel megtoldva átküldeni, vagy hogy a hibának nem csak a ténye, hanem még a helye is kimutatható lesz-e. A téma szakértői számos nagy gondossággal megtervezett, különféle hatékonyságú módszert dolgoztak már ki erre a célra.

Alkalmazás

A digitális jelátvitelben és adattárolásban az adatokat kettes számrendszerre átszámítva, bitek formájában kezelik, de a hibavédelmi algoritmus ennek ellenére alapulhat akár tízes számrendszerbeli számokra is, amelyeket végül bitekre bontva továbbítanak vagy tárolnak. A módszer lehet akkor is bináris elvű, ha a fájl tartalmát a program nagyobb számokra vagy karakterekre átalakítva jeleníti meg.

Az ellenőrző összeg egyik alkalmazása a fent leírtak szerint az adatátvitel során történt jeltorzulás tényének és esetleg helyének azonosítása. A nagyon nagy sűrűségű jelátvitelnél még kis távolságokon is alkalmazzák ezt, például egy processzoron belül haladó, másodpercenként több milliárd bitet hordozó jeleknél is, csupán néhány milliméternyi út gyakorlatilag tökéletes biztonságának szavatolására.

De a másik alkalmazás nem a jelek átvitelének, hanem az adattárolás hibátlanságát ellenőrzi. Bármilyen tárolóeszközön is helyezünk el egy digitális adatsort, az eszköz fizikai tökéletlensége miatt, vagy a hosszabb idő alatt őt érő károsító hatások miatt ez az adatsor szintén sérülhet, tehát emiatt az adat későbbi kiolvasása során hibásan kapjuk azt meg. Itt is érvényes az előzőleg említett szabály: minél kisebb méretű, minél sűrűbben elhelyezett jelekben tároljuk az adatokat, annál nagyobb kárt okozhat egyetlen sérülés. Ha például a már régen elavult lyukkártyán tárolunk adatokat, amelyen több milliméterenként áll egy-egy bitet tároló fizikai jel (egy téglalap alakú lyuk a papíron), durva fizikai sérülés kell ahhoz, hogy egy bit méretű hiba létrejöjjön rajta. Ha az adatokat CD-n tároljuk, ott az adatsűrűség már 1 megabit/mm² nagyságrendű, tehát egy vékony karcolás is bitek tízezreit fedi el. Egy memóriachip, pl. egy pendrive tárolóelemének a jelsűrűsége ennek nagyságrendileg már a 10000-szerese. Ez azt jelenti, hogy a tárolópontok és a szilíciumlapkába rajzolt árampályák annyira aprók, hogy a nyersanyag egy jelentéktelen méretű hibája is értéktelenné teszi a chipet, de a legfinomabb eszközökben halmozottan már a kozmikus sugárzás protonjai is olyan sérüléseket tudnak okozni, amely a tárolásban is egy-egy bitnyi adatsérülést eredményezhetnek.

Éppen ezért a tárolóeszközökön elhelyezett adatok hibátlanságát is célszerű ellenőrző összegekkel védeni. Ez a gyakorlatban azt jelenti, hogy a tároláskor a tárolt adat csomagjaihoz, esetleg fájljaihoz, vagy az egész tárolt fájlhoz egy ellenőrző összeget generáltatunk valamilyen erre írt programmal, és ezt is tároljuk a fájllal együtt. Majd amikor a fájlt ismét használatba vesszük, újra elvégezzük ugyanezt, és az újonnan kapott ellenőrző összeget összehasonlítjuk a tárolttal. Az eltérés mindig a fájlban történt változást jelez. Ez a változás lehet esetleg szándékos, ismert vagy rejtett módosítás következménye, de többnyire inkább véletlenül létrejött hibára, sérülésre utal.

Egy egyszerű szövegfájlban annak figyelmes átolvasásával felfedezhetjük a hibát, mivel az valamelyik karakter megváltozását, "sajtóhibát" eredményez, ám minden egyéb fájltípusnál, az MP3 zenefájltól a programfájlokig, ilyen áttekintést végezni nem tudunk. Márpedig egy programfájlban egyetlen bit eltérés is nagy eséllyel a program hibás működéséhez vezet.

Vannak egyszerű programok (Total Commander, CRC Guard, Validate), amelyek minden fájlhoz egy-egy ellenőrző összeget hoznak létre és azt külön tárolják. De egy másik megoldás egy tömörítőprogram használata, ilyenek a ZIP, RAR, ARJ, 7Z formátumú tömörített fájlokat létrehozó, elterjedt programok. Ezek úgy működnek, hogy az egyetlen tömörítvénybe csomagolt fájlokat nem csak kisebb méretben tárolják, hanem mindegyikhez automatikusan ellenőrző összeget is generálnak, és azt is tárolják. Ha egy ilyen tömörített fájlt "kicsomagolunk", a program mindig ellenőrzi a hibátlanságot, és azonnal értesít, ha valamelyik tárolt fájlban az ellenőrző összeg hibát jelez. Ez az ismeret nagyon fontos, mert ha a hibáról tudomást szerzünk, akkor az adatsort, fájlt nem használjuk fel tévedést okozó módon, és kísérletet tehetünk a fájl pótlására vagy kijavítására. Épp emiatt a mellékes szolgáltatás miatt célszerű lehet olyan fájlokat is például ZIP formátumba tömörítve tárolni, amelyeknek a mérete ezzel nem csökken (MP3, AVI, MPEG, JPG, PNG, PDF stb.), de a mellé kerülő hibavédelem biztonságosabbá teszi a fájl tárolását vagy továbbítását, e-mail mellékleteként vagy lemezen, pendrive-on.

Egyéb esetek

Numerikus ellenőrző összeg védi a személyi számot, a könyvek nemzetközi azonosítására használt ISBN számot, az euró bankjegyeinek sorozatszámát, az EAN-13 vonalkódot és még számtalan adatsort vagy azonosító jelet. Mivel ezek generálásának algoritmusa jól ismert, így hamis számok előállításakor nem nehéz a helyes ellenőrző karaktert kiszámolni, emiatt ezek a módszerek a szándékos hamisítások ellen nem védenek. De egy tévesen megadott adatra, egy elírásra, számcserére fel tudják hívni a figyelmet, persze csak akkor, ha az ellenőrző számot kiszámítjuk és megvizsgáljuk.

A fenti példák mintájára végül is bármilyen, számokból álló, vagy számkódokra fordítható tetszőleges karakterekből álló jelsorozathoz generálható valamilyen ellenőrző kód. Ennek algoritmusát egyénileg kidolgozva és titokban tartva általunk készített számításokban, elszámolásokban, számítógépes adatbázis adataiban, vagy akár levelek szövegében előforduló véletlen vagy szándékos változtatások felfedezésére kaphatunk lehetőséget.

A lehetőség természetes módon adódik az ókori görög és héber nyelvek kapcsán, amely nyelvek betűihez ismert módon számértékeket is rendeltek. Iván Nyikolájevics Panyin a görög nyelvű Biblia szövegében vélt felfedezni hibaellenőrző struktúrát, más szövegkutatók a Tóra szövegében azonosítottak ekvidisztáns betűsorozatokat (EBS-eket), amelyeknek az elképzelés szerint akár a tartalom misztikus magyarázatához, akár a továbbadott szöveg hibáinak észrevételéhez köze lehetett.

Összehasonlítások

Hatásfok

Kérdés: Miért kell ennyi számolgatás, miért nem lehet egyszerűen megismételni az átvitt adatsort? Ahol a kettő nem egyezik, ott valamelyik változat hibás. A válasz: fölöslegesen nagy lenne a redundancia.

Az adatátvitel során az egyik cél, hogy az adatsor, az "üzenet" minél rövidebb idő alatt a célba érjen. A maximális jelsebesség, más néven a sávszélesség adott, figyelembe véve az eszközök képességeit és a zavarok mértékét. Ha az adattovábbítás idejét teljes egészében hasznos adatok továbbításával töltjük ki, akkor minden adatot a lehető leghamarabb továbbítunk, vagyis az adatátvitel hatásfoka, gazdaságossága az elérhető legnagyobb, 100%.

Ha viszont az adatsorozatba olyan részleteket is teszünk, amelyek nem tartoznak az átadandó információhoz, a fogadó számára nem hasznos adatok, akkor ezekkel, úgymond, vesztegetjük az időt. Ha minden tíz átvitt bitből három bit ilyen egyéb, nem az eredeti információ részét képező jel, akkor az üzenet hatásfoka már csak 70%, az átvitel redundanciája, "veszteségessége" pedig 30%. A redundáns jelek hátráltatják a hasznos adatátvitelt, ezért mindig törekednek a minél kisebb redundancia, minél nagyobb hatásfok elérésére.

Ha minden üzenetet kétszer továbbítanánk, akkor az idő felét olyan adattovábbításra pazarolnánk, amely révén a vevő nem jut további új információkhoz, csak olyat tud meg, amit már az első adagból is megtudott. Ilyen esetben a redundancia 50% lenne, és ez magas. Nem lenne öncélú dolog, de lehet, hogy van jobb megoldás is.

Biztonság

Az ismétléses módszer a hibavédelem szempontjából nem rossz, hiszen elég kicsi (és pontosan kiszámítható) a valószínűsége annak, hogy az adatsor első és második példányában is pont ugyanaz a bit torzul, azaz vált a másik értékre. Ebben az esetben ugyanis a két átküldött példány nem különbözne egymástól, pedig az adat hibás, ám ez észrevétlen maradt. A hibavédelemnek az egyik jellemzője mindig az, hogy mekkora valószínűséggel fordulhat elő olyan hiba, amelyet a védelem nem jelez.

Hogy az észrevétlen hiba mekkora kárt okozna, milyen veszélyt hordoz, azt az adott helyzetben kell a kockázatelemzőknek eldönteniük. A nyaralási fényképeket őrző DVD-n egy bitnyi hiba más megítélés alá esik, mint egy országos bankhálózatot üzemeltető programcsomag telepítőlemezén ugyanez. Ezért használnak az utóbbihoz nagyságrendekkel magasabb biztonságú hibavédelmi technikákat.

Mivel a hibavédelmet nem csak átvitelnél, hanem adattárolásnál is használjuk, az ismétléses hibavédelmi módszer azt jelentené, hogy mindenből két példányt kellene tárolnunk, tehát egy 1 gigabyte-os pendrive-on csak fél gigabyte hasznos adat lenne tárolható.

Az ellenőrző összeg módszere azt kínálja, hogy kevesebb hibavédelmi adat továbbításával is elérhető legyen az észrevétlenül maradó hibák kellően kicsi valószínűsége, azaz a hibavédelemhez szükséges redundancia kisebbre is vehető. Ha egy 32 bites jelblokkhoz 8 paritásbitet rendelünk, már 20% redundanciával is elértük, hogy az egy bitnyi elváltozás felderítésének a valószínűsége 100% maradjon.

Nem szabad elfelejteni, hogy a hiba az ellenőrző összegbe is kerülhet. Technikailag az is csak egy adatsor, az átviteli és tárolási hibáknak éppúgy ki van téve. Egy-egy módszer megtervezésénél ennek a felderítésére is gondolni kell, továbbá a felderítetlenségi ráta kiszámításánál is figyelembe kell venni.

Újabb kérdés: miért kell új meg új hibaellenőrző és hibajavító módszerek kidolgozásával vesződni, miért nem elég egyetlen módszer?

Egy hibavédelem értékelésekor az egyik szempont az elért biztonság, tehát az észrevétlen hiba valószínűsége, egy másik az ehhez szükséges redundancia mértéke. Ilyen szempontból az említett két módszer eléggé különböző. Az első módszerben 32 adatbit átviteléhez 64 bit kell, a redundancia 50%, és a blokkon belül két hiba észrevétlenül maradásának a feltétele az, hogy a második hiba pont "a hibás bittel szemben", az ismételt sorozat azonos számú helyén üssön be, ennek a valószínűsége 1/63, 1,6%. A második módszerben 32 adatbitet csak 40 biten közlünk, tehát 40/64 arányra csökken a valószínűsége annak, hogy egyáltalán hiba kerül az átvitelbe, hasonlóképp hogy két hiba is. Viszont ha két hiba üt be, akkor az 5×8-as jelblokkban 4/39, azaz 10,3% az észrevétlenül maradó hiba esélye (a vastagított számok), 8-szor nagyobb az előzőnél. A második módszer egyik tulajdonságban jobb, másikban rosszabb, pontosan ezért van több módszer, hogy kiválaszthassuk az adott helyzetre leginkább megfelelőt.

Érzékenység

A hibavédelmi módszer értékeléséhez tartozik az is, hogy a hiba észleléséhez használt eljárás milyen mértékű elváltozást jelez. Ez nem azonos az előző fejezet tárgyával, mert egy módszer lehet elvileg is olyan, hogy egy bizonyos mértéket el nem érő hibaszám esetén nem jelzi a sérülést. Olyan adatátvitelben, amelyben egy kis hiba nem okoz értékelési nehézséget, csökkenthető a rendszer haszontalan terhelése a hibavédelem gyengítésével, így az erőforrásból vagy a sávszélességből több marad más célú felhasználásra. Analóg jelátvitelnél erre jellegzetes, ismert példa a beszédhang átvitelére előirányzott gyenge minőség, egy taxi rádióvételének nem kell HiFi minőséget teljesítenie, cserében kisebb teljesítmény és szűkebb frekvenciatartomány is elég az információ megfelelő hatásfokú továbbításához. A beszéd digitális formájának a hibaérzékenysége is alacsony, bár a digitális kódolás miatt egy-egy hiba rövid, de viszonylag nagy mértékű elváltozást tud eredményezni. Egy BMP formátumú fénykép adatsorában vagy egy gyenge minőségű szkennelt szövegben levő hibának is lehet elhanyagolható a jelentősége, ahol a képek apró hibáit a szem figyelmen kívül tudja hagyni.

Diszjunktivitás

A hibavédelemhez használt kiegészítő, biztosító jelsorozat előállítása mindig valamilyen megtervezett algoritmus szerint történik. Van, hogy két, egymástól eltérő adatsorhoz generált ellenőrző jelsorozat megegyezik. A módszer diszjunktivitása akkor nagy, ha az azonos jelsorozattal védett két adatsor egymással nehezen összetéveszthető, más szóval nagy a Hamming-távolságuk. Ha az "1101000" és "1111000" adatsorokhoz az eljárás ugyanazt az ellenőrző jelet generálja, akkor mivel a két adatsor összesen egy biten tér el egymástól, megtörténhet, hogy a hiba pont ezen a biten lép fel, és a hibavédelmi módszer ezt nem jelzi. De ha két diszjunktív, erősen eltérő adatsorhoz tartozik azonos ellenőrző jel – pl. "1101000" és "0100110", ez az ellenőrző algoritmustól függ –, akkor egyszerre négy bithibának is be kell következnie, hogy az ellenőrző jel ezt ne mutassa ki. Lehet, hogy a módszer igen érzékeny 3 és 5 bit elváltozására is, illetve más négybites hibákra is, de ennek a két adatsornak egy bizonyos meghibásodása "vakfoltra esik". Magas diszjunktivitású módszernél az egybeesés csak jól elkülöníthető adatsorokkal – optimális esetben semmilyen esetben sem – fordulhat elő.

Sebesség

Szempont az is, hogy a hibavédelemhez szükséges adatok generálása és egyeztetése mennyi munkát kíván az elektronikától, azaz mennyi időbe kerül. Ha egy bizonyos módszer hatásfoka magas, de olyan bonyolult számításokat kíván, amelyek elvégzése miatt az adatátvitelt szakaszonként mindig meg kellene állítani, akkor az átlagos jelsebesség csökken, a hatásfok romlik.

Eszközigény

A gyakorlatban az is fontos lehet, hogy a hibaellenőrző kód, az ellenőrző összeg előállítása mennyire bonyolult eszközt igényel. Ha nagyon egyszerű elektronikai elemek között egy bonyolult számítást kívánó módszert alkalmazunk hibavédelmül, akkor csak ezért az egyszerű elemek mellé egy-egy bonyolultabb elemet is építeni kell, és ez ritkán lehet gazdaságos.

Módszerek

Az alábbi fejezetekben több olyan hibaellenőrzési eljárás leírása olvasható, amelyek mind az ellenőrző összeg létrehozásának és összehasonlításának módszerére épül.

Paritásbit

Az ellenőrző összeg kifejezés születésekor az algoritmus még valóban egy egyszerű összeadás volt. Az egységes hosszúságú adatsorozat bitjeit össze kell adni, az eredménynek az utolsó, legkisebb helyiértékű bitjét továbbítjuk hibaellenőrző jelként. Ha az adatblokk magas (1 értékű) bitjeinek száma páros szám, akkor az ellenőrző összeg 0 lesz, és ha páratlan, akkor 1. A paritás, azaz párosság szó így került a legegyszerűbb ellenőrző összeg, a paritásbit nevébe.

Az algoritmus nagyon gyors, egyetlen bitnyi adattal kell a processzor számára is nagyon egyszerű logikai műveletet végezni, így tehát ez a hibaellenőrző módszer régóta használatban van mindenféle területe ma is. A módszer elemi érzékenysége végtelen nagy, bármilyen hosszú adatsorban keletkező egyetlen hibát biztosan jelez. Két hibát, és más páros számú hiba bekövetkezését viszont egyáltalán nem jelzi. A biztonság kizárólag úgy szabályozható, hogy az egy bittel védett jelblokk hosszát az adatcsatornán várható zajhoz igazítjuk. Ha alacsony zajra számíthatunk, ezért 999 bit adathoz 1 paritásbitet rendelünk, akkor mindössze 0,1% redundanciával megoldottuk egyetlen bithiba észlelését. Ám ha ennek az adatblokknak a továbbításakor még egy bitváltozás becsúszik, akkor máris 99,9% a valószínűsége annak, hogy ez egy észrevétlen hiba marad. A módszer tehát nagyon instabil, csak az "olcsósága" miatt használják, rutinszerű alapvédelemként.

Hosszparitás

Hosszabb adatsor esetén a bitsort több azonos hosszúságú "keretre" osztjuk (pl.: 8 bitenként) és az így képzett bitsorok azonos helyiértéken lévő bitjeivel képzünk paritásbitet. Ennél a módszernél egy több bites ellenőrző összeg jön létre (pl.: ha nyolcbites egységekre osztottuk az adatokat, akkor az összeg is 8 bites lesz), aminek az angol neve Framed Check Sequence röviden FSC.

CRC

Mivel a paritáson alapuló hibaellenőrzés elől rejtve maradnak a kereszthibák (pl.: két bit ellentétes hibája), és nem derül ki a képzett ellenőrző összegből a hibás bit helye sem, ezért szükséges bonyolultabb ellenőrző összeg generálási módszerek használata. Ilyen módszer a Cyclic Redundancy Check, röviden CRC. Ennél a módszernél egy meghatározott képlet szerint a küldő fél az üzenet bitjeiről egy CRC kódot hoz létre, amit elküld az üzenettel együtt. A vevő pedig meghatározott lépések alapján a fogadott üzenetet és a CRC kódot összehasonlítja. A gyors ellenőrzés érdekében a CRC ellenőrzésekor a vevő először megállapítja, hogy sérült-e az üzenet és csak abban az esetben fejti vissza a CRC kódot a hiba helyének meghatározásához, ha az szükséges. Mivel bizonyos esetekben előfordulhat, hogy a hiba nem meghatározható a CRC kódból, ezért a tényleges alkalmazásnál ezeket az eseteket igyekeznek kiküszöbölni, előre meghatározott lépések beiktatásával mind a generálás, mind a visszafejtés esetén. Jelenleg a CRC-n alapuló hibaellenőrzések igen elterjedtek, mivel nagyon megbízhatóak és megbízhatóságukhoz képest kis mennyiségű többlet adatforgalommal jár.

Források

• Oxford számítástechnikai értelmező szótár. Budapest: Novotrade. 1989. ISBN 963-585-044-1. 72. oldal.
• Hack Frigyes – Pásztorné Varga Katalin: Bevezetés a számítástudományba – egyetemi jegyzet (Tankönyvkiadó, Budapest, 1980)
• dr. Sára Attila: Számítógép hardware – egyetemi jegyzet (Tankönyvkiadó, Budapest, 1981)
• Dr. Ajtonyi István - Dr. Gyuricza István: Programozható irányítóberendezések, hálózatok és rendszerek - 2010. ISBN 963-16-1897-8