Kódovaní Cílem kódovaní je přenášet informace tak, abychom postřehli, pokud by došlo k jejich zkreslení náhodnou chybou, v ideálním případě dokonce takto vzniklou chybu nejen odhalit, ale i opravit. Použití: ukládání dat (paměť počítače, CD, DVD, Blue-ray, čárové kódy, QR-kódy), komunikace (digitální TV, vesmírné sondy), atd. Přenášená informace bude zapsána pomocí abecedy, která má p písmen (tj. jakýchsi symbolů), kde p je pevně zvolené prvočíslo. Tuto abecedu tedy můžeme ztotožnit s množinou Zp všech zbytkových tříd modulo p. Přenášet budeme slova délky n, každé takové kódové slovo a\a2^ ... an-\an lze tedy chápat jako polynom a(x) = aix"-1 + a2xn~2 + ••• + a„_ix + an G Zp[x] stupně st(a(x)) < n. Číslo n nazýváme délka kódu. Kdyby každý polynom stupně menšího než n bylo některé z kódových slov, tak bychom nemohli postřehnout, že při přenosu došlo k nějaké náhodné chybě. Polynomiální kód délky n daný polynomem g(x) £ Zp[x] Máme tedy pevně zvolené prvočíslo p a přirozené číslo n. Zafixujme také polynom g{x) G Zp[x] stupně st(g"(x)) — k < n. Kódová slova budou ty polynomy a(x) G Zp[x] stupně st(a(x)) < r?, které jsou dělitelné polynomem g{x) v okruhu Zp[x], jsou to tedy polynomy a(x) = g"(x) • h(x), kde /7(x) G Zp[x] je libovolný polynom stupně st(/7(x)) < n — k. Pokud chceme odeslat zprávu zapsanou pomocí n — k písmen, tj. polynom b{x) = bixn~k~ľ + • • • + bn-^-ix + bn-k G Zp[x] stupně st(b(x)) < n — k, vydělíme polynom xk • b(x) polynomem g(x) se zbytkem a dostaneme polynomy q(x), r(x) G Zp[x] tak, že • b(x) = g(x) • q(x) + r(x), kde st(r(x)) < /c. Odešleme pak polynom g{x) • q(x) = x^ • b(x) — r(x). Každé kódové slovo se tedy skládá z n — k významových písmen (daných polynomem b{x)) následovaných k kontrolními písmeny (daných polynomem —r(x)). Je však nutné vhodně zvolit polynom g{x). Určitě by nebyla vhodná volba g{x) — xk, protože pak bychom každou zprávu b(x) doplnili nulovým polynomem. Příklad pro prvočíslo p = 2, tedy Z2 = {0,1} Zvolme polynom g(x) — x + 1 G ^[x], tedy /c = st(g"(x)) = 1. Zvolme libovolnou délku kódu n > 1. Odesílanou zprávou je nějaký polynom b(x) G ^[x] stupně st(b(x)) < n - 1. Naše kódová slova se tedy budou skládat z n — 1 významových písmen (to jsou koeficienty polynomu b(x)) následovaných jedním kontrolním písmenem. Kontrolní písmeno určujeme takto: polynom x • b(x) vydělíme polynomem g(x) — x + 1 se zbytkem a dostaneme polynomy q(x), r(x) G ^[x] tak, že xk • b(x) = #(x) • q(x) + r(x) = (x + 1) • q(x) + r(x), kde st(r(x)) < k = 1. Tedy polynom r(x) G ^[x] je konstantní, tj. r(x) G {0,1}. Dosazením x = 1 dostaneme r(l) = b(l), a proto r(x) = b(l). Protože b(l) = 0, má-li odesílaná zpráva sudý počet jedniček, a b(l) = 1, má-li odesílaná zpráva lichý počet jedniček, doplňujeme zprávu jedním písmenem tak, aby celkový počet jedniček byl sudý. Kód tedy pozná, že došlo k jedné chybě, opravit ji neumí. Pokud došlo ke dvěma chybám, nic nepozná. Metrický prostor, Hammingova vzdálenost kódových slov Metrickým prostorem rozumíme nějakou neprázdnou množinu M (její prvkům říkáme body) spolu s metrikou na množině M, což je zobrazení p : M x M —>> IRq", kde IRq" značí množinu nezáporných reálných čísel, splňující pro každé x, y, z G M ► p(x.y) = 0 x = y, ► p(*,y) = p(y,*). ► p(x,y) + p(y,z) > p(x,z). Při práci v metrickém prostoru můžeme používat svou geometrickou intuici, například mluvit o koulích s daným středem a daným poloměrem (jde o množinu bodů, jejichž vzdálenost od daného středu je menší než daný poloměr). Pro každé dva polynomy a(x), b(x) G Zp[x] stupňů st(a(x)) < n, st(b(x)) < n, definujeme jejich Hammingovu vzdálenost jako počet nenulových koeficientů rozdílu a(x) — b(x), tj. počet koeficientů, v nichž se oba polynomy liší. Uvědomte si, že jde o metrický prostor. Užití Hammingovy vzdálenosti kódových slov Máme-li být schopni postřehnout, že došlo k chybě, pokud při přenosu bylo právě na jedné pozici přenášené písmeno náhodné změněno, je třeba, aby vzdálenost libovolných dvou různých kódových slov byla alespoň 2. Pokud tato vzdálenost libovolných dvou různých kódových slov bude alespoň 3, budeme dokonce schopni takovou chybu i opravit. Obecněji, je-li pro nějaké ŕ G N vzdálenost libovolných dvou různých kódových slov alespoň t+ 1, pak lze chybu detekovat, když došlo při přenosu ke změně na nejvýše t pozicích. Je-li tato vzdálenost alespoň 2r + l, pak takovou chybu lze dokonce i opravit. Protože u polynomiálního kódu je rozdíl libovolných dvou kódových slov opět kódové slovo, lze místo o nejmenší vzdálenosti dvou různých kódových slov hovořit o nejmenší vzdálenosti nenulového kódového slova od nuly. Příklad Zvolme p = 2, tedy písmena jsou 0 a 1. Dále položme n = 5, g(x) = x2 + x + 1. Pak kódová slova jsou polynomy 0, x2+x + l, x3+x2+x, x3 + l, x4 + x3+x2, x4+x3+x + l, x4+x, x4+x2 + l. Budeme-li polynomy psát jako posloupnosti koeficientů, budeme kódovat takto: 000 i-> 00000, 100 i-> 10010, 001 ^ 00111, 101 ^ 10101, 010 i-> 01001, 110 ^ 11011, 011 ^ 01110, 111 ^ 11100. Je ihned vidět, že nejmenší vzdálenost nenulového kódového slova od nuly je 2, jsme tedy schopni detekovat chybu na jedné pozici. Opravit tuto chybu nejsme obecně schopni, například posloupnost 01000 by mohla vzniknout jednou chybou na druhé pozici anebo jednou chybou na páté pozici. Kód opravující chybu na jedné pozici Věta 1. Zvolme prvočíslo p a přirozené číslo m > 1. Necht K je těleso mající právě pm prvků, necht a g K je libovolný generátor multiplikativní grupy Kx tělesa K a g(x) je minimální polynom prvku a nad tělesem Zp. Pak polynomiální kód délky n = p_i daný polynomem g(x) je schopen opravit chybu na jedné pozici. Důkaz. Platí st(g-(x)) = m*, je polynom ax1 kódové slovo, anebo pro nějaká 0 < / < j < n, a, b g Z£, je polynom axJ + bx1 kódové slovo. Protože polynom g(x) je nesoudělný s polynomem x, první případ g{x) \ ax1 vede ke sporu. Druhý případ g{x) | axJ + bx1 = a(xJ~' + ba~ľ)x' dává g{x) \ xJ~' + ba~ľ, tedy oé~l — —ba~ľ g Zp, odkud qC/'-OCp-1) = Protože řád prvku a v grupě Kx je pm — 1, dostáváme pm — 1 | (y — /)(p — 1), tj r? 7 — /, což je ve sporu s tím, že 0 < j — i < n, Užití kódu z věty 1 - kódovaní Parametry kódu: p prvočíslo, m G N, m > 1, K těleso, \K\ = pm Kx = (a), g(x) minimální polynom a nad Zp, n = ^ = p™"1 + p™"2 + • • • + p + 1. Nutný předpoklad pro správnou funkci kódu: K chybám pri přenosu dochází tak zřídka, že lze očekávat, že při odeslání n písmen (tj. koeficientů odesílaného polynomu) bude nejvýše jedno písmeno přijato chybně. Zpráva: polynom b(x) £ Zp[x], st(b(x)) < n — m, dělením se zbytkem: xm • b(x) = g(x) • q(x) + r(x), kde st(r(x)) < m. Odeslaná informace: g{x).q{x)=xm.b{x)-r{x). Užití kódu z věty 1 - dekódovaní Parametry kódu: těleso K, \K\ = pm', p prvočíslo, m > 1, / — 1, t > 0 jsou celá čísla. Předpokládejme, že polynom g(x) je dělitelný minimálním polynomem prvku ar^ pro každé j = 1, 2,..., 2t a platí st(g"(x)) < pm — 1. Pak polynomiální kód délky n = pm — 1 daný polynomem g(x) je schopen opravit chybu na t pozicích. Důkaz. Protože st(g"(x)) < pm — 1, existuje v Kx prvek, který není kořen g(x), a tedy 2t < n. Předpokládejme, že existuje nenulové kódové slovo, jehož vzdálenost od nuly nepřevyšuje 2t. Existují tedy ^1? • • • ? fet £ ne všechny nuly, a 0 < ki < k2 < • • • < k2t < n tak, že polynom r(x) = x)/=i biXki Je kódové slovo, tj. g{x) \ f{x) a f(ar+J) = 0 pro každé 7 = 1,2,..., 2t. Pak (a^k')j^2_2t je matice s lineárně závislými sloupci. Ovšem pro k = x)/=i ^/ P'at^ 0 = det(«(^>0;,/=i,2,...,2t = a{r+1)k • Ui<í