Magyar Tudomány, 2001/5

Megemlékezések

Claude E. Shannon

1916-2001


2001. február 24-én, 85 éves korában elhunyt Claude Elwood Shannon, az információelmélet megteremtője, a 20. század egyik legeredetibb gondolkodója.

1916. április 30-án született. A University of Michigan-en 1936-ban matematikai és villamosmérnöki BSc fokozatot szerzett, majd 1940-ben az MIT-n villamosmérnöki MSc-t és matematikai PhD-t. Témavezetője szerint a villamosmérnöki diplomaterve ezen a területen a század legnagyobb hatású munkája. Témája: hogyan lehet digitális hálózatot Booe- algebrával leírni és tervezni. A feladat onnan eredt, hogy a témavezetője analóg mechanikus számítógéppel oldott meg differenciálegyenleteket, és megkérte Shannont, hogy segítsen neki. Mivel a gép gyakran elromlott, Shanonnak sűrűn kellett azt megjavítania. Ezt a feladatot nagyon unta, és igyekezett a gép részegységeit áramkörökkel kiváltani. Az áramkörök egy része kapcsolóhálózat volt, amelynek tervezésére ekkor még nem létezett módszertan. Az volt az eljárás, hogy ad hoc módon megépítették az áramkört, utána pedig kipróbálták, teljesíti-e az előírást. Shannon remek ötlete rögtön azt eredményezte, hogy az áramkör megépítése és kipróbálása helyett elegendő az őt leíró Boole-függvény bizonyos helyettesítési értékeinek a kiszámítása. További előny a tervezés szempontjából, hogy optimalizálható a Boole-függvény olyan értelemben, hogy az adott specifikációt teljesítő digitális hálózatok közül megkereshető a legkevesebb kapcsolót tartalmazó hálózat. Bár ma ez egy villamosmérnök számára trivialitás, kevesen tudják, hogy ez is Shannon nevéhez fűződik, de nem ettől lett híres.

1941-től a Bell Laboratóriumban dolgozott. A második világháború alatt titkosítással foglalkozott, az ő eljárását használta a SIGSALY telefon, amellyel Churchill és Roosevelt biztonságosan tudott beszélgetni. 1948-ban jelent meg a The Mathematical Theory of Communication, Bell Syst. Tech. J., vol 27, pp. 379-423, 623-656 cikke (magyarul is megjelent az OMIKK kiadásában), amellyel megteremtette az információelméletet. Emlékeztetek arra, hogy ugyanebben az évben, ugyanezen a kutatóhelyen találták fel a tranzisztort.

Az információelmélet az információ tömörítésének, átvitelének, tárolásának, védelmének és feldolgozásának a természettörvényeit foglalja egységbe. Az információ tömörítésének, 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 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 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 kódolni. A matematikai feladat megfogalmazásához 1948-ban elég kevés tapasztalat állt rendelkezésre. Egyedül a Morse-kód törekedett valamilyen tömörítésre akkor, amikor az ábécé 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. A modellezés első lépcsőjében a tömörítendő sorozat legkisebb egységét nevezzük betűnek, és tekintsük azt egy véletlen, azaz valószínűségi változónak, az egész sorozatot, az információforrást pedig egy valószínűségi változósorozatnak, tudálékosan sztochasztikus folyamatnak. Ez az egyszerű fogás tette lehetővé, hogy Shannon a valószínűség-számítás módszereivel megfogalmazhatta és megoldhatta a tömörítés feladatát. Az egyszerűség kedvéért nézzük a bináris kódszavak esetét! Shannon első észrevétele az volt, hogy ha egy betűt tömörítünk, kódolunk egyértelműen dekódolható kóddal, akkor az átlagos kódhossz legalább akkora, mint a betű valószínűség-eloszlásához rendelt entrópia, tehát az átlagos kódhosszra talált egy alsó korlátot. Ezt a felismerést ezek után kombinálta azzal az elvvel, hogy egy betű tömörítése helyett több, mondjuk k betűből álló blokkot kódoljunk. Ha most egy blokkot tekintünk információs egységnek, akkor az előzőek miatt az egy betűre jutó átlagos kódszóhossz nagyobb vagy egyenlő, mint a blokk egy betűre jutó entrópiája. Az összes, gyakorlatban előforduló forrás esetén az egy betűre jutó entrópia a blokkhossz monoton fogyó függvénye, és az infimumot forrásentrópiának nevezzük. Shannon megmutatta, hogy ez az alsó korlát éles, vagyis alsó határ abban az értelemben, hogy a blokkhossz növelésével megadható egy kód, amelynek egy betűre jutó átlagos kódhossza a forrásentrópiát tetszőlegesen megközelíti, a forrásentrópia tehát az adattömörítés problémájában az elvi határ.

Shannon eredményei felhasználják a forrás eloszlásait, ám gyakorlati feladatokban azok nem ismertek. Ez az univerzális forráskódolás problémája, ahol az ismeretlen eloszlások becslését és a kódolást szimultán végezzük úgy, hogy elvi határként szintén a forrásentrópiát kapjuk. A pkzip, az arj, a compress tömörítő program és a gif képformátum ilyen univerzális forráskódoló algoritmust használ.

Szintén Shannon fedezte fel a tipikus sorozatokat, vagyis azt a természettörvényt, hogy igen általános feltételek esetén egy információforrás hosszú blokkjainak létezik egy majdnem 1 valószínűségű halmaza úgy, hogy ezeknek a blokkoknak a valószínűsége közel egyforma. Ezeket a blokkokat hívjuk tipikus sorozatoknak.

A veszteséges, vagyis torzítást megengedő forráskódolás esetén nem követeljük meg a tökéletes reprodukciót. Mindennapi alkalmazásai a beszéd, zene, kép, video tömörítése. Mivel ezekben a példákban a forrás eleve nem véges értékkészletű, ezért nyilván minden digitalizálás, véges értékkészletű reprezentálás torzítást okoz. 1948-ban ennek a feladatnak sem volt gyakorlati előzménye, hiszen ekkor csak a PCM létezett, amely a telefonos beszéd digitalizálására (a mintavételezésére és a minták kvantálására) szolgáló eljárás, de technológiai nehézségek miatt ekkor a gyakorlatban azt még nem tudták alkalmazni. Ebben a feladatban két költségfüggvényünk van. Az egyikkel mérjük a tömörítést, a másikkal a torzítást. Shannon itt is felfedezte azt az elvi határt, amely megadja a tömörítés éles alsó korlátját, az R(D)-t, ha előírunk a torzítás várható értékére egy maximális D szintet. Az R(D) függvény meghatározásához egy újabb információs mérőszámot vezetett be: a kölcsönös információt. A veszteségmentes esettel ellentétben a veszteséges tömörítés elvi határának a bizonyítása nem konstruktív, és azóta sem találtak gyakorlatban is használható kódot, amely az elvi határt megközelítené. További gond lehet az univerzalitás feladata, amikor nem ismerjük a forrás eloszlását. Az elmélet terén ezt a problémát főleg empirikus vektorkvantálókkal igyekeznek megoldani, míg a gyakorlatban prediktív kódolást használnak, aminek az az alapötlete, hogy elég egy értéknek és a predikciójának a különbségét tömöríteni. Ilyen elveket használnak a GSM-ben és a kép-, videokódolásra használt JPEG, MPEG szabványokban.

Az információelmélet harmadik alapfeladata a csatornakódolás. Az adótól a vevőbe kell eljuttatni a véges értékkészletű ü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 az üzenetekhez a közeghez illeszkedő jelalakokat rendelnek, illetve a vevőben a torzított jelalakokból döntenek a lehetséges üzenetekre. A közeg tulajdonságai miatt az adóban a modem bemenete és a vevőben a modem kimenete különbözhetnek. 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. Az információelméleti modellben a csatornát a kimenet feltételes eloszlásaival adjuk meg, feltéve a bemenetet. Tekintsük a bináris szimmetrikus csatorna esetét, vagyis amikor a csatorna bemenete és kimenete is 0 vagy 1 értékű, és p annak a valószínűsége, hogy a bemenet és a kimenet különbözik. Legyen p=0,1, vagyis egy elég rossz csatornánk van, továbbá legyen az a feladatunk, hogy egy hosszú, például 1000 soros programot akarunk átvinni úgy, hogy igényesek vagyunk: azt kérjük, hogy a teljes átvitel meghibásodásának a valószínűsége legyen akkora, mint mondjuk a lottófőnyereményé. Ha csak egyetlen bit átvitele lenne a feladatunk, akkor eljárhatunk úgy, hogy a 0-t 19 darab 0 küldésével, az 1-t 19 darab 1 küldésével kíséreljük meg, és a vevőben arra szavazunk, amelyik többségben van. Ellenőrizhető, hogy ekkor az átvitel hiba-valószínűsége kielégíti a fentit, de pazaroltunk, mivel a csatornát 1/19-es, azaz kb. 5%-os kihasználtsággal üzemeltettük. Ha a forráskódolásnál sikeres blokk-kódolási elvet alkalmazzuk, vagyis nem egy bitet, hanem egy k hosszú blokkot kódolunk n hosszú kódszavakba, akkor nyilván rögzített k/n csatornakihasználtság mellett a dekódolás hiba-valószínűségének van egy alsó határa, és ez az alsó határ a kihasználtságnak egy monoton növekvő függvénye, vagyis kis hiba-valószínűséget csak kis kihasználtság árán érhetünk el. Ugyanakkor minden realista ember úgy gondolja, adott kihasználtság mellett egy hosszabb üzenet esetén a legkisebb hibavalószínűség is nagyobb, tehát hosszabb programot csak nagyobb hiba-valószínűséggel tudunk átvinni. Shannon - véleményem szerint - itt volt a legmerészebb, a legzseniálisabb. Felfedezte, hogy az elvi határ szempontjából nem ez az igazság. Nem kell ilyen földhöz ragadt módon gondolkodni: létezik a kihasználtságnak egy szintje, ezt nevezzük C csatornakapacitásnak, úgy, hogy ha a rögzített kihasználtságot C alatt tartjuk, akkor az üzenethossz növelésével található olyan kód, hogy a dekódolás hiba-valószínűsége tetszőlegesen kicsi legyen. A fenti példában p=0,1 esetén C=0,54..., tehát a csatorna 50%-os kihasználtságával elérhető, hogy annak a valószínűsége, hogy az 1000 soros programnak legalább egy karaktere elromoljon az átvitel során, legyen kisebb, mint , és csak a program méretével azonos hosszúságú redundanciát kell hozzáadnunk a kódolás során.

Sajnos ez az eredmény sem konstruktív. Ugyanakkor lehetőséget ad az algebrai hibajavító kódok hatékonyságának az összehasonlítására, mivel itt a kapacitás adja a "fénysebességet". A mikroprocesszor megjelenése előtt még az egyszerű kódok dekódolása is túl bonyolult volt, csupán katonai, illetve űrtávközlési alkalmazásokban használtak csatornakódolást. Elméleti tanulságokkal is jártak a NASA megrendelései alapján futó projektek, ahol űrszondák méréseit, illetve fotóit kellett a Földre küldeni. Ez ínyenceknek való feladat, mert a szondán csekély az energia, és a nagy távolság miatt a Földre érkező jel amplitúdója kicsi. Továbbá a csatornában a modulált jelhez termikus zaj adódik, amely tökéletesen modellezhető Gauss-folyamattal. A feladat azért érdekes, mert a zajszint jóval nagyobb, mint a jel amplitúdója. A processzorok megjelenésével egyrészt megnőtt az adatátviteli igény, másrészt lehetővé vált a különböző hibajavító kódolási-dekódolási eljárások olcsó megvalósítása. Itt az áttörést a kódolt moduláció jelentette, amelynek segítségével a kódolás-moduláció, illetve demoduláció-dekódolás műveletpárokat együtt tervezzük. A mai modemek már ilyen elvet használnak. Napjainkban a csatornakódolás legelterjedtebb alkalmazása a CD, ahol Reed-Solomon kódot használnak arra, hogy a CD lemez felületének bizonyos sérülése vagy szennyezése esetén is tökéletesen reprodukálható legyen a rögzített zene.

1970 körül keletkezett az információelmélet egyik modern ága, a többfelhasználós hírközlés. Ebben a problémakörben vagy több adó használja a közös csatornát (többszörös hozzáférésű csatorna), vagy a csatornának több kimenete, több vevője van (adatszóró csatorna).

Ugyancsak Shannon bizonyította be a titkosítással kapcsolatban, hogy létezik tökéletes titkosság. Sajnos ez igen költséges, mert megmutatta, hogy egy lehallgatható csatornán egy üzenet biztonságos átküldése csak úgy lehetséges, ha előtte egy nem lehallgatható csatornán átküldjük a kulcsot, amely legalább olyan hosszú, mint az üzenet. Ez az eredmény nyilván érdektelen akkor, ha abból indulunk ki, hogy csak nyilvános távközlő hálózatunk, azaz lehallgatható csatornánk van. Ez vezetett a gyakorlati titkosság és a 70-es években a nyilvános kulcsú titkosítás ötletéhez, amelynek nemcsak a védett üzenetküldés a feladata, hanem a hitelesítés (digitális aláírás) is. A nyilvános kulcsú titkosítás viszont már "kilóg" az információelméletből, elsősorban számítástudományi módszereket használ.

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 hiba-valószínűségre. Shannon a világ egy olyan részének, a digitális hírközlésnek a törvényeit fedezte fel, amely rész akkor még nem is létezett. A szóban forgó jelenségeket neki "fejben" kellett lejátszania. Következésképp 1948-ban a kutatásban sem társai, sem konkurensei nem voltak. 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. Az entrópiát és a forrásentrópiát idővel valószínűleg felfedezték volna. Szkeptikus vagyok az R(D) függvénnyel kapcsolatban, elsősorban a kölcsönös információ miatt. Meggyőződésem, hogy a csatornakapacitást máig sem találták volna fel, hiába az eddig összegyűlt tapasztalat.

Shannon eredményei rendkívül gyorsan elterjedtek, és több kutató "rámozdult" a témára. 1951-ben megalakult az IRE Professional Group on Information Theory, mai nevén IEEE Information Theory Society. Első ülésének résztvevői: Shannon, Wiener, Neumann, Fano, Zadeh, Tuller (remek névsor). Periodikusan megrendezett konferenciái (IEEE ISIT) közül az 1991-es Budapesten volt. Egy ideje minden konferencián odaítélik a Shannon Awardot, amelynek 1996-os nyertese Csiszár Imre volt.

1953-ban jelent meg az IRE (ma IEEE) Transactions on Information Theory első négy száma. Ma ez a szakma standard folyóirata. Két szerkesztője is magyar: Csiszár Imre és Lugosi Gábor.

Magyarországon Rényi Alfréd már az ötvenes években tanította az információelméletet, Valószínűség-számítás című tankönyvének bizonyos kiadásaiban egy külön fejezetet szentelt az információelméletnek. Az ő korai halála után Csiszár Imre folytatta ezt a munkát, és létrehozott egy információelméleti iskolát. Az információelmélet egyrészt az információs technológia bizonyos diszciplináris alapjait adta, másrészt jelentősen hozzájárult a matematika (valószínűség-számítás, matematikai statisztika, ergodelmélet, kombinatorika, stb.) fejlődéséhez. A Csiszár-iskola mindkét területen alapvetőt alkotott. A mikroelektronika elterjedésével az információelmélet eljárásait tömegesen alkalmazzák, ezért 1986 óta a műszaki informatikusok tantervének része az információelmélet.

Visszatérve Shannonra, 1956-ban átment az MIT-re, és onnan 1978-ban vonult nyugdíjba. Kedves, szerény ember volt. 1985-ben találkoztam vele Brightonban, egy IEEE ISIT konferencián. A szervezők erőltették, hogy szólaljon fel. Mosolyogva mondta, ez neki már "magas", nem érti, hogy mi az a Shannon Theory. Minden róla szóló cikk említi, hogy a Bell Lab folyosóin egykerekű kerékpárral közlekedett, és tudott négy labdával zsonglőrködni. Számos szerkentyűt, gépet szerkesztett és épített, köztük mechanikai sakkozógépet és olyan egykerekű kerékpárt, amelyen stabilan ülve lehetett zsonglőrködni. Háza tele volt zeneszerszámokkal, köztük öt zongorával. Igyekezett minden apróságra egy matematikai modellt ráhúzni, például kombinatorikai elméletet dolgozott ki arra, hogy milyen (n, m) számpárra lehet n kézzel és m labdával zsonglőrködni. Az ilyen eredményeit ugyan leírta, de nem publikálta. Szintén nem publikálta, viszont a tőzsdén sikerrel alkalmazta az empirikus portfólió-stratégiáit. Az IEEE Information Theory Society 1998-ban az MIT-n ünnepelte az információelmélet 50 éves jubileumát, ahol előrehaladott Alzheimer-betegsége miatt sajnos már nem tudott megjelenni.

Györfi László

JEGYZET:

Ha valakinek az érdeklődését felkeltettem, akkor ajánlom a következő olvasnivalót:
T.M. Cover, J.A. Thomas: Elements of Information Theory, Wiley, 1991.
Csibi Sándor (szerk.): Információ közlése és feldolgozása Tankönyvkiadó, 1986.
Csiszár Imre, Fritz József : Információelmélet, ELTE TTK jegyzet, Budapest, 1986.
I. Csiszár, J. Körner: Information Theory: Coding Theorems for Discrete Memoryless Systems, Akadémiai Kiadó, 1981.
Györfi László, Győri Sándor, Vajda István: Információ- és kódelmélet, Typotex Kiadó, 2000.
Linder Tamás, Lugosi Gábor: Bevezetés az információelméletbe, BME jegyzet, 1990.
Nemetz Tibor, Vajda István: Algoritmusos adatvédelem, Akadémiai Kiadó, 1991.


<-- Vissza a 2001/5 szám tartalomjegyzékére
<-- Vissza a Magyar Tudomány honlapra
[Információk] [Tartalom] [Akaprint Kft.]