2001. február 24-én, nyolcvanöt é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
Michiganen 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ő 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,
Shannonnak 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ő lett 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 a Boole-függvény
optimalizálható 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óriumokban 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 című cikke (Shannon, 1948;
magyarul az OMIKK kiadásában 1986), 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
természettörvényeit foglalja egységbe. Az információ tömörítésének,
forráskódolásának 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
torzítást is megenged 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, egyértelműen dekódolható kóddal kódolunk, 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. A gyakorlatban előforduló összes 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, videó 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, amelynek 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- és 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-et 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 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özragadt 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 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,
aminek 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, 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 egyetlenegy 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éppen 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ó „mozdult rá” 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, Norbert Wiener,
Neumann János, Robert Fano, Lotfi Zadeh, William 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-díjat, amelynek 1996-os nyertese Csiszár Imre volt.2
1953-ban jelent meg az IRE (ma IEEE) Transactions
on Information Theory első négy száma. Ma ez a szakma standard
folyóirata. Négy szerkesztője is magyar volt: Csiszár Imre, Körner
János, Linder Tamá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-elmélet. 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 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-en ünnepelte az információelmélet ötvenéves jubileumát, ahol
előrehaladott Alzheimer-betegsége miatt Shannon sajnos már nem
tudott megjelenni.
Kulcsszavak: adattömörítés, hibajavító kódolás,
csatornakapacitás, titkosítás, gazdaságos és biztonságos digitális
távközlés
IRODALOM
Akik érdeklődését sikerült felkeltenem,
azoknak ajánlom a következő olvasnivalót:
Cover, Thomas M. – Thomas, Joy A. (1991):
Elements of Information Theory. Wiley
Csibi Sándor (szerk.) (1986): Információ
közlése és feldolgozása. Tankönyvkiadó, Budapest
Csiszár Imre – Fritz József (1986):
Információelmélet. ELTE TTK jegyzet, Budapest
Csiszár Imre – Körner J. (1981):
Information Theory: Coding Theorems for Discrete Memoryless Systems.
Akadémiai, Budapest
Györfi László – Győri S. – Vajda I.
(2000): Információ- és kódelmélet. Typotex, Budapest •
WEBCÍM
Linder Tamás – Lugosi Gábor (1990):
Bevezetés az információelméletbe. BME jegyzet, Budapest
Nemetz Tibor – Vajda István (1991):
Algoritmusos adatvédelem. Akadémiai, Budapest
Shannon, Claude Elwood (1948): The
Mathematical Theory of Communication. The Bell System Technical
Journal. 27, 3, 379-423., 623-656. DOI: 10.1002/
j.1538-7305.1948.tb01338.x •
WEBCÍM magyarul: Shannon Claude
E. – Weaver, Warren (1986): A kommunikáció matematikai elmélete. Az
információelmélet születése és távlatai. (ford. Füzeséri András)
OMIKK, Budapest
LÁBJEGYZETEK
1 A Magyar Tudomány
2001/5. számában megjelent megemlékezés kissé rövidített változata
<
2 A megemlékezés eredeti
közlése óta Körner Jánost és Marton Katalint is kitüntették
Shannon-díjjal.
<
|
|