Labancz Norbert. Hibajavító kódolás

Eötvös Loránd Tudományegyetem Természettudományi kar

Labancz Norbert Matematika BSc

Alkalmazott matematikus szakirány

Hibajavító kódolás Szakdolgozat

Témavezet®:

Dr. Hermann Péter egyetemi docens Algebra és Számelmélet Tanszék

Budapest, 2016

Tartalomjegyzék

1. A hibajavító kódolás 1.1.

3

Kódolási alapfogalmak

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2. Lineáris kódok

3

8

2.1.

Bináris lineáris kódok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

2.2.

Szindróma dekódolás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

2.2.1.

13

A binális Hamming-kód

. . . . . . . . . . . . . . . . . . . . . . . .

3. Véges test

14 GF(p)-ben

3.1.

Aritmetika

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

3.2.

Véges test feletti polinomok . . . . . . . . . . . . . . . . . . . . . . . . . . m Aritmetika GF(p )-ben . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

3.3.

4. Nembináris lineáris kód

16

20

4.1.

Lineáris kódok kib®vítése és ekvivalenciája . . . . . . . . . . . . . . . . . .

22

4.2.

Reed-Solomon kód

22

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5. Ciklikus kódok

24

5.1.

Ciklikus kódok szisztematikus generálása . . . . . . . . . . . . . . . . . . .

25

5.2.

Ciklikus Reed-Solomon kód

26

. . . . . . . . . . . . . . . . . . . . . . . . . .

6. A Golay-kódok

27

6.1.

Blokkrendszerek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

6.2.

A bináris Golay-kód

29

6.3.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.2.1.

G24

6.2.2.

A mohó módon el®állított

el®állítása az ikozaéder adjacenciamátrixa segítségével

G24

. . . . .

34

. . . . . . . . . . . . . . . . . . . . .

36

A ternáris Golay-kód . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

2

1. fejezet A hibajavító kódolás A hibakorlátozó kódolás célja információhibázó kommunikációs csatornákon történ® megbízható átvitele, illetve hibázó adattárolókon történ® megbízható tárolása. E célból az információt kisebb egységekre bontjuk, majd redundáns információval b®vítve kódszavakba képezzük, kódoljuk. A redundancia hozzáadása teszi lehet®vé az információ védelmét hibázás esetén. A hibakorlátozó kódolás két f® technikája a hibajelzés illetve a hibajavítás. Hibajelzés esetén a cél annak eldöntése, hogy történt-e meghibásodás az információ továbbítása illetve tárolása során. Hibajavítás esetén ezen túlmen®en a hibák kijavítása is feladat. Több kapcsolatos kérdés merül fel: hogyan történjen a kódszavakba történ® leképezés, azaz a kódolás, ha célunk a minél er®sebb hibakorlátozó képesség, azon feltétel mellett, hogy a rekonstrukció (dekódolás) a számításigényét tekintve hatékony maradjon. Az alábbiakban a hibakorlátozó kódok konstrukciós és dekódolási alapelveit tekintem át, a hangsúlyt a kapcsolatos fogalmakra és alapvet® algoritmusokra helyezve. A fejezet elkészítésekor felhasznált szakirodalom: [1], [2], [3], [4], [5]

1.1. Kódolási alapfogalmak A hibajavító kódolás alapvet® módszereit a lenti ábrán látható egyszer¶ hírközlési 0 struktúra kapcsán vizsgálom. Az u és u vektorok koordinátái egy F halmazból veszik értékeiket, mely halmazt forrásábécének nevezzük. A kódoló a üzenetet) egy

n

hosszú

c

ból veszik értékeiket. A csatorna kimenete

v,

vektorba (a kódszóba) képzi le. A

Q-t

hosszú

u

koordinátái egy

vektort (az

Q

halmaz-

kódábécének vagy csatorna bemeneti ábécének nevezik. A

szintén egy

u

c

k

n

hosszú vektor, melynek koordinátái szintén

c

v

Q-beliek.

u0

forrás −→ kódoló −→ csatorna −→ dekódoló −→ nyel®

1. Deníció.

Egy c = (c1 , . . . , cn ) bemeneti, és egy v = (v1 , . . . , vn ) kimeneti sorozat esetén azt mondjuk, hogy az m-edik id®pontban a csatorna hibázott, ha cm 6= vm . Jelölje d(c, v) azon i pozíciók számát, ahol ci 6= vi .

 d(c, v) = i : ci 6= vi , i = 1, . . . , n 3

A d(c, v) számot nevezzük a c, v sorozat Hamming-távolságának, és azt mondjuk, hogy c sorozat küldésekor és a v sorozat vételekor a hibák száma t = d(c, v). Azt az esetet, mikor a hiba helye és értéke egyaránt ismeretlen, egyszer¶ hibázásnak nevezik.

d(c, v)

valóban távolság, hiszen

d(c, v) > 0 d(c, v) = d(v, c) illetve teljesül a háromszög-egyenl®tlenség is:

d(c, v) ≤ d(c, w) + d(w, v) Kód (blokk-kód) alatt a egy

n

Qn

halmaz egy

hosszú vektor, melynek koordinátái

továbbiakban a

C(n, k, d),

C

részhalmazát értjük, azaz

Q-beliek. C

C

minden eleme

elemeit kódszavaknak nevezzük. A

illetve rövidítettebb formában a

C(n, k)

jelölést alkalmazom,

kiemelve a kód paramétereit. A kódolás egy invertálható függvény, mely

k hosszú F -beli sorozatot - üzenetet - képez

le egy kódszóban, formalizálva:

φ : Fk → C melyre minden

u 6= u0 ∈ F k

esetén

φ(u) 6= φ(u0 ) ∈ C Dekódolás alatt két függvény egymásutánját értjük. Az egyik a csatorna kimenetének

n

hosszú szegmensét képezi le

pedig a

φ

C -be,

azaz igyekszik eltalálni a küldött kódszót, a másik

függvény inverze, tehát

ψ:Q→C φ−1 : C → F k φ−1 ◦ ψ : Q → F k Mivel csak a

ψ

φ

egyértelm¶en meghatározza

függvényt értjük. A

ψ

φ−1 -et,

ezért a dekódolás alatt a kés®bbiekben

dekódoló függvényként az algebrai hibajavító kódok el-

méletében speciális függvényt választunk, nevezetesen a v vektorhoz megkeressük azt a c0 ∈ C kódszót, mely Hamming-távolsága szerint hozzá a legközelebb van, vagy ha több 0 ilyen van, akkor az egyiket, tehát teljesül, hogy ha c = ψ(v), akkor

d(c0 , v) = min d(c, v) c∈C

A dekódolás feladata ezek után arra a messze nem triviális feladatra sz¶kül, hogy egy

v vett szóhoz hogyan keressük meg a hozzá legközelebbi c0 kódszót anélkül, hogy minden d(c, v)-t kiszámítanánk. Ha mégis kiszámítjuk ezeket a távolságokat, és minden v -hez megkeressük a hozzá legközelebbi c kódszót, majd a neki megfelel® üzenetet, akkor elvben azt eltároljuk, és így egy táblázathoz jutunk, melynek címét v adja, tartalma pedig a v -nek 4

megfelel® dekódolt üzenet. Ez a táblázatos dekódolásnak a legegyszer¶bb, de legpazarlóbb n esete, hiszen a táblázat q darab üzenetb®l áll, ahol q a Q kódábécé elemszáma. A kés®bbiekben kiderül, hogy a kódoló

f

függvény leglényegesebb tulajdonsága a

kód egy paramétere, amit kódtávolságnak nevezünk, és

dmin -nel

C

jelölünk.

dmin = min0 d(c, c0 ) c6=c

c, c0 ∈ C A hibajelzés a hibakorlátozó kódolás azon feladata, amikor a vev®ben csupán detektálni akarjuk a hibázás tényét, azaz azt kérdezzük, hogy van-e hiba. Nyilván egy esetén akkor tudjuk a hibázást észrevenni, ha

v

v

vett szó

nem kódszó, amire garancia, hogy ha

c

küldött kódszó esetén

dmin > d(v, c) azaz a hibák számára

dmin > t tehát egy

dmin

kódtávolságú kód minden, legfeljebb

Hibajavítás esetén azt kérdezzük, hogy ha a 0

c

v

vett szóból a

c

t

dmin − 1

számú hibát jelezni tud.

a hibák száma, akkor mi biztosítja, hogy

küldött kódszó egyértelm¶en visszaállítható legyen, azaz minden más

kódszóra

d(v, v 0 ) > d(v, c) legyen. Mivel a Hamming-távolság valóban távolság, ezért teljesíti a háromszög-egyenl®tlenséget, azaz

d(v, c0 ) ≥ d(c, c0 ) − d(v, c) tehát úgy biztosítható, hogy

d(c, c0 ) − d(v, c) > d(v, c) ugyanis, ha ez utóbbi teljesül, akkor is teljesül, azaz minden

c0 6= c-re

d(c, c0 ) > 2d(v, c) vagyis

dmin > d(v, c) 2 Összefoglalva: egyszer¶ hibázás esetén

jd

min

2

− 1k

(1.1)

hiba javítható. Gyakran fordul el® olyan hibázás, amikor tudjuk, hogy egy pozícióban hiba lehet, vagyis tudjuk, hogy más pozíciókban nincs hiba, tehát a hiba helyét ismerjük, csak a hiba értékét nem. Az ilyen hibát törléses hibának nevezzük. Egyszer¶en belátható, hogy

5

dmin − 1 törléses hiba javítható, ugyanis a legrosszabb esetben sem fordulhat el®, 0 két c és c kódszó ugyanazon, de legfeljebb dmin pozíciójának törlésével ugyanazt a

minden hogy

szót kapnánk. Nyilván adott

n

kódhosszúság és

dmin

kódtávolság esetén nem lehet akármilyen nagy

méret¶ kódot konstruálni:

1. Tétel (Singleton-korlát).

Egy M kódszóból álló, n hosszú és dmin kódtávolságú kódra

M ≤ q n−dmin +1 Bizonyítás. Legyen

k

egy természetes szám, melyre

q k−1 < M ≤ q k k − 1 hosszú különböz® sorozatok száma q k−1 , ezért q k−1 < M c és c0 , melyek els® k − 1 koordinátában megegyeznek. Ezekre

Mivel a kódszó

miatt létezik két

d(c, c0 ) ≤ n − k + 1 következésképpen

dmin ≤ n − k + 1 azaz

M ≤ q k ≤ q n−dmin +1 M = q k , vagyis a kódoló k hosszú forrásszegmensekhez rendel n hosszú mondjuk ilyenkor, hogy a kódunk (n, k) paraméter¶. Ebben az esetben a

Jellegzetes esetben vektorokat. Azt

Singleton-korlát alakja

dmin ≤ n − k + 1

2. Deníció. Azon kódot, melyre a Singleton-korlátban egyenl®ség áll, maximális távolságú vagy MDS (maximum distance separable) kódnak nevezzük. Képzeljünk el egy olyan kódot, mely 1-hibát képes javítani. Ehhez a következ® szemléletes geometriai képet rendelhetjük. A kódszavak, mint középpontok körül képzeljünk el

1

Hamming-sugarú gömböket, azaz a gömb felületén olyan  kódszóhossz hosszúságú  bináris szavak találhatók, amelyeknek a középpontban lév® szótól való Hamming-távolsága

1. Ha egy hiba keletkezik, akkor a vett szó a leadott kódszó körüli gömbön helyezkedik el. Más szavakkal ezen gömbök a dekódolási tartományok. Abban az esetben, ha gömbi dekódolási tartományokkal hézagmentesen képesek vagyunk lefedni a teret, perfekt kódokról beszélünk. Nagyon egyszer¶ összefüggés adódik az

1

hibát javító bináris perfekt kódok n k paraméterei közötti összefüggésre. A tér elemeinek száma 2 , a kódszavak száma 2 , így n−k egy gömb elemeinek száma ezek hányadosa, azaz 2 . Másfel®l, egy 1 Hamming sugarú gömbben

1+n

elem van, így adódik, hogy

1

hibát javító bináris perfekt kódok esetén

1 + n = 2n−k 6

A következ® szakaszban bemutatok egy, az ismétléses kódnál hatékonyabb perfekt kódot, a bináris Hamming-kódot. Az összefüggés könnyen általánosítható tetsz®leges

1 hiba javítás esetére: a képlet bal oldalán a gömb elemeinek 0, 1, 2, . . . , t Hamming-távolságra lév® szavak számának összege,     n n V (n, t) = 1 + n + + ··· + 2 t

t≥

a száma, a középpontól azaz

áll. A fenti gondolatmenet alapján adódó Hamming-korlát bináris esetben az alábbi

V (n, t) ≤ 2n−k A Hamming-korlát nembináris esetben a következ® alakot ölti:

t   X n i=0

i

(q − 1)i ≤ q n−k

7

(1.2)

2. fejezet Lineáris kódok

2.1. Bináris lineáris kódok Ebben a szakaszban el®ször a bináris kódok egy fontos csoportját ismertetem. A továbbiakban a kódjainkban szerepl® kódszavakat alkotó szimbólumok legyenek 0 vagy 1 érték¶ek, a m¶veletek a

(mod 2)

összeadás és

(mod 2)

szorzás. A fejezet elkészítésekor fel-

használt szakirodalom: [1], [2], [3], [4], [5]

Vezessük be a lineáris kód fogalmát:

3. Deníció.

Egy bináris C kód lineáris, ha a C halmaza lineáris tér, azaz ha minden c, c ∈ C -re c + c ∈ C . 0

0

A lineáris kód deníciójából következik, hogy a vagyis minden lineáris kód esetén a

0

0 vektor eleme minden lineáris kódnak,

kódszó. A lineáris kódok jelent®ségét az adja, hogy

az egyes üzenetekhez tartozó kódszavak viszonylag egyszer¶en generálhatók, és ugyancsak egyszer¶ módszer található a vett kódszavak hibamentességének vizsgálatára, vagyis a hibadetektálásra, és a hibák javítása sem bonyolult. A következ®kben e módszereket fogom bemutatni. Jelentsen az

n

C

továbbra is egy lineáris kódot, a kódszóhossz legyen

n.

Ekkor

C

hosszúságú bináris koordinátájú vektorok terének egy altere. A valós vektortérben

megszokott lineáris függetlenség és bázis fogalmak itt is teljesen hasonlóan értelmezhet®ek, vagyis

4. Deníció.

 n A gi i=1 ∈ C vektorok lineárisan függetlenek, ha αi ∈ 0, 1 esetén k X

αi gi = 0

i=1

csak αi = 0 esetén teljesük minden i ∈ {1, . . . , k}-ra.  5. Deníció. A gi ni=1 ∈ C vektorok a C lineáris tér egy bázisát alkotják, ha lineárisan függetlenek, továbbá igaz az, hogy minden c ∈ C vektor el®állítható

c=

k X i=1 8

µi gi

alakban, ahol µi ∈ {0, 1} minden i ∈ {1, . . . , k}-ra. Az utóbbi denícióban a bázist alkotó vektorok függetlenségéb®l következik, hogy a kódszavak fenti típusú el®állítása egyértelm¶ is, ha ugyanis létezne két különböz® el®állítás valamely

c ∈ C -re,

tehát

c=

k X

µi gi

i=1 és

c=

k X

γi gi

i=1 ahol nem áll fenn

µi = γi

minden

i-re,

akkor a két egyenletet kivonva egymásból a null-

vektornak egy nem triviális el®állítását kapnánk a bázisvektorokkal, ami ellentmondana azok lineáris függetlenségének. Az egyenl®ség felírható mátrix alakban:

c = µG ahol

µ = (µ1 , . . . , µk ), G pedig a bázisvektorokból mint sorvektorokból álló mátrix. Az k -dimenziós és egy n-dimenziós vektort rendelünk össze lineáris

egyenlettel tehát egy

transzformációval, mégpedig kölcsönösen egyértelm¶ módon. Azt fogjuk mondani, hogy az µ üzenethez a c kódszó tartozik. A k -dimenziós µ vektorokkal 2k -féle üzenetet fejezhetünk

C

C

n-dimenziós vektorok, és n nem kisebb k -nál, hiszen k az n-dimenziós vektorok C alterének a dimenziószáma. A k = n esetnek nincs most jelent®sége, ha k kisebb, mint n, akkor viszont világos, hogy nem minden ki, s ezeket kódoljuk a

kóddal.

elemei azonban

vektort kell felhasználni kódszónak, vagyis kódunk redundáns lesz, s ezt a redundanciát tudjuk hibajavításra felhasználni. Az üzenetekhez a kódszavakat a rendeljük hozzá, vagyis a

C

alterét, a kódot

6. Deníció.

G

G

mátrix jelöli ki az

n-dimenziós

G

mátrix segítségével

vektortérnek a kódot jelent®

generálja.

A fenti tulajdonságú G mátrixot a C kód generátormátrixának nevezzük.

Vegyük észre, hogy ha nem tör®dünk azzal, hogy melyik kódszó melyik üzenethez tartozik, csak a kódszavak halmazát tekintjük, akkor

G

nem egyértelm¶, vagyis több mátrix is

generálhatja ugyan azt a kódszóhalmazt. A következ® deníció egy megfeleltetést deniál az üzenetek és a kódszavak között.

7. Deníció.

Egy (n, k) paraméter¶ lineáris kód szisztematikus, ha minden kódszavára igaz, hogy annak utolsó n − k szimbólumát elhagyva éppen a neki megfelel® k hosszúságú üzenetet kapjuk, más szavakkal a k hosszú üzenetet egészítjük ki n − k karakterrel. Már leszögeztük, hogy dekódolás alatt csak az esetleges hibák kijavítását értjük, aminek eredményeképp egy kódszót kapunk. Az üzenetvektor visszanyeréséhez még el kell ugyan végezni a kódolás inverz m¶veletét, ez azonban rendszerint triviális lépés, szisztematikus

9

kód esetén például csak el kell hagyni a kódszó egy részét (a végét). Szisztematikus kód esetén a generátormátrix is egyértelm¶, mégpedig


G = Ik B Ik

alakú, ahol

a

k × k méret¶ egységmátrix, B c kódszó szerkezete tehát:

pedig

k × (n − k)

méret¶ mátrix. Az

µ

üzenethez tartozó

c = (µ1 , . . . , µk , ck+1 , ck+2 , . . . , cn ) A

c els® k koordinátájából álló szegmensét üzenetszegmensnek, az utolsó n−k koordinátá-

jából álló paritásszegmensnek nevezzük. A lineáris kódok további tulajdonságai elvezetnek az ígért egyszer¶ hibadetektáláshoz illetve hibajavításhoz.

8. Deníció.

Ha egy n − k sorból és n oszlopból álló H mátrixra

HcT = 0 akkor és csak akkor, ha c ∈ C , akkor H -t a C kód paritásellen®rz® mátrixának nevezzük.

H

segítségével tehát meg tudjuk állapítani, hogy egy vett szó valóban kódszó-e.

2. Tétel.

Legyen G a C lineáris kód generátormátrixa, H a C lineáris kód paritásellen®rz® mátrixa. Ekkor HGT = 0. Bizonyítás. Jelölje

hoz létezik

c ∈ C,

Qk

a

k hosszú bináris sorozatok halmazát. Ekkor minden µ ∈ Qk -

amire

c = µG Ugyanakkor

c∈C

miatt

HcT = 0 azaz


T HcT = H µG = HGT µT = 0

Az utóbbi egyenl®ség csak úgy állhat fent minden

µ ∈ Qk -ra,

ha

HGT = 0. Ez pedig pontosan a tétel állítása. Az el®z® tétel alapján szisztematikus generátormátrix felhasználásával könnyen el®állíthatjuk a kód egy paritásellen®rz® mátrixát. Keressük

H -t


H = A In−k alakban. A tétel állítása alapján


h
iT HGT = A In−k Ik B = A + B T = 0. 10

Azaz

A = −B T kell teljesüljön.

Binális esetben B T = −B T

A következ®kben a súly fogalmát deniálom, majd megmutatom, hogy lineáris kódoknál a minimális súly a kódtávolsággal egyenl®.

9. Deníció.

Legyen c = (c1 , . . . , cn ) ∈ C . A c ∈ C vektor súlya  ω(c) = i : ci 6= 0, i = 1, . . . , n ,

vagyis a c ∈ C vektor súlya a koordinátái között lév® nem nulla elemek száma.

10. Deníció.

Egy C kód minimális súlyán az

ωmin = min ω(c), c∈C

3. Tétel.

ahol

c 6= 0.

Ha C lineáris kód, akkor a kódtávolsága megegyezik a minimális súlyával.

dmin = ωmin Bizonyítás.

dmin = min0 d(c, c0 ) = min0 ω(c − c0 ) = min ω(c00 ) = ωmin , 00 c6=c

c 6=0

c6=c

ahol az utolsó el®tti egyenl®ség felírásakor a C kód linearitását használtuk ki, ebb®l kö00 0 vetkezik ugyanis, hogy c = c − c is kódszó, továbbá az is, hogy minden kódszó el®áll ilyen különbség alakjában. (Utóbbi ahhoz szükséges, hogy a minimum képzésekor valóban 00 minden c ∈ C -t gyelembe vehessünk.) A tétel jelent®sége abban áll, hogy segítségével a

dmin

deníció alapján történ® kiszá-

mításához szükséges

m¶veletet az

ωmin

kiszámításához

|C|(|C| − 1) 2 szükséges |C| − 1

m¶veletre redukáljuk.

2.2. Szindróma dekódolás A

H

paritásellen®rz® mátrix hasznosnak bizonyul dekódolás során.

11. Deníció.

Legyen c az adott kódszó, v a vett szó. Jelölje ε = c − v a hibavektort. Ekkor a σ mennyiséget szindrómának nevezzük, ahol

σ = εH T .

11

1. Megjegyzés.

A Hv T értéke csak a hibavektortól függ, a kódszótól nem, ugyanis

Hv T = H(c + ε)T = HcT + HεT = HεT . A szindróma tehát a hibavektor egy lineáris leképzése. A dekódolás leggyakoribb módja a szindróma dekódolás. A fentiek alapján a dekóT T T dolás a következ®képpen mehet végbe: a vett v szóból kiszámítjuk a σ = Hv = Hε szinndrómát, ennek alapján megbecsüljük a hibavektort, és ezt

v -b®l

levonva megkapjuk

a kódszóra vonatkozó becslésünket. A szindrómának hibamintára történ® leképzési módját táblázatba szokás foglalni, az un. standard elrendezési táblázatba.

ε + c, c ∈ C(n, k) vektorok halmaza. Adott mellékosztály elemeihez azonos szindróma tartozik. Az ε = 0 zérus hibavek0 torhoz tartozó mellékosztály a C(n, k) kóddal azonos.Ha egy ε hibaminta ε = ε + c alakba 0 írható fel, akkor a két hibaminta (ε és ε ) azonos mellékosztályt generál. Azonos mellékValamely

ε

hibaminta által generált mellékosztály az

osztályba tartozó hibaminták közül válasszuk ki a legkisebb súlyút, s azt mellékosztályvezet®nek nevezzük. Ennek megfelel®en a standard elrendezési táblázat az alábbi struktúrájú:

Mellékosztályvezet® Szindróma z}|{ z }| { σ (0) σ (1)

ε(0) = 0 ε(1)

. . .

. . .

σ (2 Az

n−k

n−k −1)

ε|(2 {z −1)}

c(1) c(1) + ε(1) . . . (2n−k −1)

c|(1) + ε{z

k −1)

c(2

··· ··· ..

c(2

k −1)

. . .

.

··· |{z}

+ ε(1)

k −1)

c|(2

+{zε(2

n−k −1)

Mellékosztály elemek Mellékosztály elemek Mellékosztály elemek Mellékosztály elemek }



ω ε(i+1) ≥ ω ε(i) , ε(0) = 0, i = 0, 1, . . . , 2n−k − 2

2. Megjegyzés.

}

a szokásos sorrend.

A fenti táblázat elemei különböz®ek.

Bizonyítás. Egy soron belül ez nyilvánvaló. Különböz® sorokat tekintve tegyük fel,

hogy

ε(i) + c(j) = ε(k) + c(l)

ahol

i > k.

Ebb®l

ε(i) = ε(k) + c(l) − c(j) = ε(k) + c(n) következik, ahol

c(l) , c(j) , c(n) ∈ C(n, k), ezért ε(i) -nek is az ε(k) mellékosztályvezet®j¶ sorba

kell lennie, ami ellentmondás kiindulási feltételünknek. (i) n−k Az ε , i = 1, . . . , 2 − 1 mellékosztályvezet®ket javítható hibamintáknak nevezzük, (i) ugyanis ha a v vett szó szindrómája σ , akkor a c ¯ = v − ε(i) kódszóra döntünk. A szindróma dekódolásnak ezt az  els®sorban elvi  módját táblázatos dekódolásnak nevezzük. (Megjegyzem, hogy a fenti dekódolási módszer nembináris ábécé esetére történ® n−k n−k kiterjesztésekor 2 helyett q áll.) n−k A szindrómát használó táblázatos dekódoló tárja a vizsgált bináris esetben 2 darab hibavektort tartalmaz, és a táblázat elemeit a szindróma segítségével címezzük. Következésképpen a táblázatos módszer a gyakorlatban addig használható, amíg gyorselérés¶ tárunk mérete lehet®vé teszi a javítható hibaminták tárolását.

12

2.2.1. A binális Hamming-kód Illusztrációként egy klasszikusnak számító kódot mutatok be, mely bináris Hammingkód néven ismeretes. A konstrukció az alábbi tételen alapul:

4. Tétel. C lineáris kód kódtávolsága legalább ∆ akkor és csak akkor, ha a paritásellen®rz®

mátrixa tetsz®legesen választott ∆ − 1 oszlopa lineárisan független. A fenti tétel alapján 1-hibát javító bináris kódot kapunk, ha

H

tetsz®leges két oszlopa

lineárisan független, azaz oszlopai különböz®k. Mivel a különböz®, nemzérus n − k hosszú n−k bináris vektorok száma 2 − 1, ezért ezen vektorokat használva a H mátrix különböz® oszlopaiként, az

n = 2n−k − 1 összefüggésre jutunk, ami azt is jelenti, hogy a kapott kód perfekt tulajdonságú. Ennek alapján bináris Hamming-kód paraméterei az alábbi számpárok (dmin

n k 3 1 7 4 15 11 31 26 63 57 127 120

13

= 3):

3. fejezet Véges test Q kódábécé vezetünk be Q-n. A

Hatékony hibajavító kódok konstrukciójához szükséges, hogy a nembináris strukturált legyen, mely például úgy lehetséges, hogy m¶veleteket fejezet elkészítésekor felhasznált szakirodalom: [1], [2], [3], [4], [5]

12. Deníció.

Egy Q halmazt testnek nevezünk, ha értelmezve van tetsz®leges két elem között két m¶velet, amelyeket összeadásnak illetve szorzásnak nevezünk, + illetve ∗ szimbólumokkal jelölünk, és Q rendelkezik a következ® tulajdonságokkal: 1. Q az összeadásra nézve kommutatív csoport.  Minden α, β ∈ Q estén α + β ∈ Q, tehát Q az összeadásra nézve zárt.  Minden α, β , γ ∈ Q esetén α + (β + γ) = (α + β) + γ , vagyis az összeadás asszociatív.  Létezik a Q-nak az összeadásra nézve neutrális eleme, 0 ∈ Q, melyre minden α ∈ Q-ra α + 0 = 0 + α = α. Ezt a neutrális elemet nullelemnek nevezzük.  Minden α ∈ Q elemhez létezik β ∈ Q, hogy α + β = 0. Ezt a β elemet az α additív inverzének nevezzük, és −α-val jelöljük.  Minden α, β ∈ Q estén α + β = β + α (kommutativitás). 2. Q \ {0} a szorzásra nézve kommutatív csoport.  Minden α, β ∈ Q \ {0} estén α ∗ β ∈ Q, tehát Q a szorzásra nézve zárt.  Minden α, β , γ ∈ Q \ {0} esetén α ∗ (β ∗ γ) = (α ∗ β) ∗ γ , vagyis az szorzás asszociatív.  Létezik a Q \ {0}-nak a szorzásra nézve neutrális eleme, 1 ∈ Q \ {0}, melyre minden α ∈ Q \ {0}-ra α ∗ 1 = 1 ∗ α = α. Ezt a neutrális elemet egységelemnek nevezzük.  Minden α ∈ Q \ {0} elemhez létezik β ∈ Q \ {0}, hogy α ∗ β = 1. Ezt a β elemet az α multiplikatív inverzének nevezzük, és α−1 -zel jelöljük.  Minden α, β ∈ Q \ {0} estén α ∗ β = β ∗ α (kommutativitás). 14

3. Minden α, β , γ ∈ Q esetén α ∗ 0 = 0 ∗ α = 0 és α ∗ (β + γ) = (α ∗ β) + (α ∗ γ) (disztributivitás). Egyszer¶ konvenciókkal egy Q testben deniálható a kivonás és az osztás a következ® módon: α − β alatt az α-nak és β additív inverzének összegét értjük, azaz α + (−β)t. αβ alatt α-nak és β multiplikatív inverzének a szorzatát értjük, azaz α ∗ β −1 -t értjük, amennyiben β 6= 0. Test példálul a valós számok halmaza a valós összeadással és szorzással, a racionális számok halmaza a valós összeadással és szorzással, a komplex számok halmaza a komplex összeadással és szorzással és a

{0, 1}

halmaz a

(mod 2)

összeadással és szorzássa.

13. Deníció.

Legyen q ∈ N, Q test, melyre |Q| = q < ∞. Ekkor Q-t véges testnek nevezzük és GF(q)-val jelöljük. Miel®tt a véges testek aritmetikáját tárgyalnám, néhány a továbbiakban felhasznált fontos tulajdonságukat ismertetem.

5. Tétel. GF(q) prímhatvány.

1. Lemma.

esetén q = pm alakú, ahol p prímszám, tehát q vagy prímszám, vagy

Minden 0 6= α ∈ GF(q)-ra

αq−1 = 1

2. Lemma. Minden 0 6= α ∈ GF(q)-ra létezik egy legkisebb m ∈ N (ezt az m számot az α elem rendjének nevezzük és o(α)-val jelöljük), melyre αm = 1 m=0

(mod q − 1),

és minden i 6= j esetén (i = 1, . . . , m, j = 1, . . . , m)

αi 6= αj .

14. Deníció.

Egy α ∈ GF(q)-t a GF(q) primitív elemének nevezzük, ha

o(α) = q − 1.

6. Tétel.

Minden GF(q)-ban létezik primitív elem.

15

3.1. Aritmetika

GF(p)-ben

7. Tétel.

A G = {0, 1, . . . , p − 1} halmaz a (mod p) aritmetikával egy p prímszám esetén véges test, azaz a testm¶veletek

a + b := a + b

(mod p),

a ∗ b := a ∗ b

(mod p),

ahol + és ∗ jelöli a valós összeadást illetve szorzást. A primitív elem egyrészt igen fontos hatékony kódok konstrukciójakor, másrész beli szorzások és osztások elvégzésekor. Ha hetjük egy

a ∈ GF(q)

testelem

α

α

a

GF(q)

GF(q)-

egy primitív eleme, akkor bevezet-

alapú logaritmusát az

αloga = a egyenlet (egyértelm¶) megoldásával, ahol

a 6= 0.

Ha

a, b ∈ GF(q)

nemnulla elemei, akkor

a ∗ b = αloga ∗ αlogb = αloga+logb , tehát egy

α

alapú logaritmustábla és egy inverzlogaritmus-tábla segítségével a szorzás

(illetve az osztás) visszavezethet® valós összeadásra (illetve kivonásra). A következ®kben nagyon hasznosnak bizonyulnak a

GF(q)

feletti polinomok, így töb-

bek között egy fontos kódcsalád (a ciklikus kódok) leírásában, illetve a prímhatvány méret¶ véges testek aritmetikája generálásakor fogom használni ®ket.

3.2. Véges test feletti polinomok GF(q)

feletti vektorok reprezentálására, és vektorok közötti szorzás kényelmes beve-

zetésére egy célszer¶ eszköz a polinomreprezentáció:

15. Deníció.

Az α(x) GF(q) feletti m-ed fokú polinom, ha

α(x) =

m X

αi xi

i=0

αi ∈ GF(q)

i ∈ {0, . . . , m} am 6= 0

x ∈ GF(q) A fenti α(x) degα(x) = −∞.

polinom

m

fokszámát

degα(x)

16

jelöli. Deníció szerint

α(x) = 0,

akkor

16. Deníció. α(x) = β(x) akkor és csak akkor, ha αi = βi

17. Deníció.

i ∈ {0, . . . , m}-re

minden

M¶veletek polinomok között:

 Polinomok összeadása: γ(x) = α(x) + β(x) tagonként történik GF(q) feletti m¶veletekkel. γi = αi + βi .

degγ(x) ≤ max{degα(x), degβ(x)}  Polinomok szorzása: γ(x) = α(x)β(x) minden tagot minden taggal szorzunk, majd az azonos fokú tagokat csoportosítjuk (az összeadások és szorzások GF(q) felettiek). min{i,degα(x)}

X

γi =

aj bi−j

j=0

degγ(x) = degα(x) + degβ(x)

8. Tétel (Euklidészi osztás polinomokra).

Adott α(x) és δ(x) 6= 0 polinomok esetén egyértelm¶en létezik olyan q(x), r(x) polinomok, melyekre

α(x) = q(x)δ(x) + r(x), és degr(x) < degδ(x).

18. Deníció. r(x)-et az α(x)-nek δ(x)-re vonatkozó maradékának nevezzük. r(x) = α(x)

19. Deníció.

mod δ(x)




A δ(x) polinom osztja az α(x) polinomot, ha
α(x) = 0 mod δ(x) .

Ezt δ(x)|α(x) jelöli.

20. Deníció.

Egy ξ ∈ GF(q) gyöke az α(x) polinomnak, ha

α(ξ) = 0

9. Tétel.

Ha ξ ∈ GF(q) gyöke az α(x) polinomnak, akkor α(x) el®áll

α(x) = β(x)(x − ξ) alakban.

10. Tétel.

Legyen α(x) k -adfokú polinom, azaz

α(x) =

k X

α i xi

αk 6= 0.

i=0

Ekkor

|{ξ ∈ GF(q) : α(ξ) = 0}| ≤ k 17

3.3. Aritmetika

GF(pm)-ben

Lényeges különbség van a prím illetve a prímhatvány méret¶ testek aritmetikája között. Prím méret¶ testben a modulo aritmetika megfelelt. Prímhatvány méret esetén sajnos a modulo aritmetika nem teljesíti a testaxiómákat, például egy

2∗2=0

4

elem¶ halmazban

(mod 4),

tehát két nemnulla elem szorzata 0 lenne, ami axiómát sért. A

GF(pm )

feletti aritmetika

konstrukciója azért alapvet® fontosságú, mert manapság a hibajavító kódokat tömegesen 8 alkalmazzák számítástechnikai környezetben, ahol a természetes ábécé a GF(2 ), vagyis a bájt.

GF(pm )-beli elemek legyenek 0, . . . , pm − 1 számok, melyeknek m hosszú vektorokat feleltetünk meg, ahol a koordináták GF(p)-beliek. Ezt megfogalmazhatjuk például úgy is, m m hogy a 0, . . . , p − 1 számokat p alapú számrendszerben írjuk fel. Ezek után a GF(p )beli aritmetikát m hosszú vektorok közötti m¶veletekkel deniáljuk. A két m¶velet közül az összeadás az egyszer¶bb: két vektor összegén a koordinátánkénti GF(p)-beli összeget értjük, vagyis a koordinátánkénti mod(p) összeget. A szorzás egy kicsit bonyolultabb. A két m hosszú vektort legfeljebb m − 1-ed fokú polinom formájában reprezentáljuk, és összeszorozzuk. Az eredmény fokszáma meghaladhatja m − 1-et, ezért itt egy speciális A

polinom szerinti maradékot képzünk. Ezt a speciális polinomot irreducíbilis polinomnak nevezzük, és ez a polinom ugyanolyan szerepet játszik, mint a prímszám a

GF(p)-beli

aritmetikában.

21. Deníció.

A GF(p) feletti, nem nulladfokú P (x) polinomot irreducibilis polinomnak nevezzük, ha nem bontható fel két, nála alacsonyabb fokú GF(p) feletti polinom szorzatára, azaz nincs GF(p) feletti α1 (x), α2 (x) polinom, melyekre

P (x) = α1 (x)α2 (x) és



0 < deg αi (x) < deg P (x)

i ∈ {1, 2}.

3. Megjegyzés.

Minden véges testben található tetsz®leges fokszámú irreducibilis polinom. Példát mutatok arra, hogy hogyan lehet GF(2) feletti irreducibilis polinomokat generálni. A denícióból következik, hogy minden els®fokú polinom (x és x + 1) irreducibilis. Ha találunk olyan másodfokú polinomot, mely különbözik az x2 , az x(x + 1) és az (x + 1)2 mindegyikét®l, akkor találtunk irreducibilis másodfokú polinomot. Egy ilyen van:

x2 + x + 1 Más testben és nagyobb fokszámok esetén ennél hatékonyabb konstrukciókat érdemes használni, de bináris esetben így is találhatók irreducibilis polinomok, amelyeket táblázatban foglalok össze:

18

Fokszám

2 3 4 5 6 7 8 9

Irreducibilis polinom 2

x +x+1 x3 + x + 1 x4 + x + 1 x5 + x2 + 1 x6 + x + 1 x7 + x3 + 1 8 x + x4 + x3 + x2 + 1 x9 + x4 + 1

11. Tétel.

Legyen p egy prím, m egy természetes szám, P (x) egy GF(p) feletti m-edfokú, irreducibilis polinom, és Q = {0, . . . , pm − 1}. Egy α ∈ Q és β ∈ Q elemeknek kölcsönösen egyértelm¶en feleltessük meg GF(p) feletti, legfeljebb (m − 1)-edfokú α(x) és β(x) polinomokat. α + β deníció szerint az a γ ∈ Q, melynek megfelel® γ(x) polinomra

γ(x) = α(x) + β(x). α ∗ β deníció szerint az a δ ∈ Q, melynek megfelel® δ(x) polinomra
δ(x) = α(x)β(x) mod P (x) . Ezzel az aritmetikával Q egy GF(pm ).

19

4. fejezet Nembináris lineáris kód Ebben a szakaszban a kódok egy fontos csoportjával ismerkedek meg, melyek a már megismert bináris lineáris kódok kiterjesztései nembináris esetre. A továbbiakban a kódjainkban szerepl® kódszavakat alkotó szimbólumokat vegyük

GF(q)-ból, a lehetséges szimbólumok tehát a {0, . . . , q − 1} számoknak feleltethet®k meg. A fejezet elkészítésekor felhasznált szakirodalom: [1], [2], [3], [4], [5]

22. Deníció. c0 ∈ C esetén

Egy C kód lineáris, ha C halmaz lineáris tér GF(q) fölött, azaz minden c,

c + c0 ∈ C ,

illetve µ ∈ GF(q) esetén

µc ∈ C . Itt is hasonló módon belátható, hogy tetsz®leges árisan független sorból és

n

oszlopból álló

G

C

lineáris kódhoz létezik egy

k

line-

mátrix, melyre

c = uG, ahol a

k

hosszú

u

üzenethez a

c

kódszó tartozik, és a

G

mátrixot a

C

kód generátormát-

rixának nevezzük. A bináris esethez hasonlóan a

H

C

lineáris kódhoz egy

n−k

sorból és

n

oszlopból álló

mátrixot paritásellen®rz® mátrixnak nevezzük, amennyiben

HcT = 0 akkor és csak akkor teljesül, ha

c ∈ C.

A bináris eset másolataként kapjuk, hogy

12. Tétel.

Minden lineáris C kódnak létezik paritásellen®rz® mátrixa.

Példaként bemutatom a nembináris Hamming-kódot. Ismét 1-hibát javító kódot konstruálok. A bináris esetben a hiba javításához elég volt ismerni a hiba helyét, amihez elégséges volt, ha a

H

paritásellen®rz® mátrix minden oszlopa különböz®. Nembináris esetben

20

nem csak a hiba helyét, hanem a hiba értékét is meg kell állapítani, ezért a

0-k,

oszlopait úgy választom, hogy azok nem

H

mátrix

mind különböz®k legyenek, és az els® nem

0

elem miden oszlopban 1 érték¶ legyen. Ekkor, ha egy hiba az i-edik helyen fordul el® és T értéke εi , akkor a szindróma σ = εi hi , ahol hi a H i-dik oszlopa. Tehát a hiba értéke, εi éppen a szindróma els® nem 0 értéke, míg

σ , εi

hi = amib®l az Ha

H

i

visszakereshet®.

tartalmazza az összes lehetséges, a fenti módon megengedett oszlopvektort,

akkor

n=

q n−k − 1 , q−1

azaz

1 + n(q − 1) = q n−k , másrészt a Hamming-korlát miatt

1 + n(q − 1) ≤ q n−k , tehát

13. Tétel.

A maximális hosszúságú nembináris Hamming-kód perfekt kód.

A nembináris Hamming-kódok közül különösen érdekes az az eset, amikor a kód szisztematikus és a paritásszegmens hossza 0 elem, melynek rendje

m ≥ 2.

2,

n − k = 2. Legyen α ∈ GF(q) egy nem n ≤ (m + 2)-t és k = (n − 2)-t. Ekkor a

azaz

Válasszunk

paritásellen®rz® mátrix:

 H= Ez egy

(n, n − 2)

1 1 1 ... 1 1 0 2 n−3 1 α α ... α 0 1



paraméter¶ nembináris Hamming-kód paritásmátrixa.

A 10. oldal 2. tétele alapján meghatározhatjuk a

    G=  

. . .

. . .

..

.

0 0 0 ... Mivel ez a kód 1-hibát tud javítani, ezért

lineáris kód generátormátrixát.

 0 −1 −1 0 −1 −α   0 −1 −α2    . . . . . .  . . . n−3 1 −1 α

1 0 0 ... 0 1 0 ... 0 0 1 ... . . .

C

dmin ≥ 3,

de a Singleton-korlát miatt

dmin ≤ n − k + 1 = 3, ezért

14. Tétel.

Az (n, n − 2) paraméter¶ nembináris Hamming-kód MDS kód. 21

4.1. Lineáris kódok kib®vítése és ekvivalenciája

23. Deníció.

A GF(q) test feletti, n hosszú C lineáris kód kib®vítettje a C¯ kód, ha

 C¯ = (c, cn+1 ) : c = (c1 , . . . , cn ) ∈ C

és

n+1 X

ci = 0 (mod q)



i=1

1. Következmény.

Ha a {0, 1} ábécé feletti C bináris lineáris kódra dmin = k páratlan, akkor a kib®vített C¯ kódra a kódtávolság k + 1.

24. Deníció.

A C lineáris kód permutáció-ekvivalens (vagy ekvivlens) a C 0 lineáris kóddal, ha létezik egy olyan P permutáció-mátrix, melyre c ∈ C akkor, és csak akkor, ha:

cP ∈ C 0

4.2. Reed-Solomon kód Ebben a szakaszban a lineáris kódok egyik leggyakrabban használt osztályát, a ReedSolomon kódokat, azok különböz® konstrukcióit mutatom be.

1. Konstrukció.

 n−1 Legyenek αi i=0 ∈ GF(q) különböz® elemei (n ≤ q), és u = (u0 , u1 , . . . , uk−1 )

ui ∈ GF(q)

a k hosszúságú üzenetszegmens, amelyhez az

u(x) =

k−1 X

ui xi

i=0

üzenetpolinomot rendeljük. Ekkor a Reed-Solomon kódnak az

u

üzenethez tartozó

n

hosszú

c

kódszavát a következ®

módon állítjuk el®:

ci = u(αi )

i ∈ {0, . . . , n − 1}

c = (c0 , c1 , . . . , cn−1 ) A konstrukcióból látható, hogy a Reed-Solomon kód lineáris, és a következ®.



1 1 1 ... 1  α0 α1 α2 . . . αn−k  G =  .. . . . .. . . .  . . . . . k−1 k−1 k−1 k−1 α2 . . . αn−k α0 α1

15. Tétel.

G

    

Az (n, k) paraméterü Reed-Solomon kód MDS kód, melyre

dmin = n − k + 1. 22

generátormátrixa

Bizonyítás.

  ω(c) = i : ci 6= 0, i = 1, . . . , n = n − i : ci = 0, i = 1, . . . , n ≥  ≥ n − λ ∈ GF(q) : u(λ) = 0 ≥ n − (k − 1), tehát

ωmin ≥ n − k + 1. Ugyanakkor a 6. oldal 1. tételét, illetve a 11. oldal 3. tételét felhasználva

n − k + 1 ≥ dmin = ωmin . Az

(n, k)

paraméter¶ Reed-Solomon kód tehát

n−k

hibát tud jelezni,

jn − k k 2 egyszer¶ hibát javítani, és

n−k

törléses hibát javítani. Ez utóbbi azt jelenti, hogy az

u

ismeretére vonatkozó

uG = c n

darab egyenletb®l bármelyik

egyenletrendszer marad, tehát

n − k egyenlet elhagyásával egy egyértelm¶en megoldható G mátrix minden k × k -s négyzetes részmátrixa invertál-

ható.

2. Konstrukció. rukcióban legyen

Legyen α(6= 0) ∈ GF(q), melynek rendje m (m ≥ n), és az 1. konst-

αi = αi

Ekkor a generátormátrix: 

   G=  

1 1 1 .. .

1 α α2 .. .

i ∈ {0, . . . , n − 1}.

1 α2 α4 .. .

... ... ... .. .

1 αk−1 α2(k−1) . . .

23

1



αn−1 α2(n−1) .. .

     

α(k−1)(n−1)

5. fejezet Ciklikus kódok A fejezet elkészítésekor felhasznált szakirodalom: [1], [2], [3], [4], [5]

25. Deníció.

Egy c = (c0 , c1 , . . . , cn−1 ) vektor ciklikus eltoltja a

Σc = (cn−1 , c0 , . . . , cn−2 ). Σ-t a ciklus eltolási operátorának nevezzük.

26. Deníció.

szó.

A C kódot ciklikusnak nevezzük, ha bármely kódszó ciklikus eltoltja is kód-

A ciklikus eltolás operátorát kényelmesebben tudjuk kezelni, ha a kódszavakat mint vektorokat a már megszokott polinomos formában reprezentáljuk.

27. Deníció.

Rendeljünk polinomot az egyes kódszavakhoz a következ® módon:

c = (c0 , c1 , . . . , cn−1 ) 7→ c(x) =

n−1 X

ci x i

i=0

Ekkor a c kódszónak megfeleltetett c(x) polinomot kódszópolinomnak nevezzük. A kódszópolinomok halmazát jelölje C[x].

3. Lemma.

Legyen c0 (x) a c kódszó Σc eltoltjához rendelt kódszópolinom. Ekkor

c0 (x) = xc(x)

(mod xn − 1)

16. Tétel.

Minden (n, k) paraméter¶, ciklikus, lineáris C kódban a nem azonosan nulla kódszópolinomok között egyértelm¶en létezik egy minimális fokszámú g(x) normált polinom. A g(x) polinom fokszáma n − k , és egy c ∈ C akkor és csak akkor, ha g(x)|c(x), azaz létezik egy u(x) polinom úgy, hogy

c(x) = u(x)g(x). 24

28. Deníció. 17. Tétel.

A fenti g(x)-et a kód generátorpolinomjának nevezzük.

Minden ciklikus, lineáris kód g(x) generátorpolinomjára

g(x)|xn − 1. Valamint, ha egy g(x) polinomra g(x)|xn −1, akkor létezik egy lineáris ciklikus kód, melynek g(x) a generátorpolinomja. A paritásellen®rz® mátrixnak is van polinomos megfelel®je:

29. Deníció.

Egy g(x) generátorpolinomú lineáris, ciklikus kód esetén a

h(x) =

xn − 1 g(x)

polinomot paritásellen®rz® polinomnak nevezzük.

18. Tétel.

Egy lineáris, ciklikus kódra c(x) akkor és csak akkor kódszópolinom, ha

(mod xn − 1)

c(x)h(x) = 0 és

degc(x) ≤ n − 1.

5.1. Ciklikus kódok szisztematikus generálása A ciklikus kódok el®nyös tulajdonságai egyrészt a generálási lehet®ségek sokféleségében, másrészt egyszer¶ dekódolási eljárásokban jelentkeznek. Egy lineáris ciklikus kódot lehet például a generátorpolinom és az üzenetpolinom szorzásával generálni. Ez a módszer megfogalmazható egy olyan úgy juthatunk el, ha

G



G

sorai a

g0 g1 g2  0 g0 g1   G =  ... ... ...   0 0 0 0 0 0 kihasználva, hogy

g(x)

generátormátrix segítségével is, amelyhez legegyszer¶bben

g(x)-nek ... ... ..

.

... ...

polinom, így

megfelel® vektor eltoltjai:

gn−k−1 1 gn−k−2 gn−k−1

0 1

. . .

. . .

. . .

g0 0

g1 g0

g2 g1

... ... ··· ... ...

0 0 . . .

1 gn−k−1

gn−k = 1.

Egy másik generálási módszer kapcsán azt is megmutatom, hogy

19. Tétel.

Minden lineáris ciklikus kód generálható szisztematikusan.

25

 0 0   .  .  .  0  1

Bizonyítás. Vegyük észre, hogy

egy

g -nél

g0 6= 0,

mert ha

0

lenne, akkor a

g -t

egyel kisebb fokszámú kódszópolinomot kapnánk, ami lehetetlen.

balra eltolva

g0 6= 0

miatt

viszont a Gauss-eliminációt balról jobbra végrehajtva szisztematikus generátormátrixot kapunk. A szisztematikus generálás egy praktikus módszere a következ®: Legyen feljebb

(k − 1)-edfokú

üzenetpolinom,

p(x)

u(x)

egy leg-

a paritás részt.

c(x) = u(x)xn−k + p(x)
c(x) kódszópolinomnak oszthatónak kell lennie g(x)-szel, így c(x) = 0 mod g(x) .

Tekintettel arra, hogy deg p(x) ≤ n − k − 1, és deg g(x) = n − k , így
mod g(x) p(x) = u(x)xn−k

Mivel a

Ezen generálás szisztematikus: a

c(x)-et

deniáló egyenl®ség jobb oldalának els® tagja

adja az üzenetszegmenst, míg a második tagja a paritásszegmenst.

5.2. Ciklikus Reed-Solomon kód A Reed-Solomon kód legfontosabb gyakorlati el®állítási módja a 20. tételen alapszik.

20. Tétel.

A Reed-Solomon kódok esetén legyen a kódszó n hossza egyenl® az ott szerepl® α elem m rendjével. Ekkor a kód ciklikus, és generátorpolinomja

g(x) =

n−k Y

(x − αi ),

i=1

továbbá paritásellen®rz® polinomja

h(x) =

n Y

(x − αi ),

i=n−k+1

tehát a nem rövidített Reed-Solomon kód ciklikus.

21. Tétel.

A 20. tétel Reed-Solomon kódjának  1 α α2  1 α2 α4  H =  .. .. ..  . . . n−k 2(n−k) 1 α α

26

paritásellen®rz® mátrixa:  ... αn−1 ... α2(n−1)    .. ..  . . (n−1)(n−k) ... α

6. fejezet A Golay-kódok A fejezet elkészítésekor felhasznált szakirodalom: [2], [6], [7], [8], [9], [10]

6.1. Blokkrendszerek

30. Deníció.

Legyen |H| = v , H ⊆ 2H , melyre minden B ∈ H esetén |B| = k , továbbá H minden t elem¶ részhalmazát H-nak pontosan λ eleme tartalmazza. Ekkor a (H, H) halmazrendszer t − (v, k, λ)-blokkrendszer. H elemeit blokkoknak, H elemeit pontoknak nevezzük

4. Lemma.

Legyen C egy 0-t tartalmazó e-hibajavító bináris perfekt kód. Továbbá legyen (H, H) halmazrendszer, melyre H elemei a koordináta-pozíciók, H ⊆ 2H elemei a minimális súlyú kódszavak tartói. Ekkor a (H, H) halmazrendszer (e + 1) − (n, 2e + 1, 1)blokkrendszer. Bizonyítás Tudjuk, hogy

B∈H

blokknak, ha a

minden

B∈H

B -hez

|H| = n.

Egy

h ∈ H

legyen eleme pontosan akkor egy

tartozó kódszóban az adott helyen

1

érték szerepel. Ekkor

blokkra igaz, hogy

|B| = 2e + 1. Legyen

¯ ⊆ H, H

melyre

szóhoz egyértelm¶en létezik

¯ = e + 1. Ez |H| olyan h kódszó a

a

¯ H

egy

e+1

súlyú szó. Minden ilyen

¯ H

perfektség miatt, melyre

¯ h) ≤ e. d(H, Mivel

e-nél

közelebb csak

2e + 1

súlyú szavak vannak, melyek nem kódszavak, így

¯ h) = e d(H, teljesül. Azokon a helyeken, ahol az tartozó

2e + 1

súlyú kódszóban is

a súlya, azaz bármely

e+1

e+1

1-nek

súlyú szóban

1

érték szerepel, ott a hozzá

kell szerepelnie, ellenkez® esetben kisebb lenne

koordináta-pozícióhoz létezik egyértelm¶en egy blokk, mely

tartalmazza.

27

4. Megjegyzés.

Tetsz®leges t − (v, k, λ) blokrendszerre teljesül, hogy
v

|H| =

1. Állítás.

t
λ. k t

Egyértelm¶en létezik a 2 − (11, 5, 2) blokkrendszer.

Bizonyítás. Az állításban szerepl® létezésre bizonyíték a Paley-féle konstrukció.

3. Konstrukció (Paley-féle konstrukció).

Legyen H = {k ∈ Z : 0 ≤ k ≤ 10}. Legyen S = {0, 1, 3, 4, 5, 9} ⊂ H a kvadratikus maradékok, valamint H = {S + i|i ∈ H}. Ekkor (H, H) 2 − (11, 5, 2) blokkrendszer. Az egyértelm¶ség bizonyításához el®ször vezessük be a következ® jelölést:

Si = S + i

i∈H

Tekintsük minden halmaz komplementerét, melyet jelöljön rendre kapott

S

halmazrendszer minden

|S¯i | = 5

S¯i ∈ S

és minden

S¯i = H \ Si .

Az így

elemére:

i 6= j

esetén

|S¯i ∩ S¯j | = 2 S¯j ∈ S

s1 , s2 pontok, melyeket három halmaz is tartalmaz, {s1 , s2 } ∈ S¯l ∩ S¯m ∩ S¯n . Az tudjuk, hogy bármely két halmaz metszete két elem¶, ¯l \ {s1 , s2 }, S¯m \ {s1 , s2 }, S¯n \ {s1 , s2 } halmazok páronként diszjunktak, és mivel így S |S¯l | = |S¯m | = |S¯n | = 5, így |S¯l ∪ S¯m ∪ S¯n | = 11. Most tekintsünk egy eddigiekt®l különböz® S¯j halmazt, és S¯j ∩ {s1 , s2 } elemszámát. 1. eset |S¯j ∩ {s1 , s2 }| = 0, ekkor |S¯j | = 6. 2. eset |S¯j ∩ {s1 , s2 }| = 1, ekkor |S¯j | = 4. 3. eset |S¯j ∩ {s1 , s2 }| = 2, ekkor |S¯j | = 2. Mind a három eset ellentmondás, ami azt jelenti, hogy bármely {s1 , s2 } pontpárt Most tegyük fel, hogy léteznek az

vagyis

legfeljebb két halmaz tartalmaz. Most számoljuk meg az

11 · 5 · 4, legfeljebb

{(s1 , s2 , S¯i ) : s1 6= s2 ∈ S¯i }

halmaz elemszámát. Ez egyrészt

mert 11 halmazból 5, illetve 4 féleképpen választhatok ki

s1 -t

és

s2 -t.

Másrészt

11·5·4, mert tetsz®leges két pontot legfeljebb két halmaz tartalmaz. Összegezve

a kapott eredményeket, tetsz®leges két pontot pontosan kett® halmaz tartalmaz. Most deniáljunk hat darab gráfot a következ® módon (Hussain-gráf ): minden

S¯1

S¯1 -en

s ∈ /

(v1 , v2 ) ∈ Es él, abban az esetben, ha (v1 , v2 )-re illeszked®, különböz® halmaz átmegy s-en. Azt az el®bb 0 láttuk, hogy bármely két pontra pontosan két halmaz illeszkedik, így különböz® s és s 0 ¯1 -gyel, esetén a Gs (Vs , Es ) ∩ Gs0 (Vs0 , Es0 ) az {s, s }-re illeszked® két halmaz metszete S ¯1 két szomszédja vagyis |Es ∩ Es0 | = 2. Továbbá vegyük észre, hogy tetsz®leges v1 ∈ S ¯ Gs (Vs , Es ) gráfban az s-re és v1 -re illeszked® két halmaz metszete S1 -gyel, így Gs (Vs , Es ) esetén deniáljuk a

Gs (Vs , Es )

gráfot

S¯1 -t®l

úgy, hogy a

gráf minden pontjának foka 2. Az így deniált gráfokból egyértelm¶en visszavezethet®ek a halmazok, ugyanis egy

{v1 , v2 } ∈ S¯1

meghatározza a

{v1 , v2 , s1 , s2 , s3 } 28

halmazt, ahol

(v1 , v2 ) ∈ Gsi (Vsi , Esi ),

i ∈ {1, 2, 3}.

Minegyik gráf 5 csúcsának a foka 2, vagyis a gráf nem más, mint egy 5

hosszú kör. Legyen

Gs1 (Vs1 , Es1 )

az a gráf, melyre:

Vs1 = {1, 2, 3, 4, 5} Es1 = {(1, 2), (2, 3), (3, 4), (4, 5), (5, 1)} Mindegyik gráf ezekb®l pontosan két élt tartalmaz, de ezek nem lehetnek szomszédosak, mert akkor tartalmaznia kellene a szomszédos élekkel szemközti éleket is, ami nem lehetséges, tehát csak két nem szomszédos élt tartalmazhatnak, ami egyértelm¶en meghatározzák a többi gráfot. Konkrétan a hat gráf az

{(1, 3), (3, 2), (2, 5), (5, 4), (4, 1)}

gráf és

ennek elforgatottjai. Ezzel beláttuk, hogy a Hussain-gráfok rendszere egyértelm¶, amib®l következik a blokkrendszer egyértelm¶sége.

2. Következmény.

Mivel egy 2 − (11, 5, 2) blokkrendszer komplementere (H, {H \ B : B ∈ H}) 2 − (11, 6, 3) blokkrendszer, és fordítva, így ez is egyértelm¶.

5. Megjegyzés.

Ha H ⊂ 2H egy t − (v, k, λ) blokkrendszer, és A ⊂ H , |A| = a ≤ t, akkor (H \ A, {B \ A : B ∈ H, A ⊂ B}) egy (t − a) − (v − a, k − a, λ) blokkrendszer.

6.2. A bináris Golay-kód C , {0, 1} ábécé feletti, 24 hosszú, 212 elem¶, 8 kódtávolságú lineáris kó(24, 212 , 8)2 paraméter¶ lineáris kódot). Próbáljuk el®állítani C egy "szép"

Tekintsük a dot (röviden a

bázisát a következ® módon: Legyen

c1 ∈ C

tetsz®leges kódszó, melyre

ω(c1 ) = 12. Tegyük fel, hogy a

c1 ∈ C

kódszó koordinátái úgy vannak permutálva, hogy

(s)

s ∈ S = {2, . . . , 13}

c1 = 0 és

(k)

k ∈ K \ S,

c1 = 1 ahol

K = {1, . . . , 24}.

Tekintsük minden

ci ∈ C

ci ∈ C

kódszó

S

koordináta-halmazra vetítettjét, vagyis minden

kódszó esetén a

(m)

ci számot. Az így kapott kód

12

m∈S

hosszú, és bármely

c ∈ C

kódszóra

c és c + c1 vetítettje 0 szót kapjuk, akkor tehát csak 0, vagy 12

ugyanaz, másnak viszont nem lehet ugyanez a vetítettje, ha ugyanis a az eredeti

c

nem lehet

súlyú, mert akkor

0 vagy c1 maga. c¯m ∈ C¯ kódszóra

súlyú lehet, vagyis Bármely

8

c + c1

4 súlyú szó lenne,

Tehát az így kapott

2|ω(¯ cm ), 29

C¯ kód 11

dimenziós.

mert minden szó súlya eredetileg is páros volt, és

hc, c1 i = 0

minden

c ∈ C

esetén. A

[12, 11, 2] paraméter¶ és minden páros súlyú szót tartalmaz. Most válasszuk c2 , . . . , c12 kódszavakat úgy, hogy a ci i-edik és 13-dik helyen 1 érték áll, vetítettje többi helyén 0. Mivel ci helyett ci + c-t is vehetjük, ezért feltehetjük, hogy a c2 , . . . , c12 kódszavak els® koordinátája 0. Az így kapott 12 vektor C bázisa, mert lineárisan függetlenek az els® 12 koordináta miatt. Most tekintsük c2 , . . . , c12 kódszavak utolsó 11 koordinátáját. Ezt a 11 vektort jelölje a2 , . . . , a12 . Mivel ω(ci ) ≥ 8, így

kapott kód

ω(ai ) = 6 Ha

vagy

ω(ai ) = 10.

ω(ai ) = 10 valamely i ∈ {2, . . . , 12} esetén, akkor ω(c1 +ci ) = 4, ami ellentmondás,

vagyis:

ω(ai ) = 6

i ∈ {2, . . . , 12}

Jelölje

 (l) (l) supp(ai ) = ai : ai = 1|l ∈ {2, . . . , 12} x = |supp(ai ) ∩ supp(aj )| Ekkor

ω(ci + cj ) = 2 + (6 − x) + (6 − x) = 14 − 2x így

x=1

vagy

x=3

x = 1 lenne, akkor ω(c + ci + cj ) = 4 lenne, így x = 3 a helyes megoldás, vagyis supp(ai ) halmazok mindegyike egy 11 elem¶ halmaz 6 elem¶ részhalmaza, és bármely kett® metszete 3 elem¶. A fentieket felhasználva megalkothatjuk C egy bázisát: Ha

31. Deníció.

Legyen I12 ∈ {0, 1}12×12 egység-mátrix, A ∈ {0, 1}12×12 .   0 1 1 1 1 1 1 1 1 1 1 1  1 1 1 0 1 1 1 0 0 0 1 0     1 1 0 1 1 1 0 0 0 1 0 1     1 0 1 1 1 0 0 0 1 0 1 1     1 1 1 1 0 0 0 1 0 1 1 0     1 1 1 0 0 0 1 0 1 1 0 1  T  A=  1 1 0 0 0 1 0 1 1 0 1 1  A =A    1 0 0 0 1 0 1 1 0 1 1 1     1 0 0 1 0 1 1 0 1 1 1 0     1 0 1 0 1 1 0 1 1 1 0 0     1 1 0 1 1 0 1 1 1 0 0 0  1 0 1 1 0 1 1 1 0 0 0 1
Ekkor a G = I12 |A ∈ {0, 1}12×24 mátrix által generált bináris, lineáris kód a kib®vített Golay-kód, melyet G24 jelöl. 30

A 33. denícióból következik, hogy a

2. Állítás.

G24

kód hossza

24,

és

dim(G24 ) = 12.

A kib®vített G24 Golay-kód paritásellen®rz®-mátrixa
H = A|I12 ∈ {0, 1}12×24

Bizonyítás. A 2. tételt felhasználva adódik az állítás.

32. Deníció. ha

Az x = (x1 , . . . , xn ) és y = (y1 , . . . , yn ) bináris kódszavak ortogonálisak,

hx, yi =

n X

xi y i = 0

(mod 2)

i=1

5. Lemma.

Legyen x és y bináris kódszó, melyre 4|ω(x) és 4|ω(y). Ekkor 4|ω(x+y) akkor és csak akkor, ha x és y ortogonálisak. Bizonyítás. Legyen

c = |supp(x) ∩ supp(y)|.

Ekkor

ω(x + y) = ω(x) + ω(y) − 2c és

hx, yi = c Mindkét állítás páros

3. Állítás.

c

(mod 2)

esetén teljesül.

A kib®vített G24 Golay-kód önortogonális. ⊥ G24 = G24

Bizonyítás. Legyen

G24

kód generátor-mátrixának tetsz®leges két sora

gi

és

gj .

A

fejezet elején leírt konstrukcióból adódik, hogy

4|ω(gi )

vagyis teljesülnek az 5. lemma feltételei, azaz

|supp(gi ) ∩ supp(gj )|

érték páros,

G24

4|ω(gj ),

és

G

bármely két sora ortogonális, vagyis

kód lineáris,

|G24 | = 212 . Ezzel beláttuk, hogy Azt láttuk, hogy

⊥ G24 ⊆ G24 . dim(G24 ) = 12,

így

⊥ ) = 24 − dim(G24 ) = 24 − 12 = 12, dim(G24 vagyis

⊥ G24 = G24 .

3. Következmény. G24

paritásellen®rz®-mátrixa


H 0 = I12 |A 31

4. Következmény. G24

generátor-mátrixa

G0 = A|I12

4. Állítás.




Legyen c ∈ G24 tetsz®leges kódszó. Ekkor:

4|ω(c) Bizonyítás. Egy

c ∈ G24

kódszóról tudjuk, hogy az a

G24

kód

G

generátor-mátrix

sorainak egy lineáris kombinációja.

1. eset:

c ∈ G24 kódszó a G generátor-mátrix egy súlya 8 vagy 12, így triviálisan teljesül, hogy

Legyen

mátrix sorainak

sora. Mivel a

G

generátor-

4|ω(c). 2. eset: Most legyen gi és gj a G generátor-mátrix két tetsz®leges sora, és tegyük fel, hogy c = gi + gj . Ekkor azt kell megmutatni, hogy 4|ω(gi + gj ). Tudjuk, hogy G generátormátrix sorainak súlya 4 töbszöröse, valamint bármely két sora ortogonális egymásra, így alkalmazható az 5. lemma, azaz:

4|ω(c) Innen indukcióval adódik az állítás.

5. Állítás.

A kib®vített G24 Golay-kódra:

dmin = 8 Bizonyítás. A 4. állítás alapjána a kib®vített G24 Golay-kódra dmin = 4 vagy dmin = 8. Most tekintsük G24 egy nemnulla v kódszavát, melyre ω(v) = 4. Írjuk fel v ∈ G24 kódszót (v1 , v2 ) alakban, ahol a v1 12-dimenziós vektor v els® 12 koordinátája, a v2 12-dimenziós vektor v utolsó 12 koordinátája. Ekkor a következ® esetekfordulhatnak el®: 1. eset: ω(v1 ) = 0 és ω(v2 ) = 4. Ez az eset nem fordulhat el®, mert ha megnézzük a G24 kód G generátor-mátrixát, az egyetlen 0 súlyú szó a 0. 2. eset: ω(v1 ) = 1 és ω(v2 ) = 3. Ebben az esetben v kódszó a G generátor-mátrix egy

sora kell, hogy legyen, ami ismét ellentmondás.

3. eset: ω(v1 ) = 2

és

ω(v2 ) = 2.

Ekkor

v

kódszó a

G

generátor-mátrix két különböz®

sorának összege. Könnyen látható, hogy semelyik két sor összegére nem fordulhat el®,

ω(v2 ) = 2, mert az ilyen sorok súlya 8 vagy 12.
4. eset: ω(v1 ) = 3 és ω(v2 ) = 1. Jelölje G0 = A|I12 ∈ {0, 1}24×12 mátrixot, ami 0 szintén generátormátrix. Ebben az esetben v kódszó a G generátor-mátrix egy sora, így itt a 2. eset fordul el®. 5. eset: ω(v1 ) = 4 és ω(v2 ) = 0. Ez az eset megegyezik az 1. eset -tel, mikor a kód 0 generátor-mátrixa a G . A fent leírt 5 eset mindegyikében ellentmondásra jutottunk, így a dmin = 4 eset nem lehetséges, vagyis szükségképp dmin = 8. hogy

Az el®bb megmutattam, hogy k j a kib®vített

alapján egyszer¶ hibázás esetén

dmin −1 2

G24

Golay-kódra

dmin = 8.

Az 1.1. képlet

hiba javítható. Elvégezve a helyettesítést kapjuk,

hogy

32

6. Állítás.

A kib®vített G24 Golay-kód 3-hibajavító kód.

33. Deníció.

Legyen I12 ∈ {0, 1}12×12 egység-mátrix, A¯ ∈ {0, 1}12×11 .   0 1 1 1 1 1 1 1 1 1 1  1 1 1 0 1 1 1 0 0 0 1     1 1 0 1 1 1 0 0 0 1 0     1 0 1 1 1 0 0 0 1 0 1     1 1 1 1 0 0 0 1 0 1 1     1 1 1 0 0 0 1 0 1 1 0   A¯ =   1 1 0 0 0 1 0 1 1 0 1     1 0 0 0 1 0 1 1 0 1 1     1 0 0 1 0 1 1 0 1 1 1     1 0 1 0 1 1 0 1 1 1 0     1 1 0 1 1 0 1 1 1 0 0  1 0 1 1 0 1 1 1 0 0 0
¯ = I12 |A¯ ∈ {0, 1}12×23 mátrix által generált kód a bináris Golay-kód, melyet Ekkor a G G23 jelöl.

6. Megjegyzés.

A bináris G23 Golay-kód 23 hosszú, 12 dimenziós és paritásellen®rz® ¯ ∈ {0, 1}12×23 mátrixa H
¯ = A¯T |I11 H

7. Megjegyzés. Golay-kód.

A bináris G23 Golay-kód kib®vítettje egy paritásbittel a kib®vített G24

5. Következmény.

A bináris G23 Golay-kódra:

dmin = 7 Ebb®l látható, hogy a bináris

G23

Golay-kód szintén 3-hibajavító kód az 1.1. képletbe

helyettesítve.

22. Tétel.

A G23 3-hibajavító bináris kód perfekt.

Bizonyítás. A

GF(2)

test feletti

(23, 212 , 7)2 3-hibajavító

következ®:

12

2

3   X n i=0

i

kódra a Hamming-korlát a

≤ 223

Az egyenl®tlenség bal oldalát kiírva láthatjuk, hogy az egynl®séggel teljesül, vagyis a kód eléri a Hamming-korlátot, így perfekt.

     23 23 2 1 + 23 + + = 223 2 3 12

33

23. Tétel.

A kib®vített G24 Golay-kód egyértelm¶.

8. Megjegyzés.

Az egyértelm¶ség úgy értend®, hogy bármely (24, 212 , 8)2 paraméter¶ bináris, lineáris kód permutáció-ekvivalens a kib®vített G24 Golay-kóddal. Bizonyítás. A fejezetben eddig leírtakat gyelembe véve már csak azt kell megmutat-

nunk, hogy a

G24 G

generátor-mátrixában szerepl®

A

mátrixból képzett

A0 ∈ {0, 1}11×11

mátrix, melyet az els® sor és az els® oszlop elhagyásával kapunk, permutáció erejéig egyértelm¶.

         0 A =        

1 1 0 1 1 1 0 0 0 1 0

1 0 1 1 1 0 0 0 1 0 1

0 1 1 1 0 0 0 1 0 1 1

Az 5. állításban már láttuk, hogy

1 1 1 0 0 0 1 0 1 1 0

1 1 0 0 0 1 0 1 1 0 1

1 0 0 0 1 0 1 1 0 1 1

dmin = 8,

0 0 0 1 0 1 1 0 1 1 1

0 0 1 0 1 1 0 1 1 1 0

0 1 0 1 1 0 1 1 1 0 0

1 0 1 1 0 1 1 1 0 0 0

emiatt

A0

0 1 1 0 1 1 1 0 0 0 1

                 

minden sorában legalább 6

darab 1-es áll. Ellenben 6-nál több nem lehet, mert a súlyok 4 többszörösei, így ebben az esetben 10 darab 1-nek kell állnia, és egy ilyen sort az els®höz adva 4 súlyú kódszót kapnánk. A fejezet elején leírt konstrukcióban már láttuk, hogy

A0

bármely két sorában "közös

egyeseinek" száma 3, vagyis:

|supp(ai ) ∩ supp(aj )| = 3, azaz

A0

sorainak mindegyike egy

metszete

3

11

elem¶ halmaz 6 elem¶ részhalmaza, és bármely kett® A0 egy 2 − (11, 6, 3) blokkrendszer illeszkedési

elem¶. Ezzel beláttuk, hogy

mátrixa, mely a 6.1. következmény alapján a

2 − (11, 5, 2)

blokkrendszer komplementere,

így létezik, és permutáció erejéig egyértelm¶.

6.2.1.

G24

el®állítása az ikozaéder adjacenciamátrixa segítségével

N ∈ {0, 1}12×12 mátrix az ikozaéder csúcsaiból és éleib®l alkotott gráf (6.1. ábra) 12×12 12×12 adjacenciamátrixát, továbbá tekintsük az E ∈ {1} , illetve I12 ∈ {0, 1} mátrixokat. Állítsuk el® a kib®vített G24 Golay-kód generátor-mátrixát ezen mátrixok segítségével. Jelölje

24. Tétel.

A kib®vített G24 Golay-kód G ∈ {0, 1}12×24 generátor-mátrixa felírható a következ® alakban:
G = I12 |E − N

34

6.1. ábra. Az ikozaéder csúcsaiból és éleib®l alkotott gráf

Bizonyítás. Tegyük fel, hogy a


G = I12 |E − N ∈ {0, 1}12×24

mátrix a

C

bináris

kódot generálja. Az ikozaéder minden pontjának pontosan 5, nem átellenes pontjainak 2 közös szomszédja van, átellenes pontok esetén pedig nem létezik közös szomszéd, vagyis a

G

mátrix

minden sorában pontosan 8 darab egyes szerepel, és bármely két sora mer®leges egymásra, azaz bármely két, a sorok által generált kód is mer®leges egymásra. Tekintsük

c1 , c2 ∈ C

c1 , és c2 a G 4|ω(c1 ) és 4|ω(c2 ),

kódszavakat. Mivel

lineáris kombinációjaként jön létre, így

generátor-mátrix sorainak egy vagyis

4|ω(c1 + c2 ),

|supp(c1 + c2 )| = |supp(c1 )| + |supp(c2 )| − 2|supp(c1 ) ∩ supp(c2 )| 2|supp(c1 ) ∩ supp(c2 )|

C bármely két kódszava mer®leges egymásra. dim(C) = 12, hiszem a G generátor-mátrix els® 12 oszlopa lineárisan független, vagyis C önadjungált. Az önadjungáltság, illetve E − N szimetrikussága, valamint, hogy GF(2) feletti valgyunk, a C kódszó egy másik generátor-mátrixa
¯ = E − N |I12 . G Annak bizonyítása, hogy a C kódszóban a minimális súly 8, megegyezik az 5. állításban bemutatott bizonyítással egy c = (a, b) ∈ C kódszóra, melyr®l itt is feltételezzük, hogy ω(c) = 4. Az ellentmondások kizárásával láthatjuk, hogy C kód minimális súlya 8, és mivel a Golay-kód egyértelm¶, így a fent deniált G mátrix valóan a G24 kódot generálja. páros, mert

Az világos, hogy a

A bizonyításban láttuk, hogy a kib®vített esetén az

k.

tranzitív az

G = I12 |E − N




és

¯ = E − N |I12 G




mátrixok szintén

G24 Golay-kódot generálják, ami azt jelenti, hogy minden k ∈ {1, . . . , 12} (k + 12). koordináta felcserélhet®. Az ikozaéder automorzmus csoportja összes csúcson, ami azt jelenti, hogy a kib®vített G24 Golay-kód automor-

és

zmus csoportja is tranzitív a koordinátákon, vagyis a kód tetsz®leges elemét elhagyva

G24 Golay-kód a kib®vített G24 Golay-kód

G23

permutáció-ekvivalens kódokat kapunk. Mivel a kib®vített

bináris

Golay-kód kib®vítettje egy paritásbittel, így ha a

egyértelm¶

(ezt már ismerjük), akkor a bináris

6. Következmény. 9. Megjegyzés.

G23

Golay-kód is, így kimondhatjuk, hogy

A perfekt G23 Golay-kód egyértelm¶.

Az egyértelm¶ség itt is a koordináták permutációinak erejéig értend®.

35

6.2.2. A mohó módon el®állított

G24

 224 ci i=1 ∈ {0, 1}24 vektorok sorozatát, melyr®l tegyük fel, hogy lexirendezve, így c1 a csupa nulla 24-hosszú vektor, c224 a csupa egyesekb®l

Most tekintsük a kograkusan van

álló 24-hosszú vektor. Ekkor jelölje

C (1) = c1 (i) (i) kódot. A következ®kben b®víts®k C -t olyan módon, hogy C -hez hozzá veszünk a lexi 224 kograkusan rendezett ci ∈ {0, 1}24 sorozat legkisebb olyan index¶ elemet, mely C (i) i=1 minden tagjától legalább 8 távolságra van. Ekkor

C (2) = C (1) ∪ c9 , ahol

c9

az a vektor, aminek az els® 16 koordinátájban nulla szerepel, az utolsó 8 helyen

pedig egyes. Az

k.

lépésben

C (k) = C (k−1) ∪ cl , ahol

cl ∈ {0, 1}24 a legkisebb olyan szó, melyre cl > C (k−1) \C (k−2) , és minden cj ∈ C (k−1) -re: d(cj , cl ) ≥ 8

A

212 .

lépés után vezessük be a következ® jelölést: 12 )

C = C (2

7. Állítás.

A fenti módon deniált bináris C kód egyenl® a kib®vített G24 Golay-kóddal.

6.3. A ternáris Golay-kód B ∈ {−1, 0, 1}6×6 mátrixot a kövezkez® módon:   0 1 1 1 1 1  1 0 1 −1 −1 1     1 1 0 1 −1 −1    BT = B (6.1) B=  1 −1 1 0 1 −1    1 −1 −1 1 0 1  1 1 −1 −1 1 0
34. Deníció. A G = I6 |B ∈ {−1, 0, 1}6×12 mátrix által generált háromelem¶ test feletti lineáris kód a kib®vített ternáris Golay-kód, melyet G12 jelöl, ahol I6 a 6 × 6 méret¶ egységmátrix. A ternáris Golay-kód bevezetéséhez deniáljuk a

8. Állítás.

A kib®vített G12 ternáris Golay-kód paritásellen®rz®-mátrixa
H = B|I6 ∈ {−1, 0, 1}6×12

Bizonyítás. A 2. tételt felhasználva adódik az állítás.

36

9. Állítás.

A kib®vített G12 ternáris Golay-kód önortogonális. ⊥ G12 = G12

Bizonyítás. Vegyük a

G

generátor-mátrix tetsz®leges két sorát, majd a 6. lemmát

felhaszálva vizsgáljuk ezek skaláris szorzatát.

6. Lemma.

¯ ∈ {−1, 0, 1}5×5 az a mátrix (Paley-mátrix), melyet a 6.1 mátrix Legyen B els® sorának és oszlopának törlésével kapunk. Ekkor: ¯B ¯ T = 5I5 − E , B ahol E ∈ {1}5×5 mátrix. Az egyértelm¶en látszik, hogy

G

bármely sorának skaláris szorzata az els® sorával,

illetve azonos sorok skaláris szorzata nulla. Most tekintsük G tetsz®leges gi , gj sorát, T melyre i, j > 1, és i 6= j . Bontsuk a gi gj szorzatot a következ® tényez®k összegére:

(7) (7)

gi gjT = [gi gjT ]I6 + gi gj + [gi gjT ]B¯ , ahol sor,

(7)

[gi gjT ]I6 a gi és gj sorok I6 -ra vetített koordinátáinak skaláris szorzata, gi a gi (7) ¯ -ra vetített gj a gj sor hetedik koordinátája, valamint [gi gjT ]B¯ a gi és gj sorok B

koordinátáinak skaláris szorzata. Ekkor bármely két sor esetén:

[gi gjT ]I6 = 0 (7) (7)

gi gj = 1 [gi gjT ]B¯ = −1, ⊥ bármely két sorának skaláris szorzata nulla, vagyis G12 ⊆ G12 . ⊥ ⊥ Az egyenl®ség belátásához vegyük észre, hogy dim(G12 ) = dim(G12 ), így G12 = G12 .

így beláttuk, hogy

G

7. Következmény. G12

paritásellen®rz®-mátrixa

H 0 = I6 |B

8. Következmény. G12




generátor-mátrixa

G0 = − B|I6

10. Állítás.

(6.2)




Minden c ∈ G12 kódszó esetén

3|ω(c). Bizonyítás. Vegyük észre, hogy egy

szorzata megegyezik a

c

c ∈ G12

kódszó esetén

c

önmagával vett skaláris

kódszó súlyával. A 9. állítás alapján a kib®vített

Golay-kód önortogonális, és mivel a

c ∈ G12

ternáris

c ∈ G12 kódszó a G generátor-mátrix sorainak egy c kódszó önmagával vett skaláris szorzata is

lineáris kombinációjaként jön létre, így a nulla, vagyis tetsz®leges

G12

kódszó súlya osztható hárommal.

37

11. Állítás.

A kib®vített G12 ternáris Golay-kódra:

dmin = 6 Bizonyítás. Tegyük fel, hogy létezik olyan c ∈ G12 kódszó, melyre ω(c) = 3. Mivel c = (c1 , . . . , c12 ) kódszó a G generátor-mátrix sorainak egy lineáris kombinációja, így létezik i ∈ {1, . . . , 6}, melyre ci 6= 0. Pontosan egy ilyen nemnulla elem nem lehet, mert akkor c a G generátor-mátrix egy sora, és G sorairól láttuk, hogy közöttük nincs 3 súlyú

a

sor.

c

Most tegyük fel, hogy a

j ∈ {1, . . . , 6}), hogy ci és cj

kódszó olyan, melyre létezik pontosan kett®

nemnulla. Egy ilyen

i 6= j (i

és

c kódszót szorozva a 6.2 paritásellen®rz®c a kib®vített

mátrixal, egy nemnulla koordinátát kapnánk, ami ellent mond annak, hogy

G12

ternáris Golay-kód egy szava. A fentiek alapján látszik, hogy ha létezik olyan

akkor az a

G

c ∈ G12

kódszó, melyre

generátor-mátrix három sorának egy nemtriviális lineáris kombinációjaként

állítható el®. Számítással ellen®rizhet®, hogy a

G

generátor-mátrix tetsz®leges három so-

rának nem létezik olyan nemtriviális lineáris kombinációja, melyre a vetítettje nem tartalmaz nemnulla elemet, így Mivel a kib®vített illetve egy

ω(c) = 3,

c ∈ G12

G12

c kódszó B

mátrixra

ω(c) > 3.

ternáris Golay-kód bármely szavának súlya osztható hárommal,

kódszó súlya legalább 4, így

egyenl®séget, keressünk a kib®vített

G12 G

súlya pontosan 6. Ilyen létezik, mert a

dmin ≥ 6.

Ahhoz, hogy belássuk az

ternáris Golay-kód egy olyan szavát, melynek generátor-mátrix

g1

els® sorára teljesül, hogy

ω(g1 ) = 6, így a kib®vített

G12

9. Következmény.

ternáris Golay-kódra

dmin = 6.

A kib®vített G12 ternáris Golay-kód 2-hibajavító kód.

35. Deníció.

Legyen B 0 ∈ {−1,
0, 1}6×5 a 6.1 mátrix els® oszlopának törlésével kelet¯ = I6 |B 0 ∈ {−1, 0, 1}6×11 generátor-mátrix által generál kód a kezett mátrix. Ekkor a G G11 ternális Golay-kód.

12. Állítás.

A G11 ternális Golay-kódra

dmin = 5 Bizonyítás. Mivel a

G11

ternális Golay-kód generátor-mátrixa a kib®vített

náris Golay-kód generátor-mátrixában szerepl® létre, így

B

dmin = 5.

10. Következmény. 13. Állítás.

A G11 ternáris Golay-kód 2-hibajavító kód.

A 2-hibajavító G11 ternáris Golay-kód perfekt.

38

G12

ter-

mátrix els® oszlopának törlésével jön

G11 ternáris Golay-kód 11 hosszú, 6 dimenziós lineáris = 5, azaz [11, 6, 5]3 paraméter¶ kód. A kód paramétereit az 1.2. képletbe

Bizonyítás. A 2-hibajavító

kód, melyre

dmin

helyettesítve kapjuk, hogy a kód eléri a Hamming-korlátot.

2   X 11 i 2 ≤ 35 i i=0

      11 11 11 + 2+ 4 = 35 0 1 2 A fejezet zárásaként kimondok egy tételt a ternáris Golay-kódok egyértelm¶ségér®l, melynek bizonyítása túl mutat jelen szakdolgozat tartalmán, így azt bizonyítás nélkül közlöm.

25. Tétel.

telm¶.

A perfekt G11 ternáris Golay-kód és a kib®vített G12 ternáris Golay-kód egyér-

10. Megjegyzés.

Az egyértelm¶ség itt is a koordináták permutációinak erejéig értend®.

39

Irodalomjegyzék [1] Shu Lin/Daniel J. Costello, Jr.,

tions,

Error Controll Coding: Fundamentals and Applica-

Prentice-Hall, Inc. Englewood Clis, New Jersey 07632, 1983.

[2] Kiss Emil,

Bevezetés az algebrába,

[3] Wettl Ferenc,

Typotex Kiadó, Budapest, 2007.

Kódelmélet és kriptográa,

2011.

[4] Maróti Miklós,

Hibajavító kódolás egyetemi el®adásjegyzete,

[5] Ivanyos Gábor,

Matemetikai kriptográa és kódelmélet egyetemi el®adásjegyzete

[6] Vrana Péter,

Golay-kódok jegyzete

[7] Csikvári Péter,

Golay-kód és Witt-design egyetemi jegyzete,

[8] J. C. Bowman,

Coding Theory and Cryptography,

[9] R. Hill,

2008.

A First Course in Coding Theory,

[10] S. Ling, C. Xing,

online jegyzetek, 2015.

Oxford University Press, 1988.

Coding Theory: A First Course, Cambridge University Press, 2004.