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.
A fenti feltételeknek eleget tevő
(
x
1
,
…
,
x
11
)
vektorok alkotják a ternér
[]
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[].
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.