Freud Róbert (2014)
ELTE Eötvös Kiadó
Lineáris kód esetén eddig a kódszavak K halmazát egy lineáris leképezés képtereként jellemeztük. Most ugyanezt a K halmazt egy másik lineáris leképezés magtereként fogjuk tekinteni.
Legyen k=n+s és egy lineáris kód. Ekkor K egy n-dimenziós altér Tk-ban. Legyen egy olyan lineáris leképezés, amelynek a magtere A dimenziótétel szerint ekkor képtere az egész Ts.
Ilyen lineáris leképezés létezik: a K altér egy bázisát a vektorokkal egészítsük ki Tk egy bázisává és legyen a -k pedig legyenek tetszőleges független vektorok (azaz alkossanak bázist Ts-ben). Innen az is látszik, hogy a leképezés általában nem egyértelmű.
Legyen egy Tn→Tk lineáris kód kódszavainak a halmaza K és olyan lineáris leképezés, amelynek a magtere K. Írjuk fel a leképezés 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 vektorral megszorozzuk. Ekkor eredményül azon komponenseinek az összegét kapjuk, amely helyeken a P adott sorában 1-es áll, vagyis azt, hogy ezeken a helyeken -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 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 vektorra akkor és csak akkor teljesül, ha kódszó.
A már említett tulajdonság ekvivalens azzal, hogy ami ugyanazt jelenti, hogy a P mátrix (F2 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 Tn→Tk 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 alakú, akkor paritásellenőrző mátrixnak megfelel a P=(Bs×nEs×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 akkor és csak akkor teljesül, ha kódszó. Ha az átvitelnél hiba történt és a kapott üzenet ahol a helyes kódszó, pedig a hibaminta, akkor A vektort a vektor szindrómájának („tünetcsoportjának”) nevezzük.
Ha a hibamintában egyedül az i-edik helyen áll 1-es, akkor éppen a P mátrix i-edik oszlopa. Így a 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≤2s–s–1. Most megmutatjuk, hogy ennek a megfordítása is igaz:
Legyen (s≥2 és) n≤2s–s–1. Ekkor létezik olyan Tn→Ts+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 Ts-nek 2s–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=2s–s–1 esetben a kódra külön elnevezést vezetünk be:
Ha n=2s–s–1 és k=n+s=2s–1, akkor az 1-hibajavító Tn→Tk 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 Ts vektortér összes nemnulla eleme pontosan egyszer fordul elő.
Feladatok
Valamennyi feladatban egy Tn→Tk 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 kód (egyik) paritásellenőrző mátrixa:
I. r(P)=s és bármely kódszóra
II. r(P)=s és PG=0;
III. P sorai bázist alkotnak az 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
10.3.5
a) Ellenőrizzük, hogy ha alakú, akkor paritásellenőrző mátrixnak valóban megfelel a P=(Bs×nEs×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 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 Tk-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 Tk-ban egymás merőleges kiegészítői: Milyen kapcsolatban állnak egymással a duális kódok generátor- és paritásellenőrző mátrixai?
10.3.12 Az lineáris kód paritásellenőrző mátrixa legyen P=(BE). Lássuk be, hogy az kód akkor és csak akkor lesz önmagának a duálisa, ha BT=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=2s–s–1 és k=2s–1. Legyen továbbá minden 0≤j≤s–1-re Mj azoknak a természetes számoknak a halmaza, amelyek kettes számrendszerbeli alakjában a 2j együtthatója (azaz hátulról számítva a j+1-edik számjegy) 1. Nyilván bármely j-re |Mj|=2s–1.
Egy Tn→Tk 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,22,…,2s–1 kettőhatványokat kellett kihagynunk). Tekintsük ezek után a
kódot, ahol Mutassuk meg, hogy így egy Hamming-kódot kapunk.