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.