Legyen egy Tⁿ→T^k lineáris kód kódszavainak a halmaza K és $\mathcal{P}\mathcal{ }:\mathcal{ }{T}^k\to T^s$ olyan lineáris leképezés, amelynek a magtere K. Írjuk fel a $\mathcal{P}$ leképezés $P=\left[\mathcal{P}\right]$ mátrixát a természetes bázispár szerint. Ezt az s×k-as P mátrixot a kód paritásellenőrző mátrixának nevezzük.❶

Az elnevezés magyarázatául gondoljuk végig, hogy mi történik, amikor a P mátrix egy sorát egy $\underset{\_}{z}{T}^k$ vektorral megszorozzuk. Ekkor eredményül $\underset{\_}{z}$ azon komponenseinek az összegét kapjuk, amely helyeken a P adott sorában 1-es áll, vagyis azt, hogy ezeken a helyeken $\underset{\_}{z}$-ben összesen páros vagy páratlan sok 1-es fordul-e elő. Ezt bármely sorral elvégezve pontosan a kódszavak esetén lesz minden ilyen összeg nulla. Azaz P valóban a vektorok bizonyos helyein álló 1-esek számának paritását ellenőrzi.

Mivel a $\mathcal{ }\mathcal{P}$ leképezés az esetek zömében nem egyértelmű, ezért egy kódnak általában több P paritásellenőrző mátrixa is létezik (vö. a 10.3.3–10.3.4 feladatokkal). Ezeket a definíció alapján azzal jellemezhetjük, hogy egy $\underset{\_}{z}{T}^k$ vektorra $P\underset{\_}{z}=\underset{\_}{0}$ akkor és csak akkor teljesül, ha $\underset{\_}{z}$ kódszó.

A már említett $\mathrm{I}\mathrm{m}\mathcal{ }\mathcal{P}=T^s$ tulajdonság ekvivalens azzal, hogy $\dim \mathrm{I}\mathrm{m}\mathcal{ }\mathcal{P}=s$ ami ugyanazt jelenti, hogy a P mátrix (F₂ feletti) rangja r(P)=s. Így egy paritásellenőrző mátrix rangja szükségképpen s. Sőt, ez a tulajdonság az előző bekezdés „akkor” részével kiegészítve már karakterizálja is a(z adott) kód paritásellenőrző mátrixait (lásd a 10.3.3 feladatot). Az is könnyen adódik, hogy ha egy 0–1 mátrixnak s sora, k=n+s oszlopa van és a rangja s, akkor van olyan Tⁿ→T^k lineáris kód, amelynek éppen ez a paritásellenőrző mátrixa (lásd a 10.3.1 feladatot).

Illusztrációként nézzük a paritásvizsgálat-kódnak (a 10.1 pont P3 példájának) a paritásellenőrző mátrixát. Ez egyetlen „csupaegy” sorból áll (azaz olyan sorvektor, amelynek mind a k eleme 1-es): P=(1 1 1 … 1).

A G generátormátrixból általában könnyen megkaphatjuk a(z egyik) P paritásellenőrző mátrixot (lásd a 10.3.5 feladatot). Speciálisan, ha a kódszavak a hozzájuk tartozó közleményszavakkal kezdődnek, azaz a generátormátrix $G=\left(\genfrac{}{}{0pt}{}{E_{n \times n}}{B_{s \times n}}\right)$ alakú, akkor paritásellenőrző mátrixnak megfelel a P=(B_s×nE_s×s) mátrix.

Nézzük meg, hogyan használható a paritásellenőrző mátrix a hibajavításra. Először is a definíció szerint $P\underset{\_}{z}=\underset{\_}{0}$ akkor és csak akkor teljesül, ha $\underset{\_}{z}$ kódszó. Ha az átvitelnél hiba történt és a kapott üzenet $\underset{\_}{z}=\underset{\_}{c}+\underset{\_}{h}$ ahol $\underset{\_}{c}$ a helyes kódszó, $\underset{\_}{h}$ pedig a hibaminta, akkor $P\underset{\_}{z}=P\underset{\_}{h}$ A $P\underset{\_}{z}{T}^s$ vektort a $\underset{\_}{z}{T}^k$ vektor szindrómájának („tünetcsoportjának”) nevezzük.

Ha a $\underset{\_}{h}$ hibamintában egyedül az i-edik helyen áll 1-es, akkor $P\underset{\_}{h}$ éppen a P mátrix i-edik oszlopa. Így a $\underset{\_}{z}$ vektor szindrómája a hibás helyeknek megfelelő P-beli oszlopok összege. Innen azonnal adódik az alábbi tétel:

Egy lineáris kód pontosan akkor t-hibajavító, ha a P paritásellenőrző mátrixának bármely legfeljebb t darab oszlopát összeadva a kapott összegvektorok mind különbözők és egyikük sem nulla.❶

Speciálisan, az 1-hibajavítás feltétele az, hogy P-ben minden oszlop különböző és egyik oszlop sem nulla.

A 10.1 pont végén láttuk, hogy ha egy 1-hibajavító kódnak s ellenőrző jegye van, akkor szükségképpen n≤2^s–s–1. Most megmutatjuk, hogy ennek a megfordítása is igaz:

Legyen (s≥2 és) n≤2s–s–1. Ekkor létezik olyan Tⁿ→T^s+n lineáris kód, amely 1-hibajavító.❶

Bizonyítás: Legyen P olyan s×(s+n)-es mátrix, amelynek az oszlopai különböző nemnulla vektorok úgy, hogy ezek között található s darab lineárisan független. Ilyen P létezik, hiszen T^s-nek 2^s–1≥n+s miatt elegendő számú nemnulla eleme van, a lineáris függetlenségi feltételt pedig biztosítja, ha pl. az utolsó s oszlopot az s darab egységvektornak választjuk.

Mivel P rangja s, ezért létezik olyan lineáris kód, amelynek P a paritásellenőrző mátrixa. Ez(ek) a kód(ok) a 10.3.2 Tétel, illetve az utána tett megjegyzés szerint 1-hibajavító(k).❷

Visszatérve a 10.1 pont végén említett n=500 példára, a most bizonyított tételből következik, hogy az 1-hibajavítást mindössze s=9 darab ellenőrző jeggyel meg tudjuk oldani (és ez a lehetséges minimum). Mindezt érdemes még egyszer összevetni a háromszori ismétlés kódjából adódó s=1000 értékkel.

Az n=2^s–s–1 esetben a kódra külön elnevezést vezetünk be:

Ha n=2^s–s–1 és k=n+s=2^s–1, akkor az 1-hibajavító Tⁿ→T^k lineáris kódokat Hamming-kódoknak nevezzük.❶

Az előzőek szerint egy Hamming-kód azzal jellemezhető, hogy a paritásellenőrző mátrixában az oszlopok között a T^s vektortér összes nemnulla eleme pontosan egyszer fordul elő.

Feladatok

Valamennyi feladatban $n+s=k, \mathcal{A}$ egy Tⁿ→T^k lineáris kód, amelynek a generátormátrixa G, továbbá P egy s×k méretű 0–1 mátrix.

10.3.1 Igazoljuk, hogy egy 0–1 mátrixhoz akkor és csak akkor található olyan lineáris kód, amelynek ő a paritásellenőrző mátrixa, ha a sorai függetlenek, az oszlopai pedig összefüggők.

10.3.2 Írjuk fel a 10.1 pont P1 és P2 példájának, valamint a 10.1.2 feladatban szereplő kódok közül a lineárisaknak egy-egy paritásellenőrző mátrixát.

10.3.3 Mutassuk meg, hogy az alábbi három feltétel bármelyike ekvivalens azzal, hogy P az $\mathcal{A}$ kód (egyik) paritásellenőrző mátrixa:

I. r(P)=s és bármely $\underset{\_}{c}$ kódszóra $P\underset{\_}{c}=\underset{\_}{0}$

II. r(P)=s és PG=0;

III. P sorai bázist alkotnak az ${\left(\mathrm{I}\mathrm{m}\mathcal{ }\mathcal{A}\right)}^{\perp }$ altérben.

10.3.4

a) Mutassuk meg, hogy egy kód paritásellenőrző mátrixa akkor és csak akkor egyértelmű, ha s=1.

b) Bizonyítsuk be, hogy egy kód paritásellenőrző mátrixainak a száma ${}_{i=0}^{s-1}\left(2^s-2^i\right)$

10.3.5

a) Ellenőrizzük, hogy ha $G=\left(\genfrac{}{}{0pt}{}{E_{n \times n}}{B_{s \times n}}\right)$ alakú, akkor paritásellenőrző mátrixnak valóban megfelel a P=(B_s×nE_s×s) mátrix.

b) Adjunk általában is gyors algoritmust arra, hogyan lehet G ismeretében a paritásellenőrző mátrixo(ka)t megkapni.

10.3.6

a) Mutassunk példát arra, hogy különböző kódoknak lehet ugyanaz a paritásellenőrző mátrixa.

b) Hány olyan kód van, amelynek egy adott P mátrix a paritásellenőrző mátrixa?

10.3.7 Legyen Q egy olyan m×k méretű 0–1 mátrix, amelynek a magtere az $\mathcal{A}$ kód kódszavainak a halmaza. Bizonyítsuk be, hogy r(Q)=s, és Q bármely s független sora a kód (egyik) paritásellenőrző mátrixát adja.

10.3.8 Mutassuk meg, hogy egy lineáris kódnál két T^k-beli vektor akkor és csak akkor kerül a dekódolási tábla azonos sorába, ha ugyanaz a szindrómájuk.

10.3.9 Egy lineáris kódban a kódszavak közötti minimális távolság pontosan akkor d, ha a(z egyik) paritásellenőrző mátrixban bármely d–1 oszlop lineárisan független, de van d olyan oszlop, amely összefüggő.

10.3.10 Egy lineáris kódban a kódszavak közötti minimális távolság legfeljebb 1-gyel lehet nagyobb az ellenőrző jegyek számánál.

10.3.11 Két lineáris kód egymás duálisa, ha a kódszavak alkotta alterek T^k-ban egymás merőleges kiegészítői: $K_2=K_1^{\perp }$ Milyen kapcsolatban állnak egymással a duális kódok generátor- és paritásellenőrző mátrixai?

10.3.12 Az $\mathcal{A}$ lineáris kód paritásellenőrző mátrixa legyen P=(BE). Lássuk be, hogy az $\mathcal{A}$ kód akkor és csak akkor lesz önmagának a duálisa, ha B^T=B^–1.

10.3.13 Mennyi egy Hamming-kódban a kódszavak közötti minimális távolság?

10.3.14 Bizonyítsuk be, hogy egy Hamming-kódban bármely kódszónak a komplementere is kódszó. (Két vektor egymás komplementere, ha minden komponensükben különböznek, vö. a 9.4.2a feladattal).

10.3.15 Legyen s≥2, n=2^s–s–1 és k=2^s–1. Legyen továbbá minden 0≤j≤s–1-re M_j azoknak a természetes számoknak a halmaza, amelyek kettes számrendszerbeli alakjában a 2^j együtthatója (azaz hátulról számítva a j+1-edik számjegy) 1. Nyilván bármely j-re |M_j|=2^s–1.

Egy Tⁿ→T^k kódot fogunk megadni. A közleményszavak jegyeit azonban most nem a szokásos módon indexezzük, hanem az indexek közül a kettőhatványokat (beleértve az 1-et is) kihagyjuk (mint egyes szállodákban a szobaszámok közül kihagyják a 13-at, csak mi most a kettőhatványokra vagyunk „babonásak”). Így az indexekben (az 1,2,…,n számok helyett) rendre a 3,5,6,7,9,…,k=n+s számok szerepelnek (hiszen éppen az 1,2,2²,…,2^s–1 kettőhatványokat kellett kihagynunk). Tekintsük ezek után a

kódot, ahol ${\gamma }_j={}_{i{M}_j}{\alpha }_i, j=\mathrm{0,1},\dots s-1.$ Mutassuk meg, hogy így egy Hamming-kódot kapunk.