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. Přenášená informace bude zapsána pomocí abecedy, která má p symbolů (tj. jakýchsi písmen), 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) < 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") — k < n. Kódová slova budou ty polynomy a(x) g Zp[x] stupně st(a) < 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(h) < n — k. Pokud chceme odeslat zprávu zapsanou pomocí n — k symbolů, tj. polynom b{x) = bixn~k~ľ + • • • + bn-^-ix + bn-k g Zp[x] stupně st(b) < 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) < /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 symbolů (daných polynomem b{x)) následovaných k kontrolními symboly (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. Hammingova vzdálenost kódových slov Pro každé dva polynomy a(x), b(x) £ Zp[x] stupňů st(a) < n, st(b) < n, definujeme jejich 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. Máme-li být schopni postřehnout, že došlo k chybě, pokud při přenosu byl právě na jedné pozici přenášený symbol náhodné změněn, je třeba, aby vzdálenost libovolných dvou různých kódových slov byla alespoň 2. Pokud 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 symboly 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 v jednom symbolu. 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-) = 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" 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) = 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, Ještě lepší (pro p > 2) kód opravující chybu na jedné pozici Věta 2. Zvolme prvočíslo p a přirozené číslo m. 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 f(x) je minimální polynom prvku a nad tělesem Zp. Je-li pm — 1 > m + 1, pak polynomiální kód délky n — pm — 1 daný polynomem g(x) — (x — 1) • f(x) je schopen opravit chybu na jedné pozici. Důkaz. Platí st(g-) = m + 1 < n. Stačí tedy ukázat, že žádné kódové slovo nemá vzdálenost 1 nebo 2 od nuly. Předpokládejme naopak, že pro nějaké / g {0,1,..., n — 1}, a g Z*, je polynom ax1 kódové slovo, anebo pro nějaká 0 < / < j < n, a, b g Z*, je polynom ax7 + bx1 kódové slovo. Protože polynom g je nesoudělný s polynomem x, první případ g{x) \ ax1 vede ke sporu. Druhý případ g{x) | axJ + bx1 = a(xy_/ + ba~1)x/ dává g{x) | x7-' + ba-1, odkud x — 1 | x7-' + ba-1, a proto ba~ľ = —1. Dále odtud plyne f{x) \ xJ~' + ba~ = xJ~' — 1, tedy aJ~' = 1. Protože řád prvku a v grupě Kx je n = pm — 1, dostáváme 7 — /, což je ve sporu s tím, že 0 < j — i < n, Kódy opravující chyby na více pozicích Věta 3. Zvolme prvočíslo p a přirozené číslo m. Necht K je těleso mající právě pm prvků, necht a £ K je libovolný generátor multiplikativní grupy Kx tělesa K. Necht r > — 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) < 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") < 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 f (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*'*1)* • Ili^^tí"*' - «*'') užitím vzorce pro Vandermondův determinant. Ale to je součin mající pouze nenulové činitele, neboť a má řád n, spor. Přiklad Věta 3 je zobecněním věty 2, stačí zvolit r — — 1 a t — 1. Je-li p = 2, je i věta 1 důsledkem věty 3, zvolte r — 0, t — 1 a uvědomte si, že ap = a2 je také kořen polynomu g(x). Užijme větu 3 pro konstrukci kódu, který by měl mít skutečně reálné využití (užívá se prý při vyhodnocování QR kódů): Nechť K — Z2[x]/(x4 + x + 1), označme a = x + (x4 + x + 1). Minimální polynom prvků a, a2, a4, a8 je x4 + x + 1. Minimální polynom prvků a3, a6, a12, a9 je x4 + x3 + x2 + x + 1 Minimální polynom prvků a5, a10 je x2 + x + 1. Proto předpoklady předchozí věty pro p = 2, m = 4, r? = 15, r = 0, t = 3 splňuje polynom ^(x) = (x4 + x + 1) • (x4 + x3 + x2 + x + 1) • (x2 + x + 1) = = x10 + x8 + x5 + x4 + x2 + x + 1. Odpovídající kód délky 15 má 5 významových symbolů, 10 kontrolních symbolů a je schopen opravit chyby až na třech pozicích.