(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. o 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 přednášky O (n,k)-kódy (n, /c)-kódy •oo Polynomiální kódy oooooo Lineárni kódy ooooo Pri 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. H 1_; 2.; (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. Wq---fc> t ^ 1Ai (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 P ^ O rozpoznávat ___0^ O opravovat a za tím účelem přidáváme dodatečných n — k bitů informace pro pevně zvolené n > k. Mluvme 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. (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ě. . . . >• tří- . ieAifce^- ujko** l--3 (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ě. 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é. oo /M (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ě. 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ě. 04 —iô Polynomiální kódy oooooo Lineární 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. O Kód opravuje r a méně chyb právě, když je minimální Hammingova vzdálenost kódových slov /Dj&Pě 2r + 1. tu n Udí (n, /c)-kódy Polynomiální kódy Lineární kódy ooo oooooo ooooo Plán přednáš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ě. ©01 0 -OOO OOO - A11 1 -» / * . (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 jsmp už viděli, další triviální možnost je prosté opakování bituWnapr. (3, l)-kód bere jednotlivé bity a posílá je třikrát po sobě. 0*6* V*— b« **<\---t^-i Docela systematickou cestou je využití dělitelnosti polynomů. Zpráva b^bi... bk-\ je reprezentována jako polynom m(x) = bo + bix + ■ ■ ■ + ó/c-i^-1 e Z2[x]. - 04/1 (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 bnbi ... bu-\_ ie reprezentována jako polynom ftt/k) Jjn(x) = bn + bix + --- + /^_ix/c~1 G Z2[x]. Definice Nechť p(x) = ao + " - + an-kxn £ 2^2 [x] je polynom s ao = 1, an-k — 1 Polynomiální kód generovaný polynomem p(x) je (r?, /c)-kód jehož slova jsou polynomy stupně dělitelné p(x). fU)W *X >0 0,0 (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-i0 Q,o HC HA Kr 9 m 428&ui. poo ^ 4 f \ Ě \ ^ X J it (n, k)—kódy ooo Polynomiální kódy o«oooo Lineárni kódy ooooo Z definice víme v(x) = xn~km(x) + r(x) = q{x)p(x) + r(x) + r(x) = q(x)p(x). Budou tedy všechna kódová slova dělitelná p(x). (n, k)—kódy ooo Polynomiální kódy o«oooo Lineárni kódy ooooo Z definice víme v (x) = xn~km(x) + r (x) = g(x)p(x) + r (x) + r (x) = g(x)p(x). Budou tedy všechna kódová slova dělitelná p(x). Původní zpráva je obsažena přímo v polynomu v(x), takže dekódování správného slova je snadné. (n, k)—kódy ooo Polynomiální kódy o«oooo Lineárni kódy ooooo Z definice víme v (x) = xn km(x) + r (x) = g(x)p(x) + r (x) + r (x) = g(x)p(x) Budou tedy všechna kódová slova dělitelná p(x). Původní zpráva je obsažena přímo v polynomu v(x), takže dekódování správného slova je snadné. Příklad O Polynom p(x) = 1 + x generuje (á*^^J.)-kód kontroly parity pro všechna n > 3. O Polynom p(x) = 1 + x + x2 generuje (3, l)-kód opakování bitů. o —^ o x o 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é. (J y 1/ r ^ a », — lot A J J ) v (n, k)—kódy ooo Polynomiální kódy OO0OOO Lineárni kódy ooooo Přenos slova v G Z^[x] dopadne příjmem polynomu u (x) = i/(x) + e(x) kde e(x) je tzv. chybový polynom ^prezentující vektor chyby přenosu. >w \ po^ I e,0cj ť - ' L 5 -ť) <\(y (n, k)—kódy ooo Polynomiální kódy OO0OOO 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 OO0OOO 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. ID* Definice Ireducibilní polynom p(x) G 2^[x] stupně m se nazývá primitivní, jestliže p(x) dělí polynom (1 + x£) pro £ = 2m — 1 ale nedělí jej pro žádná menšíc. . \« (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 — — i (n, k)—kódy ooo Polynomiální kódy OOO0OO Lineárni kódy ooooo 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 i jednoduché a dvojité chyby ^ w^"1* J^d^- Ca' 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. 4, Lf 3 gjL. QfW& (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ů: (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 k^T 7 127 " * 1 + x2 + x3 + x4 + x8 8 255 l+x4 + x9 9 511 1 + x3 + x10 10 1023 Wfa--2> /IQV> (n, k)—kódy ooo Polynomiální kódy ooooo* 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) 1M t-od 00 1 St-- M 0 (n, k)—kódy ooo Polynomiální kódy ooooo* 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. Polynomiální kódy oooooo Lineární kódy ooooo Plán přednášky Q Lineární kódy □ 3 ► < ► 4 = (n, k)—kódy OOO Polynomiální kódy Lineární kódy OOOOOO «0000 ^ fc,-ŕfe,x-*---yL^^i JL Definice Lineární kód je injektivní lineárni zobrazení g : (^2)^ —>» {^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 : {^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. v U\ -» (n, k)—kódy Polynomiální kódy Lineárni kódy ooo oooooo OfOOO Každý polynomiální (n, k)-kód je lineárni kód. Matice príslušná k polynomu p(x) = 1 + x + x3 a jím určenému (7,4)-kódu je ---4.* 4000 G = (l 0 1 1 0 1 AiOAQóQ ^—"* ***** 4101 &0O č—* 1 0 1 1 10 0 0 0 10 0 0 0 10 \0 0 0 1/ V/ V / u--' - (n, k)—kódy ooo Polynomiální kódy oooooo Lineárni kódy oo«oo Je-// g : {1é2)k ~^ (^2)" lineární kód s (blokově zapsanou) maticí G = I/c. n-k potom zobrazení h : (Zy7 —>» (Zy7 s matici H = (I„-k P) ^ d* má následující vlastnosti O Ker /? = Im g" O Přijaté slovo v = G ■ u je kódové slovo právě, když je H ■ v = 0. /I 00 A 0 e (Tr)(jV >0 Q,o (n, k)—kódy ooo Polynomiální kódy oooooo Lineárni kódy oo«oo Je-// g : (Z2) —> i^2)n lineární kód s (blokově zapsanou) maticí má následující vlastnosti O Ker h = Im g O Přijaté slovo v — G - u je kódové slovo právě, když je H-v = 0._ Matici H z věty se říká matice kontroly parity přílušného (r?, /c)-kódu. potom zobrazení h : (Zy7 —>» (Zy7 s matici H = (ln_k P) (n, k)—kódy Polynomiální kódy Lineárni kódy ooo oooooo OOO0O 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 OOO0O 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 ^ (n, k)—kódy ooo Polynomiální kódy oooooo Lineárni kódy OOO0O 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 H* 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). <□► -íínfl^ ^ O o, O (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ě: j>