Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

3. Példák a kódolás alkalmazásaira

3. Példák a kódolás alkalmazásaira

A jelen dolgozat kódok néhány alkalmazását igyekszik bemutatni. Megírásakor elsősorban az [5] és [6] dolgozatokra, valamint J. H. van Lint könyvére [7] támaszkodtunk.

Először matematikai fogalmak használata nélkül érzékeltetjük, hogy mikor használunk kódolást. Tegyük fel, hogy két ember (vagy berendezés) üzeneteket akar váltani. Az egyik ember először kódolja üzenetét, majd ezt a kódolt sorozatot küldi el partnerének. Az egyszerűség kedvéért az üzeneteket számsorozatként képzeljük el. Ez lehet tízes, de lehet más alapú számrendszerben felírt szám is, pl. nullákból és egyesekből, vagy 0, ± 1 -ekből felírt sorozat, vagy betűkből álló üzenet esetén lehet a betűk sorszámából álló sorozat. Az az eljárás, amellyel az üzenetből számsorozatot készítünk, a kódolás. Kódolás használatának egyik tipikus oka az, hogy a csatorna, amelyen a két ember (vagy gép) kommunikál, nem alkalmas kézírás, kép vagy hang átvitelére. Az üzenet címzettje a megkapott számsorozatból visszafejti az üzenetet. Ezt az eljárást dekódolásnak nevezik. A nehézséget az okozza, hogy az üzenet továbbításakor egyes számjegyek megváltozhatnak. Gondoljunk arra, hogy az adatok átvitele mondjuk telefonvonalon történik, de ott hálózati zavar, recsegés következhet be, vagy egyéb üzenetek részei hozzákeveredhetnek. Ugyanez a helyzet, ha rádióhullámmal történik az adatátvitel. Célunk az lesz, hogy a címzett akkor is vissza tudja fejteni az eredeti üzenetet, ha néhány számjegy a továbbítás során megváltozott.

Kódolás használatának másik gyakori oka lehet az, hogy a felek nem akarják, hogy más is megértse, amit egymással közölni akarnak. Ilyenkor titkosításról beszélünk. Ez az írás nem a titkosírásról szól.

Nagyon gyakran előfordul, hogy a kódolt üzenetek 0 – 1 sorozatok, hiszen ezt elektromos berendezéssel könnyű megvalósítani (folyik áram – nem folyik áram). Ugyancsak gyakori, hogy egy-egy üzenet hossza valamilyen műszaki okból rögzítve van. Mi csak ilyen kódokkal foglalkozunk majd. Lássunk erre egy jellegzetes példát. Számítógépünk két részegysége kábellel van összekötve, ezen keresztül küldenek adatokat egymásnak. Ezek az adatok mondjuk 7 hosszú 0 – 1 sorozatok. Néha előfordulhat, hogy valamely 0 vagy 1 megváltozik (például mert bekapcsoljuk a porszívót stb.). Ezért a részegységek olyan nyolcadik elemet illesztenek a sorozathoz, hogy a nyolc elem között páros sok egyes forduljon elő. Ezt a nyolcadik elemet (bitet) szokták paritásbitnek is nevezni. Ha egyetlen elem változott meg, akkor a sorozatban szereplő egyesek száma eggyel változik, azaz páratlan sok egyes lesz a 8 elem között. Ekkor a fogadó részegység jelzést küld az adónak, hogy küldje újra az üzenetet.

A paritásbiten múlik a 2. feladat optimális megoldása is. Ügyes taktika esetén a leghátsó ember által adott információ alapján az összes többi rab megszabadulhat. Hogyan?

Kódokkal a mindennapi életben is gyakran találkozunk. Ha bemegyünk az ABC-be, a megvásárolt árucikket a pénztárnál vonalkód segítségével azonosítják. Az alábbi rövid leírás [6]-ből való. Minden árucikk vonalkódja 12 decimális jegyből áll. Ezeket a jegyeket ezután alkalmas módon 7 darab 0-ból ill. 1-ből álló sorozattal kódolják, de az első hatot és az utolsó hatot különbözőképpen. Például az 5-ös számjegynek a 0110001 sorozat felel meg, a vonalkód egyik felén. A vonalkódban a 0-kat fehér, az 1-eseket fekete vonal jelöli. Eszerint két egymás utáni egyes két egység vastagságú vonal, három egymás utáni nulla három egység széles sáv formájában jelenik meg a vonalkód egyik felén. Gyakran előfordul, hogy a vonalkód-leolvasó sikertelenül próbálkozik, ilyenkor a pénztáros megismétli az eljárást, majd sikertelenség esetén manuálisan beüti a 12 decimális számot. Ilyenkor bosszankodni szoktunk, pedig örülnünk kellene: a vonalazás úgy van kialakítva, hogy szennyeződés, a csomagolóanyag gyűrődése vagy egyéb kisebb zavar esetén sem olvassa be a műszer egy másik – esetleg jóval drágább – termék kódját, hanem jelzi, hogy nem sikerült a beolvasás. A vonalkódokról további részleteket a http://64.21.138.30/barean.htm webcímen találhatunk.

Ehhez némileg hasonló a helyzet a személyi szám, adószám stb. esetén, csak ott maguk a decimális számjegyek a kódolt adatok. Ha felnyitunk egy könyvet, abban is találunk az adott könyvre jellemző kódot az ún. ISBN-kódot, melyet most részletesebben ismertetünk. Ilyen ISBN szám például ez lehet: 0-387-54894-7, amely a [7] ISBN száma. Az első kötőjel előtti szám azt mutatja, hogy milyen nyelvterületen adták ki a könyvet. Itt 0 , 1 azt mutatja, hogy angolul, 3 azt, hogy németül beszélőben. A magyar könyvek ISBN-száma 963-mal kezdődik. A [7] könyvnek két ISBN-száma is van, a Springer kiadó amerikai székhelyű, illetve németországi székhelyű vállalata által kért szám. A német vállalathoz tartozó ISBN-szám 3-540-54894-7. A második (elválasztójelek közti) rész a kiadót azonosítja, a harmadik magát a könyvet (ez tehát azonos az amerikai, illetve a német ISBN-számban). Az utolsó jegyet, az ellenőrző jegyet, a következőképpen számolhatjuk ki: szorozzuk meg az első számot 10-zel, a másodikat 9-cel, a harmadikat 8-cal, és így tovább, a kilencediket 2-vel. Adjuk össze ezeket a számokat. A tizedik jegy olyan kell legyen, hogy ha ehhez az összeghez hozzáadjuk, akkor 11-gyel osztható számot kell kapjunk. A tizedik jegy 0 , 1 , , 9 valamint X lehet. Ha a tizedik számjegyre 10 adódna a fenti szabály szerint, akkor X-et írunk. Az olvasó könnyen utánajárhat, hogy a számítógép észre tudja venni, hogy ha valaki az ISBN kód begépelésekor a 10 karakter egyikét elírja, vagy kettőt véletlenül fölcserél. Érdemes ezután újra próbálkozni a 3. feladat megoldásával!

Ezek a példák azt mutatják, hogy gyakran van szükség információk valamilyen formájú kódolására, és arra, hogy azt alkalmas berendezéssel gyorsan értékelhessük. Ezért ezekben a példákban az a lényeges, hogy a csak ritkán előforduló hibákat (pl. két számjegy felcserélése, melléütés stb.) ki tudjuk szűrni, és ezeket viszonylag gyorsan javítani tudjuk.

Vannak azonban olyan esetek is, amikor a hibák meglehetősen gyakran bekövetkezhetnek. A kódelmélet egyik korai sikere volt a Merkur, Mars expedícióknál a képek kódolására használt eljárás. Ha nem használtak volna hibajavító kódokat, akkor semmit nem lehetett volna látni a Mariner, Voyager által készített képekből. A távolról küldött jelek ugyanis annyira gyengék, hogy a vevőberendezésben óhatatlanul meglevő zaj gyakran átváltoztatja az üzenet egy-egy bitjét. Szemben az előző példákkal, itt nem lehet megismételni az adást, így a kódnak akkor is élvezhető képet kellett szolgáltatnia, ha viszonylag sok hiba történt. Az előző példákban az is fontos, hogy a hiba felderítése gyorsan történjen, itt ez nem létkérdés (hiszen a beérkezett adatok feldolgozása utólag történik).

A Mariner 1969 az alábbi kódot használta: készítsünk olyan egész elemű, 32 × 32 -es H mátrixot, amelyben minden elem + 1 vagy - 1 , és bármely két különböző sort skalárisan összeszorozva 0-t kapunk. Ilyen mátrixot nem nehéz konstruálni, először 2 × 2 -es ilyen mátrixot mutatunk, majd megmutatjuk, hogy ha van n × n -es ilyen H n mátrix, akkor van 2 n × 2 n -es is. Négy ilyen kétszerezéssel 32 × 32 -es mátrixig jutunk. A 2 × 2 -es mátrix a H 2 = + 1 + 1 + 1 - 1 mátrix, a kétszerezés pedig ennek mintájára a H n H n H n - H n módon történhet. Itt - H n az a mátrix, amelyet H n minden elemének előjelét ellenkezőjére változtatva kapunk. (Eszerint tehát H 2 az 1 × 1 -es H 1 = ( 1 ) mátrixból éppen a fenti kétszerezéssel kapható.)

Meg kell mutatnunk, hogy a kétszerezéssel kapott 2 n × 2 n -es mátrixban bármely két sor skaláris szorzata 0, ha az eredetiben ez volt a helyzet. Ez nyilvánvaló, ha mindkét sor az első n vagy az utolsó n között van, hiszen ekkor a sorok első n vagy második n koordinátájának skaláris szorzata külön-külön 0 a H n mátrix megfelelő tulajdonsága miatt. Ha az i -edik és n + j -edik sort választjuk, akkor i = j -re az első n koordinátában levő elemek mindegyikének szorzata +1, a második n -é (külön-külön) - 1 , azaz a skaláris szorzat tényleg 0. Ha i j , akkor az első n koordináta szorzatának összege 0, hiszen ez a rész ugyanaz, mint H n i -edik és j -edik sorának skaláris szorzata, a második n koordinátában pedig hasonló okokból ( - 1 -et kiemelve) szintén 0-t kapunk.

Állítsuk elő ezen a módon a H 32 mátrixot. Mivel ebben bármely két különböző sor skaláris szorzata 0, ezek a sorok pontosan 16 helyen egyeznek meg, és ugyanennyi helyen különböznek. Írjuk H 32 alá a - H 32 mátrixot. Így egy 64 × 32 -es mátrixot kapunk. Ebben cseréljük le a - 1 -eket 0-ra. Így a mátrix sorai 64 db 32 hosszú 0 – 1 vektort adnak meg. A Mariner képeinek kódolása a következőképpen történt. Minden ilyen vektort megfeleltettek egy-egy szürkeségi fokozatnak. A képet 700 × 832 képpontra bontották, és minden képpont helyett a szürkeségének megfelelő ( 32 hosszú) 0 – 1-sorozatot küldték el.

Vajon hány hibát lehet javítani ezzel a kóddal? Pontosítsuk a kérdést! Tegyük fel, hogy egy képpontnak megfelelő 0 – 1 sorozatban k bit értéke megváltozott. A kapott „rossz” sorozatot a számítógép kicseréli egy olyan „jó” (tehát valamely szürkeségi fokozatnak megfelelő) sorozatra, amely a legkevesebb bitben különbözik tőle. Mely k esetén lehetünk biztosak benne, hogy így a Mariner által küldött szürkeségi fokozatot kapjuk vissza?