Ugrás a tartalomhoz

Lineáris algebra

Freud Róbert (2014)

ELTE Eötvös Kiadó

10.3. Hamming-kód

10.3. Hamming-kód

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 A : TnTk egy lineáris kód. Ekkor K egy n-dimenziós altér Tk-ban. Legyen P : TkTs egy olyan lineáris leképezés, amelynek a magtere Ker P=K A dimenziótétel szerint ekkor P képtere az egész Ts.

Ilyen P lineáris leképezés létezik: a K altér egy b_1,,b_n bázisát a d_1,,d_s vektorokkal egészítsük ki Tk egy bázisává és legyen Pb_i=0_ a Pd_j-k pedig legyenek tetszőleges független vektorok (azaz alkossanak bázist Ts-ben). Innen az is látszik, hogy a P leképezés általában nem egyértelmű.

10.3.1. Definíció

Legyen egy TnTk lineáris kód kódszavainak a halmaza K és P : TkTs olyan lineáris leképezés, amelynek a magtere K. Írjuk fel a P leképezés P=P 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 z_Tk vektorral megszorozzuk. Ekkor eredményül z_ azon komponenseinek az összegét kapjuk, amely helyeken a P adott sorában 1-es áll, vagyis azt, hogy ezeken a helyeken 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  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 z_Tk vektorra Pz_=0_ akkor és csak akkor teljesül, ha z_ kódszó.

A már említett Im P=Ts tulajdonság ekvivalens azzal, hogy dimIm P=s 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 TnTk 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=En × nBs × n 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 Pz_=0_ akkor és csak akkor teljesül, ha z_ kódszó. Ha az átvitelnél hiba történt és a kapott üzenet z_=c_+h_ ahol c_ a helyes kódszó, h_ pedig a hibaminta, akkor Pz_=Ph_ A Pz_Ts vektort a z_Tk vektor szindrómájának („tünetcsoportjának”) nevezzük.

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

10.3.2 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≤2ss–1. Most megmutatjuk, hogy ennek a megfordítása is igaz:

10.3.3 Tétel

Legyen (s≥2 és) n≤2s–s–1. Ekkor létezik olyan TnTs+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=2ss–1 esetben a kódra külön elnevezést vezetünk be:

10.3.4 Definíció

Ha n=2ss–1 és k=n+s=2s–1, akkor az 1-hibajavító TnTk 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 n+s=k, A egy TnTk 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 A kód (egyik) paritásellenőrző mátrixa:

I. r(P)=s és bármely c_ kódszóra Pc_=0_

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

III. P sorai bázist alkotnak az Im A 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=0s-12s-2i

10.3.5

a) Ellenőrizzük, hogy ha G=En × nBs × n 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 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 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: K2=K1  Milyen kapcsolatban állnak egymással a duális kódok generátor- és paritásellenőrző mátrixai?

10.3.12 Az A lineáris kód paritásellenőrző mátrixa legyen P=(BE). Lássuk be, hogy az A 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=2ss–1 és k=2s–1. Legyen továbbá minden 0≤js–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 TnTk 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 γj=iMjαi, j=0,1,s-1. Mutassuk meg, hogy így egy Hamming-kódot kapunk.