Ha a ϕ kód (injektív) lineáris leképezés a Tⁿ és T^k (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 Tⁿ és T^k 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 T^k-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 $\mathcal{A}$ lineáris kód, és írjuk fel az $\mathcal{A}$ lineáris leképezés $G=G_{\mathcal{A}}=\left[\mathcal{A}\right]$ mátrixát a természetes bázispár (azaz a Tⁿ-beli, illetve T^k-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=\left(\genfrac{}{}{0pt}{}{E_{n \times n}}{B_{s \times n}}\right)$ alakú (ahol E az n×n-es egységmátrix, B pedig egy s×n-es mátrix).

Legyen ${\underset{\_}{v}T}^n$ egy tetszőleges közleményszó és $\underset{\_}{c}=\mathcal{A}\underset{\_}{v}$ a hozzá tartozó kódszó. Ha $\underset{\_}{v}$-t és $\underset{\_}{c}$-t most valóban oszlopvektornak, azaz n×1-es, illetve k×1-es mátrixnak tekintjük, akkor a kapcsolatuk a $\underset{\_}{c}=G_{\mathcal{A}}\underset{\_}{v}$ 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 $\underset{\_}{z}{T}^k$ vektorhoz megkeressük a hozzá legközelebbi (egyik) $\underset{\_}{c}$ kódszót, és ha az átvitelnél a fogadó félhez a $\underset{\_}{z}$ érkezett, akkor ezt a dekódoláskor $\underset{\_}{c}$-re javítja. Itt a $\underset{\_}{h}=\underset{\_}{z}-\underset{\_}{c}$ vektort hibamintának nevezzük, mert a $\underset{\_}{z}$ és $\underset{\_}{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 $\underset{\_}{z}$ vektort megkapjuk. (Ha $\underset{\_}{z}$ kódszó, akkor $\underset{\_}{h}=0$) A T^k elemeit ennek megfelelően a kódszavaknak a hibaminták szerinti eltoltjaiként érdemes felírni. Ez azt jelenti, hogy a kódszavak $K=\mathrm{I}\mathrm{m}\mathcal{ }\mathcal{A}$ alterének $\underset{\_}{h}+K$ eltoltjait kell tekinteni (lásd a 4.2.16 feladatot). Ily módon T^k-t 2^k–n darab diszjunkt osztályra bontottuk, amelyek mindegyike |K|=2ⁿ vektort tartalmaz. Az osztályok között szerepel maga a K is (mint önmagának a $\underset{\_}{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 $\underset{\_}{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 $\mathcal{A}\mathcal{ }:\mathcal{ }{\alpha }_1{\alpha }_1\mapsto {\alpha }_1{\alpha }_2{\alpha }_1{\alpha }_2\beta$ ahol β=α₁+α₂. 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ó $\underset{\_}{z}=01010$ esetén a helyes kódszó a $\underset{\_}{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 Tⁿ→T^k 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 F₂ 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 Tⁿ→T^k lineáris kód páros súlyú kódszavai alteret alkotnak T^k-ban. Hány dimenziós ez az altér?

10.2.7 Legyen ϕ₁ és ϕ₂ két kód, ${\phi }_j : T^{n_j}\to T^{k_j}$, ahol d_j 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 n₁=n₂=n, $\underset{\_}{a}{T}^n$ és legyen $\phi : T^n\to T^{k_1+k_2}$ a $\phi \left(\underset{\_}{a}\right)={\phi }_1\left(\underset{\_}{a}\right){\phi }_2\left(\underset{\_}{a}\right)$ kód.

II. „A közleményszavakat és a kódszavakat is egymás mellé írjuk.” Legyen ${\underset{\_}{a}}_j{T}^{n_j}$ és $\phi : T^{n_1+n_2}\to T^{k_1+k_2} \mathrm{a} \phi \left({\underset{\_}{a}}_1{\underset{\_}{a}}_2\right)={\phi }_1\left({\underset{\_}{a}}_1\right)|{\phi }_2\left({\underset{\_}{a}}_2\right)$ kód.

III. „A közleményszavakat, valamint a kódszavak (aszimmetrikus) kombinációját írjuk egymás mellé.” Tegyük fel, hogy $k_1=k_2=k, {\underset{\_}{a}}_j{T}^{n_j}$ és legyen $\phi : T^{n_1+n_2}\to T^{2k} \mathrm{a} \phi \left({\underset{\_}{a}}_1{\underset{\_}{a}}_2\right)={\phi }_1\left({\underset{\_}{a}}_1\right)\left({\phi }_1\left({\underset{\_}{a}}_1\right)+{\phi }_2\left({\underset{\_}{a}}_2\right)\right)$ kód.

a) Mit állíthatunk az új kódokban a kódszavak közötti minimális távolságról?

b) Ha ϕ₁ és ϕ₂ 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=F₂, és jelölje T_m[x] a T feletti legfeljebb m–1-edfokú polinomok szokásos vektorterét. Ekkor az

megfeleltetés izomorfizmus a T^m és T_m[x] vektorterek között. Legyen k>n, s=k–n. Ebben a feladatban a Tⁿ, illetve T^k vektortereket a belőlük a fenti izomorfizmussal létesített T_n[x], illetve T_k[x] vektorterekkel azonosítjuk.

a) Legyen g≠0 egy rögzített, legfeljebb s-edfokú polinom T felett. Legyen az $\mathcal{A}\mathcal{ }:\mathcal{ }{T}_n\left[x\right]\to T_k\left[x\right]$ leképezés a g polinommal történő szorzás, azaz $\mathcal{A}$ minden legfeljebb n–1-edfokú f polinomhoz a gf polinomot rendeli hozzá: $\mathcal{A}f=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 $\mathcal{A}\mathcal{ }:\mathcal{ }{T}_n\left[x\right]\to T_k\left[x\right]$ 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 Tⁿ→T^k 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 $\underset{\_}{c}$ kódszó a $\underset{\_}{v}$ közleményszóból származott, akkor $H\underset{\_}{c}=\underset{\_}{v}$). Adjunk (gyors) algoritmust ilyen H megkeresésére.