Györfi László: Claude E. Shannon (1926-2001)

Claude E

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 Boole 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 romlott el, 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 dolgozott a Bell Laboratóriumban. 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, 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 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 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. 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égszá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égeloszlá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 sorozatok.

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 hibavaló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 hibavaló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 hibavaló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 hibavaló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 hibavaló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 amplitudó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áslegelterjedtebb 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ögzitett 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 hibavaló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, az 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égszá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 diszciplínáris alapjait adta, másrészt jelentősen hozzájárult a matematika (valószínűségszá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.

Ha valakinek  az érdeklődését felkeltettem, akkor ajánlom a következő olvasnivalót:

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.