Fejezetek az információátadásról és a hibakódok kódolásáról (összeállítás) - PDF

TARTALOMJEGYZÉK (cím kiválasztása) Hibatípusok: a zavarok jellemzői (zaj) BLOKKKÓDOK Hiba észlelésének/kijavításának lehetősége Egyszerű termékkódok Hamming kódok Általános termékkódok Egyetlen hiba nem bináris javító kódok lineáris blokk- és csoportkódok Módosított lineáris kódok Ciklikus kódok BCH-kódok Két hiba kijavítása Eseményhibák (burst) Vezetékkódok: meghatározás Interleaved kódok A BCH-kódok meghatározása Reed-Salamon-kódok Dekódoló algoritmusok a BCH-kódokhoz Törlések korrekciója Maximum KONVOLUCIÓS KÓDOK Dekódolás Dekódolás (Viterbi dekódolás) 3. o. 3 3 4 8 9 7 49 6 76 86 9 95 97 4 5 63 65

kódolásáról

.9.8 E n t ro p ie C a p a c it a t e.7.6.5.4.3. 3.4.5.6 R a t a e r o r il o r.7.8.9 A szimmetrikus bináris csatorna (BSC) kapacitását nagyon könnyű kiszámítani, de nagyon nehéz elérni. A csatornakapacitás kifejezése C (ε) = H (ε) és H (ε) = ε logε (ε) log (ε) a bináris entrópikus függvény. H (ε) egy bináris döntés információmennyiségének vagy bizonytalanságának a mértéke, a priori valószínűséggel ε, ε. Mellette olyan görbe adatok találhatók, amelyek a kapacitást és az entrópiát ábrázolják a hibás bitek különböző sebességével. A kísérő táblázat számszerűen szemlélteti a két függvényt, H (ε) és C (ε). Rossz bitsebesség (ε) 3 4 5 6 7 8 9 H (ε), 4689955935893,8793358959,477577375,47333583,85383,37469,46969,88,334 C (ε), 5344647,9968644,98859465,99856966477,999 99999753388,99999979888,9999999686599 Véletlenszerű bithibák A véletlenszerű hibás bitekre utalva egy bináris csatorna azonos eloszlású független hibákat tartalmaz (iid függetlenül azonos eloszlású), más szóval szimmetrikus bináris csatorna. A szimmetrikus bináris csatornának egyetlen zajparamétere van, ε: 3

Euklidész megmutatta, hogy a prímszámok száma végtelen sok. A tüntetést abszurdra redukálva hajtják végre. Elfogadott, hogy csak véges számú díj lenne,. Ekkor m = (p p pt) + olyan szám lenne, amely nem osztható egyetlen pi-vel sem. Tehát vagy m elsődleges, vagy m első osztó, amelynek különböznie kell bármely pi-től. Bár az első x-re nincs egyszerű képlet, a prímszámok tétele azt mondja, hogy: Az x-nél kisebb prímek száma π (x) körülbelül x/lnx. Pontosabban: π (x) x-szel. Bertrand által bizonyított tény: Bármely n egész számra, n és n között van egy prím. Pontosabban, legalább m bit prímje van bármelyik m-hez. Ha d> nem n tényező, n osztva d-vel nem nulla maradékot kapunk. Az osztási algoritmus az n osztót az d osztó qd többszörösének és egy kis r: n = qd + r és r m összegének fejezi ki, akkor legalább egy mezőnek egynél több objektumot kell tartalmaznia. 3

A megfelelő H alcsoport elemeinek száma kielégíti az egyenlőtlenséget, i-vel az első kitevő, amelyre az ismétlés megjelenik, és n a legkisebb szám erre: i. Az egyenlőség szorzata i = (ai) -vel e = an-t kapunk. Így az által generált alcsoport. ai j i j i j Ha i, j t hibák] 5.4 . 3 3. 4 3.5 5 3.3 6.6 7.8 8

6 8 3 3 4 57 7 88 6385 64 646 643,96,96,958,955. 9 5.5.5. 3 Hány bitre van szükség a megbízható kommunikációhoz? A Hamming-korlátozás azt mutatja, hogy a redundancia több mint 4% -ára van szükség az ésszerű bitenkénti hibaarány eléréséhez. A minimális távolság egyéb korlátai A felső határ McEliece-Rodemich-Rumsey-Welch (MRRW) R H (, 5 δ (δ)) ahol H a bináris entrópia függvény és δ = d */n a normalizált minimális távolság. A lineáris bináris blokk kódok Plotkin felső határa (gyakorlat): n k d * k d = d */n, 5 a nagy k esetén. Varshamov-Gilbert bináris blokk kódok alsó határa. Ha d * bináris Golay-kód: q =, n = 3, k =, t = 3 háromkomponensű Golay-kód: q = 3, n =, k = 6, t =. A Golay-kódok 949-ig nyúlnak vissza. Kvázi tökéletes kódok 6

Példa rövidített kódra A bináris Hamming-kód (5,) szisztematikus paritásellenőrző mátrixa H = Ez a kód (, 8) -ra rövidíthető a maximális súly oszlopok törlésével 4-re. H = A rövidített kód kijavíthatja a hibákat egyetlen bit 8 bites információs szóban. Minden ellenőrzési egyenlet egy 5 vagy 6 bites exkluzív, kevesebb mint 8 bejegyzés a forráskódban. Hosszabbított kódok Nyújtás: tartsuk n k-t, növeljük k-t, ennek megfelelően n. További információ-szimbólumokat vezetnek be és tartalmaznak az ellenőrzési egyenletek. A megnyúlást nehéz elérni a minimális kódtávolság csökkentése nélkül. Példa: Kiterjesztett Reed-Salamon kódok, amelyeket a ReedSolomon kódok (Q, k) - (Q +, k +) meghosszabbításával kapunk, a H mátrix bal oldalán két oszlop hozzáadásával. H = α α α α α4 α d α d α Q α (Q) d (Q) α átjut H-ra = α α α α4 α d α d α Q α (Q) d (Q) α Kihalt kódok Öblítés: n tartsa meg, vonja le k és növelje n k. 6.

3 4 5 6 7 8 α α = α + α + α = α + α + α = 3α + = α α = α + α + α = 4α + = α + α + α = 3α + = A várakozásoknak megfelelően, α 8 =. Az α szorzási sorrendje 8. Szorzás és osztás GF-ben (9) Az a = a + aα és b = b + bα elemek szorzata GF-ben (9): (a + aα) (b + bα) = ab + (ab + ab) α + abα = = ab + (ab + ab) α + (abα + ab) = (ab + ab) + (ab + ab + ab) α (A GF-hez is használt kifejezés (4), de itt a szorzások és az összeállítások modulo 3). (a, a) (b, b) = (ab + ab, ab + ab + ab) Gyakorlat: Keresse meg a reciprok képletét (a + aα) = (b + bα). Tipp: A lehetséges kezelések egyike: a rendszer megoldása b és b ab + ab = ab + (a + a) b = aritmetika a GF véges mezőben (6) A GF felett három három, 4 fokú polinom van:, x4 + x3 +, x4 + x3 + x + x + A legegyszerűbb: x4 + x +. Legyen α olyan elem, amely kielégíti α4 + α + = α4 = α +. Az α hatványai lehetnek egy paritásellenőrző mátrix oszlopai, szisztematikus változatban. H = GF-ben (6) az α4 = α + alkalmazásával az y = ab szorzat komponensei: y = ab + ab3 + ab + a3b y = ab + ab + ab3 + ab + a3b + ab3 + a3b y = ab + ab + ab + ab3 + a3b + a3b3 y3 = ab3 + ab + ab + a3b + a3b3 Az algebra alaptétele 7

Lemma: Legyen f (x) polinom a GF (q) GF (Q) felett. A GF (Q) β eleme akkor és csak akkor nulla f (x), ha x β az f (x) osztója GF (Q) felett. Bizonyítás: Az f (x) = q (x) (x β) + r (x) osztási algoritmus segítségével fokozattal az αi sorrendje (q)/d és implicit módon nk, amelyre g (x) (xn). Betűszó: CRC ciklikus redundancia-ellenőrzés; CCITT Nemzetközi Telefon- és Távirati Tanácsadó Bizottság 9 88

Legyen α3 a választott elem. Ez a látszólag nyilvánvaló választás nagyon jól működik. A GF (m) fölött ábrázolt paritásellenőrző mátrix α α α n H = 3 α 6 α 3 (n) α. A H által definiált kódszavak a c (x) polinomok, amelyekben az α és az α3 nulla. Így a kód minden szava az α és α3 minimális polinomjának többszöröse. Legyen f (x) és f3 (x) ezek a minimális polinomok a GF () felett. A generátor polinomja g (x) = f (x) f3 (x). A két minimális polinom foka legfeljebb m. Így az m. H foknak két vonala van GF-ből származó elemekkel (m), ugyanaz a m-es vonalakkal GF felett (). Ezért az ellenőrző bitek száma kielégíti az nk m összefüggést. Tény: Ha m 3, akkor nk = m. A két hibát kijavító BCH kód szindrómái Vegyük figyelembe a súlyhiba mintáját: e (x) = xi + xi, i r + gyakorlat: A blokk kód (n, k) esetleges hibáinak észlelésének képessége legfeljebb n k. Az incidens hibajavító kódok jellemzése Mottó: A blokk kód csak akkor képes kijavítani az összes l-nél hosszabb eseményt, ha csak két kódszó különbözik legfeljebb két hosszúságú esemény összegével. 94

<> d * = 5 4 hatványt igényel. Konjugált kitevők. d * = 9 8 hatványt igényel. 4 exponens konjugátum. d * = áramot igényel. A 7. exponensek konjugátumok d * = 4 3 hatványt igényel. Konjugált exponensek, de jobb 7 konjugált (megtisztított kód eltűnt). GF (56): egy primitív elem hatványai A GF dekóder ábécéje (56) A szűk értelemben vett primitív BCH kódok, két hibát kijavítva a GF (), GF (), GF (4), GF (8) felett meghatározhatók o ugyanaz a paritásellenőrző mátrix: H = α α α3 α4 α α α α 4 6 8 α 54 α 58 α 75 α 6 Polinomok generálása lcm (f (x), f (x), f3 (x), f4 ( x)) az altestek együtthatói vannak. GF () = = GF (4) = =