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

8. A Golay-kódok

8. A Golay-kódok

Lássuk a Tietäväinen, Van Lint tételben beharangozott perfekt kódokat. Az egyikben n = 11 , e = 2 és Q = 3 . Egy kódszó köré írt 2 sugarú Hamming-gömbben 1 + 11 1 · 2 + 11 2 · 2 2 = 243 = 3 5 szó van, így 3 6 gömb fedi le a 3 1 1 szót, tehát 3 6 kódszót kell megadnunk. Eszerint perfekt kódunkat 5 egyenlettel fogjuk definiálni. Az ( x 1 , , x 11 ) első hat koordinátáját szabadon választjuk, a maradék pedig a következőképp függ x 1 , , x 6 -tól.

x 7 = x 1 + x 3 + 2 x 4 + 2 x 5 + x 6 , x 8 = x 1 + x 2 + x 4 + 2 x 5 + 2 x 6 , x 9 = x 1 + 2 x 2 + x 3 + x 5 + 2 x 6 , x 10 = x 1 + 2 x 2 + 2 x 3 + x 4 + x 6 , x 11 = x 1 + x 2 + 2 x 3 + 2 x 4 + x 5 +

A fenti feltételeknek eleget tevő ( x 1 , , x 11 ) vektorok alkotják a ternér [19] Golay-kódot, amelyről a finn TOTÓ kapcsán már beszéltünk. Itt tehát modulo 3 számolunk, az = is ? ( mod 3 ) -at jelent.

A kód fenti egyenletrendszeres megadása geometriailag is szépen elképzelhető. Tekintsünk egy szabályos ötszög alapú gúlát, az alaplap csúcsait jelölje 2 , 3 , 4 , 5 , 6 , a 6 . csúcsot pedig 1. Legyen ( x 1 , x 2 , , x 6 ) tetszőleges, ahol x i ? { 0 , 1 , 2 } . Ezekkel az x i -kkel modulo 3 számolunk, és úgy képzeljük, hogy x i az i -vel jelölt csúcshoz rendelt érték. Tekintsük a 2 csúcs szomszédait. Ezek 1, 3, 6, a nem-szomszédok pedig x 4 és x 5 . Az x 7 változó is a 2 csúcshoz kapcsolódik, értéke így számolható ki: adjuk össze a 2 csúcs szomszédaihoz rendelt számokat, és ebből vonjuk ki a nem-szomszédokhoz rendelt számokat. Ez éppen ( x 1 + x 3 + x 6 ) - ( x 4 + x 5 ) . Mivel modulo 3 számolunk, - ( x 4 + x 5 ) helyett 2 ( x 4 + x 5 ) -öt is írhatunk. Az x 8 , , x 11 értékek ugyanígy keletkeznek, a 2 csúcs helyett rendre 3, 4, 5, 6-ot választva.

Még ez a rövid dolgozat sem lenne teljes, ha nem szerepelne benne a bináris Golay-kód. Ez 23 hosszú, 2 12 kódszóból álló, 3 hibát javító perfekt kód. Egyik előállítása az alábbi.

Először a 24 hosszú 4 hibát javító G 24 kódot készítjük el. Tekintsük az ikozaédert[20]. Ennek csúcsait számozzuk meg az 1 , 2 , 12 számokkal és minden csúcshoz írjunk egy-egy „bitet”: x 1 -et, x 2 -t, , x 12 -t. Tehát az x i -k a modulo 2 maradékosztálytest elemei, azaz 0-k vagy 1-ek. Ezek értékeit tetszőlegesen megadhatjuk, ami 2 12 lehetőség. A kód további x 13 , x 14 , , x 24 koordinátái az előzőekből már kiszámolhatók. Legyen i = 1 , 2, , 12 esetén x 12 + i értéke az i -edik csúcshoz tartozó x i számnak és az i -edik csúccsal az ikozaéderen nem szomszédos csúcsokhoz írt biteknek a modulo 2 vett összege.

Figyelembe véve, hogy az ikozaéder két átellenes csúcsához nincs olyan csúcs, amely mindkettőjükkel össze lenne kötve, míg a nem átellenes csúcspárokhoz két olyan csúcs van, amelyek mindkettőjükkel össze vannak kötve, nem túl nehéz megmutatni, hogy G 24 -ben minden kódszó 4-gyel osztható számú egyest tartalmaz. Mivel két kódszó összege is kódszó, G 24 minimális távolsága osztható 4-gyel. Megmutatható, hogy G 24 -ben nincs 4 egyest tartalmazó kódszó, azaz minimális távolsága 8. Ebből a G 23 kódot úgy kapjuk, hogy mondjuk az utolsó koordinátát minden kódszóban kitöröljük. Ezzel a minimális távolság legfeljebb eggyel csökken. A kódszavak száma 2 12 marad, hiszen G 24 különböző szavainak rövidítettjei különbözőek. A Hamming korláttal összevetve ezt, kiderül, hogy a minimális távolság 7, azaz a kód 3 hibát javít, ráadásul perfekt is, hiszen 2 12 ( 1 + 24 + 24 2 + 24 3 ) = 2 23 .

A konstrukcióban szereplő G 24 kódot kibővített Golay-kódnak nevezik. Ezt az elnevezést az motiválja, hogy G 23 -ból a 24. helyre írt paritás-bit hozzáillesztésével kapjuk G 24 -et. Ha tehát ( c 1 , , c 23 ) G 23 -beli kódszó, akkor a neki G 24 -ben megfelelő kódszó ( c 1 , , c 23 , ? i = 1 23 c i ) lesz, ahol az utolsó koordinátában szereplő összeget modulo 2 számoljuk.

Meglepő, hogy a G 24 kódot teljesen naiv és mohó módon is előállíthatjuk. Annak belátása, hogy így valóban G 24 -gyel lényegében azonos kódot kapunk, meglehetősen bonyolult. Induljunk el a 24 hosszú ( 0 , 0 , , 0 ) vektorból. Ha már néhány kódszót kiválasztottunk, amelyek páronkénti távolsága legalább 8, akkor az ezek mindegyikétől legalább 8 távolságra lévő szavak közül vegyük hozzá kódszavaink halmazához a lexikografikusan legkisebbet. Az a = ( a 1 , , a n ) vektor lexikografikusan akkor kisebb a b = ( b 1 , , b n ) vektornál, ha az első olyan koordinátájuk, amely nem egyenlő, az a vektorban kisebb. Formálisan, a lexikografikusan kisebb b -nél, ha a i //<// b i , és minden 1 ? j //<// i -re a j = b j . A konkrét konstrukcióban tehát ( 0 , , 0 ) után a ( 0 , , 0 , 1 , , 1 ) -et választjuk, amelyben 16 nulla után 8 egyes szerepel. A következő kódszó ( 0 , , 0 , 1 , , 1 , 0 , 0 ) lesz, amelyben 8 nulla, majd 8 egyes, majd megint 8 nulla áll. Önmagában már az is meglepő, hogy ezen a naiv módon bármi érdekeset kapunk.

Mivel a bináris Golay-kódok tárgyalása meglehetősen vázlatos volt, a részletek kidolgozását feladatnak hagyjuk. A bináris Golay-kódok leírását a Cameron, Van Lint [8] könyvből vettük. A bevezetőben már említettük, hogy az űrkutatásban már nagyon hamar kitűnt a hibajavító kódok fontossága. A Golay-kódok kapcsán érdekességként érdemes megemlíteni, hogy az 1977-beli Voyager expedíció (melynek célja a Jupiter és a Szaturnusz vizsgálata volt), a G 24 bináris Golay-kódot használta. A képet itt 800 × 800 darab 8 bites képpontra osztották. A részleteket megtalálhatjuk [11]-ben, a 2139. oldalon. A Voyager II. szonda is a Golay-kóddal küldte képeit, de több évvel elindulása után, mikor rájöttek, hogy a szondát továbbirányíthatják az Uránusz, majd a Neptunusz felé, akkor a CD-n és újabban a DVD-n is használt Reed-Solomon kódra tértek át. Ezt azért tették, mert a még távolabbról jövő egyre gyengülő jelekhez több hiba kijavítására volt szükség.

A Mariner 10 és a Voyager űrkutatási programról részletesen olvashatunk és képeket is nézhetünk az alábbi webcímeken:

Nem beszéltünk arról, hogy mikor tekintünk azonosnak két kódot, noha a G 24 mohó előállítása kapcsán a fogalmat már használtuk. A koordináták, valamint az ábécé elemeinek tetszőleges permutációja nem változtatja lényegesen a kódot. Ha megengedjük ezeket a transzformációkat, akkor megmutatható, hogy mind a bináris, mind a ternér Golay-kódok egyértelműen meghatározottak paramétereik által (kódszavak száma, hossz, minimális távolság). Ugyanez nem teljesül az egy hibát javító perfekt Hamming-kódokra. Igaz viszont az a gyengébb tulajdonság, hogy a paraméterek meghatározzák, hogy milyen távolságok fordulnak elő két kódszó között, és ezen távolságok hányszor.

Több magyar nyelven megjelent könyv tárgyalja a kódelmélet bizonyos fejezeteit, így Fried Ervin [4], valamint Birkhoff és Bartee [1] művei. Az algebrai alapokkal kapcsolatban [2] lehet hasznos. Ajánljuk továbbá Freud Róbert Lineáris algebra tankönyvét ([13]), amelyben szintén sok szó esik a kódelméletről.

Végezetül Van Lint (angol nyelvű) könyvére hívnánk fel a figyelmet, amelyben sok további érdekesség található. A [9] könyv a kódelmélet szinte minden ágának igen részletes áttekintését adja.

Nem véletlen, hogy az irodalomjegyzékben is ilyen gyakran szerepel Prof. Jack van Lint (TUE Eindhoven) neve, az ő előadásai nagy hatással voltak a jelen dolgozat egyik szerzőjére, amiért őszinte köszönetet mondunk. Ugyancsak köszönjük Neki, hogy a [6] dolgozatot, valamint az annak irodalomjegyzékében szereplő dolgozatokat elküldte. A jelen dolgozat jó része a J. J. Seidel 80. születésnapjára Oisterwijkben szervezett konferencián Prof. Jack van Lint által tartott előadás alapján készült.

Ugyancsak szeretnénk köszönetet mondani Faragó Istvánnak az MTA Rényi Alfréd Matematikai Kutatóintézete könyvtárvezetőjének az ISBN-számokkal kapcsolatos segítségéért.

Most néhány olyan feladat következik, amelyek közvetlenül kapcsolódnak a dolgozat anyagához.



[19] Ternér = „három jelet használó”, bináris = „két jelet használó”.

[20] Lásd Recski András cikkének első ábráján a jobb alsó poliédert