Freud Róbert (2014)
ELTE Eötvös Kiadó
Ha a ϕ kód (injektív) lineáris leképezés a Tn és Tk (modulo 2 test feletti) vektorterek között, akkor ϕ-t lineáris kódnak nevezzük.❶
A fenti definíció ekvivalens azzal, hogy ϕ (injektív) csoporthomomorfizmus a Tn és Tk additív csoportok között. Ezért használatos a csoportkód elnevezés is.
A továbbiakban a lineáris kódokat (mint speciális lineáris leképezéseket) írott nagybetűvel fogjuk jelölni. Az előző pont P1–P3 példája, valamint a 10.1.2 feladatban szereplő kódok egy része is lineáris kód.
Lineáris kód esetén a kódszavak egy n-dimenziós alteret alkotnak Tk-ban, speciálisan a nullvektor is kódszó.
Lineáris kód esetén sokkal egyszerűbben ellenőrizhetjük a t-hibajelzést, illetve t-hibajavítást:
Egy lineáris kód pontosan akkor t-hibajelző, ha minden nemnulla kódszó súlya legalább t+1, és pontosan akkor t-hibajavító, ha minden nemnulla kódszó súlya legalább 2t+1.❶
Bizonyítás: Mivel lineáris kód esetén a kódszavak alteret alkotnak, ezért két kódszó különbsége is kódszó. Ennélfogva bármely két (különböző) kódszó távolsága egy alkalmas nemnulla kódszó súlya. Megfordítva, egy nemnulla kódszó súlya megegyezik ennek a kódszónak a nulla kódszótól való távolságával. Ezzel beláttuk, hogy a kódszavak közötti távolságok halmaza egybeesik a nemnulla kódszavak súlyainak a halmazával. Így speciálisan a kódszavak közötti minimális távolság megegyezik a nemnulla kódszavak súlyának minimumával. A tétel állításai ennek alapján a 10.1.5 Tételből következnek.❷
Így például egy lineáris kód pontosan akkor 1-hibajavító, ha minden nemnulla kódszó súlya legalább 3.
Legyen lineáris kód, és írjuk fel az lineáris leképezés mátrixát a természetes bázispár (azaz a Tn-beli, illetve Tk-beli egységvektorok) szerint. Ezt a k×n-es G mátrixot a kód generátormátrixának nevezzük.❶
A generátormátrix oszlopait tehát az egységvektorokhoz tartozó kódszavak alkotják. Az előző pont P3 példájának, a paritásvizsgálat-kódnak a generátormátrixa a következő (n+1)×n-es mátrix:
Ha minden kódszó magával a hozzá tartozó közleményszóval kezdődik, akkor a generátormátrix alakú (ahol E az n×n-es egységmátrix, B pedig egy s×n-es mátrix).
Legyen egy tetszőleges közleményszó és a hozzá tartozó kódszó. Ha -t és -t most valóban oszlopvektornak, azaz n×1-es, illetve k×1-es mátrixnak tekintjük, akkor a kapcsolatuk a mátrixszorzat formájában is kifejezhető. A lineáris kódolást tehát a generátormátrixszal (balról) történő szorzás jelenti.
A pont hátralevő részében azt vizsgáljuk, hogyan lehet lineáris kód esetén a hibajavítást elvégezni. A későbbiekben erre lényegesen jobb módszert is mutatunk majd.
A hibajavítás azt jelenti, hogy minden vektorhoz megkeressük a hozzá legközelebbi (egyik) kódszót, és ha az átvitelnél a fogadó félhez a érkezett, akkor ezt a dekódoláskor -re javítja. Itt a vektort hibamintának nevezzük, mert a és távolságának a minimalitása miatt ez a(z egyik) lehető legkisebb súlyú vektor, amelyet egy kódszóhoz hozzáadva a vektort megkapjuk. (Ha kódszó, akkor ) A Tk elemeit ennek megfelelően a kódszavaknak a hibaminták szerinti eltoltjaiként érdemes felírni. Ez azt jelenti, hogy a kódszavak alterének eltoltjait kell tekinteni (lásd a 4.2.16 feladatot). Ily módon Tk-t 2k–n darab diszjunkt osztályra bontottuk, amelyek mindegyike |K|=2n vektort tartalmaz. Az osztályok között szerepel maga a K is (mint önmagának a vektorral történő eltoltja). A csoportelméleti megfogalmazásban ezek az osztályok éppen a K részcsoport szerinti mellékosztályokat jelentik. A továbbiakban az osztályokra ezt a mellékosztály elnevezést fogjuk használni.
A hibajavítást ezek után az alábbi dekódolási tábla segítségével végezhetjük el. Ennek első sorába felírjuk a kódszavakat (azaz K elemeit), kezdve a kódszóval. Ezután a többi sorba rendre felírjuk az iménti mellékosztályokat, amelyekből mindig a legkisebb súlyú reprezentánst (azaz a hibamintát) választjuk, és rendre ezt adjuk hozzá a kódszavakhoz. A sorok elején álló „osztályelső” tehát maga a hibaminta, és dekódoláskor minden vektort a fölötte álló (első sorbeli) kódszóra korrigálunk. (Ezután a kódszóból természetesen meg kell még határoznunk a közleményszót. Ha a kódszó magával a közleményszóval kezdődik, akkor ez nem okoz nehézséget, egyéb esetben egy lehetséges módszert a 10.2.9 feladatban tárgyalunk.)
Ha a kód t-hibajavító, akkor a legfeljebb t darab 1-est tartalmazó hibaminták mind különböző mellékosztályba kerülnek, azaz különböző sorok osztályelsői.
Példa: Legyen ahol β=α1+α2. Ennek a lineáris kódnak a dekódolási táblája
Látjuk, hogy az egy darab 1-est tartalmazó hibaminták különböző sorokba kerültek, tehát a kód valóban 1-hibajavító. Például a 6. sor 3. helyén álló esetén a helyes kódszó a Az utolsó két sorban az osztályelső nem egyértelmű (a 7. sor elején állhatna pl. a 00110 is). Ez (is) mutatja, hogy az utolsó két sor a hibajavítás szempontjából nem használható, az itteni vektorok legalább 2-hibásak, és a kód a 2-hibákat nem tudja javítani.
A fenti eljárás meglehetősen kényelmetlen. A következő pontban a lineáris kódokat más módon fogjuk jellemezni, amellyel gyorsan és „automatikusan” lehet majd a hibajavítást elvégezni.
Feladatok
M10.2.1 Legyen k>n, az összes Tn→Tk kódok számát jelölje κ, a lineáris kódok számát pedig λ. Mutassuk meg, hogy λ|κ.
10.2.2 Írjuk fel a 10.1 pont P1 és P2 példájának, a kétszeri, illetve háromszori ismétlés kódnak a generátormátrixát.
10.2.3 A 10.1.2 feladatban szereplő kódok közül válasszuk ki a lineárisakat és írjuk fel ezek generátormátrixát, valamint dekódolási tábláját.
10.2.4 Legyen A egy k×n-es 0-1 mátrix. Mutassuk meg, hogy akkor és csak akkor van olyan lineáris kód, amelynek a generátormátrixa A, ha az A-nak az F2 test feletti rangja r(A)=n.
10.2.5 Bizonyítsuk be, hogy lineáris kód esetén a kódszavak éppen a generátormátrix oszlopainak összes lineáris kombinációi.
10.2.6 Mutassuk meg, hogy egy Tn→Tk lineáris kód páros súlyú kódszavai alteret alkotnak Tk-ban. Hány dimenziós ez az altér?
10.2.7 Legyen ϕ1 és ϕ2 két kód, , ahol dj a kódszavak közötti minimális távolság (j=1,2). A két kódból új kódokat képezünk az alábbi módon.
I. „A kódszavakat egymás mellé írjuk.” Tegyük fel, hogy n1=n2=n, és legyen a kód.
II. „A közleményszavakat és a kódszavakat is egymás mellé írjuk.” Legyen és kód.
III. „A közleményszavakat, valamint a kódszavak (aszimmetrikus) kombinációját írjuk egymás mellé.” Tegyük fel, hogy és legyen kód.
a) Mit állíthatunk az új kódokban a kódszavak közötti minimális távolságról?
b) Ha ϕ1 és ϕ2 lineáris kódok, akkor hogyan kapjuk meg a generátormátrixaikból az új kódok generátormátrixait?
10.2.8 Legyen T=F2, és jelölje Tm[x] a T feletti legfeljebb m–1-edfokú polinomok szokásos vektorterét. Ekkor az
megfeleltetés izomorfizmus a Tm és Tm[x] vektorterek között. Legyen k>n, s=k–n. Ebben a feladatban a Tn, illetve Tk vektortereket a belőlük a fenti izomorfizmussal létesített Tn[x], illetve Tk[x] vektorterekkel azonosítjuk.
a) Legyen g≠0 egy rögzített, legfeljebb s-edfokú polinom T felett. Legyen az leképezés a g polinommal történő szorzás, azaz minden legfeljebb n–1-edfokú f polinomhoz a gf polinomot rendeli hozzá: Mutassuk meg, hogy így egy lineáris kódot definiáltunk, és írjuk fel a generátormátrixát. Az ilyen kódokat polinomkódoknak, a g polinomot pedig a kód generáló polinomjának nevezzük.
b) Legyen h egy k-adfokú, g pedig egy tetszőleges nemnulla polinom T felett. Az leképezés minden legfeljebb n–1-edfokú f polinomhoz rendelje hozzá a gf szorzatpolinom h-val való osztási maradékát. Mutassuk meg, hogy így akkor és csak akkor definiáltunk egy lineáris kódot, ha g és h legnagyobb közös osztójának a foka legfeljebb s.
c) Tegyük fel, hogy a b) részben g és h legnagyobb közös osztójának a foka pontosan s, és legyen az így definiált kódban a kódszavak halmaza K. Mutassuk meg, hogy ekkor létezik olyan a)-beli értelemben vett polinomkód is, amelynek a generáló polinomja osztója a h-nak, és a kódszavak halmaza ugyancsak K.
10.2.9 Tekintsünk egy Tn→Tk lineáris kódot. Mutassuk meg, hogy létezik olyan n×k-as H 0–1 mátrix, hogy a kódszavakat H-val balról megszorozva visszakapjuk a megfelelő közleményszavakat (azaz ha a kódszó a közleményszóból származott, akkor ). Adjunk (gyors) algoritmust ilyen H megkeresésére.