Informatika | Információelmélet » Visontay Péter - Kódelmélet összefoglaló

Kódelmélet összefoglaló Visontay Péter (sentinel@sch.bmehu) 2002. január 1. Alapfogalmak Kódolás: a k hosszú u üzenetet egy n hosszú c kódszóba képézzük le. Hibák: a csatorna két végén megjelenő c bemeneti és v kimeneti vektorok Hamming távolsága d(c, v) azon i pozı́ciók száma, ahol ci 6= vi . Ez az átküldött üzenet hibáinak száma − Egyszerű hiba: a hiba helye és értéke is ismeretlen. − Törléses hiba: a hiba helye ismert, csak az érték nem. Dekódolás: − Meghatározzuk, hogy a csatorna kimenetén megjelenő jelsorozat melyik kódszónak felelt meg a csatorna bemenetén. − A kódolófüggvény inverzével a kódszóból visszaállı́tjuk az eredeti üzenetet. Hibás detekció: ha a hibák egy kódszót egy másikba visznek át. Kódtávolság: a kód szavai közötti minimális Hamming-táv: dmin = min d(c, c0 ) Hibajelzés: egy dmin kódtávolságú kód.

− dmin − 1 hibát tud jelezni. −1 − b dmin c egyszerű hibát tud javı́tani. 2 − dmin − 1 törléses hibát tud javı́tani. Kód paramétere: ha egy kódolás k hosszú üzeneteket n hosszú kódba képez le, a kód (n, k) paraméterű. Ha dmin értékét ismerjük, a kód (n, k, dmin ) paraméterű Singleton-korlát (1. alak): egy M kódszóból álló, n hosszú és dmin kódtávú kódra (q a kódábécé elemszáma): M ≤ q n−dmin +1 Singleton-korlát (2. alak): egy (n, k) paraméterű kódra a korlát alakja: dmin ≤ n − k + 1 MDS kód: azon kódot, melyre a Singleton-korlátban = áll, maximális távolságú (maximum distance separable) kódnak nevezzük. Hamming-korlát: ha egy (n, k) paraméterű kód t hibát tud javı́tani, akkor ! t X n i=0 i (q − 1)i ≤ q n−k 1 Perfekt kód: olyan kód, melyre a Hamming-korlátban = áll. 2. Bináris lineáris kódok Lineáris kód:

egy C kód lineáris, ha minden c, c0 ∈ C-re c + c0 ∈ C. A 0 vektor minden lineáris kódnak eleme. Generátormátrix: egy C kód generátormátrixa a C lineáris tér egy bázisának vektoraiból (mint sorvektorokból) álló G mátrix. A generátormátrix segı́tségével kódolhatjuk az üzeneteket, azaz ha u = (u1 , u2 , . , uk ), akkor a kódolt üzenet: c = uG Megj.: több generátormátrix is generálhatja ugyanazt a kódszóhalmazt Szisztematikus kód: egy (n, k) paraméterű lineáris kód szisztematikus, ha minden kódszavára igaz, hogy annak utolsó n − k szimbólumát elhagyva éppen a neki megfelelő k hosszú üzenetet kapjuk, azaz kódolás során a k hosszú üzenetet egészı́tjük ki n − k karakterrel. Szisztematikus kód generátormátrixa: G = (Ik , B) ahol Ik a k ×k méretű egységmátrix, B pedig egy k ×(n−k) méretű mátrix (ı́gy G mérete k ×n). Innen a kódszó szerkezete: c

= (u1 , u2 , . , uk , ck+1 , ck+2 , , cn ) Itt a kód első k karaktere az üzenetszegmens, a maradék a paritásszegmens. Paritásmátrix: olyan n − k × n-es H mátrix, melyre HcT = 0 akkor és csak akkor, ha a c ∈ C. (Azaz ezt használjuk annak ellenőrzésére, hogy egy kód helyes-e.) Minden lineáris kódnak van paritásmátrixa Tétel: minden C lineáris kódra igaz, hogy HGT = 0. Paritásmátrix számı́tása: G = (Ik , B) =⇒ H = (−B T , In−k ) Itt a −B-t az adott test (pl. GF (7)) felett kell értelmezni, ı́gy pl bináris esetben −B T = B T ! Vektor súlya: egy c vektor w(c) súlya a koordinátái közt lévő nem nulla elemek száma. Kód minimális súlya: wmin = min w(c) c∈C,c6=0 Tétel: minden lineáris kód kódtávolsága megegyezik a minimális súlyával, azaz dmin = wmin 2 Tétel: minden lineáris kód kódtávolsága egyenlő a paritásmátrixa azon oszlopainak minimális

számával, melyek lineárisan összefüggők. Ortogonális komplemens: egy kód ortogonális komplemense (duálisa) a paritásmátrix mint generátormátrix által képzett kód. Szindróma: s = eH T ahol az e = v − c vektor a hibavektor, a szindrómavektor dimenziója pedig n − k. A szindróma lényege, hogy ha a HcT kiszámı́tásakor nem 0-t kapunk (azaz a vett kódszó hibás), akkor ki tudjuk következtetni, hogy mi a hibavektor, amit a vett kódból kivonva kapjuk meg az eredeti kódszót. Standard elrendezési táblázat: Szindróma s(0) s(1) s(2) . Javı́tható hibaminták e(0) = 0 e(1) e(2) . . c(1) + e(1) c(1) + e(2) . c(1) c(2) + e(1) c(2) + e(2) . . c(2) . . . . . Az első oszlopban felsoroljuk az összes lehetséges szindrómát (q n−k db). A második oszlop felı́rása az sT = HeT egyenlet megoldásával történik (az e-k lesznek a javı́tható hibaminták). Ha több lehetséges megoldás van, akkor a

minimális súlyút kell választani. A táblázat segı́tségével végezhető a táblázatos dekódolás. Példa:   1 0 1 | {z } szindróma   0 0 1 1 1  = 0 1 0 0 1· 1 0 0 1 1 | {z H }   e1 e   2    e3     e4  e5 | {z } hibavektor Megoldás: Az egyenletrendszer megoldásához ki kell választani, hogy a paritásmátrix melyik oszlopainak összege adja ki a szindrómát. A hibavektorban ezen oszlopok i sorszámainak megfelelő ei -k értéke 1, a többié 0. Ez esetben a jó megoldások: (4); (1, 3); (2, 5); (1, 2, 3, 4, 5); hiszen ezen oszlopok összege [1 0 1]T Mivel nekünk a minimális elemszámú megoldás kell, válasszuk az első megoldást, a 4. oszlopot Ez alapján a keresett hibavektor [0 0 0 1 0]T Bináris Hamming-kód: egy hibát tud javı́tani, paritásmátrixa az összes lehetséges n − k hosszú nemnulla oszlopvektorból álló

mátrix. Pl (7,4) paraméterű Hamming-kód:   1 1 0 1 1 0 0  H = 1 0 1 1 0 1 0 0 1 1 1 0 0 1 3 Tétel: a Hamming kód perfekt, és a Hamming korlát alapján igaz rá, hogy 1 + n = 2n−k 3. Nembináris lineáris kódok Véges test: egy q elemszámú testet véges testnek nevezünk és GF (q)-val jelöljük. (Test: értelmezett rajta az összeadás és szorzás.) Tétel: GF (q) esetén q = pm alakú, ahol p prı́m és m ≥ 1. Elem rendje: Minden 0 6= a ∈ GF (q)-ra létezik egy legkisebb m természetes szám, amit az a elem rendjének nevezünk, és melyre am = 1. Primitı́v elem: Egy α ∈ GF (q)-t a GF (q) primitı́v elemének nevezzük, ha α rendje q − 1. Különböző testek primitı́v elemei: GF (q) GF (3) GF (5) GF (7) GF (11) GF (13) Primitı́v elemek 2 2, 3 3, 5 2, 6, 7, 8 2, 6, 7, 11 Nembináris kód: hasonlóan értelmezett és generált, mint a bináris kódok, de értékkészlete egy GF

(q) test elemeiből kerül ki. Nembináris Hamming-kód: egy hibát tud javı́tani. A paritásmátrix oszlopai mind különbözőek, nincs köztük nullvektor, és az első nem nulla elem minden oszlopban 1. Példa: az (n, n − 2) paraméterű Hamming-kód (ez MDS kód): H= ’ 1 1 1 α 1 α2 . . 1 αn−3 1 0 0 1 “ Itt α egy nem 0 elem, és a hatványozások a GF (q) test felett értelmezettek! (Azaz pl. 32 = 2 mod 7) Tétel: a maximális hosszú nembináris Hamming-kód perfekt, és a Hamming korlát alapján igaz rá, hogy 1 + n(q − 1) = q n−k Véges test feletti polinomok: a(x) = a0 + a1 x + . + am xm GF (q) feletti n-edfokú polinom, ha ai , x ∈ GF (q) és am 6= 0 A polinom fokszáma deg a(x). Műveletek véges test feletti polinomokkal: − Összeadás: az azonos fokú együtthatókat összeadjuk. − Szorzás: minden tagot minden taggal szorzunk, majd az azonos fokú tagokat csoportosı́tjuk. A műveletek

elvégzése után a tagoknak venni kell a q-val vett osztási maradékát. Pl. 15x2 + 9x = x2 + 2x mod 7 4 Euklideszi osztás polinomokra: a(x) = q(x)d(x) + r(x) Ha nincs maradék, d(x) | a(x) (d(x) osztója a(x)-nek) Reed-Solomon kód: lineáris kód, kódtávolsága dmin = n − k + 1 (MDS kód). Megjegyzés: ha t és n meg van adva egy feladatban, de k nincs, akkor használhatjuk a 2t = n − k összefüggést. Primitı́v (szóhosszú) Reed-Solomon kód: olyan, GF (q) feletti RS-kód, melynek kódszóhosszára igaz, hogy n = q − 1. Reed-Solomon kód 1. konstrukció: Legyenek α0 , α1 , . , αn−1 a GF (q) különböző elemei, és u = (u0 , , uk−1 ), amelyhez az u(x) = u0 + u1 x + . + uk−1 xk−1 üzenetpolinomot rendeljük Ekkor a kódszó előállı́tása: c0 = u(α0 ), c1 = u(α1 ), .     G= 1 α0 . . 1 α1 1 α2 . . . . α0k−1 α1k−1 α2k−1 . 1  αn−1    .  .

k−1 αn−1 Reed-Solomon kód 2. konstrukció: Legyen α a GF (q) egy nem 0 eleme, melynek rendje m ≥ n és az 1. konstrukcióban legyen αi = α i :   1 1 1 . 1   α α2 . αn−1 1  1  2 4 2(n−1) α α . α G=   .  . . . . .  (n−1)(k−1) 2(k−1) k−1 . α α 1 α Reed-Solomon kód 3. konstrukció: A c vektorhoz rendeljük a c(x) = c0 + c1 x + · · · + cn−1 xn−1 polinomot. Ha az α elem rendje m ≥ n, akkor a kód definı́ciója: C = {c : c(αi ) = 0, i = 1, 2, . , n − k} ≡ {c : HcT = 0}  1 α 2 1 α  H =  . . 1 αn−k α2 α4 α2(n−k) . . . . . αn−1 α2(n−1) . . α(n−k)(n−1)      Nem rövidı́tett Reed-Solomon kód: ha a 3. konstrukcióban m = n, azaz a generáló elem rendje megegyezik a kódszóhosszal. Ilyenkor a 3 és a 2 konstrukció megegyezik Rövidı́tett Reed-Solomon kód: ha a 3. konstrukcióban m > n Reed-Solomon kódok

dekódolása: Bonyolult, lásd TK243. . 4. Aritmetika GF (pm )-ben 5 Irreducı́bilis polinom: GF (p) feletti, nem nulladfokú P (x) polinom irreducı́bilis, ha nem bontható fel két, nála alacsonyabb fokú GF (p) feletti polinom szorzatára. Bináris esetben irreducı́bilis polinomok: Néhány példa: x2 + x + 1; x3 + x + 1; x5 + x2 + 1; x4 + x + 1; x6 + x + 1; x7 + x3 + 1; . GF (pm ) − GF (p) konverzió Legyen p prı́m, P (x) egy GF (p) feletti irreducı́bilis polinom és Q = {0, 1, . , pm − 1} Q két kiválasztott elemének (a és b) kölcsönösen egyértelműen feleltessünk meg egy-egy GF (p) feletti, legfeljebb (m − 1)-edfokú polinomot. − a + b legyen az a c ∈ Q, melynek megfelelő c(x)-re c(x) = a(x) + b(x). − a · b legyen az a d ∈ Q, melynek megfelelő d(x)-re d(x) = a(x) · b(x) mod P (x). Ezzel az aritmetikával Q egy GF (pm ). GF (22 )-beli aritmetika: P (x) = x2 + x + 1 Testelem Polinom 0 0 1 1 2 x 3 x+1 GF

(22 )-beli műveletek: Összeadás: koordinátánkénti (átvitel nélküli) bináris összeadás, pl. 11 + 01 = 10 Szorzás: a két számnak megfelelő polinomokat összeszorozzuk és vesszük a szorzat P (x) szerinti osztási maradékát, pl. 3 · 3 = (x + 1)(x + 1) = x2 + 2x + 1 = x2 + 1 = x mod (x2 + x + 1) GF (22 ) GF (2) műveleti táblái a fentiek alapján felı́rva: + 0 1 2 3 0 0 1 2 3 1 1 0 3 2 2 2 3 0 1 ∗ 0 1 2 3 3 3 2 1 0 0 0 0 0 0 1 0 1 2 3 2 0 2 3 1 3 0 3 1 2 5. Ciklikus kódok Ciklikus eltolás: Egy c = (c0 , c1 , . , cn−1 ) vektor ciklikus eltoltja az Sc = (cn−1 , c0 , , cn−2 ) Ciklikus kód: olyan kód, amiben bármely kódszó ciklikus eltoltja is kódszó. Kód(szó)polinom: a c = (c0 , c1 , . , cn−1 ) kódszóhoz rendelt c(x) = c0 + c1 x + · · · + cn−1 xn−1 polinom. 6 Generátorpolinom: minden (n, k) paraméterű, ciklikus, lineáris kódban a nem azonosan 0 kódpolinomok között

egyértelműen létezik egy minimális fokszámú g(x) főpolinom. Egy c ∈ C akkor és csak akkor, ha g(x) | c(x), azaz létezik egy u(x) üzenetpolinom úgy, hogy c(x) = g(x)u(x). Tétel: a generátorpolinom fokszáma n − k. Tétel: ciklikus, lineáris kód generátorpolinomára g(x) | xn − 1. Generátorpolinom generátormátrixa (1. módszer):  g0  0  G =  .  . 0 g1 g0 . . g2 g1 . . . gn−k−1 . gn−k−2 . . 0 0 . 1 gn−k−1 . . 0 1 . . . . . . 0 0 . . g0 g1 . gn−k−1 0  0 0  1   gn−k = 1 minden sorban, mert g(x) főpolinom (= legmagasabb fokú tagjának együtthatója 1). Megj.: ez a felı́rás nem szisztematikus! Generátorpolinom generátormátrixa (2. módszer, szisztematikus generálás): G első k oszlopa az Ik egységmátrix lesz, a maradék n − k × k elem kitöltése: 1. Kiszámı́tjuk az [x(n−k)+i mod g(x)] maradékpolinomokat i = 0, 1, , k − 1-re Pl.

x5 = x2 (1 + x + x3 ) − x2 (1 + x) = x2 (1 + x) = 1 + x + x2 mod (1 + x + x3 ) 2. Az ezen polinomokhoz tartozó vektorokat (pl x2 + x =⇒ [1 1 0]) beı́rjuk a generátormátrix üres soraiba (lentről felfelé haladva). Paritásellenőrző polinom: egy g(x) generátorpolinomú lineáris, ciklikus kód esetén h(x) = xn − 1 g(x) Tétel: lineáris, ciklikus kód esetén c(x) akkor és csak akkor kódszó, ha mod (xn − 1) c(x)h(x) = 0 Ciklikus Reed-Solomon kód: A 3-as RS-kód konstrukcióban legyen az n kódszóhossz egyenlő az α elem m rendjével (nem rövidı́tett RS-kód). Ekkor a kód ciklikus és generátorpolinoma, valamint paritásellenőrző polinoma: gCRS (x) = n−k Y i=1 hCRS (x) = n Y (x − αi ) (x − αi ) i=n−k+1 CRC kód: generátorpolinomával megadott bináris, ciklikus kód, melyet a generátorpolinom szerinti maradékos osztással, szisztematikusan generálnak. (Lásd TK219, 418 tétel) 5. Vegyes

kódok 7 BCH-kód: az n = q m − 1 kódszóhosszú, GF (q) feletti kódot t hibát javı́tó BCH-kódnak nevezzük, ha a g(x) generátorpolinomjának gyökei az αi ∈ GF (q m ), i = 1, 2, . , 2t testelemek BCH-kód generátorpolinoma: lásd TK232. BSC(p) csatorna: p valószı́nűséggel elrontja a bitet, 1 − p valószı́nűséggel hiba nélkül átviszi. Rövidı́tett kód: egy C(n, k) kód azon kódszavai által alkotott C(n − i, k − i) kód, melyeket a kód az i darab 0-val kezdődő üzenetekhez rendel. Páros paritásbit (egyszerű paritásbit): a kódszó végére illesztett bit, mely a kódszó 1eseinek számát párosra egészı́ti ki. Paraméterek: C(n, k, d) =⇒ C 0 (n + 1, k, d0 ) Ha d páros: d0 = d; ha d páratlan: d0 = d + 1.     HC 0 =    1 1 1 HC ···  1  0 .  .  0 0 Páratlan paritásbit: a kódszó végére illesztett bit, mely a kódszó

1-eseinek számát páratlanra egészı́ti ki. Paraméterek: C(n, k, d) =⇒ C 0 (n + 1, k, d0 ) Ha d páros: d0 = d + 1; ha d páratlan: d0 = d. Kódátfűzés: egy C(n, k, d) kód m db n hosszú kódszavát egy m × n-es mátrixba rendezzük soronként, majd a mátrix oszlopait sorrendben kiolvasva kapjuk a C m = C(mn, mk, d) kódot. Hibacsomó: a hibavektor egy l hosszúságú szegmense hibacsomó, ha a szegmens első és utolsó karaktere nem zérus. Tétel: ha g(x) a C kód generátorpolinoma, akkor g(xm ) a C m kód generátorpolinoma. Tétel: A C m átfűzéses kód m · t hosszú hibacsomót javı́t (t a C kód hibajavı́tó képessége) Hibacsomójavı́tó képesség: egy C(n, k) lineáris kód l hibacsomójavı́tó képességére fennáll, hogy l ≤ b n−k 2 c. Reiger-optimalitás: ha egy kód hibacsomójavı́tó képességére igaz, hogy l = b n−k 2 c, a kód Reiger-optimális. Szorzatkód: egy C1

(n1 , k1 , d1 ) és egy C2 (n2 , k2 , d2 ) lineáris kód felhasználásával egy C1 × C2 (n1 n2 , k1 k2 , d1 d2 ) kódot hozunk létre. Szorzatkód generátormátrixa: lásd TK238. 6. Transzformációs kódolás 8 Transzformációs kódolás: a Reed-Solomon kódok Fourier-transzformációt felhasználó kódolási módszere. Paraméterek: legyen GF (q) = GF (pm ), ahol p prı́m; α pedig legyen GF (q) egy n-edrendű eleme (n a kódszóhossz). Üzenet trafókódolása: 1. Az u = (u0 , u1 , , uk−1 ) kódszó elé teszünk n − k darab 0-t, ı́gy kapjuk meg az n hosszú spektrumot: C = (0, 0, . , 0, u0 , u1 , , uk−1 ) | {z n−k } 2. A spektrumon elvégezzük az inverz Fourier-transzformációt: ci = f (n) n−1 X α−ij Cj j=0 3. Az ı́gy kapott c = (c0 , c1 , , cn ) a transzformációs kódolású kódszó f (n) számı́tása: − Legyen a−1 az a inverze GF (p) fölött, azaz a · a−1 = 1

mod p Pl. 3−1 = 5 mod 7, mert 3 · 5 = 15 = 1 mod 7 − Ekkor f (n) = (n mod p)−1 − Bináris esetben f (n) = 1 − Ha α primitı́v eleme GF (q)-nak, akkor f (n) = (p − 1)−1 mod p 7. Konvolúciós kódolás A konvolúciód kódolás alapelve: a forrás bitfolyama k bites üzenetkeretekre van osztva. A kódoló m üzenetkeretet tárol léptetőregiszterben (időegység alatt 1 keretet léptetünk be a regiszterbe, a legrégebbi keretet pedig eldobjuk). Minden időegység alatt az éppen bejövő új keret és a tárolt m keret alapján a kódoló kiszámol egy n bit hosszúságú kódszókeretet, ami a kódoló kimenetén megjelenik. Ezen kódolás eredménye egy fa-kód Kódsebesség: R = nk Kényszerhossz: K = (m + 1)k Blokkhossz: N = (m + 1)n Konvolúciós kód: egy (n, k) fa-kódot, ha lineáris, invariáns és véges kényszerhosszú, (N, K) konvolúciós kódnak hı́vunk. Kibővı́tett bináris fa

reprezentáció: a fa csomópontjaiból két irányba léphetünk a kódolandó üzenetbitnek megfelelően. A fa éleit azon bit n-essel cı́mkézzük meg, amely a kódoló kimenetén megjelenik az aktuális üzenetbit belépésének hatására. A gyökértől a fa élei mentén a fa leveleiig vezető utak egy-egy kódszónak felelnek meg. A csomópontokat állapotokkal cı́mkézzük meg (az állapotkódnak érdemes a shiftregiszterben éppen eltárolt biteket megfeleltetni.) Állapotátmenet-gráf: az előbbi fa reprezentáció állapotkódjai lesznek a csomópontok 9 (állapotok), melyek mindegyikéből két nyı́l vezet másik állapotokba. Az él i/jk formában cı́mkézett, ahol i az üzenetbit, jk pedig a kimeneten megjelenő bitek. Trellis ábrázolás: a fa-ábrázoláshoz hasonló, de az egy mélységben lévő azonos állapotokat összevonjuk. Az egymást követő élek utakat alkotnak,

amelyek mindegyike a 00 állapotból indul, és oda is fut be végül. A kódoló kétféle leı́rása (példa): Lineáris kombinációk x2i−1 = ui + ui−2 x2i = ui + ui−1 + ui−2 Ekvivalens generátorpolinomok g1 (x) = 1 + x2 g2 (x) = 1 + x + x2 Generátorpolinom-mátrix: általános esetben a gij (x) az üzenetkeret i-edik bitje és a kódkeret j-edik bitje közti összefüggést ı́rja le. Ekkor a generátorpolinomokat mátrixba rendezhetjük: G(x) = [gij (x)] Katasztrofális kód: egy konvolúciós kód katasztrofális, ha tetszőlegesen nagy Hamming-súlyú input-sorozat esetén korlátos Hamming-súlyú marad az output. Tétel: egy kód akkor és csak akkor katasztrofális, ha állapotgráfjában létezik egy hurok, amelyet alkotó valamennyi élen a kódszókeretek 0 súlyúak. i -edik minimális távolság: a legkisebb Hamming-táv az output sorozatok első i kódszókeret hosszú (i · n bit) szegmense

között. Jelölése: d∗i Távolságprofil: d∗1 , d2∗ , d∗3 , . Szabad távolság: df ree = d∞ = max d∗i Viterbi-dekódolás: a konvolúciós kódok maximum-likelihood dekódolására optimalizált algoritmus. Lásd TK270 Leágazó kódszavak: Legyen a(d, i) a trellis-ábrázoláson a zéró kódszónak megfelelő útból az 1. csomópontban leágazó azon utak darabszáma, amelyek d Hamming-távolságra vannak és i súlyú üzenetekhez tartoznak. T(D,I) meghatározása: − Állapotgráf átrajzolása: 00 állapot felbontása A és B állapotokká. − Élek felcı́mkézése I j Dk alakú cı́mkékkel, ahol j az üzenetbit, és k az élhez tartozó kimenet Hamming-súlya. − Egyenletrendszer felı́rása a csomópontokra, a pontba bemenő élek összegzésével (pl. X = ID2 A + IZ). − B = T (D, I) · A felhasználásával T (D, I) kiszámı́tása. 10