(n, k)—kódy oooo Lineárni kódy ooooo Polynomiální kódy ooooooooo Diskrétni matematika - 7. týden Lineární kódy Lukáš Vokřínek Masarykova univerzita Fakulta informatiky podzim 2024 O (n, /c)-kódy Q Lineární kódy Q Polynomiální kódy (n, /c)-kódy oooo Lineárni kódy ooooo Polynomiální kódy ooooooooo 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, k)—kódy Lineární kódy Polynomiální kódy oooo ooooo ooooooooo 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. • 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, k)—kódy •OOO Plán prednášky Lineárni kódy ooooo Polynomiální kódy ooooooooo O (n,k)-kódy (n, k)—kódy •OO Lineárni kódy ooooo Polynomiální kódy ooooooooo 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 Lineárni kódy ooooo Polynomiální kódy ooooooooo 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 Lineárni kódy ooooo Polynomiální kódy ooooooooo 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) □ ť3? - = (n, k)—kódy 0090 Lineárni kódy ooooo Polynomiální kódy ooooooooo Ú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ě. (n, k)—kódy 0090 Lineárni kódy ooooo Polynomiální kódy ooooooooo Ú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 0090 Lineárni kódy ooooo Polynomiální kódy ooooooooo Ú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 0009 Lineárni kódy ooooo Polynomiální kódy ooooooooo Definice Hammingova vzdálenost dvou slov je rovna počtu bitů, ve kterých se liší. (n, k)—kódy 0009 Lineárni kódy ooooo Polynomiální kódy ooooooooo 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 Hammingova vzdálenost kódových slov alespoň r + 1. Q Kód opravuje r a méně chyb právě, když je Hammingova vzdálenost kódových slov alespoň 2r + 1. (n, k)—kódy oooo Plán prednášky Lineárni kódy •OOOO Polynomiální kódy ooooooooo 0 Lineárni kódy (n, k)—kódy Lineárni kódy Polynomiální kódy oooo o»ooo ooooooooo 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ýva generující matice kódu. (n, k)—kódy oooo Lineárni kódy o»ooo Polynomiální kódy ooooooooo 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. Pro jednoduchost budeme předpokládat, že kód přidává dodatečnou informaci a pro konkrétnost tedy, že v má blokový tvar v — (p„), kde Pu je ona dodatečná informace a u je původní vektor. Proto matice G bude mít blokový tvar G = (n, k)—kódy oooo Lineárni kódy oo»oo Polynomiální kódy ooooooooo Je-// g : (Z2) —>• (^2)" lineární kód s (blokově zapsanou) maticí G = potom zobrazení h : (Zy7 ~~^ (^2)" k s matici H={ln-k P) má následující vlastnost: slovo v je kódové, právě když H • v = 0 (n, k)—kódy OOOO Lineárni kódy oo»oo Polynomiální kódy ooooooooo Věta Je-li g : (Z2) —> (Z2)n lineární kód s (blokově zapsanou) maticí * ■ (0 • potom zobrazení h : (Z2)n —>» (Z2)n_/c s matici H = (ln-k P) má následující vlastnost: slovo v je kódové, právě když H • v = 0. Důkaz. Slovo v = (y) je kódové, právě když v = Gy = (/y/), protože v takovém případě jsme schopni původní slovo y dekódovat z informačních bitů. Slovo v je tedy kódové, právě když x = Py, což je přesně podmínka H(y) = 0. □ (n, k)—kódy Lineárni kódy Polynomiální kódy oooo 0090 ooooooooo Matici H z věty se říká matice kontroly parity přílušného (r?, /c)-kódu, součinu Hv říkáme syndrom slova v. (n, k)—kódy oooo Lineárni kódy 0090 Polynomiální kódy ooooooooo Matici H z věty se říká matice kontroly parity přílušného (r?, /c)-kódu, součinu Hv říkáme syndrom slova v. Význam syndromu Pokud Hv 7^ 0, hledáme co nejbližší kódové slovo, tj. co nejmenší e tak, aby H(v + e) = 0. Přitom přičtení jedničky na /-tém místě způsobí změnu hodnoty přesně o /-tý sloupec kontrolní matice H. Chceme tedy syndrom Hv vynulovat přičtením co nejmenšího počtu sloupců matice H. (n, k)—kódy oooo Lineárni kódy 0090 Polynomiální kódy ooooooooo Matici H z věty se říká matice kontroly parity přílušného (r?, /c)-kódu, součinu Hv říkáme syndrom slova v. Význam syndromu Pokud Hv 7^ 0, hledáme co nejbližší kódové slovo, tj. co nejmenší e tak, aby H(v + e) = 0. Přitom přičtení jedničky na /-tém místě způsobí změnu hodnoty přesně o /-tý sloupec kontrolní matice H. Chceme tedy syndrom Hv vynulovat přičtením co nejmenšího počtu sloupců matice H. V levé submatici máme právě sloupce s jednou jedničkou. Kdybychom využívali pouze tyto sloupce (opravovali pouze kontrolní bity), potřebujeme opravit přesně tolik bitů, kolik obsahuje syndrom Hv jedniček, navíc přesně na stejných pozicích. (n, k)—kódy oooo Lineárni kódy ooo« Polynomiální kódy ooooooooo Naopak, necht A? je lineárni zobrazení, jehož matice je tvaru H = (ln-k P)- Pak můžeme sestrojit lineární kód s maticí G — (ik) a podle věty pak H bude matice kontroly parity. Jsme tedy schopni lineární kód zadat jeho (lineární) kontrolou parity. (n, k)—kódy oooo Lineárni kódy ooo« Polynomiální kódy ooooooooo Naopak, necht A? je lineárni zobrazení, jehož matice je tvaru H = (ln-k P)- Pak můžeme sestrojit lineární kód s maticí G — (ik) a podle věty pak H bude matice kontroly parity. Jsme tedy schopni lineární kód zadat jeho (lineární) kontrolou parity. Příklad Jednoduše to lze ilustrovat na klasické kontrole parity, kde /7(xq, ..., x^) = xq + • • • + Xf< je zjevně lineární s maticí H=(l 1 ••• 1), kýženého tvaru. Nemusíme tedy specifikovat matici kódu, tu lze z matice kontroly parity odvodit. (n, k)—kódy oooo Lineárni kódy ooo« Polynomiální kódy ooooooooo Naopak, necht A? je lineárni zobrazení, jehož matice je tvaru H = (ln-k P)- Pak můžeme sestrojit lineární kód s maticí G — (ik) a podle věty pak H bude matice kontroly parity. Jsme tedy schopni lineární kód zadat jeho (lineární) kontrolou parity. Příklad Jednoduše to lze ilustrovat na klasické kontrole parity, kde /7(xq, ..., x^) = xq + • • • + Xf< je zjevně lineární s maticí H=(l 1 ••• 1), kýženého tvaru. Nemusíme tedy specifikovat matici kódu, tu lze z matice kontroly parity odvodit. V další části uvedeme konstrukci polynomiálních kódů skrze jejich matici kontroly parity. Lineární kódy ooooo Polynomiální kódy •oooooooo I I r\ I-r\ l Jl J V Q Polynomiální kódy (n, k)—kódy oooo Lineárni kódy ooooo Polynomiální kódy •ooooooo 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ě. <□► < rnP ► < -E ► < -E ► -E o °n o (n, k)—kódy oooo Lineárni kódy ooooo Polynomiální kódy •ooooooo 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... b^-i je reprezentována jako polynom m(x) = b0 + bix + • • • + b/c.ix^-1 G Z2[x]. (n, k)—kódy oooo Lineárni kódy ooooo Polynomiální kódy •ooooooo 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-^xn~k £ Z2[x] je polynom s ao = 1, an_k — 1- Polynomiální kód generovaný polynomem p(x) je lineární (r?, /c)-kód, jehož slova jsou polynomy stupně menšího než n dělitelné p(x) a jehož kontrola parity je lineární zobrazení h posílající polynom na jeho zbytek po dělení p(x). (n, k)—kódy oooo Lineárni kódy ooooo Polynomiální kódy o«oooooo Zobrazení h je opravdu lineární (zbytek součtu je součet zbytků). Polynomy stupně menšího než n — k jsou automaticky zbytkem po dělení p(x), takže je na nich h identita a matice H je tedy tvaru H =(ln-k P), jak je potřeba. (n, k)—kódy oooo Lineárni kódy ooooo Polynomiální kódy o«oooooo Zobrazení h je opravdu lineární (zbytek součtu je součet zbytků). Polynomy stupně menšího než n — k jsou automaticky zbytkem po dělení p(x), takže je na nich h identita a matice H je tedy tvaru H =(ln-k P), jak je potřeba. Sestavení matic Nastíníme nyní, jak matici P sestavit. Její první sloupec je zbytek xn~k a sestává se tedy z koeficientů p(x) stupně menšího než n — k. Další sloupec je zbytkem xn~k+1 — x • xn~k a získáme jej tedy z předchozího sloupce vynásobením x, přičemž případný výskyt xn~k nahradíme jeho zbytkem, tedy prvním sloupcem P. Konkrétně tedy sloupec posuneme dolů a případná jednička se při přetečení nahradí přičtením prvního sloupce. Takto postupujeme i pro další sloupce - posouváme předchozí, při přetečení přičítáme první! (n, k)—kódy oooo Lineárni kódy ooooo Polynomiální kódy OOO0OOOOO r Příklad 1 O Polynom p(x) = 1 + x generuje (r?, n — l)-kód kontroly parity pro všechna n > 3. O Polynom p(x) = 1 + x + x2 generuje (3, l)-kód opakovaní 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, k)—kódy oooo Lineárni kódy ooooo Polynomiální kódy oooo»oooo Matice príslušná k polynomu p(x) = 1 + x + x 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 OOOO Lineárni kódy ooooo Polynomiální kódy OOOO0OOO Přenos slova v G Z^[x] dopadne prijmem 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 oooo Lineárni kódy ooooo Polynomiální kódy OOOOO0OOO 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. Analýza 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. Připomeňme, že matice kontroly parity obsahuje ve sloupcích zbytky po dělení x' polynomem p(x). Pokud chceme, aby kód rozpoznal jednoduché chyby, nesmí matice kontroly parity obsahovat žádný nulový sloupec - to totiž odpovídá p(x) | x'. Pokud chceme, aby kód rozpoznal dvojité chyby, nesmí matice kontroly parity obsahovat žádný sloupec dvakrát - to totiž odpovídá p(x) | x1 + x7. Při počtu řádků m = n — k, tak může P obsahovat maximálně n = 2m — 1 sloupců. (n, k)—kódy oooo Lineárni kódy ooooo Polynomiální kódy oooooo»oo Ireducibilní polynom p(x) 6 Z^[x] stupně m se nazývá primitivní, jestliže p(x) | (1 + x^) pro £ < 2m — 1, a teprve p(x) | (1 + x£) pro £ = 2m-l. (n, k)—kódy oooo Lineárni kódy ooooo Polynomiální kódy oooooo»oo Definice Ireducibilní polynom p(x) 6 Z^[x] stupně m se nazývá primitivní, jestliže p(x) | (1 + x^) pro í < 2m — 1, a teprve p(x) | (1 + x^) pro £ = 2m-l. Je-// p(x) primitivní polynom stupně m, pak pro všechna n < 2m — 1 rozpoznává příslušný (r?, r? — m)-kód všechny jednoduché a dvojité chyby (n, k)—kódy oooo Lineárni kódy ooooo Polynomiální kódy oooooo»oo Definice Ireducibilní polynom p(x) 6 Z^[x] stupně m se nazývá primitivní, jestliže p(x) | (1 + x^) pro í < 2m — 1, a teprve p(x) | (1 + x^) pro £ = 2m-l. Je-// p(x) primitivní polynom stupně m, pak pro všechna n < 2m — 1 rozpoznává příslušný (r?, r? — m)-kód všechny jednoduché a dvojité chyby Důsledek \na Je-li q(x) primitivní polynom stupně m, pak pro všech _ r? < 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 oooo Lineární ooooo kódy Polynomiální kódy oooooo»o Tabulka dává o informace o výsledcích předchozích dvou vět pro několik polynomů: (n, k)—kódy oooo Lineárni kódy ooooo Polynomiální kódy OOOOOOO0O 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 <□► < rnP ► < -E ► < -E ► -E o °n o (n, k)—kódy oooo Lineárni kódy ooooo Polynomiální kódy 00000000« 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). (n, k)—kódy OOOO Lineárni kódy ooooo Polynomiální kódy 00000000« 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. <□► < rnP ► < -E ► < -E ► E o °n o