K´ odelm´ elet ¨ osszefoglal´ o Visontay P´eter (
[email protected]) 2002. janu´ ar
1. Alapfogalmak K´ odol´ as: a k hossz´ uuu ¨zenetet egy n hossz´ u c k´odsz´oba k´ep´ezz¨ uk le. Hib´ ak: a csatorna k´et v´eg´en megjelen˝o c bemeneti ´es v kimeneti vektorok Hamming t´avols´ aga d(c, v) azon i poz´ıci´ ok sz´ama, ahol ci 6= vi . Ez az ´atk¨ uld¨ott u ¨zenet hib´ainak sz´ama. − Egyszer˝ u hiba: a hiba helye ´es ´ert´eke is ismeretlen. orl´eses hiba: a hiba helye ismert, csak az ´ert´ek nem. − T¨ Dek´ odol´ as: − Meghat´arozzuk, hogy a csatorna kimenet´en megjelen˝o jelsorozat melyik k´odsz´onak felelt meg a csatorna bemenet´en. − A k´odol´of¨ uggv´eny inverz´evel a k´odsz´ob´ol vissza´all´ıtjuk az eredeti u ¨zenetet. Hib´ as detekci´ o: ha a hib´ak egy k´odsz´ot egy m´asikba visznek ´at. otti minim´alis Hamming-t´av: K´ odt´ avols´ ag: a k´od szavai k¨oz¨ dmin = min d(c, c0 ) odt´ avols´ ag´ u k´od. . . Hibajelz´ es: egy dmin k´ − dmin − 1 hib´at tud jelezni. −1 − b dmin c egyszer˝ u hib´at tud jav´ıtani. 2 − dmin − 1 t¨orl´eses hib´at tud jav´ıtani. as k hossz´ uu ¨zeneteket n hossz´ u k´odba k´epez le, a k´od (n, k) K´ od param´ etere: ha egy k´odol´ param´eter˝ u. Ha dmin ´ert´ek´et ismerj¨ uk, a k´od (n, k, dmin ) param´eter˝ u. Singleton-korl´ at (1. alak): egy M k´odsz´ob´ol ´all´o, n hossz´ u ´es dmin k´odt´av´ u k´odra (q a k´od´ab´ec´e elemsz´ama): M ≤ q n−dmin +1 Singleton-korl´ at (2. alak): egy (n, k) param´eter˝ u k´odra a korl´at alakja: dmin ≤ n − k + 1 MDS k´ od: azon k´odot, melyre a Singleton-korl´atban = ´all, maxim´ alis t´ avols´ ag´ u (maximum distance separable) k´odnak nevezz¨ uk. u k´od t hib´at tud jav´ıtani, akkor Hamming-korl´ at: ha egy (n, k) param´eter˝ ! t X n i=0
i
(q − 1)i ≤ q n−k 1
Perfekt k´ od: olyan k´od, melyre a Hamming-korl´atban = ´all.
2. Bin´aris line´aris k´odok Line´ aris k´ od: egy C k´ od line´aris, ha minden c, c0 ∈ C-re c + c0 ∈ C. A 0 vektor minden line´aris k´odnak eleme. ol Gener´ atorm´ atrix: egy C k´ od gener´atorm´atrixa a C line´aris t´er egy b´azis´anak vektoraib´ (mint sorvektorokb´ ol) ´all´ o G m´atrix. A gener´atorm´atrix seg´ıts´eg´evel k´odolhatjuk az u ¨zeneteket, azaz ha u = (u1 , u2 , . . . , uk ), akkor a k´odolt u ¨zenet: c = uG Megj.: t¨obb gener´atorm´ atrix is gener´alhatja ugyanazt a k´odsz´ohalmazt. Szisztematikus k´ od: egy (n, k) param´eter˝ u line´aris k´od szisztematikus, ha minden k´odszav´ ara igaz, hogy annak utols´o n − k szimb´ olum´at elhagyva ´eppen a neki megfelel˝o k hossz´ uu ¨zenetet uu ¨zenetet eg´esz´ıtj¨ uk ki n − k karakterrel. kapjuk, azaz k´odol´ as sor´an a k hossz´ Szisztematikus k´ od gener´ atorm´ atrixa: G = (Ik , B) u egys´egm´ atrix, B pedig egy k ×(n−k) m´eret˝ u m´atrix (´ıgy G m´erete k ×n). ahol Ik a k ×k m´eret˝ Innen a k´odsz´ o szerkezete: c = (u1 , u2 , . . . , uk , ck+1 , ck+2 , . . . , cn ). Itt a k´od els˝o k karaktere az u ¨ zenetszegmens, a marad´ek a parit´ asszegmens. Parit´ asm´ atrix: olyan n − k × n-es H m´atrix, melyre HcT = 0 akkor ´es csak akkor, ha a c ∈ C. (Azaz ezt haszn´aljuk annak ellen˝orz´es´ere, hogy egy k´od helyes-e.) Minden line´aris k´odnak van parit´asm´atrixa. T´ etel: minden C line´aris k´odra igaz, hogy HGT = 0. Parit´ asm´ atrix sz´ am´ıt´ asa: G = (Ik , B) =⇒ H = (−B T , In−k ) Itt a −B-t az adott test (pl. GF (7)) felett kell ´ertelmezni, ´ıgy pl. bin´aris esetben −B T = B T ! Vektor s´ ulya: egy c vektor w(c) s´ ulya a koordin´at´ai k¨ozt l´ev˝o nem nulla elemek sz´ama. K´ od minim´ alis s´ ulya: wmin = min w(c) c∈C,c6=0
T´ etel: minden line´aris k´od k´odt´ avols´aga megegyezik a minim´alis s´ uly´aval, azaz dmin = wmin 2
avols´aga egyenl˝o a parit´asm´atrixa azon oszlopainak minim´alis T´ etel: minden line´aris k´od k´odt´ sz´am´aval, melyek line´arisan ¨osszef¨ ugg˝ok. Ortogon´ alis komplemens: egy k´od ortogon´alis komplemense (du´alisa) a parit´asm´atrix mint gener´atorm´atrix ´altal k´epzett k´od. Szindr´ oma: s = eH T ahol az e = v − c vektor a hibavektor, a szindr´omavektor dimenzi´oja pedig n − k. A szindr´oma l´enyege, hogy ha a HcT kisz´am´ıt´asakor nem 0-t kapunk (azaz a vett k´odsz´o hib´as), akkor ki tudjuk k¨ovetkeztetni, hogy mi a hibavektor, amit a vett k´odb´ol kivonva kapjuk meg az eredeti k´odsz´ ot. Standard elrendez´ esi t´ abl´ azat: Szindr´ oma (0) s s(1) s(2) ...
Jav´ıthat´ o hibamint´ ak (0) e =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˝o oszlopban felsoroljuk az ¨osszes lehets´eges szindr´om´at (q n−k db). A m´asodik oszlop fel´ır´asa az sT = HeT egyenlet megold´as´aval t¨ort´enik (az e-k lesznek a jav´ıthat´o hibamint´ak). Ha t¨obb lehets´eges megold´as van, akkor a minim´alis s´ uly´ ut kell v´alasztani. A t´abl´azat seg´ıts´eg´evel v´egezhet˝o a t´abl´ azatos dek´odol´ as. P´ elda:
1 0 1
| {z }
szindr´oma
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´ as: Az egyenletrendszer megold´as´ ahoz ki kell v´alasztani, hogy a parit´asm´atrix melyik oszlopainak ¨osszege adja ki a szindr´om´ at. A hibavektorban ezen oszlopok i sorsz´amainak megfelel˝o ei -k ´ert´eke 1, a t¨obbi´e 0. Ez esetben a j´o megold´asok: (4); (1, 3); (2, 5); (1, 2, 3, 4, 5); hiszen ezen oszlopok ¨osszege [1 0 1]T Mivel nek¨ unk a minim´alis elemsz´am´ u megold´as kell, v´alasszuk az els˝o megold´ast, a 4. oszlopot. Ez alapj´an a keresett hibavektor [0 0 0 1 0]T Bin´ aris Hamming-k´ od: egy hib´at tud jav´ıtani, parit´asm´atrixa az ¨osszes lehets´eges n − k hossz´ u nemnulla oszlopvektorb´ ol ´all´ o m´atrix. Pl. (7,4) param´eter˝ u Hamming-k´od:
1 1 0 1 1 0 0 H = 1 0 1 1 0 1 0 0 1 1 1 0 0 1 3
T´ etel: a Hamming k´od perfekt, ´es a Hamming korl´at alapj´an igaz r´a, hogy 1 + n = 2n−k
3. Nembin´aris line´aris k´odok am´ u testet v´eges testnek nevez¨ unk ´es GF (q)-val jel¨olj¨ uk. V´ eges test: egy q elemsz´ (Test: ´ertelmezett rajta az ¨osszead´ as ´es szorz´as.) u, ahol p pr´ım ´es m ≥ 1. T´ etel: GF (q) eset´en q = pm alak´ Elem rendje: Minden 0 6= a ∈ GF (q)-ra l´etezik egy legkisebb m term´eszetes sz´am, amit az a elem rendj´enek nevez¨ unk, ´es melyre am = 1. Primit´ıv elem: Egy α ∈ GF (q)-t a GF (q) primit´ıv elem´enek nevezz¨ uk, ha α rendje q − 1. K¨ ul¨ onb¨ oz˝ o 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´ aris k´ od: hasonl´oan ´ertelmezett ´es gener´alt, mint a bin´aris k´odok, de ´ert´ekk´eszlete egy GF (q) test elemeib˝ol ker¨ ul ki. Nembin´ aris Hamming-k´ od: egy hib´at tud jav´ıtani. A parit´asm´atrix oszlopai mind k¨ ul¨onb¨oz˝oek, nincs k¨ozt¨ uk nullvektor, ´es az els˝o nem nulla elem minden oszlopban 1. P´elda: az (n, n − 2) param´eter˝ u Hamming-k´od (ez MDS k´od): H=
1 1 1 α
1 α2
... ...
1 αn−3
1 0 0 1
asok a GF (q) test felett ´ertelmezettek! Itt α egy nem 0 elem, ´es a hatv´anyoz´ (Azaz pl. 32 = 2 mod 7) T´ etel: a maxim´alis hossz´ u nembin´ aris Hamming-k´od perfekt, ´es a Hamming korl´at alapj´an igaz r´a, hogy 1 + n(q − 1) = q n−k V´ eges test feletti polinomok: a(x) = a0 + a1 x + . . . + am xm GF (q) feletti n-edfok´ u polinom, ha ai , x ∈ GF (q) ´es am 6= 0. A polinom foksz´ama deg a(x). M˝ uveletek v´ eges test feletti polinomokkal: ¨ − Osszead´ as: az azonos fok´ u egy¨ utthat´okat ¨osszeadjuk. − Szorz´as: minden tagot minden taggal szorzunk, majd az azonos fok´ u tagokat csoportos´ıtjuk. A m˝ uveletek elv´egz´ese ut´an a tagoknak venni kell a q-val vett oszt´asi marad´ek´at. Pl. 15x2 + 9x = x2 + 2x mod 7 4
Euklideszi oszt´ as polinomokra: a(x) = q(x)d(x) + r(x) Ha nincs marad´ek, d(x) | a(x) (d(x) oszt´oja a(x)-nek) Reed-Solomon k´ od: line´aris k´od, k´odt´avols´aga dmin = n − k + 1 (MDS k´od). Megjegyz´es: ha t ´es n meg van adva egy feladatban, de k nincs, akkor haszn´alhatjuk a 2t = n − k ¨osszef¨ ugg´est. Primit´ıv (sz´ ohossz´ u) Reed-Solomon k´ od: olyan, GF (q) feletti RS-k´od, melynek k´odsz´ohossz´ ara igaz, hogy n = q − 1. Reed-Solomon k´ od 1. konstrukci´ o: Legyenek α0 , α1 , . . . , αn−1 a GF (q) k¨ ul¨onb¨oz˝o elemei, ´es u = (u0 , . . . , uk−1 ), amelyhez az ¨zenetpolinomot rendelj¨ uk. Ekkor a k´odsz´o el˝o´all´ıt´asa: u(x) = u0 + u1 x + . . . + uk−1 xk−1 u 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´ od 2. konstrukci´ o: Legyen α a GF (q) egy nem 0 eleme, melynek rendje m ≥ n ´es az 1. konstrukci´oban 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´ od 3. konstrukci´ o: uk a c(x) = c0 + c1 x + · · · + cn−1 xn−1 polinomot. Ha az α elem rendje A c vektorhoz rendelj¨ m ≥ n, akkor a k´od defin´ıci´ oja: 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¨ ovid´ıtett Reed-Solomon k´ od: ha a 3. konstrukci´oban m = n, azaz a gener´al´o elem rendje megegyezik a k´odsz´ ohosszal. Ilyenkor a 3. ´es a 2. konstrukci´o megegyezik. R¨ ovid´ıtett Reed-Solomon k´ od: ha a 3. konstrukci´oban m > n. Reed-Solomon k´ odok dek´ odol´ asa: Bonyolult, l´ asd TK243. ...
4. Aritmetika GF (pm )-ben 5
Irreduc´ıbilis polinom: GF (p) feletti, nem nulladfok´ u P (x) polinom irreduc´ıbilis, ha nem bonthat´o fel k´et, n´ala alacsonyabb fok´ u GF (p) feletti polinom szorzat´ara. Bin´ aris esetben irreduc´ıbilis polinomok: N´eh´ any p´elda: x2 + x + 1;
x3 + x + 1;
x5 + x2 + 1;
x4 + x + 1;
x6 + x + 1;
x7 + x3 + 1;
...
GF (pm ) −→ GF (p) konverzi´ o Legyen p pr´ım, P (x) egy GF (p) feletti irreduc´ıbilis polinom ´es Q = {0, 1, . . . , pm − 1}. Q k´et kiv´alasztott elem´enek (a ´es b) k¨olcs¨ on¨ osen egy´ertelm˝ uen feleltess¨ unk meg egy-egy GF (p) feletti, legfeljebb (m − 1)-edfok´ u polinomot. − a + b legyen az a c ∈ Q, melynek megfelel˝o c(x)-re c(x) = a(x) + b(x). − a · b legyen az a d ∈ Q, melynek megfelel˝o d(x)-re d(x) = a(x) · b(x) mod P (x). Ezzel az aritmetik´aval Q egy GF (pm ). GF (22 )-beli aritmetika: P (x) = x2 + x + 1 Testelem Polinom 0 0 1 1 2 x 3 x+1 uveletek: GF (22 )-beli m˝ ¨ Osszead´ as: koordin´at´ ank´enti (´atvitel n´elk¨ uli) bin´aris ¨osszead´as, pl. 11 + 01 = 10 uk a szorzat P (x) szerinti Szorz´ as: a k´et sz´amnak megfelel˝o polinomokat ¨osszeszorozzuk ´es vessz¨ oszt´asi marad´ek´ at, pl. 3 · 3 = (x + 1)(x + 1) = x2 + 2x + 1 = x2 + 1 = x mod (x2 + x + 1) GF (22 ) → GF (2) m˝ uveleti t´ abl´ ai a fentiek alapj´an 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´odok Ciklikus eltol´ as: Egy c = (c0 , c1 , . . . , cn−1 ) vektor ciklikus eltoltja az Sc = (cn−1 , c0 , . . . , cn−2 ) Ciklikus k´ od: olyan k´od, amiben b´armely k´odsz´o ciklikus eltoltja is k´odsz´o. K´ od(sz´ o)polinom: a c = (c0 , c1 , . . . , cn−1 ) k´odsz´ohoz rendelt c(x) = c0 + c1 x + · · · + cn−1 xn−1 polinom. 6
Gener´ atorpolinom: minden (n, k) param´eter˝ u, ciklikus, line´aris k´odban a nem azonosan 0 k´odpolinomok k¨oz¨ ott egy´ertelm˝ uen l´etezik egy minim´alis foksz´am´ u g(x) f˝opolinom. Egy c ∈ C akkor ´es csak akkor, ha g(x) | c(x), azaz l´etezik egy u(x) u ¨zenetpolinom u ´gy, hogy c(x) = g(x)u(x). T´ etel: a gener´atorpolinom foksz´ama n − k. T´ etel: ciklikus, line´aris k´od gener´atorpolinom´ara g(x) | xn − 1. Gener´ atorpolinom gener´ atorm´ atrixa (1. m´ odszer):
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
u tagj´anak egy¨ utthat´oja 1). gn−k = 1 minden sorban, mert g(x) f˝opolinom (= legmagasabb fok´ Megj.: ez a fel´ır´ as nem szisztematikus! Gener´ atorpolinom gener´ atorm´ atrixa (2. m´ odszer, szisztematikus gener´ al´ as): G els˝o k oszlopa az Ik egys´egm´ atrix lesz, a marad´ek n − k × k elem kit¨olt´ese: 1. Kisz´am´ıtjuk az [x(n−k)+i mod g(x)] marad´ekpolinomokat 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´o vektorokat (pl. x2 + x =⇒ [1 1 0]) be´ırjuk a gener´atorm´atrix u ¨res soraiba (lentr˝ ol felfel´e haladva). Parit´ asellen˝ orz˝ o polinom: egy g(x) gener´atorpolinom´ u line´aris, ciklikus k´od eset´en h(x) =
xn − 1 g(x)
T´ etel: line´aris, ciklikus k´od eset´en c(x) akkor ´es csak akkor k´odsz´o, ha mod (xn − 1)
c(x)h(x) = 0
Ciklikus Reed-Solomon k´ od: A 3-as RS-k´od konstrukci´ oban legyen az n k´odsz´ohossz egyenl˝o az α elem m rendj´evel (nem r¨ovid´ıtett RS-k´od). Ekkor a k´od ciklikus ´es gener´atorpolinoma, valamint parit´asellen˝orz˝o polinoma: gCRS (x) =
n−k Y i=1
hCRS (x) =
n Y
(x − αi ) (x − αi )
i=n−k+1
CRC k´ od: gener´atorpolinom´aval megadott bin´aris, ciklikus k´od, melyet a gener´atorpolinom szerinti marad´ekos oszt´assal, szisztematikusan gener´alnak. (L´ asd TK219, 4.18. t´etel.)
5. Vegyes k´odok 7
BCH-k´ od: az n = q m − 1 k´odsz´ ohossz´ u, GF (q) feletti k´odot t hib´at jav´ıt´o BCH-k´odnak nevezz¨ uk, ha a g(x) gener´atorpolinomj´anak gy¨okei az αi ∈ GF (q m ), i = 1, 2, . . . , 2t testelemek. BCH-k´ od gener´ atorpolinoma: l´ asd TK232. us´eggel hiba n´elk¨ ul ´atviszi. BSC(p) csatorna: p val´ osz´ın˝ us´eggel elrontja a bitet, 1 − p val´osz´ın˝ R¨ ovid´ıtett k´ od: egy C(n, k) k´od azon k´odszavai ´altal alkotott C(n − i, k − i) k´od, melyeket a k´od az i darab 0-val kezd˝ od˝ ou ¨zenetekhez rendel. P´ aros parit´ asbit (egyszer˝ u parit´ asbit): a k´odsz´o v´eg´ere illesztett bit, mely a k´odsz´o 1eseinek sz´am´ at p´ arosra eg´esz´ıti ki. Param´eterek: C(n, k, d) =⇒ C 0 (n + 1, k, d0 ) Ha d p´aros: d0 = d; ha d p´aratlan: d0 = d + 1.
HC 0 =
1 1
1 HC
···
1 0 .. . 0 0
P´ aratlan parit´ asbit: a k´odsz´ o v´eg´ere illesztett bit, mely a k´odsz´o 1-eseinek sz´am´at p´ aratlanra eg´esz´ıti ki. Param´eterek: C(n, k, d) =⇒ C 0 (n + 1, k, d0 ) Ha d p´aros: d0 = d + 1; ha d p´aratlan: d0 = d. K´ od´ atf˝ uz´ es: egy C(n, k, d) k´od m db n hossz´ u k´odszav´at egy m × n-es m´atrixba rendezz¨ uk soronk´ent, majd a m´atrix oszlopait sorrendben kiolvasva kapjuk a C m = C(mn, mk, d) k´odot. us´ag´ u szegmense hibacsom´o, ha a szegmens els˝o ´es utols´o Hibacsom´ o: a hibavektor egy l hossz´ karaktere nem z´erus. T´ etel: ha g(x) a C k´od gener´atorpolinoma, akkor g(xm ) a C m k´od gener´atorpolinoma. atf˝ uz´eses k´od m · t hossz´ u hibacsom´ot jav´ıt (t a C k´od hibajav´ıt´o k´epess´ege) T´ etel: A C m ´ Hibacsom´ ojav´ıt´ o k´ epess´ eg: egy C(n, k) line´aris k´od l hibacsom´ojav´ıt´o k´epess´eg´ere fenn´all, c. hogy l ≤ b n−k 2 Reiger-optimalit´ as: ha egy k´od hibacsom´ojav´ıt´o k´epess´eg´ere igaz, hogy l = b n−k od 2 c, a k´ Reiger-optim´ alis. Szorzatk´ od: egy C1 (n1 , k1 , d1 ) ´es egy C2 (n2 , k2 , d2 ) line´aris k´od felhaszn´al´as´aval egy C1 × C2 (n1 n2 , k1 k2 , d1 d2 ) k´odot hozunk l´etre. Szorzatk´ od gener´ atorm´ atrixa: l´ asd TK238.
6. Transzform´ aci´ os k´odol´ as
8
o Transzform´ aci´ os k´ odol´ as: a Reed-Solomon k´odok Fourier-transzform´aci´ot felhaszn´al´ k´odol´asi m´odszere. u Param´ eterek: legyen GF (q) = GF (pm ), ahol p pr´ım; α pedig legyen GF (q) egy n-edrend˝ eleme (n a k´odsz´ ohossz). ¨ Uzenet traf´ ok´ odol´ asa: 1. Az u = (u0 , u1 , . . . , uk−1 ) k´odsz´ o el´e tesz¨ unk n − k darab 0-t, ´ıgy kapjuk meg az n hossz´ u spektrumot: C = (0, 0, . . . , 0, u0 , u1 , . . . , uk−1 ) |
{z
n−k
}
2. A spektrumon elv´egezz¨ uk az inverz Fourier-transzform´aci´ot: ci = f (n)
n−1 X
α−ij Cj
j=0
3. Az ´ıgy kapott c = (c0 , c1 , . . . , cn ) a transzform´ aci´ os k´ odol´ as´ u k´ odsz´ o. am´ıt´ asa: f (n) sz´ −1 − Legyen a az a inverze GF (p) f¨ol¨ ott, azaz a · a−1 = 1 mod p −1 Pl. 3 = 5 mod 7, mert 3 · 5 = 15 = 1 mod 7 − Ekkor f (n) = (n mod p)−1 − Bin´aris esetben f (n) = 1 − Ha α primit´ıv eleme GF (q)-nak, akkor f (n) = (p − 1)−1 mod p
7. Konvol´ uci´ os k´odol´ as A konvol´ uci´ od k´ odol´ as alapelve: a forr´as bitfolyama k bites u ¨zenetkeretekre van osztva. ¨ zenetkeretet t´arol l´eptet˝oregiszterben (id˝oegys´eg alatt 1 keretet l´eptet¨ unk be a A k´odol´o m u regiszterbe, a legr´egebbi keretet pedig eldobjuk). Minden id˝oegys´eg alatt az ´eppen bej¨ov˝o u ´j keret ´es a t´arolt m keret alapj´an a k´odol´o kisz´amol egy n bit hossz´ odsz´ okeretet, ami us´ag´ u k´ a k´odol´o kimenet´en megjelenik. Ezen k´odol´as eredm´enye egy fa-k´od. K´ odsebess´ eg: R = nk K´ enyszerhossz: K = (m + 1)k Blokkhossz: N = (m + 1)n Konvol´ uci´ os k´ od: egy (n, k) fa-k´odot, ha line´aris, invari´ans ´es v´eges k´enyszerhossz´ u, (N, K) konvol´ uci´os k´odnak h´ıvunk. unk a Kib˝ ov´ıtett bin´ aris fa reprezent´ aci´ o: a fa csom´opontjaib´ol k´et ir´anyba l´ephet¨ k´odoland´o u ¨zenetbitnek megfelel˝oen. A fa ´eleit azon bit n-essel c´ımk´ezz¨ uk meg, amely a k´odol´o kimenet´en megjelenik az aktu´alis u ¨zenetbit bel´ep´es´enek hat´as´ara. A gy¨ok´ert˝ol a fa ´elei ment´en a fa leveleiig vezet˝ o utak egy-egy k´odsz´onak felelnek meg. A csom´opontokat ´allapotokkal c´ımk´ezz¨ uk meg (az ´allapotk´odnak ´erdemes a shiftregiszterben ´eppen elt´arolt biteket megfeleltetni.) ´ Allapot´ atmenet-gr´ af: az el˝obbi fa reprezent´aci´o ´allapotk´odjai lesznek a csom´opontok 9
(´allapotok), melyek mindegyik´eb˝ ol k´et ny´ıl vezet m´asik ´allapotokba. Az ´el i/jk form´aban c´ımk´ezett, ahol i az u ¨zenetbit, jk pedig a kimeneten megjelen˝o bitek. Trellis ´ abr´ azol´ as: a fa-´abr´ azol´ ashoz hasonl´o, de az egy m´elys´egben l´ev˝o azonos ´allapotokat ¨osszevonjuk. Az egym´ast k¨ovet˝ o ´elek utakat alkotnak, amelyek mindegyike a 00 ´allapotb´ol indul, ´es oda is fut be v´eg¨ ul. A k´ odol´ o k´ etf´ ele le´ır´ asa (p´ elda): Line´ aris kombin´ aci´ok x2i−1 = ui + ui−2 x2i = ui + ui−1 + ui−2
Ekvivalens gener´atorpolinomok g1 (x) = 1 + x2 g2 (x) = 1 + x + x2
Gener´ atorpolinom-m´ atrix: ´altal´ anos esetben a gij (x) az u ¨zenetkeret i-edik bitje ´es a k´odkeret j-edik bitje k¨ozti ¨osszef¨ ugg´est ´ırja le. Ekkor a gener´atorpolinomokat m´atrixba rendezhetj¨ uk: G(x) = [gij (x)]
uci´ os k´od katasztrof´alis, ha tetsz˝olegesen nagy Hamming-s´ uly´ u Katasztrof´ alis k´ od: egy konvol´ input-sorozat eset´en korl´ atos Hamming-s´ uly´ u marad az output. T´ etel: egy k´od akkor ´es csak akkor katasztrof´alis, ha ´allapotgr´afj´aban l´etezik egy hurok, amelyet alkot´o valamennyi ´elen a k´odsz´ okeretek 0 s´ uly´ uak. i -edik minim´ alis t´ avols´ ag: a legkisebb Hamming-t´av az output sorozatok els˝o i k´odsz´okeret hossz´ u (i · n bit) szegmense k¨oz¨ ott. Jel¨ol´ese: d∗i . T´ avols´ agprofil: d∗1 , d2∗ , d∗3 , . . . Szabad t´ avols´ ag: df ree = d∞ = max d∗i Viterbi-dek´ odol´ as: a konvol´ uci´ os k´odok maximum-likelihood dek´odol´as´ara optimaliz´alt asd TK270. algoritmus. L´ Le´ agaz´ o k´ odszavak: Legyen a(d, i) a trellis-´abr´azol´ason a z´er´o k´odsz´onak megfelel˝o u ´tb´ol az 1. csom´opontban le´agaz´ o azon utak darabsz´ama, amelyek d Hamming-t´avols´agra vannak ´es i s´ uly´ uu ¨zenetekhez tartoznak. T(D,I) meghat´ aroz´ asa: ´ − Allapotgr´ af ´atrajzol´asa: 00 ´allapot felbont´asa A ´es B ´allapotokk´a. ´ − Elek felc´ımk´ez´ese I j Dk alak´ u c´ımk´ekkel, ahol j az u ¨zenetbit, ´es k az ´elhez tartoz´o kimenet Hamming-s´ ulya. − Egyenletrendszer fel´ır´ asa a csom´opontokra, a pontba bemen˝o ´elek ¨osszegz´es´evel (pl. X = 2 ID A + IZ). − B = T (D, I) · A felhaszn´al´ as´ aval T (D, I) kisz´am´ıt´asa.
10
