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

4. Hamming távolság, kódolás, hibajavítás

4. Hamming távolság, kódolás, hibajavítás

Lássuk, hogyan modellezhetjük az előbbiekben tárgyalt problémákat matematikailag. Legyen Q véges halmaz, melyet ábécének nevezünk. Az üzenetek Q elemeiből álló rögzített hosszúságú sorozatok lesznek. A korábban említett és a további alkalmazásokban Q = { 0 , 1 } , Q = { 0 , 1 , 2 } , Q = { 0 , 1 , 9 } , Q = { 0 , 1 , , 9 , X } , Q = 31 , Q = { ékezet nélküli betűk, írásjelek } fordul elő. Legyen n rögzített, és tekintsük a Q elemeiből alkotott n hosszú vektorokat, azaz a Q n = Q × Q × × Q n -tényezős Descartes-szorzatot. Két n hosszú sorozat (vektor), a és b Hamming távolsága azon koordinátáik száma, amelyek különböznek. Formálisan, ha a = ( a 1 , , a n ) , b = ( b 1 , , b n ) , akkor

d ( a , b ) = { i : a i b i } .

Ez a Hamming távolság bizonyos szempontból hasonlít a geometriai távolságra: szimmetrikus, továbbá d ( x , y ) = 0 csak akkor lehet, ha x = y , és teljesül a háromszög-egyenlőtlenség megfelelője is. Ezek belátását feladatnak hagyjuk. Az n hosszú sorozatokat szavaknak nevezzük. Gondoljunk az írásra! Egy szó és az esetleg sajtóhibával leírt szó eltéréseinek száma (azaz a sajtóhibák száma) éppen a két szó Hamming távolsága. A későbbiekben a szavakat is dőlt betűvel írjuk, nem kövérrel.

Célunk az lesz, hogy bizonyos szavakat kiválasszunk – ezek lesznek a kódszavak –, oly módon, hogy az lehetővé tegye néhány hiba javítását. Persze a hibajavításnak ára van, mint azt később konkrétan is látni fogjuk. Ahhoz, hogy hibát javíthassunk, hosszabb üzeneteket kell elküldjünk. Minél hosszabb üzeneteket küldünk, annál több hibát tudunk javítani, de annál több hiba is keletkezhet. A kódelmélet alapproblémája, hogy minél rövidebb kóddal minél több hibát javítsunk. Ezek egymásnak ellentmondó célok, így a kompromisszumot a konkrét feladatnak megfelelően kell megkeresni. (Ha például jó minőségű vonalon továbbítjuk az adatokat, és az adattovábbítás olcsó, akkor kevés hiba javítása is elég, mint a bevezetőben a számítógépek összekötése esetén. Máskor, mint a Mariner példájában, az adatok újraküldése lehetetlen, a csatorna pedig zajos, így itt a minél több hiba javítása a jó kompromisszum. Sokszor fordul elő az is, hogy ha hiba történik, akkor egyszerre sok egymásutáni hiba is, pl. megkarcoljuk a CD lemezt. Ilyenkor ún. hibacsomók fordulnak elő, olyan kódot érdemes választani, amely ezeket javítja jól.) Ha tehát kódolás alkalmazásakor a fogadó olyan szót vesz, amely nem kódszó, akkor a dekódolás során megkeresi a hozzá legközelebbi kódszót, és azt tekinti beérkezett üzenetnek. (Olvasáskor is ezt szoktuk csinálni, csak ott még a szövegkörnyezetet is figyelembe tudjuk venni: pl. hxz lehet hoz, húz, ház stb. Olvasásnál a kódszavak az értelmes szavaknak felelnek meg.) Az általános megközelítésben kódnak egy rögzített ABC betűivel leírt adott hosszúságú jelsorozatok tetszőleges halmazát értjük.

4.1. Definíció. Legyen C ? Q n . Ekkor C -t kódnak, Q n elemeit szavaknak, C elemeit pedig kódszavaknak nevezzük. Azt mondjuk, hogy a C kód e -hibajavító, ha bármely két v , w ? C , v w kódszó Hamming távolsága legalább 2 e + 1 . A C kód minimális távolsága d , ha

d = min { d ( c , c ' ) : c , c ' ? C , c c ' } .

Ez a definíció nem közvetlenül annak az intuitív ténynek a megfogalmazása, hogy ha valamely kódszót legfeljebb e helyen megváltoztatunk, akkor abból az eredeti kódszót vissza tudjuk állítani, de ekvivalens vele, mint azt a következő lemmában látni fogjuk. Ehhez még egy fogalomra van szükségünk.

4.2. Definíció. A c középpontú r sugarú gömb vagy más néven Hamming-gömb az alábbi halmaz:

S r ( c ) = { x ? Q n : d ( x , c ) ? r } .

8. feladat. Mutassuk meg, hogy Hamming-gömb komplementere is Hamming-gömb. (Mi lesz a középpont és a sugár?)

4.3. Lemma. Legyen C kód. Ekkor ekvivalensek az alábbiak:

  1. bármely v ? Q n -hez legfeljebb egy c ? C kódszó van, amelyre d ( v , c ) ? e .

  2. az S e ( c ) gömbök c ? C -re páronként diszjunktak.

  3. C minimális távolságára d ? 2 e + 1 teljesül.

Bizonyítás. (i) és (ii) nyilván ekvivalens. Ha két olyan c , c ' ? C lenne, amelyre d ( v , c ) ? e , és d ( v , c ' ) ? e teljesülne, akkor a v és v ' egymástól legfeljebb 2 e koordinátában térhetne el, azaz (iii) sem teljesülne. (Hivatkozhattunk volna a háromszög-egyenlőtlenségre is.)

Megfordítva, ha van olyan c , c ' ? C , amelyre d ( c , c ' ) ? 2 e , akkor tekintsük azokat a koordinátákat, ahol c és c ' eltérnek egymástól. Ezen koordináták halmazát osszuk két legfeljebb e elemű részre. Arra a v szóra, amely az első részen c -vel, a másodikon c ' -vel egyezik meg (és persze mind c -vel mind c ' -vel megegyezik azokban a koordinátákban, ahol c és c ' megegyezik), d ( v , c ) ? e és d ( v , c ' ) ? e teljesül. ?

9. feladat. Vizsgáljuk meg, hogy a Mariner 1969 expedíciónál használt, az előző szakasz végén leírt kód hány hibát javít (egy képpontra)!

4.4. Példa. Legyen Q = { 0 , 1 } , n = 7 , és tekintsük az alábbi 16 sorozat által alkotott kódot:

h 0 ( 1 , 1 , 1 , 1 , 1 , 1 , 1 ) ; h 15 ( 0 , 0 , 0 , 0 , 0 , 0 , 0 ) h 1 ( 1 , 1 , 1 , 0 , 0 , 0 , 0 ) ; h 14 ( 0 , 0 , 0 , 1 , 1 , 1 , 1 ) h 2 ( 0 , 1 , 0 , 1 , 0 , 1 , 0 ) ; h 13 ( 1 , 0 , 1 , 0 , 1 , 0 , 1 ) h 3 ( 1 , 0 , 0 , 1 , 1 , 0 , 0 ) ; h 12 ( 0 , 1 , 1 , 0 , 0 , 1 , 1 ) h 4 ( 0 , 0 , 1 , 1 , 0 , 0 , 1 ) ; h 11 ( 1 , 1 , 0 , 0 , 1 , 1 , 0 ) h 5 ( 0 , 1 , 0 , 0 , 1 , 0 , 1 ) ; h 10 ( 1 , 0 , 1 , 1 , 0 , 1 , 0 ) h 6 ( 1 , 0 , 0 , 0 , 0 , 1 , 1 ) ; h 9 ( 0 , 1 , 1 , 1 , 1 , 0 , 0 ) h 7 ( 0 , 0 , 1 , 0 , 1 , 1 , 0 ) ; h 8 ( 1 , 1 , 0 , 1 , 0 , 0 , 1 )

1. ábra.

Érdekes módon kapcsolódik ez a kód a projektív geometriához[18] Tekintsük a Fano-síkot. Ennek 7 pontját rendezzük el valamilyen sorrendben. A pontok egy részhalmazához hozzárendelhetünk egy 0 – 1 sorozatot: az i -edik helyre 1-et írunk, ha az i -edik pont benne van a részhalmazban, és 0-át írunk, ha nincs. Vegyük a következő 16 részhalmazt: az üres halmaz; a teljes sík; az egyenesek; az egyenesek komplementerei. E 16 részhalmaznak épp kódunk 16 0 – 1 sorozata felel meg, ha a 7 pontot megfelelően rendeztük sorba.

2. ábra.

Kódunk egy kocka segítségével is szemléltethető. A kódszavaknak 7 koordinátája van. Az egyes koordinátáknak megfeleltetjük a kocka egy-egy csúcsát (így az egyik csúcs kimarad). Az 1. koordinátának a ( 0 , 0 , 1 ) csúcs, a 2. koordinátának a ( 0 , 1 , 0 ) csúcs, , az n . koordinátának az a csúcs felel meg, amelynek térbeli koordinátái az n szám kettes számrendszerbeli alakjának számjegyei (így csak a ( 0 , 0 , 0 ) csúcs, azaz az origó marad ki). Minden kódszóhoz hozzárendeljük a kocka csúcsainak egy részhalmazát: azoknak a koordinátáknak megfelelő csúcsok alkotják ezt a részhalmazt, amelyek értéke 1 az adott kódszóban. A mellékelt ábrán látható 7 „halványszürke részhalmaz” a h 14 h 8 kódszavaknak felel meg, a 7 „fekete részhalmaz” pedig a h 1 h 7 kódszavaknak (a fekete részhalmazokhoz egy később ismertetett konstrukció miatt vettük hozzá az origót). A h 0 , h 15 kódszavak részhalmazait (az összes csúcs, illetve az üres halmaz) nem ábrázoltuk. A kód úgy szerkesztettük, hogy bármelyik kódszóhoz tartozó részhalmazból, a kocka bármely – az origót nem tartalmazó – lapján páros sok csúcs van. Ez magyarázatot ad arra is, hogy miért 1-hibajavító a kód. Ha egy kódszó egyik bitje megváltozik, akkor a kódszóhoz tartozó részhalmazból eltűnik az egyik csúcs, vagy éppen új csúcs kerül a részhalmazba. Nem lesz igaz, hogy minden – az origót nem tartalmazó – lapon páros sok csúcs van az adott részhalmazból. Ha megtaláljuk, hogy a paritási feltétel melyik lapokra nem igaz, akkor megleljük a hibás csúcsot is, hiszen mindegyik csúcsot egyértelműen jellemzi, hogy mely – az origót nem tartalmazó – lapokon van rajta.

A bevezetésben említett, számítógépek részegységei közötti kommunikációban használt paritásbittel hibát javítani nem tudunk. Ha viszont legfeljebb 1 hiba történt, akkor azt jelezni tudjuk, hiszen ha egy összeg egyetlen tagjának párossága megváltozik, akkor megváltozik az összeg paritása is.

A 4.4. példában említett kódhoz is hozzátehetünk még egy paritásbitet. Így a kódszavak 8 hosszú sorozatok lesznek, és bármelyik kettő Hamming-távolsága legalább 4 lesz. Valóban, ha az eredeti kódban két szó távolsága csak 3 volt, akkor az egyikben páratlan, a másikban páros sok 1-es szerepelt, így különböző paritásbitet kapnak, ami 4-re növeli távolságukat. Ezáltal nem leszünk képesek több hibát javítani, de a karakterek törléséből származó bajoknál jól jöhet a nagyobb távolság (lásd a 14. feladatot). E kibővített kód is szemléltethető a kockán úgy, hogy a „paritás-koordinátának” az origót feleltetjük meg. Így minden kódszónak páros sok csúcsból álló részhalmaz felel meg. Ezért nem csak az origót nem tartalmazó lapokon, hanem azok komplementerein, azaz végül is minden lapon páros sok csúcs lesz minden kódszónak megfelelő részhalmazból.

Bármely e -hibajavító kódra a kódszavak köré írt e sugarú gömbök diszjunktak. Az azonban lehetséges, hogy nem fedik le a teljes Q n -et. Nyilván azok a legjobb kódok, amikor a kódszavak köré írt gömbök le is fedik Q n -et.

4.5. Definíció. Az e -hibajavító C kód perfekt, ha minden v ? Q n -hez van olyan c ? C , amelyre d ( v , c ) ? e . (Persze ez a c egyértelmű is, lásd a 4.3 Lemma (i) részét.)

Most térjünk rá arra a kérdésre, hogy egy e -hibajavító kódban hány kódszó lehet. Először lássuk az e = 1 esetet.

4.6. Tétel. (Hamming-korlát) Ha C 1-hibajavító kód, akkor

C ? Q n n ( Q - 1 ) + 1 .

Itt egyenlőség pontosan akkor áll, ha C perfekt.

Bizonyítás. Bármely 1 sugarú gömbben a középponton kívül pontosan n ( Q - 1 ) szó van, hiszen a középponttól való egyetlen eltérés helye n -féleképpen választható, az ideírt Q -beli elem pedig nem lehet azonos a középpont megfelelő koordinátájával. ?

Hasonlóan látható be az e -hibajavító kódokra vonatkozó becslés:

C ? Q n ? i = 0 e n i ( Q - 1 ) i .

(1)

Próbáljunk alsó becslést adni a 4. b), 5. a) és b), 6. c) és 7. feladatokban kérdezett számokra! Az ebben a fejezetben tanultak hozzásegíthetnek a 6. feladat megoldásához is. Tegyük fel, hogy már megfogalmaztunk n kérdést. A kérdések ilyenek is lehetnek: „Az 1, 3 és 7 számok egyike a gondolt szám?”. Képzeljük azt, hogy Mr. X az 1-re gondolt, és adjunk helyes választ sorban az n kérdésre: ha 1-est írunk az „igen” és 0-t a „nem” válasz helyett, akkor egy n hosszúságú 0 – 1 sorozatot kapunk. Ezután sorban azt feltételezve, hogy 2, 3, , 16 volt a gondolt szám, összesen 16 darab n hosszúságú 0 – 1 sorozatot készíthetünk. Az n megfogalmazott kérdéssel akkor tudjuk biztosan kitalálni a gondolt számot, ha a 16 jelsorozat

a) mind különböző;

b) bármelyik kettő legalább két helyen eltér;

c) bármelyik kettő legalább három helyen különbözik egymástól.

Mely n esetén lehetséges ez az egyes esetekben?



[18] lásd könyvünkben a „Véges projektív síkok” című írást.