(n, k)—kódy ooo Polynomiální kódy oooooo Lineárni kódy ooooo Diskrétni matematika - 8. týden Lineární kódy Lukáš Vokřínek Masarykova univerzita Fakulta informatiky podzim 2020 (n, /c)-kódy Polynomiální kódy Lineární kódy ooo oooooo ooooo Obsah přednášky O {n, /c)-kódy Q Polynomiální kódy Q Lineárni kódy □ s1 (n, /c)-kódy Polynomiální kódy Lineární kódy ooo oooooo ooooo Doporučené zdroje • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne. (n, /c)-kódy Polynomiální kódy Lineární kódy ooo oooooo ooooo Doporučené zdroje • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne. 9 W. J. Gilbert, W. K. Nicholson, Modern algebra with applications, 2nd ed. John Wiley and Sons (Pure and applied mathematics) ISBN 0-471-41451-4 (n, /c)-kódy Polynomiální kódy Lineární kódy ooo oooooo ooooo Plán prednášky O (n,k)-kódy (n, k)—kódy •OO Polynomiální kódy oooooo Lineárni kódy ooooo Při přenosu informace zpravidla dochází k její deformaci. Budeme pro jednoduchost pracovat s modelem, kdy jednotlivé částečky informace jsou buď nuly nebo jedničky (tj. prvky v Z2) a přenášíme slova o k bitech. (n, k)—kódy •OO Polynomiální kódy oooooo Lineárni kódy ooooo Při přenosu informace zpravidla dochází k její deformaci. Budeme pro jednoduchost pracovat s modelem, kdy jednotlivé částečky informace jsou buď nuly nebo jedničky (tj. prvky v Z2) a přenášíme slova o k bitech. Přenosové chyby chceme O rozpoznávat O opravovat a za tím účelem přidáváme dodatečných n — k bitů informace pro pevně zvolené n > k. Mluvíme pak o (r?, k)-kódu. (n, k)—kódy •OO Polynomiální kódy oooooo Lineárni kódy ooooo Při přenosu informace zpravidla dochází k její deformaci. Budeme pro jednoduchost pracovat s modelem, kdy jednotlivé částečky přenášíme slova o k bitech. Přenosové chyby chceme O rozpoznávat O opravovat a za tím účelem přidáváme dodatečných n — k bitů informace pro pevně zvolené n > k. Mluvíme pak o (r?, k)-kódu. Všech slov o k bitech je 2k a každé z nich má jednoznačně určovat jedno kódové slovo z 2n možných. Máme tedy ještě slov, které jsou chybové. Lze tedy tušit, že pro veliké k nám i malý počet přidaných bitů dává hodně redundantní informace. informace jsou buď nuly nebo jedničky (tj. prvky v Z2) a n-k i) (n, k)—kódy Polynomiální kódy oooooo Lineárni kódy ooooo Úplne jednoduchým příkladem je kód kontrolující paritu. Kódové slovo o k + 1 bitech je určené tak, aby přidáním prvního bitu byl zaručen sudý počet jedniček ve slově. (n, k)—kódy Polynomiální kódy oooooo Lineárni kódy ooooo Úplne jednoduchým příkladem je kód kontrolující paritu. Kódové slovo o k + 1 bitech je určené tak, aby pridaním prvního bitu byl zaručen sudý počet jedniček ve slově. Pokud při přenosu dojde k lichému počtu chyb, přijdeme na to. Dvě různá kódová slova se při tomto kódu vždy liší alespoň ve dvou pozicích, chybové slovo se ale od dvou různých kódových slov liší pouze v pozici jedné. Nemůžeme proto umět chyby opravovat ani kdybychom věděli, že došlo k právě jedné. (n, k)—kódy Polynomiální kódy oooooo Lineárni kódy ooooo Úplne jednoduchým příkladem je kód kontrolující paritu. Kódové slovo o k + 1 bitech je určené tak, aby pridaním prvního bitu byl zaručen sudý počet jedniček ve slově. Pokud při přenosu dojde k lichému počtu chyb, přijdeme na to. Dvě různá kódová slova se při tomto kódu vždy liší alespoň ve dvou pozicích, chybové slovo se ale od dvou různých kódových slov liší pouze v pozici jedné. Nemůžeme proto umět chyby opravovat ani kdybychom věděli, že došlo k právě jedné. Navíc neumíme detekovat tak obvyklé chyby, jako je záměna dvou sousedních hodnot ve slově. (n, k)—kódy Polynomiální kódy oooooo Lineárni kódy ooooo Definice Hammingova vzdálenost dvou slov je rovna počtu bitů, ve kterých se liší. (n, k)—kódy Polynomiální kódy oooooo Lineárni kódy ooooo Definice Hammingova vzdálenost dvou slov je rovna počtu bitů, ve kterých se liší. O Kód odhaluje r a méně chyb právě, když je minimální Hammingova vzdálenost kódových slov právě r + 1. Q Kód opravuje r a méně chyb právě, když je minimální Hammingova vzdálenost kódových slov právě 2r + 1. ■ (n, /c)-kódy Polynomiální kódy Lineární kódy ooo oooooo ooooo Plán prednášky Q Polynomiální kódy (n, k)—kódy ooo Polynomiální kódy •ooooo Lineárni kódy OOOOO Jak konstruovat kódová slova, abychom je snadno rozpoznali? Kontrolu parity jsme už viděli, další triviální možnost je prosté opakování bitů - např. (3, l)-kód bere jednotlivé bity a posílá je třikrát po sobě. (n, k)—kódy ooo Polynomiální kódy •ooooo Lineárni kódy OOOOO Jak konstruovat kódová slova, abychom je snadno rozpoznali? Kontrolu parity jsme už viděli, další triviální možnost je prosté opakování bitů - např. (3, l)-kód bere jednotlivé bity a posílá je třikrát po sobě. Docela systematickou cestou je využití dělitelnosti polynomů. Zpráva bobi... bk-i je reprezentována jako polynom m(x) = b0 + bix + • • • + b/c.ix^-1 G Z2[x]. (n, k)—kódy ooo Polynomiální kódy •ooooo Lineárni kódy OOOOO Jak konstruovat kódová slova, abychom je snadno rozpoznali? Kontrolu parity jsme už viděli, další triviální možnost je prosté opakování bitů - např. (3, l)-kód bere jednotlivé bity a posílá je třikrát po sobě. Docela systematickou cestou je využití dělitelnosti polynomů. Zpráva bobi... bk-i je reprezentována jako polynom m(x) = b0 + bix + • • • + b/c.ix^-1 G Z2[x]. Definice Nechť p(x) = ao + " - + an-i 3. O Polynom p(x) = 1 + x + x2 generuje (3, l)-kód opakování bitů. První tvrzení plyne z toho, že 1 + x dělí polynom v(x) tehdy a jen tehdy, když v(l) = 0 a to nastane tehdy, když je ve v(x) sudý počet nenulových koeficientů. Druhé je zřejmé. (n, /c)-kódy OOO Polynomiální kódy OO0OOO Lineárni kódy ooooo Přenos slova v G ^[x] dopadne příjmem polynomu u(x) = v (x) + e(x) kde e(x) je tzv. chybový polynom reprezentující vektor chyby přenosu. □ s (n, k)—kódy ooo Polynomiální kódy oo»ooo Lineárni kódy ooooo Přenos slova v G Z^[x] dopadne příjmem polynomu u (x) = v (x) + e (x) kde e(x) je tzv. chybový polynom reprezentující vektor chyby přenosu. Chyba je rozpoznatelná pouze, když generátor kódu p(x) nedelí e(x). Máme proto zájem o polynomy, které nevystupují jako dělitelé zbytečně často. (n, k)—kódy ooo Polynomiální kódy oo»ooo Lineárni kódy ooooo Přenos slova v G Z2[x] dopadne příjmem polynomu u (x) = v (x) + e (x) kde e(x) je tzv. chybový polynom reprezentující vektor chyby přenosu. Chyba je rozpoznatelná pouze, když generátor kódu p(x) nedelí e(x). Máme proto zájem o polynomy, které nevystupují jako dělitelé zbytečně často. Definice Ireducibilní polynom p(x) G Z2[x] stupně m se nazývá primitivní, jestliže p(x) dělí polynom (1 + x£) pro í — 2m — 1 ale nedělí jej pro zadna menši í. (n, k)—kódy ooo Polynomiální kódy OOO0OO Lineárni kódy ooooo Věta Je-li p(x) primitivní polynom stupně m, pak pro všechna n < 2m — 1 rozpoznává příslušný (r?, n — m)-kód všechny jednoduché a dvojité chyby (n, k)—kódy ooo Polynomiální kódy OOO0OO Lineárni kódy ooooo rVěta_J Je-li p(x) primitivní polynom stupně m, pak pro všechna n < 2m — 1 rozpoznává příslušný (r?, n — m)-kód všechny jednoduché a dvojité chyby Důsledek Je-li q{x) primitivní polynom stupně m, pak pro všechna n < 2m — 1 rozpoznává (n. n — m — l)-kód generovaný polynomem p(x) = g(x)(l + x) všechny dvojité chyby a všechna slova s lichým počtem chyb. (n, /c)-kódy OOO Polynomiální kódy OOOO0O Lineárni kódy ooooo Tabulka dává o informace o výsledcích předchozích dvou vět pro několik polynomů: (n, k)—kódy ooo Polynomiální kódy OOOO0O Lineárni kódy ooooo Tabulka dává o informace o výsledcích předchozích dvou vět pro několik polynomů: primitivní polynom kontrolní bity délka slova 1 + x + x2 2 3 1 + x + x3 3 7 1 + x + x4 4 15 1 + x2 + x5 5 31 1 + x + x6 6 63 1 + x3 + x7 7 127 1 + x2 + x3 + x4 + x8 8 255 l+x4 + x9 9 511 1 + x3 + x10 10 1023 (n, /c)-kódy Polynomiální kódy Lineárni kódy ooo 00000« ooooo Nástroje pro konstrukci primitivních polynomů dává teorie konečných polí. Souvisíš tzv. primitivními prvky v Galoisových polích G(2m). □ s (n, k)—kódy ooo Polynomiální kódy 00000« Lineárni kódy ooooo Nástroje pro konstrukci primitivních polynomů dává teorie konečných polí. Souvisíš tzv. primitivními prvky v Galoisových polích G(2m). Ze stejné teorie lze také dovodit příjemnou realizaci dělení se zbytkem (tj.) ověřování, zda je přijaté slovo kódové, pomocí zpožďovacích registrů. Jde o jednoduchý obvod s tolika prvky, kolik je stupeň polynomu. (n, k)—kódy Polynomiální kódy Lineárni kódy ooo oooooo ooooo Plán prednášky Q Lineárni kódy (n, k)—kódy ooo Polynomiální kódy oooooo Lineárni kódy •oooo Definice Lineární kód je injektivní lineárni zobrazení g : (Z2) —>• (^2)"-Matice G typu r?//c reprezentující toto zobrazení v standardních bazích se nazývá generující matice kódu. (n, k)—kódy ooo Polynomiální kódy oooooo Lineárni kódy •oooo Definice Lineární kód je injektivní lineárni zobrazení g : {1é2)k ~~^ (^2)"-Matice G typu n/k reprezentující toto zobrazení v standardních bazích se nazývá generující matice kódu. Pro každé slovo u je v — G - u příslušné kódové slovo. (n, k)—kódy ooo Polynomiální kódy oooooo Lineárni kódy OtOOO Každý polynomiální (n, k)-kód je lineárni kód. (n, k)—kódy ooo Polynomiální kódy oooooo Lineárni kódy OtOOO Věta Každý polynomiální (n, k)-kód je lineárni kód. Matice příslušná k polynomu p(x) = 1 + x + x3 a jím určenému (7,4)-kódu je f1 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 0 Vo 0 0 1/ (n, k)—kódy ooo Polynomiální kódy oooooo Lineárni kódy oo«oo Věta Je-li g : (Z2)k ->• (2 ^2)" lineární kód s (blokově zapsanou) maticí ^ fP\ G = L , potom zobrazení h : (Z2)n ->• (Z2)n_'c s maí/'o H P) má následující vlastnosti O Ker /? = \mg O Prijaté slovo v — G - u je kódové slovo právě, když je H ■ v = 0. (n, k)—kódy ooo Polynomiální kódy oooooo Lineárni kódy oo«oo Je-// g : (Z2) —> (Z2)n lineární kód s (blokově zapsanou) maticí má následující vlastnosti Q Ker h = Img- O Přijaté slovo v — G - u je kódové slovo právě, když je H - v = Q._ Matici H z věty se říká matice kontroly parity přílušného (r?, /c)-kódu. potom zobrazení h : (Z2)n —>» (Z2) n-k s matici H = (ln_k P) (n, k)—kódy Polynomiální kódy Lineárni kódy ooo oooooo ooo«o Jak jsme viděli, přenos zprávy u dává výsledek v = u + e, kde ale neznáme u, e a hledáme takový "rozklad", kde e obsahuje co nejméně jedniček (oprava chyby za předpokladu co nejmenšího počtu chyb). (n, k)—kódy ooo Polynomiální kódy oooooo Lineárni kódy ooo«o Jak jsme viděli, přenos zprávy u dává výsledek v = u + e, kde ale neznáme u, e a hledáme takový "rozklad", kde e obsahuje co nejméně jedniček (oprava chyby za předpokladu co nejmenšího počtu chyb). Je-li v = , pak jednou z možností na odeslanou zprávu je Gy — \ Py) (ne nutně optimální), tedy y ;)=(?)+ery (n, k)—kódy ooo Polynomiální kódy oooooo Lineárni kódy ooo«o Jak jsme viděli, přenos zprávy u dává výsledek v = u + e, kde ale neznáme u, e a hledáme takový "rozklad", kde e obsahuje co nejméně jedniček (oprava chyby za předpokladu co nejmenšího počtu chyb). Je-li v = , pak jednou z možností na odeslanou zprávu je Gy — {^y^j (ne nLJtně optimální), tedy kde s = x + Py je právě syndrom slova v a jedná se tedy o chybu za předpokladu, že k ní došlo pouze na kontrolních bitech (z informačních bitů lze proto přečíst původní slovo). (n, k)—kódy ooo Polynomiální kódy oooooo Lineárni kódy oooo* Protože kódová slova jsou právě součty sloupců matice G, lze všechny další možnosti obdržet přičítáním sloupců g\ ke kódovému slovu i chybě: e)-((?)"M(x+o*H atd. (n, k)—kódy ooo Polynomiální kódy oooooo Lineárni kódy oooo* Protože kódová slova jsou právě součty sloupců matice G, lze všechny další možnosti obdržet přičítáním sloupců g\ ke kódovému slovu i chybě: e)-((?)"M(x+o*H atd. Přitom přičtení každého sloupce vyrobí jednu 1 v informačních bitech chyby, snažíme se jejich počet kompenzovat snížením počtu 1 v kontrolních bitech. Toto budeme zkoušet pouze pro malý počet chyb, viz cvičení.