Ugrás a tartalomhoz

Lineáris algebra

Freud Róbert (2014)

ELTE Eötvös Kiadó

10.4. BCH-kódok

10.4. BCH-kódok

A Hamming-kód a kódelmélet hajnalán, a 40-es évek végén már megszületett. Ezután több, mint 10 évet kellett várni, míg az 1-hibajavítást sikerült hasonló hatékonyságú 2-hibajavításra fejleszteni. Az új kódokat közel egyidejűleg fedezte fel (vagy találta fel?) R. C. Bose és D. K. Ray-Chaudhuri (aki ekkor még Bose diákja volt), valamint tőlük függetlenül A. Hocquenghem. A kódokat a felfedezők nevének kezdőbetűiről BCH-kódoknak nevezik.

A BCH-kódokban a véges testek lényeges szerephez jutnak. (A véges testekre vonatkozó legfontosabb tudnivalókat az A.8 pont tartalmazza.)

Továbbra is n,k és s=kn jelöli a kód dimenzióját, hosszát, illetve az ellenőrző jegyek számát, és valamilyen adott t-vel t-hibajavító kódokat keresünk. Az eddigiekben az n-et tekintettük adottnak, és az s-et az n-hez képest igyekeztünk minimalizálni. Ezen a szemléletmódon egy picit változtatunk, mostantól kezdve k=n+s-t tekintjük rögzítettnek, és így szeretnénk minél kisebb s-et és vele együtt minél nagyobb n-et biztosítani.

Ennek alapján most Tk-ban egy minél nagyobb olyan K alteret keresünk, amelynek az elemei, a kódszavak, legalább 2t+1 távolságra esnek egymástól. Ez a K altér éppen a P paritásellenőrző mátrix magtere. A t-hibajavítás a P oszlopainak megfelelő tulajdonságából olvasható le, tehát a kódot egy megfelelő s×k méretű P mátrix kijelölésével adhatjuk meg. Az s minimalizálása azt jelenti, hogy P-nek minél kevesebb sora legyen.

Tekintsünk el egy pillanatra attól a követelménytől, hogy P sorai lineárisan függetlenek. Ha valamelyik sor függ a többitől, akkor ennek a sornak az elhagyása nyilván nem változtat sem a mátrix magterén, sem pedig az oszlopoknak a hibajavítással kapcsolatos tulajdonságain. Így a sorok számát mindaddig csökkenthetjük, amíg azok már függetlenek lesznek (vö. a 10.3.7 feladattal).

Ennek megfelelően olyan m×k-as Q mátrixokat fogunk megadni, amelyekben bármely legfeljebb t oszlop összege mindig különböző és nemnulla vektort eredményez (azaz bármely 2t oszlop lineárisan független), és m lehetőleg kicsi. Ekkor Q magtere éppen egy t-hibajavító lineáris kód kódszavainak a halmazát definiálja. Ennél a kódnál az ellenőrző jegyek száma s=r(Q)≤m, és egy P paritásellenőrző mátrixot úgy kaphatunk, hogy Q-nak csak s (tetszőlegesen választott) független sorát tartjuk meg. Magát a Q-t nevezhetjük a kód „kvázi-paritásellenőrző mátrixának”.

Mielőtt az általános t-hibajavító BCH-kódokra rátérnénk, nézzük meg külön a t=2 speciális esetet. Ez a tárgyalásmód több előnnyel is jár, ugyanis a BCH-kódok meglehetősen bonyolult konstrukcióját így először mégiscsak egy könnyített változatban kell megértenünk, továbbá a t-hibajavítás bizonyítása is lényegesen egyszerűbb t=2-re, mint az általános esetben.

Legyen q≥3 és k=2q–1. A 10.1.8 feladatból következik, hogy 2-hibajavító kód esetén az ellenőrző jegyek száma szükségképpen s≥2q–1. A 2-hibajavító BCH-kódok lényegében az alsó határt érik el, mert s≤2q-t biztosítanak. (Az is megmutatható, hogy ezeknél mindig pontosan s=2q teljesül.) Látjuk tehát, hogy azonos k mellett a Hamming-kódhoz képest egy 2-hibajavító BCH-kódnál kétszer annyi ellenőrző jegyre van szükség. Ez igen méltányos „ár”, hiszen a nyújtott „szolgáltatás” formálisan nézve is „megduplázódott”, valójában azonban a 2-hibaminták száma sokszorosa az 1-hibamintákénak (k2 , illetve k).

A 2-hibajavító BCH-kódot a(z egyik) P paritásellenőrző mátrixával adjuk meg. Ehhez először egy 2q×k méretű Q kvázi-paritásellenőrző mátrixot definiálunk. Ennek első q sora legyen ugyanaz, mint a Hamming-kódnál, vagyis az oszlopok éppen Tq nemnulla elemei.

A Q alsó q sorának a megadásához a továbbiakban a Tq halmazt új szerepkörben, 2q elemű testként fogjuk tekinteni. Ennek a testnek és a Tq vektortérnek az additív szerkezete megegyezik, ezért nem okoz zavart, ha a testet is Tq-val jelöljük. Legyen Δ a Tq test multiplikatív csoportjának egy generátoreleme, ekkor a Tq test nemnulla elemei felírhatók Δ-nak (a 0-tól a 2q–2 kitevőig terjedő) hatványaiként. A Q felső felében ezek szerint az oszlopok éppen a Δj hatványok, j=0,1,2,…,2q–2.

Ezután a Q mátrix alsó q sorát a következőképpen definiáljuk: az oszlopok alsó fele legyen mindig a felső rész köbe, azaz

(1)

Megmutatjuk, hogy a Q mátrix magtere egy 2-hibajavító kód kódszavait adja. Ehhez azt kell igazolni, hogy Q bármely legfeljebb 2 oszlopának az összege mindig más és más (és nemnulla) vektort eredményez. Ez könnyen láthatóan ekvivalens azzal, hogy az

egyenletrendszernek a_0_ esetén a Tq testben legfeljebb egy megoldása van (x_ és z_ szimmetriájától eltekintve).

Az első egyenletet köbre emelve, majd a második egyenletet ebből levonva x_z_x_+z_=a_3-b_ adódik, vagyis x_z_=a_2-b_/a_  Azt kaptuk, hogy az x_ és z_ elemek összege és szorzata is ismert, és így pl. a gyökök és együtthatók közötti összefüggés alapján x_ és z_ csak egy adott másodfokú egyenlet (egyértelműen meghatározott) gyökei lehetnek (ha ez az egyenlet egyáltalán megoldható a Tq testben).

Mint már említettük, megmutatható, hogy Q rangja 2q (lásd a 10.4.4 feladatot), és így maga a Q lesz ennek a kódnak a(z egyik) paritásellenőrző mátrixa. (Ha nem így lenne, akkor „még jobban járnánk”, hiszen akkor változatlan k=2q–1 mellett 2q-nál kevesebb ellenőrző jeggyel is biztosítani tudnánk a 2-hibajavítást.)

A kapott eredményt az alábbi tételben foglalhatjuk össze:

10.4.1 Tétel

Legyen q≥3,n=2q–2q–1,k=2q–1. A fenti módon az (1) képlettel megadott Q mátrix egy 2-hibajavító lineáris kódot definiál. Ezt a kódot 2-hibajavító BCH-kódnak nevezzük.❶

Példa: Legyen q=4. A 24=16 elemű testben meg kell keresnünk a nemnulla elemek multiplikatív csoportjának egyik generáló elemét. Az ilyen elemek száma ϕ(15)=8. Ezek bármelyike negyedfokú algebrai szám T=F2 felett, tehát egy negyedfokú f irreducibilis polinomnak a gyöke. Mivel f(0)≠0, f(1)≠0, ezért f-ben páratlan sok tag fordul elő, azaz f az alábbi négy polinom valamelyike: x4+x+1, x4+x3+1, x4+x2+1, x4+x3+x2+x+1. A harmadik polinom (x2+x+1)2, tehát nem irreducibilis, a negyedik irreducibilis, azonban osztója az x5–1-nek, tehát a gyökeinek már az ötödik hatványa 1, vagyis azok nem generálhatják a test multiplikatív csoportját. Az első két polinom megfelelő, ezek gyökeiként kapjuk a test multiplikatív csoportjának 8 generáló elemét. Válasszuk mondjuk az első polinom egyik gyökét Δ-nak. Ekkor a T4 vektortér bázisa 1,Δ,Δ23, ezek lesznek most az egységvektorok. A többi hatvány koordinátáit a minimálpolinomból adódó Δ4=1+Δ összefüggés ismételt alkalmazásával számíthatjuk ki. Ennek megfelelően az alábbi 8×15-ös paritásellenőrző mátrixhoz jutunk:

A t-hibajavító BCH-kódokra történő általánosítás a 2-hibajavító mintájára a következőképpen történik. Az eddigiekhez hasonlóan k értéke k=2q–1, az ellenőrző jegyek számára most az stq „méltányos” feltételt szabjuk (itt már az a szerencsés eset is előfordulhat, hogy s a jelzett korlátnál jóval kisebb lesz). A Q „kvázi-paritásellenőrző” mátrix t darab q×k méretű blokkból áll, ahol a felső blokk oszlopai továbbra is Tq nemnulla elemei, az i-edik blokk oszlopai pedig a felső blokkbeli vektoroknak (mint a Tq test elemeinek) a 2i–1-edik hatványai, i=2,3,…,t. (A köbök alatt tehát az ötödik, majd a hetedik hatványok következnek stb.) Ha Q sorai összefüggők, akkor válasszunk ki közülük egy maximális független rendszert, ezek alkotják a kód (egyik) P paritásellenőrző mátrixát. Mindezt pontosan az alábbi tételben mondjuk ki és bizonyítjuk be.

10.4.2. Tétel

Legyen q rögzített pozitív egész, amelyre 2q–1>qt, továbbá k=2q–1, m=tq, Δ a Tq test multiplikatív csoportjának egy generátoreleme és Q az a tq×k-as mátrix, amelynek a j+1-edik oszlopában egymás alatt rendre az alábbi t darab Tq-beli vektor áll: Δj, Δ3j, Δ5j,…,Δ(2t–1)j, azaz

Ekkor Ker Q egy t-hibajavító lineáris kód kódszavait definiálja, ahol az ellenőrző jegyek száma stq. Ezt a kódot t-hibajavító BCH-kódnak nevezzük.❶

A tétel állítása az, hogy az így definiált kód valóban t-hibajavító. Ennek bizonyítása további előkészületeket igényel. Először felelevenítjük a 10.2.8a feladatban bevezetett polinomkód fogalmát. 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. Azonosítsuk a Tn, illetve Tk vektortereket a belőlük a fenti izomorfizmussal létesített Tn[x], illetve Tk[x] vektorterekkel.

10.4.3 Definíció

Legyen g≠0 egy rögzített 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 Az így definiált lineáris kódot polinomkódnak, a g polinomot pedig a kód generáló polinomjának nevezzük.❶

A 10.2.8a feladatban megengedtük a degg<s lehetőséget is, azonban ekkor minden kódszó végén s–degg darab nulla áll, ami semmire sem használható. Így nyilván csak az az eset érdekes, amikor degg=s. Ekkor a kódszavak éppen g többszörösei (polinomszorosai).

Most megmutatjuk, hogy a Hamming-kód és a BCH-kódok is polinomkódok, és meghatározzuk a generáló polinomjaikat.

Tekintsük elsőként a Hamming-kódot. Itt paritásellenőrző mátrixnak vehető az s sorból és k=2s–1 oszlopból álló P=(1ΔΔ2…Δk–1) mátrix. Legyen a c_=γ0γ1γk-1Tk vektornak megfelelő polinom C=γ0+γ1x++γk-1xk-1Tkx A c_ vektor pontosan akkor kódszó, ha Pc_=0_ azaz j=0k-1γjj=0 Ez azt jelenti, hogy a C polinomnak gyöke a Δ, vagyis c_ pontosan akkor kódszó, ha az mΔ minimálpolinom osztója C-nek. Ennek megfelelően a Hamming-kód olyan polinomkód, amelynek a generáló polinomja g=mΔ.

Nézzük most a 2-hibajavító BCH-kódot. Az előzőkhöz hasonlóan adódik, hogy c_ pontosan akkor kódszó, ha mΔ és m3 is osztója a C polinomnak, azaz a generáló polinom most Δ és Δ3 minimálpolinomjának a legkisebb közös többszöröse: g=m,m3 

Ugyanígy adódik az általános eset is:

10.4.4 Tétel

Jelöljük mj-t mj-vel. A 10.4.2 Tételben megadott általános t-hibajavító BCH-kód olyan polinomkód, amelynek a generáló polinomja gt=[m1, m3,…, m2t–1].❶

Ennek alapján a kódban az ellenőrző jegyek száma éppen a gt generáló polinom foka. Így s=tq pontosan akkor teljesül, ha Δ, Δ3,…, Δ2t–1 mindegyike q-adfokú F2 felett és semelyik kettőnek sem ugyanaz a minimálpolinomja (lásd a 10.4.2 feladatot).

Most már minden a rendelkezésünkre áll a 10.4.2 Tétel igazolásához: megmutatjuk, hogy az ott megadott kód valóban t-hibajavító.

A 10.4.2 Tétel bizonyítása: Először belátjuk, hogy bármely i-re mi=m2i. A Tq testben a négyzetre emelés izomorfizmus, amely a T=F2 alaptest elemeit helybenhagyja. Ezért ha ρ0+ρ1Θ+…+ρvΘv=0, akkor ugyanez Θ helyett Θ2-re is teljesül. Ezzel igazoltuk, hogy m2i|mi. A másik irányú oszthatóság pl. abból adódik, hogy Θ-t is megkaphatjuk Θ2-ből ismételt négyzetre emelésekkel.

A fentiek alapján gt=[m1, m2,…, m2t]. Most megmutatjuk, hogy a kódban a minimális távolság legalább 2t+1, amiből a kívánt t-hibajavítás már következik.

Indirekt tegyük fel, hogy lenne egy legfeljebb 2t súlyú c_ kódszó. Az ennek megfelelő C polinom gyökei között szerepel Δi minden i≤2t-re. Írjuk fel ezt a 2t darab Ci)=0 egyenlőséget. Közben a C polinomból esetleg hagyjunk el 0 együtthatókat úgy, hogy pontosan 2t együttható maradjon.

Ekkor C-nek erre a 2t együtthatójára nézve egy 2t×2t-es homogén lineáris egyenletrendszert kaptunk, amelynek van nemtriviális megoldása (éppen C megfelelő együtthatói). Másrészt az egyenletrendszer determinánsa nem nulla, hiszen ez a különböző elemekkel generált Vi1, i2,,i2t Vandermonde-determináns nemnulla konstansszorosa, ahol i1, i2,…, i2t a C polinomban szereplő tagok fokszámai. Ekkor azonban az egyenletrendszernek csak triviális megoldása lehet, ami ellentmondás.❷

Feladatok

A feladatoknál is a szövegben használt jelöléseket alkalmazzuk, tehát s az ellenőrző jegyek száma, k a kód hossza, Δ a 2q elemű véges test multiplikatív csoportjának a(z egyik) generátoreleme, mi a Δi minimálpolinomja stb.

10.4.1 Írjuk fel q=5-re egy 2-hibajavító BCH-kód paritásellenőrző mátrixát.

10.4.2 Mutassuk meg, hogy a q paraméterű t-hibajavító BCH-kódban s=tq pontosan akkor teljesül, ha Δ, Δ3,…, Δ2t–1 mindegyike q-adfokú F2 felett és semelyik kettőnek sem ugyanaz a minimálpolinomja.

M10.4.3 Tekintsünk q>3-ra egy 3-hibajavító BCH-kódot.

a) Határozzuk meg s-et a q=4 esetben.

*b) Mutassuk meg, hogy ha q páratlan, akkor s=3q.

*10.4.4 Bizonyítsuk be, hogy bármely q esetén egy 2-hibajavító BCH-kódban s=2q.

M*10.4.5

a) Igazoljuk, hogy deg mi a legkisebb olyan v pozitív egész, amelyre v|q és (2q–1)/(2v–1)|i.

b) Mutassuk meg, hogy mi összes gyökei a Δ-nak az i·2j kitevőjű hatványai, ahol 0≤j<deg mi.

M*10.4.6 Lássuk be, hogy ha t≤2q/2–1, akkor a q paraméterű t-hibajavító BCH-kódban az s=tq egyenlőség érvényes.

10.4.7 Legyen egy polinomkód generáló polinomja g. Bizonyítsuk be, hogy

a) minden kódszó akkor és csak akkor páros súlyú, ha 1+x|g;

b) minden páros súlyú vektor akkor és csak akkor kódszó, ha g=1+x.

10.4.8 Mutassuk meg, hogy egy BCH-kód generáló polinomja osztója xk–1-nek.

10.4.9 Ciklikusnak nevezzük az olyan lineáris kódokat, amelyeknél a kódszavak ciklikus permutációja is kódszó, tehát (Tk elemeit z_=γ0γ1γ2γk-1 alakban írva) γ0γ1γ2γk-1Kγk-1γ0γ1γk-2K 

M*a) Bizonyítsuk be, hogy a ciklikus kódok lényegében speciális polinomkódokként jellemezhetők: egy kód akkor és csak akkor ciklikus, ha a kódszavainak a halmaza megegyezik egy olyan polinomkód kódszavainak a halmazával, amelynek a g generáló polinomjára g|xk–1 teljesül.

b) Minden BCH-kód ciklikus.

M10.4.10 Tegyük fel, hogy az m<k és d számokra i=0d-2k-1i<2m  Ekkor létezik olyan lineáris kód, amelynek a hossza k, az ellenőrző jegyek száma legfeljebb m és a kódszavak közötti minimális távolság legalább d.

M*10.4.11 Reed-Muller-kódok.

a) Legyen q adott, n=q+1, k=2q és a kód generátormátrixa a következő: soronként rendre a 2q és 2q+1–1 közötti számok kettes számrendszerbeli alakja szerepel. (A q=3 esetre a mátrixot lásd a b) rész után.) Mutassuk meg, hogy ebben a kódban a kódszavak közötti minimális távolság 2q–1. Ezt a kódot elsőrendű Reed-Muller-kódnak nevezzük.

b) Legyen m<q. Az m-edrendű Reed-Muller-kód esetén n=i=0mqi, k=2q  és a generátormátrix a következő: az első q+1 oszlop azonos az elsőrendű esetben látottal, a további oszlopokat pedig úgy kapjuk meg, hogy a 2-odik, 3-adik, ..., q+1-edik oszlop közül minden lehetséges módon kiválasztunk 2, 3, ..., m darabot és ezeket összeszorozzuk a komponensenkénti szorzással. Mutassuk meg, hogy ebben a kódban a kódszavak közötti minimális távolság 2q–m.

Például q=3-ra az első- és másodrendű Reed-Muller-kód generátormátrixai:

Itt G(2,3) utolsó három oszlopa rendre a 2. és 3., a 2. és 4., illetve a 3. és 4. oszlop szorzata.