-
1. ábra
|1|
-
2. ábra
|2|
-
3. ábra
|3|
-
4. ábra
|4|
-
5. ábra
|5|
-
6. ábra
|6|
-
7. ábra
|7|
-
8. ábra
|8|
-
9. ábra
|9|
-
10. ábra
|10|
-
11. ábra
|11|
-
12. ábra
|12|
-
13. ábra
|13|
-
14. ábra
|14|
-
15. ábra
|15|
-
16. ábra
|16|
-
17. ábra
|17|
-
Animáció : CD-re írandó szöveg, soronkénti kódolás
|1|
-
Animáció Oszloponkénti kódolás, rögzítés a CD-n
|2|
-
Animáció Hibázás CD-n
|3|
-
Animáció Törléses hiba CD-n
|4|
Györfi László
Az információtechnológia természettörvényei, avagy meddig véletlen a véletlen?
I. Információtechnológiai feladatok
Az információelmélet bizonyos információtechnológiai feladatok gazdaságos megoldásának elvi határait és az ezeket a határokat közelítő kódolási eljárásokat foglalja egységbe. Ezek közé a feladatok közé tartozik az információ átvitele, illetve tárolása során az információ tömörítése és védelme. Az információval, adattal lehet mást is csinálni, például adatkezelést, információfeldolgozást stb., amely a feladatok az előbbiekkel együtt a tág értelemben vett informatika témái.
Az információ tömörítésének, a forráskódolásnak két típusát különböztetjük meg. Az egyik a veszteségmentes - ezt adattömörítésnek is hívjuk -, a másik a veszteséges forráskódolás, amely megenged torzítást is a reprodukció során.
Az adattömörítés feladata, hogy egy üzenetsorozatot gazdaságosan reprezentáljon, vagyis kódoljon úgy, hogy egyrészt a kódolt sorozat minél rövidebb legyen, másrészt a kódsorozatból az üzenetsorozat egyértelműen reprodukálható legyen. Ilyen problémával találkozunk, ha például könyvet, programot, adatsorozatot kell tömöríteni.
Képzeljük el, hogy a magyar szépirodalmat szeretnénk CD-re vinni, amikor nem közömbös, hogy ez hány CD-re fér el, tehát érdemes tömöríteni. Egyáltalán nem nehéz 1:10-es tömörítési arányt elérni, amikor tömörítéssel 10-szer kevesebb CD kell, mint tömörítés nélkül. Egy másik példa lehet, amikor mobiltelefonon szeretnénk szöveget átküldeni. Ilyenkor a kis adatsebességű mobilon akkor tudom mégis gyorsan átküldeni a szöveget, ha átküldés előtt tömörítem. 1:10-es tömörítéssel például tizedannyi idő alatt tudom átküldeni a tömörített üzenetet.
Az első tömörítő eljárás a Morse-kód volt, amely az ABC gyakran előforduló betűihez rövid, a ritkábban előfordulókhoz hosszabb ti-tá (mai szóhasználattal bináris) kódszavakat rendelt.
- |1|
A veszteséges forráskódolás esetén nem cél a tökéletes reprodukció, vagyis megengedünk torzítást, de a cél továbbra is a gazdaságos, tömör reprezentáció. Mindennapi alkalmazásai a beszéd, zene, kép, videó tömörítése. Kép tömörítése esetén például nyilván felesleges megkövetelni, hogy a reprodukált kép képpontról képpontra egyezzen meg az eredeti képpel, csupán azt szeretnénk, hogy szemmel ne érzékeljünk romlást. Ebben a feladatban két célfüggvényünk van. Az egyikkel mérjük a tömörítést, a másikkal a torzítást, vagyis azt, hogy a tömörítés utáni reprodukció mennyire hasonlít az eredetire. Ha két, egymásnak ellentmondó célunk van, nevezetesen alacsony értéken tartani mind a tömörítési arányt, mind a torzítást, akkor a probléma úgy kezelhető, ha az egyiket, például a torzítást egy előírt értéken rögzítjük, és emellett minimalizáljuk a tömörítési arányt. Az elvi határ ekkor is tisztázható, de az elvi határt közelítő kódok ma még nem ismertek. Ugyanakkor léteznek a gyakorlatban hatékony veszteséges tömörítő eljárások, amelyeket sikerrel alkalmaznak a mobiltelefonban és a kép, videó, zene kódolására.
Az információ védelme jelentheti az információ sérülése elleni védelmet (csatornakódolás), vagy az adatvédelmet (titkosítás), vagy a hozzáférésvédelmet, illetve hitelesítést (digitális aláírás). Ha például interneten akarok egy banki tranzakciót lebonyolítani, akkor nyilván elvárom, hogy a megadott adatok pontosan legyenek továbbítva (hibajavító kódolás), más személy ne tudja meg ezeket az adatokat még akkor sem, ha az információtovábbítás nyilvános hálózaton, például mobil eszközön történik (titkosítás), a bank számára pedig bizonyított legyen, hogy valóban én kezdeményeztem a tranzakciót (digitális aláírás).
A védelmi feladatok közül nézzük részletesen a csatornakódolást, más néven hibajavító kódolást, mégpedig először néhány hibajavító elvet és technikát. Az adótól a vevőbe kell eljuttatni az üzenetet egy fizikai közegen (vezeték, rádiós frekvenciasáv stb.) keresztül. A távközlő mérnök is ezzel a feladattal foglalkozik. Nevezetesen az adóba és a vevőbe olyan áramköröket, modemeket tervez, amelyek az adóban a bitekhez a közeghez illeszkedő jelalakokat rendelnek, illetve a vevőben a torzított jelalakokból következtetnek a lehetséges bitekre.
A közeg zavarai miatt az adóban a modem bemenete és a vevőben a modem kimenete különbözhet.
A távközlő mérnök feladata az, hogy ennek az eltérésnek a valószínűségét alacsony értéken tartsa. Itt kezdődik az információelmélet feladata, amikor a távközlő mérnök eredményét adottságként tekintjük, amelyen vagy nem tudunk, vagy nem akarunk javítani. Tudomásul vesszük, hogy adott egy többé-kevésbé megbízhatatlan eszköz, ezt nevezzük csatornának, és ennek segítségével akarunk megbízható átvitelt biztosítani.
- |5|
- |6|
kódok, például a Reed-Solomon-kódok, amelyeknél m darab paritásellenőrző karakter esetén bármely legfeljebb m darab karakter meghibásodását lehetséges jelezni. A hibajavító kódolás akkor is használható, ha ilyen visszairányú csatorna nincs. Erre példa lehet az űrszonda problémája, ahol ráadásul a nagy távolság miatt a jelszint jóval kisebb, mint a zajszint, tehát gyakori a hibázás.
Ha t darab hiba történt, akkor 2t ismeretlenünk van, a t hiba helye és a t megsérült karakter. Lényegében ez az oka annak, hogy az előbb említett, m darab paritásellenőrző karaktert használó Reed-Solomon-kód képes megtalálni m ismeretlent, tehát bármely legfeljebb m/2 darab hibát kijavítani.
- |7|
A visszairányú csatorna hiányára egy másik példa a CD, ahol a vett hibás betűsorozat esetén nem kérhetek ismételt küldést. Itt ráadásul a hibázás mechanizmusa kellemetlen, mert a hibák csomókban fordulnak elő. Bor Zsolt előadásából is tudhatjuk, hogy a CD-lemezen a digitális információt a spirálpályák mentén elhelyezkedő negyedhullámhossz mélységű gödröcskék hossza és a gödröcskék távolsága tartalmazza. Ha a CD a winchesterhez hasonlóan az olvasó optikával és mechanikával együtt egy zárt dobozban lenne, akkor gyakorlatilag nem fordulna elő hiba, viszont ekkor éppen a CD fő előnyei tűnnének el. A lemez felületének esetleges sérülésekor vagy a lencse szennyeződésekor azonban egész karaktersorozatok sérülnek meg, ezek a csomós hibák. A csomós hibák ellen védekezik az átfűzési (interleaving) technika. Az üzeneteket (hangmintákat) egy 24x24-es táblázatba írjuk, és minden sort és minden oszlopot 4 paritásellenőrző karakterrel kódoljuk.
Animáció |1}| : CD-re írandó szöveg, soronkénti kódolás
Az így kapott 28x28-as táblázatot oszlopfolytonosan tároljuk a lemezen.
Animáció |2}|
Oszloponkénti kódolás, rögzítés a CD-n
Animáció |3}|
Hibázás CD-n
Animáció |4}|
Törléses hiba CD-n
- |8|
A csomós hibák az oszlopok mentén fordulnak elő, és ezeket a hibás oszlopokat hibajelzéssel detektáljuk, és a hibás oszlopok sorszámai a sorokra elvégzett hibajavítás számra a hibahelyek, azaz mesterségesen törléses hibákat generáltunk, tehát legfeljebb 4 hibás oszlop kijavítható.
Természetszerűen vetődik fel egy hibajavító kódolás minőségének a kérdése. Jellegzetesen egy kódot két számmal jellemzünk, az egyik a kihasználtság, az üzenethossznak és a kódszóhossznak az aránya, a másik a hibavalószínűség, vagyis annak a valószínűsége, hogy a dekódolt üzenet nem egyezik az eredeti üzenettel. A csatornakódolásnak az az alapproblémája, hogy milyen kihasználtságot érhetünk el, ha ambiciózusan a hibavalószínűséget kis értékre akarjuk leszorítani.
II. A véletlen törvényei
Az eddig tárgyalt feladatokban az információ legfontosabb tulajdonsága az volt, hogy véletlen. Ha a tömörítendő adat nem lenne véletlen, azaz adott lenne, akkor nem kellene tömöríteni. Ha a hibázó csatorna nem lenne véletlen, akkor a javítás is triviális lenne, következésképp az információelmélet törvényei főleg a véletlen törvényeit használják fel, illetve fejlesztik tovább.
A véletlennel kapcsolatban a legtöbb ember gyanakszik, hiszen az egyrészt jelenthet szerencsét, ami elkerüli, másrészt jelenthet bajt, katasztrófát, ami viszont megtalálja. A valószínűségszámítás a véletlen tömegjelenségek törvényeit tárja fel, ugyanakkor egy szuverén egyén nem szereti, ha a tömeg egy jelentéktelen pontjaként kezelik, tehát elsőre úgy tűnik, hogy számára a valószínűségszámítás érdektelen. Ennek az ellenkezőjéről szeretnék mindenkit meggyőzni.
A klasszikus valószínűségszámítás főleg a szerencsejátékok, illetve a matematikai statisztika bizonyos problémáival foglalkozott. Ez utóbbi esetén általában kevés adatból próbáltak törvényszerűséget levezetni, azaz jellegzetesen olyan megállapításokat, amelyek nagy, körülbelül 95%-os biztonsággal igazak. Kérdés az, hogy ez a 95% tényleg nagy-e egy egyén szempontjából, aki ezt a törvényszerűséget fel akarja használni? Ha nyáridőben a kedvenc meteorológusom reggel azt mondja, hogy a zápor valószínűsége 5%, akkor ez számomra csak annyit mond, hogy vagy esik, vagy nem, hiszen ha bőrig áztam, akkor nem vigasztal engem, hogy ennek pici volt a valószínűsége. A valószínűségszámítás jelentősége ott kezdődik, amikor a törvényszerűség helyett törvény van, vagyis a valószínűből majdnem biztos - pestiesen szólva tuti - lesz. Mindenkinek van egy tapasztalati fogalma a tutiról. Az, hogy nem lesz hármas találatom a lottón, az valószínű. (A hármas találat valószínűsége körülbelül 0,0008.) Már szubjektív dolog az, hogy az, hogy nem lesz négyes találatom, az tuti-e, vagy ezt csak az ötös találatra mondom. (A négyes találat valószínűsége körülbelül 10-5, az ötösé 10-8.) Törvény alatt a későbbiekben a tutit értem, vagyis amikor a véletlen tömegjelenséggel kapcsolatban ilyen értelemben eltűnik a véletlen.
A valószínűségszámítás legfontosabb törvénye a nagy számok törvénye, amely szerint, ha egy véletlen esemény bekövetkezésére "sok" kísérletet végzünk, és kiszámítjuk a bekövetkezések számának és a teljes kísérlethossznak az arányát, akkor ez az arány "közel" lesz egy számhoz, mégpedig a véletlen esemény valószínűségéhez. Kérdés, hogy mit jelent a "sok", és mit jelent a "közel". Lássunk erre egy példát!
- |9|
- |10|
Az is megmutatható, hogy ezek az adatok nem függnek attól, hogy hányan vesznek részt a szavazásban, tehát adott tűrés és hibavalószínűség esetén ugyanannyi minta kell az USA elnökválasztási eredményének előrejelzésekor, mint a magyar parlamenti választáskor, ezért exit poll-felmérést csak listás szavazás esetén érdemes csinálni.
A véletlen törvényeinek egy jelentős alkalmazási területe a kvantumfizika. Itt a Mindentudás Egyetemén is több ilyen témájú előadást hallhattunk, amikor a fizikus az elemi részecskék véletlen viselkedését, kölcsönhatását egy egyszerű modellel jellemzi, és valószínűségszámítási technikával, többnyire egy rafinált nagy számok törvényével levezeti a makroszkopikus viselkedést. Ha ez a levezetett viselkedés összhangban van a mérésekkel, akkor határtalan örömmel állapítja meg, hogy felfedezett egy új részecskét. (Lásd Horváth Zalán, Mihály György, Sólyom Jenőés Vicsek Tamáselőadását!)
A modern valószínűségszámítást Andrej Nyikolájevics Kolmogorov (1903-1987) alapozta meg egy 1933-ban publikált cikkében. Magyarországon e diszciplína úttörője Rényi Alfréd (1921-1970) volt.
III. A hibajavító kódolás törvénye
- |13|
Nézzünk először egy mindenki számára természetesen adódó technikát, az ismétléses kódot! Ha csak egyetlen bit átvitele lenne a feladatunk, akkor alkalmazhatjuk ezt az egyszerű eljárást. A 0-t például 3 darab 0 küldésével, azaz 000-val, az 1-t 3 darab 1 küldésével kíséreljük meg, és a vevőben arra szavazunk, amelyik többségben van.
- |16|
Érdekes módon ez nem így van. A fentebb már emlegetett Claude Shannon 1948-ban publikált cikkében 32 évesen nemcsak az adattömörítés, hanem a csatornakódolás elvi határát - a "fénysebességet" - is felfedezte, és ő bizonyította elsőként, hogy létezik tökéletes titkosító.
- |17|
A fenti példában p=0,1 esetén C=0,53, tehát a csatorna 50%-os kihasználtságával elérhető, hogy annak a valószínűsége, hogy egy hosszú programnak legalább egy karaktere elromoljon az átvitel során, legyen kisebb, mint 10-6, és csak a program méretével azonos hosszúságú redundanciát kell hozzáadnunk a kódolás során. Nyilvánvaló, hogy léteznek az ismétléses kódnál hatékonyabb eljárások, de a csatornakódolási tétel minden józan elvárást felülmúl.
Képzeljük el, hogy egy 10 bites, tehát igen rövid üzenetet szeretnénk 50%-os kihasználtsággal, azaz 20 bit hosszú kódszavakkal átvinni. Ugyan a legkisebb hibavalószínűségű kódot nem tudjuk megtalálni, de magát a legkisebb hibavalószínűséget jól tudjuk becsülni. Az jön ki, hogy bizony ez a hibavalószínűség túl nagy, amitől elcsüggedünk. Azt mondja erre a Shannon, hogy ne bánkódjunk, ha egy egyszerű feladatot nem tudunk megoldani, akkor próbálkozzunk egy nehézzel, egy jóval nehezebbel, nevezetesen ne 10 bites, hanem 1000 bites üzenetet küldjünk át 50%-os kihasználtsággal, azaz 2000 bit hosszú kódszavakkal. Itt jön az igazi meglepetés: ekkor a minimális hibavalószínűség már mindenki számára elfogadhatóan kicsi lesz. Nyilván történelmietlen dolog eljátszani azzal a gondolattal, hogy hogyan alakult volna ez a diszciplína, ha Shannon meg sem születik. Meggyőződésem, hogy a csatornakapacitást máig sem találták volna fel, hiába az eddig összegyűlt tapasztalat a digitális távközlés területén.
Az üzenethossz és ezzel a kódszóhossz növelésével egy tömegjelenséget konstruálunk úgy, hogy az eredmény, a biztonságos átvitel tuti lesz az egyén, a távközlési szolgáltatás felhasználója számára, és ehhez a szolgáltatónak nem kell pazarlóan bánni a jellegzetesen igen drága távközlési erőforrással. Ha egy csatorna értékét, árát csak a kapacitása határozná meg, akkor a fenti csatorna fele annyit érne, mint egy nem hibázó csatorna - azzal is indítottam a példát, hogy ez egy mit sem érő, vacak csatorna. Hangsúlyozni kell azonban, hogy a kapacitás a hasznosítható kihasználtságok elvi határa, elvi maximuma, és a zajos csatornák zöménél ezt ma még igen nehéz megközelíteni. A GSM-ben például csúcsidőben is csak a kapacitásnak körülbelül 10%-a a kihasználtság.
Visszatérve a csatornakapacitásra, joggal vetődik fel az a kérdés, hogy miért nem működik a valamit valamiért elv, a hibavalószínűség leszorításához miért nem kell a kihasználtságot lerontani. Shannon itt a véletlent többszörösen is munkára fogta. Egyrészt a kódolás bevezetésével egy ügyes kísérletet tervezett, ahol a véletlenszerűen hibázó csatorna a kísérlet egy komponense, másrészt a jó kód létezését egy ravasz véletlen kódválasztással bizonyította.
Számomra bámulatos Shannon képzelőereje és absztrakciós készsége. A nagy tudományos felfedezésekhez többnyire egy új, az addigi elméletekkel ütköző tapasztalat vezetett, márpedig 1948-ban egyetlen egy példa létezett digitális kommunikációra: a távíró, amelynél viszont nem volt szigorú előírás a hibavalószínűségre. A 20. század tudománytörténete minőségileg más, új gondolkodási technikákat eredményezett. Gondoljunk arra például, hogy egészen Descartes-ig úgy vélték, hogy az egyenletes mozgás fenntartásához is erőre van szükség, ugyanis nem tudtak azidáig olyan pontosan sebességet mérni, hogy ennek a kiinduló feltételnek, hipotézisnek a hibája kiderüljön. Ezek után viszont könnyű dolga volt Newtonnak, hiszen csak a differenciálszámítást kellett kidolgoznia, majd kimennie az almáskertbe. Ugyanakkor még a 20. századi elméleti fizika nagyszerű eredményei között is csak elvétve akad olyan törvény, amely addig nem tapasztalt jelenségről szólt, azaz egy elméleti modell alapján először megjósolták a jelenséget, és csak utána "mérték ki" laboratóriumban. Örömmel tapasztaltam, hogy ilyen eredmények Magyarországon is vannak, mégpedig fiatal fizikusoké, ugyanis a 2004-es Talentum-díj egyik kitüntetettje, Domokos Péter alacsony hőmérsékletek területén két jelenséget is megjósolt, amelyek létezését később Párizsban, illetve Stanfordban laboratóriumi kísérlettel bizonyították.
Shannon az információtechnológia természettörvényeit akkor fedezte fel, amikor még nem is létezett digitális távközlés. 1948-ban ugyanezen a kutatóhelyen, a Bell Laboratóriumban találták fel a tranzisztort, de a kódolási, dekódolási eljárásokat hardverben, digitális céláramkörökben lehetett csak megvalósítani még 30 évig, ezért csupán katonai hírközlési és űrkutatási feladatokban lehetett felhasználni az információelmélet eredményeit. A mikroprocesszor megjelenésével a dekódolási algoritmusokat már olcsón, szoftverben implementálták, és így megnyílt az út a tömeges digitális távközlési szolgáltatások előtt. De 1948-ban a szóban forgó jelenségeket Shannonnak még "fejben" kellett lejátszania.