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

6. Lineáris és MDS kódok

6. Lineáris és MDS kódok

A Hamming-kódot speciális homogén lineáris egyenletrendszer segítségével adtuk meg. Ebben a fejezetben ezt az eljárást általánosítjuk.

Függetlennek nevezzük az olyan egyenletrendszert, amelynek egyik egyenlete sem kapható meg a többiből, úgy, hogy az egyenleteket számokkal szorozzuk és összeadjuk. Független egyenletrendszernek az egyik egyenlete sem fölösleges, mindegyik új megszorítást jelent a változókra az összes többi egyenlethez képest. Megmutatható, hogy ha egy homogén lineáris egyenletrendszer független, n változója és k egyenlete van ( k ? n ), akkor a változók közül kiválasztható n - k , amelyek értéke szabadon megválasztható, és amelyekből a többi változó értéke már egyértelműen meghatározható.

Homogén lineáris egyenletrendszert az együtthatóinak mátrixával szoktunk megadni. Az egyenletrendszer pontosan akkor független, ha a mátrix sorvektorai függetlenek, azaz ha egyik sorvektor sem kapható meg a többiből úgy, hogy azokat számokkal szorozzuk, és összeadjuk. Ezek a fogalmakkal és velük kapcsolatos állítások nem csak a valós számokkal kapcsolatban hasznosak és érvényesek, de bármely más test esetén is.

Legyen Q egy p elemű test, p prím, H a Q elemeiből képzett olyan k × n -es mátrix, melynek sorai függetlenek. Tekintsük az alábbi C kódot:

C = { x = ( x 1 , , x n ) ? Q n : ? j = 1 n h i j x j = 0 ; i = 1 , , k } .

(3)

Azaz C a ? j = 1 n h i j x j = 0 ; i = 1 , , k lineáris egyenletrendszer megoldásainak halmaza.

Az előbb elmondottak szerint C = p n - k . A C kód minimális távolsága H oszlopaitól függ.

11. feladat. Bizonyítsuk be, hogy C minimális távolsága d , ha H bármely d - 1 oszlopa lineárisan független, de van olyan d oszlop, amelyek összefüggenek.

Az ilyen kódokat lineáris kódoknak nevezzük, a H mátrixot szokás a kód paritás-ellenőrző mátrixának hívni. A lineáris kódok előnye, hogy ezekre viszonylag hatékony kódolási és dekódolási eljárás ismert, mint azt az előző szakaszban tárgyalt speciális esetben a Hamming-kódok példája is mutatja.

Sok esetben fontos volna egynél több hibát javítani, és persze az is jó lenne, ha sikerülne perfekt kódokat szerkeszteni. Ez sajnos csak ritkán lehetséges, amint azt az alábbi tétel mutatja.

6.1. Tétel. (Tietäväinen, Van Lint) e //>// 1 -re csak két perfekt kód létezik, az ún. Golay-kódok, melyekre Q = 2 n = 23 , e = 3 , illetve Q = 3 , n = 11 , e = 2 .

Ha viszont lényegében nincsenek egynél több hibát javító perfekt kódok, akkor olyan kódokat lenne érdemes szerkeszteni, amelyek közel ilyen jók, de sokkal több n -re léteznek. Először becsüljük meg, hogy adott elemszámú kód hány hibát javíthat.

6.2. Tétel. (Singleton) Legyen a C ? Q n kód minimális távolsága d . Ekkor C ? Q n - d + 1 .

Bizonyítás. Töröljük ki minden kódszó utolsó d - 1 koordinátáját. Így különböző kódszavakból különböző rövidített szót kapunk. A rövidített szavak száma legfeljebb Q n - d + 1 , tehát C is legfeljebb annyi. ?

Ebből persze azt is ki lehet olvasni, hogy adott méretű kód legfeljebb hány hibát javíthat, t. i. annyit, mint ( n - log Q C ) / 2 egész része. Ha a kód lineáris és k független egyenletből álló egyenletrendszerrel definiáltuk, akkor a Singleton-korlát azt adja, hogy k ? d - 1 , hiszen ekkor C = Q n - k .

6.3. Definíció. Olyan C kódot, amelyre C = Q n - d + 1 , MDS kódnak nevezünk. (MDS = maximum distance separable).

Az MDS-kódok között már vannak e //>// 1 hibát javító kódok. Lássunk megint egy konkrét példát! Ezt a példát a [6] dolgozatból vettük, beleértve a hibák valószínűségéről szóló részeket is.

Üzeneteink olyan ábécé elemeiből lesznek, amely 31 szimbólumot tartalmaz (az ékezet nélküli betűkön kívül helyköz, vessző, pont stb. is előfordul benne). Számoláskor minden betűt azonosítunk sorszámával és ezekkel modulo 31 számolunk, leíráskor azonban magát a betűt vagy írásjelet írjuk le. A szöveget négy betűből álló csoportokra osztjuk, és minden ilyen 4 hosszú üzenet elé két további betűt illesztünk. Ez a hatbetűs szó lesz a kódolt üzenet. Minden betűt és szimbólumot azonosítsunk azzal a számmal, ahányadik helyen a betű az ábécében áll. Tehát A -nak 1, C -nek 3 felel meg, és így tovább. A hozzáillesztett két karaktert úgy választjuk, hogy a hatbetűs ( a 0 , a 1 , , a 5 ) szóra

a 0 + a 1 + + a 5 ? 0 ( mod 31 ) , (4) a 1 + 2 a 2 + + 5 a 5 ? 0 ( mod 31 ) (5)

teljesüljön, ahol a hozzátett betűk a 0 és a 1 . Ha a koordinátákat egész számnak tekintjük, akkor ez azt jelenti, hogy a baloldali kifejezések értéke osztható kell legyen 31-gyel. Nem nehéz belátni, hogy a 0 -t és a 1 -et egyértelműen meghatározza ez a két egyenlet (ha 1 ? a 0 , a 1 ? 31 ). Így az ennek a két feltételnek eleget tevő n = 6 hosszú kódszavak száma megegyezik a négybetűs szavak számával, azaz C = 31 4 .

Ha tehát szövegünk úgy kezdődik, hogy: „ADAG”, akkor erre ( a 2 , , a 5 ) = ( 1 , 4 , 1 , 7 ) , azaz a második egyenletből a 1 + 2 + 12 + 4 + 35 ? 0 ( mod 31 ) , vagyis a 1 = 9 adódik, az első egyenletből pedig a 0 = 9 jön. Ha betűkkel akarjuk ezt leírni, akkor ADAG kódolt alakja IIADAG. Tegyük fel, hogy azt kapjuk, hogy NKBABC. Erre az első összeg 14 + 11 + 2 + 1 + 2 + 3 , ami 2 modulo 31. Ha abban bízunk, hogy egy hiba történt, akkor valamelyik összeadandó 2-vel nagyobb a kelleténél. Ha még a második egyenlet baloldalát is kiszámítjuk, akkor meg fogjuk kapni, hogy hol történt a hiba, hiszen ott a 2-es eltérést a hiba helyével szorozzuk. Ez 11 + 4 + 3 + 8 + 15 = 41 , ami 10 modulo 31, így a hiba az a 5 -nél történt. a 5 helyes értéke 1, azaz a szó helyesen BABA volt.

Fontos megjegyezni, hogy ha ezt a kódolást használjuk, akkor az átküldendő üzenet hossza másfélszer annyi lesz, mint kódolás nélkül, így még az is előfordulhatna, hogy a kódolással nem nyerünk semmit. Ráadásul azáltal, hogy összességében több üzenetet kell küldenünk, lehet, hogy csak kevésbé hatékony berendezést használhatunk, azaz még a hiba valószínűsége is növekedhet. Hogy a helyzetet illusztráljuk, tegyük fel, hogy 100000 négybetűs sorozatot kell átvinnünk, és a hiba véletlenszerű, 0,001 valószínűséggel. Ez azt jelenti, hogy kb. 400 hibás betű lesz. Most tegyük fel, hogy a fenti kódolást alkalmazzuk, és a hiba valószínűsége is 0,002-re nő. Ugyanakkor, ha valamely hatbetűs szóban csak egy hiba van, akkor azt ki tudjuk a fenti eljárással javítani. Annak a valószínűsége, hogy bennmaradjon hiba, tehát valamelyik hatbetűs szó legalább két hibát tartalmazzon, körülbelül

? i = 2 6 6 i ( 0,002 ) i ( 0,998 ) 6 - i ? 0,00006

lesz. A 100000 szóból így várhatóan 6 lesz kéthibás, ami lényegesen jobb, mintha nem alkalmaztunk volna kódolást.

Egy az előzőnél jobb, két hibát javító kóddal még sokkal jobb eredményt érhetünk el. Most négyesek helyett nyolcas csoportokra osszuk a kódolandó üzenetet, és ezekhez négy további betűt illesszünk. Nevezetesen a hozzáillesztett négy betű legyen ( a 0 , a 1 , a 2 , a 3 ) , az eredeti üzenet pedig ( a 4 , , a 11 ) . Szabályaink legyenek

a 0 + a 1 + + a 11 ? 0 ( mod 31 ) ; (6) a 1 + 2 a 2 + + 11 a 11 ? 0 ( mod 31 ) ; (7) a 1 + 4 a 2 + 9 a 3 + + 11 2 a 11 ? 0 ( mod 31 ) ; (8) a 1 + 8 a 2 + 27 a 3 + + 11 3 a 11 ? 0 ( mod 31 ) . (9)

Annak részletes vizsgálatát, hogy így 2-hibajavító kódot kapunk, (nehéz) feladatnak hagyjuk. Jegyezzük meg, hogy ebben az esetben is csak másfélszer annyi üzenetet kell átküldenünk, mint kódolás nélkül. Ha tehát itt is a 0,002 hibájú berendezést használjuk, akkor a legalább 3 hibát tartalmazó szavak lesznek azok, amelyeket nem tudunk javítani. Ennek valószínűsége

? i = 3 12 12 i ( 0,002 ) i ( 0,998 ) 12 - i //<// 0,000002 .

Ez viszont azt jelenti, hogy várhatóan legfeljebb 0,2 hibás szó lesz, vagyis legtöbbnyire nem lesz hibásan átvitt üzenet.

Ez a rövid eszmefuttatás világosan mutatja a kódolás fő problémáját. Ha adott az ábécé ( Q ), és az elküldendő üzenetek száma (azaz C ), akkor egyrészt azt szeretnénk, hogy a szavak minél rövidebbek legyenek (vagyis hogy n kicsi legyen), másrészt minél több hibát szeretnénk javítani (azaz a d minimális távolság legyen nagy). Ez a két cél a Singleton-korlát szerint egymással ellentétes, így a kód megválasztásakor jó kompromisszumot kell kötnünk e két ellentétes cél között.

Ehhez hasonló elven működik a hibajavítás a CD lemezeken. Itt egymás után két kódot is használnak, mindkettő két hibát képes javítani, az első kód hossza 28, a másodiké 32. Ezek késleltetéssel működnek együtt, a részletes leírást ld. [6]-ban. Ezen felül több apróbb trükköt használnak, részben matematikai, részben mérnöki jellegűt. Így pl. a dekódoláskor a külső kódot csak 1 hiba javítására használják, ha valamelyik szót nem sikerült dekódolni, akkor a két szomszédos szó átlagával helyettesítik, stb. A teljes rendszer leírása pontosan ezen okokból nagyon hosszadalmas lenne. Így most csak néhány megjegyzést teszünk: másodpercenként 44 100 audio-jel van. Minden ilyen jel 2 × 16 hosszú 0 – 1 sorozatnak felel meg. Ezt nyolcas csoportokra (=byte) osztják, és ezeket a nyolcasokat a 64 elemű test elemeinek (nem modulo 64!!) tekintjük. Ezután 24 ilyen byte-hoz az előző oldali példához hasonlóan az egyik kódot használva 4, majd az eredményre a másik kódot használva további 4 byte-ot tesznek hozzá. Így 32 byte-ot kapunk, amihez egy további kontroll byte-ot tesznek, amely lehetővé teszi, hogy tudjuk, hogy a lemezen hol tartunk. Mechanikai, optikai megfontolásokból a CD lemezen olyan 0 – 1 sorozatot használnak, amelyben két egyes között legalább két, de legfeljebb tíz 0 van. Tehát először egy-egy byte-ból csinálnak egy 14 hosszú 0 – 1 sorozatot, amely ennek a feltételnek megfelel. Mivel két ilyen 14-es sorozat egymásutánja megsérthetné a szabályt, a 14-es sorozat után három további bit következik. Végül a 33 × 17 bit után 27 szinkronizáló bit következik. Így tehát egy másodpercnyi zene végül is 4 321 800 bitként jelenik meg a CD lemezen. Még néhány impresszív szám: a CD lemezen a pálya hossza kb. 5 kilométer. A hibajavítással (bizonyos feltételek mellett), a pálya irányában ejtett mintegy 3 mm-es karcolást ki lehet javítani. További részletekről [6]-ban olvashatunk, illetve annak hivatkozásai között a rendszer mérnöki alaposságú leírása is megtalálható.

A CD példája azt mutatja, hogy sok esetben előre tudunk valamit arról, hogy milyen jellegű hibák várhatók. Itt pl. a karcolás egy csomóban előforduló hibákat okoz. A feladatok között találunk arra is példát, hogy sok esetben csak bizonyos jellegű, egyszerű hibákat kívánunk javítani.