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

5. Hamming-kódok

5. Hamming-kódok

A 4.6. Tétel után természetes ötlet, hogy perfekt kódokat próbáljunk szerkeszteni. Részletesen mi a Q = 2 , e = 1 esetet vizsgáljuk. A Hamming korlátból ebben az esetben azt kapjuk, hogy n + 1 osztója kell legyen 2 n -nek. Ez azt jelenti, hogy csak n = 2 r - 1 esetén van esélyünk 1-hibajavító perfekt kódot szerkeszteni. Q elemei legyenek 0 és 1, amelyekkel modulo 2 számolunk.

Készítsünk el egy r × ( 2 r - 1 ) -es H mátrixot! A mátrix i -edik oszlopa legyen az i szám kettes számrendszerbeli alakja. Az r = 3 esetben például

H = 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1 .

Tetszőleges r esetén formálisan i = ? j = 1 r h j i 2 r - j . H -t egy homogén lineáris egyenletrendszer mátrixának tekintjük, és C -t az egyenletrendszer megoldásaként definiáljuk. Az egyenletek száma r , az ismeretleneké n = 2 r - 1 , tehát a megoldások a Q elemeiből álló n = 2 r - 1 hosszú vektorok. Azaz x i ? { 0 , 1 } és

C = ( x 1 , , x n ) : x i = 0 , 1 , ? j = 1 n h i j x j = 0 , i = 1 , , r .

(2)

Ezt a kódot (bináris) Hamming-kódnak nevezzük, és Ham ( r ) -rel jelöljük. Például Ham ( 3 ) kódszavai azok az ( x 1 , x 2 , x 3 , x 4 , x 5 , x 6 , x 7 ) vektorok, amelyekre

0 · x 1 + 0 · x 2 + 0 · x 3 + 1 · x 4 + 1 · x 5 + 1 · x 6 + 1 · x 7 = 0 . 0 · x 1 + 1 · x 2 + 1 · x 3 + 0 · x 4 + 0 · x 5 + 1 · x 6 + 1 · x 7 = 0 , 1 · x 1 + 0 · x 2 + 1 · x 3 + 0 · x 4 + 1 · x 5 + 0 · x 6 + 1 · x 7 = 0 ,

Az egyenleteket át is rendezhetjük:

x 1 = x 3 + x 5 + x 7 , x 2 = x 3 + x 6 + x 7 , x 4 = x 5 + x 6 + x 7 .

10. feladat. Mutassuk meg, hogy a 4.4 Példa vektorai épp az itt megadott Ham ( 3 ) kód kódszavai!

5.1. Tétel. (Hamming) A (bináris) Hamming-kódok perfekt, 1-hibajavító kódok.

Bizonyítás. Először is azt kell kiszámolnunk, hogy mennyi Ham ( r ) , azaz a fenti (2) egyenletrendszernek hány megoldása van. Rögzítsük tetszőlegesen az olyan x j ismeretlenek értékét, amelyekre j ? 2 i (ez n - r ismeretlent jelent). Mivel H -nak a 2 i -edik oszlopa egyetlen egyest tartalmaz, x 1 , x 2 , x 4 , , x 2 i , , x 2 r - 1 , vagyis r ismeretlen egyértelműen meghatározható egyenleteinkből a többi ismeretében. Azokat viszont szabadon megválaszthatjuk, s ezért Ham ( r ) = 2 n - r , vagyis Ham ( r ) ( n + 1 ) = 2 n - r ( 2 r - 1 + 1 ) = 2 n , tehát a 4.6 Tételbeli becslésben tényleg egyenlőség van.

Még azt kell belátnunk, hogy Ham ( r ) 1-hibajavító. Ehhez azt kell megmutatnunk, hogy minimális távolsága legalább 3. Mivel a (2) egyenletrendszer homogén, két megoldásának koordinátánkénti különbsége és összege (ez modulo 2 ugyanaz) is megoldás. Ha lenne két olyan kódszó, amelyek távolsága 2 vagy 1, akkor lenne (2)-nek olyan megoldása, amely legfeljebb két koordinátában nem nulla. Ez viszont csak akkor lehetne, ha az ezen két koordinátának megfelelő két oszlopa H -nak azonos lenne, vagy valamely oszlop a nullvektor lenne, ami ellentmond a H mátrix konstrukciójának. ?

Lássuk a bináris Hamming-kódok esetére a kódolási és a dekódolási eljárást is!

A kódolás annyiból áll, hogy üzeneteinket valami módon megfeleltetjük Ham ( r ) elemeinek. Mivel Ham ( r ) = 2 n - r , ennyi üzenetet kódolhatunk Ham ( r ) segítségével. Ha ezeket ( n - r ) jegyű, kettes számrendszerben felírt számmal azonosítjuk, akkor ezt a megfeleltetést úgy csinálhatjuk, hogy a számjegyeket az x j ( j 2 i , i = 0 , , r - 1 ) helyekre írjuk, majd (2) felhasználásával kiszámoljuk az x 2 i ( i = 0 , 1 , , r - 1 ) koordinátákat. Tegyük fel, hogy az elküldött üzenet c ? Ham ( r ) , és ehelyett a fogadó az x ? { 0 , 1 } n -t kapja. Számítsuk ki, hogy x behelyettesítésével mit kapunk (2) jobboldalán (más szóval számítsuk ki a H x mátrix-szorzatot)! Ez azonos lesz H valamelyik oszlopával, és a hiba éppen abban a koordinátában történt, ahányadik oszlopot kaptuk. Valóban, írjuk fel x -et c + e alakban, ahol c ? Ham ( r ) , e pedig legfeljebb 1 egyest tartalmaz. Mivel c kódszó, így c -t beírva teljesül a (2) egyenletrendszer (azaz mátrixos alakban H c = 0 , ahol itt a 0 az r koordinátájú nullvektort jelenti). Az egyenletrendszer lineáris lévén, ( c + e ) -t behelyettesítve ugyanazt kapjuk, mintha e -t helyettesítenénk, hisz c megoldás. Ha az e -ben a j -edik koordinátában szerepel egyes, akkor az i -edik egyenletbe helyettesítve e -t x j együtthatóját, vagyis h i j -t kapjuk. A behelyettesítés eredménye tehát a H mátrix j -edik oszlopa lesz. (Mátrixok szorzását használva tehát H e pontosan annyiadik oszlopa lesz H -nak, ahányadik koordinátájában e -nek 1 áll). A konkrét esetben ez még ennél is egyszerűbb, hiszen ha a H j -edik oszlopát (azaz a behelyettesítés eredményét) kettes számrendszerbeli számnak tekintjük, akkor ez azonnal megadja a hiba helyét.

A Hamming-kód lényegét így foglalhatjuk össze a Ham ( 6 ) kód példáján: Ez a kód n = 2 6 - 1 = 63 hosszúságú 0 – 1 vektorokból áll. Hivatkozzunk a koordinátákra az 1, 2, , 63 számok kettes számrendszerbeli alakja szerint: x 000001 , x 000010 , , x 111111 . A koordinátáknak összesen 2 63 -féleképpen adhatunk értéket, de ezek közül nem mindegyik kódszó. A következőképpen dönthető el, egy szóról, hogy kódszó-e: Válasszuk ki azokat a koordinátákat, amelyeknek az értéke 1. Írjuk fel ezeknek a koordinátáknak az indexeit, és adjuk össze az indexek első jegyeit modulo 2, majd a második jegyeket is modulo 2, , végül a hatodik jegyeket is modulo 2. Ha mind a hat érték 0, akkor a vizsgált szó kódszó, ha van 1-es eredmény is, akkor nem kódszó. Ha egy kódszóban 1 koordináta megváltozott, akkor az indexösszegek ellenőrzésekor a hatból néhány esetben nem 0 lesz az eredmény. Ha pl. az 1., a 3., és a 6. jegynél kaptunk egyet, akkor az x 101001 koordináta értéke volt hibás.

Ham ( 6 ) segítségével megoldhatjuk a 7. feladatot is. A 4. fejezetben ismertetett képletekkel és módszerekkel kiszámolható, hogy legfeljebb 65 információ továbbítható, ez a korlát paritással kapcsolatos megfontolással 64-re csökkenthető. Alább Pósa Lajos konstrukcióját ismertetjük 64 információra, az ő megoldása inspirálta a Hamming-kód előbbi összefoglalását is.

A 64 információt az előzetes megbeszélésen a 000001, 000010, , 111111 kettes számrendszerbeli számoknak feleltetik meg. Ugyanakkor a tábla 63 mezőjét is megszámozzák ugyanezekkel a számokkal (a 64. mező fölösleges, nem veszik figyelembe). A kém úgy ügyeskedik, hogy a fekete mezők sorszámainak jegyenkénti összege (minden jegynél külön-külön modulo 2) az elküldendő üzenet sorszáma legyen. Ezt bármely kapott mintázat és bármely üzenet esetén el tudja érni. Tegyük fel pld, hogy a 001001, 101010, 111100 mezők feketék, és az 100001 üzenetet akarja elküldeni. A jegyenkénti összegek: 0 + 1 + 1 = 0 , 0 + 0 + 1 = 1 , 1 + 1 + 1 = 1 , 0 + 0 + 1 = 1 , 0 + 1 + 0 = 1 , 1 + 0 + 0 = 1 , tehát ha nem csinál semmit, akkor a 011111 sorszámú üzenet kerül adásba. Ha viszont a kém megváltoztatja az 111110 sorszámú mező állapotát, akkor a kívánt 100001 üzenetet fogják közvetíteni.

A Hamming-kódok konstrukciója jelentősen általánosítható. Ha nem modulo 2, hanem mondjuk modulo p számolunk, és Q = p lesz, akkor a H mátrix konstrukcióját módosíthatjuk. Az oszlopokba az 1 , , p r - 1 számok p alapú számrendszerbeli alakját írjuk, de az így felírt oszlopok között lesznek olyanok, amelyek egymás konstansszorosai. Az ilyenekből csak egyet írjunk le, mégpedig azt, amelynek első nem-nulla számjegye 1-es. Tehát ( 1 , 0 , , 0 ) , ( 2 , 0 , , , 0 ) , , ( p - 1 , 0 , , 0 ) közül csak az ( 1 , 0 , , 0 ) -t tartjuk meg. Mivel az első nem-nulla számjegy ( p - 1 ) -féle lehet, és ezek közül csak egyet veszünk tekintetbe, így ( p r - 1 ) / ( p - 1 ) oszlopot tartunk meg. (Aki már hallott véges projektív terekről az tudja, hogy ezek az oszlopok épp a modulo p test feletti ( r - 1 ) dimenziós projektív tér pontjainak felelnek meg.) A bináris esethez teljesen hasonlóan lehet a (2) egyenletrendszer módosításával definiálni a modulo p Hamming-kódot. Pontosabban n = ( p r - 1 ) / ( p - 1 ) -et kell írnunk, és az x i -k a 0 , 1 , , p - 1 értékeket vehetik fel. Annak bizonyítása is lemásolható, hogy ezek a Hamming-kódok 1-hibajavító perfekt kódok. A modulo 3 maradékosztályok, azaz { 0 , 1 , 2 } feletti, r = 3 -hoz tartozó Hamming-kódokkal még találkozunk a későbbiekben, de ezek egy korábbi problémánkkal is kapcsolatosak. Mutassuk meg, hogy a 4. b) feladatban 9 szelvény elegendő!