Ugrás a tartalomhoz

Lineáris algebra

Freud Róbert (2014)

ELTE Eötvös Kiadó

10.2. Lineáris kód

10.2. Lineáris kód

10.2.1 Definíció

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:

10.2.2 Tétel

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.

10.2.3 Definíció

Legyen A lineáris kód, és írjuk fel az A lineáris leképezés G=GA=A 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 G=En × nBs × n alakú (ahol E az n×n-es egységmátrix, B pedig egy s×n-es mátrix).

Legyen v_Tn egy tetszőleges közleményszó és c_=Av_ a hozzá tartozó kódszó. Ha v_-t és c_-t most valóban oszlopvektornak, azaz n×1-es, illetve k×1-es mátrixnak tekintjük, akkor a kapcsolatuk a c_=GAv_ 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 z_Tk vektorhoz megkeressük a hozzá legközelebbi (egyik) c_ kódszót, és ha az átvitelnél a fogadó félhez a z_ érkezett, akkor ezt a dekódoláskor c_-re javítja. Itt a h_=z_-c_ vektort hibamintának nevezzük, mert a z_ és c_ 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 z_ vektort megkapjuk. (Ha z_ kódszó, akkor h_=0) 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 K=Im A alterének h_+K 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 h_=0 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 0_ 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 A : α1α1α1α2α1α2β ahol β=α12. 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ó z_=01010 esetén a helyes kódszó a c_=01011  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 TnTk 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 TnTk 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, φj : TnjTkj, 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, a_Tn  és legyen φ : TnTk1+k2 a φa_=φ1a_φ2a_ kód.

II. „A közleményszavakat és a kódszavakat is egymás mellé írjuk.” Legyen a_jTnj  és φ : Tn1+n2Tk1+k2 a φa_1a_2=φ1a_1|φ2a_2 kód.

III. „A közleményszavakat, valamint a kódszavak (aszimmetrikus) kombinációját írjuk egymás mellé.” Tegyük fel, hogy k1=k2=k, a_jTnj és legyen φ : Tn1+n2T2k a φa_1a_2=φ1a_1φ1a_1+φ2a_2 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=kn. 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 A : TnxTkx leképezés a g polinommal történő szorzás, azaz A minden legfeljebb n–1-edfokú f polinomhoz a gf polinomot rendeli hozzá: Af=gf  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 A : TnxTkx 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 TnTk 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 c_ kódszó a v_ közleményszóból származott, akkor Hc_=v_). Adjunk (gyors) algoritmust ilyen H megkeresésére.