\chyph \hoffset=-1cm \voffset=-1.2cm \hsize=18cm \ifx\pdfoutput\undefined \else \pdfpagewidth=21cm \pdfpageheight=15cm \fi \font\logocvut=lev scaled400 \ifx\zkratka\undefined\edef\zkratka{\jobname}\fi \def\cislo{18} \headline={\setfonts[/10]\rm \ifnum\pageno>1 \hfill {\setfonts[/7] BI-LIN, \zkratka, \cislo, P. Olšák \quad}\else \firstpage\hfill\fi [\the\pageno]} \footline={} \def\firstpage{\vbox to0pt{\kern13.7cm\hbox{% \setfonts[/8] a) \zkratka, \cislo, b) P. Olšák, FEL ČVUT, c) P. Olšák 2010, d) BI-LIN, e) L, f) 2009/2010, g) \lower1pt\hbox{\logocvut L}. Viz p. d. 4/2010 }\vss}} \input ofs [a35] %\def\fomenc{CM} %\showfonts \end %\displayfontmessages \setfonts[NewCentury/17] \setmath[17/12/8] \baselineskip=22pt \normalbaselineskip=\baselineskip \message{\fontname\tenit} \medskipamount=9pt \let\ms=\medskip \parskip=\medskipamount \def\n#1\par{\vfill\break} \def\g#1\par{{\null \vskip-31pt \baselineskip=30pt\setfonts[/23]\bf #1\par}\medskip} \def\gg#1\par{{\setfonts[/55]\bf #1}\medskip} \def\hb{\hfil\break} \def\emerge{{\emergencystretch=2em\par}} \parindent=0pt \catcode`\*=13 \def* {\par \hangindent=15pt \hangafter=1 \noindent \hbox to\hangindent {$\bullet$\hss}} \let\em=\it \def\C{{\bf C}} \def\R{{\bf R}} \def\Q{{\bf Q}} \def\a{{A}} \def\A{{\bf A}} \def\B{{\bf B}} \def\D{{\bf D}} \def\E{{\bf E}} \def\G{{\bf G}} \def\H{{\bf H}} \def\P{{\bf P}} \def\L{{\bf L}} \def\U{{\bf U}} \def\X{{\bf X}} \def\Z{{\bf Z}} \def\Circ{\mathbin{\raise.1em\hbox{$\scriptscriptstyle\bigcirc$}}} \def\ker{\mathop{\rm Ker}} \def\st{\mathop{\rm St}} \def\hod{\mathop{\rm hod}} \def\vecc #1_#2{\vec#1_1, \vec#1_2, \ldots, \vec#1_{#2}} \def\lob<#1>{\langle #1\rangle} \def\|{||} % =============================================================== \vglue .5cm \gg Úvod do kódování \bigskip\bigskip * samoopravné kódy: terminologie, princip * blokové lineární kódy * Hammingův kód * cyklické kódy \n --------------------------------------------------------------- \g Samoopravné kódy, k čemu to je * Data jsou uložena (nebo posílána do linky) {\em kodérem} podle určitého pravidla ({\em kódování\/}). Posléze jsou čtena {\em dekodérem} a restaurována do původní podoby. * Kodér může přidat k datům doplňující informaci (zhruba řečeno kontrolní součet) a umožnit tím dekodéru, aby poznal, zda při přenosu dat došlo k chybě. Dokonce při vhodně zvoleném kódování může dekodér chybu opravit. {\em Kód} je množina slov (tj. úseků dat), které může generovat kodér. {\bf Příklady kódů}: * ASCII (slova sedmibitová, ne všechna) * Morseova abeceda (slova různě dlouhá, efektivní přenos) * UTF-8 (slova různě dlouhá, délka rozpoznaná podle prefixu) \n ------------------------------------------------------- \g Binární, blokový kód je kód, kde jsou všechna slova stejně dlouhá. {\bf Definice}: Nechť $A$ je množina znaků (abeceda).\hb {\em Slovo} je konečná posloupnost znaků z množiny $A$.\hb Počet znaků ve slově je {\em délka slova}.\hb {\em Kód} $K$ je množina všech slov, která generuje kodér.\hb Prvek kódu $K$ se nazývá {\em kódové slovo}.\hb {\em Blokový kód} $K$ obsahuje jen slova stejné délky.\hb {\em Binární kód} je kód se slovy nad abecedou $A=\{0,1\}$. {\bf Příklady:} * ASCII je binární blokový kód délky 7. * Moreseovka není binární a není blokový kód. * UTF-8 je binární, ale ne blokový kód. Dále se budeme zabývat jen binárními blokovými kódy \n ------------------------------------------------------ \g Lineární kód Binární blokový kód $K$ délky $n$ je podmnožinou lin. prostoru~$\Z_2^n$. {\bf Definice}: Je-li $K$ lienární podprostor $\Z_2^n$, pak se kód nazývá {\em lineární}. Je-li dimenze kódu $k$, pak mluvíme o lineárním $(n,k)$ kódu. {\bf Příklad}: Kód s kontrolním bitem parity je lineární. Kodér přidává nulu nebo jedničku k informačním bitům tak, aby kódové slovo obsahovalo sudý počet jedniček. Množina všech slov délky $n$ se sudým počtem jedniček je lineární podprostor lineárního prostoru~$\Z_2^n$. \n ----------------------------------------------------- \g Generující a kontrolní matice {\em Generující matice\/} lineárního kódu $K$ je matice, která v řádcích obsahuje bázi kódu. {\em Kontrolní matice\/} lineárního kódu $K$ je matice $\H$, pro kterou platí, že $K$ je řešením soustavy $\H\,{\bf x} = {\bf o}$. {\bf Příklad}: Předpokládejme lineární $(4,3)$ kód s kontrolním bitem parity (přidávaný na konec slova za tři informační bity). Generující matice $\G$ a kontrolní matice $\H$ jsou: $$ \G = \pmatrix{1&0&0&1\cr 0&1&0&1\cr 0&0&1&1}, \qquad \H = \pmatrix{1&1&1&1} $$ {\bf Pozorování}: Generující matice $(n,k)$ kódu je typu $(k,n)$ a kontrolní matice je typu $(n-k,n)$. Platí: $\G\cdot\H^T = {\bf O}$. \n ----------------------------------------------------- \g Výpočet jedné matice, známe-li druhou Je-li dána generující (resp. kontrolní) matice, vyřešíme homogenní soustavu rovnic s touto maticí a bázi řešení zapíšeme do řádků kontrolní (resp. generující) matice. Pro systematický kód dokonce platí: Je-li $\G = (\E\,|\,\C)$, pak $\H = (\C^T\,|\,\E')$. \n ----------------------------------------------------- \g Kodér a dekodér Kodér lin. $(n,k)$ kódu může převzít kódované slovo $\vec u$ (délky~$k$) a vytvořit z něj kódové slovo $\vec v$ (délky $n$) maticovým násobením: $$ \vec v = \vec u \cdot \G. $$ Dekodér může zkontrolovat přijaté slovo $\vec w$ pomocí testu: $$ \H \cdot \vec w^T = {\bf o}. $$ Kódování je {\em systematické}, jsou-li informační bity (ze slova $\vec u$) beze změny zkopírovány do kódového slova a za nimi následují kontrolní bity. Pak může dekodér (po provedeném testu) rekonstruovat informační bity zkopírováním prvních $k$ pozic přijatého slova. {\bf Pozorování}: Kódování je systematické, je-li generující matice tvaru $\G = (\E\,|\,\C)$. Přidávané kontrolní bity pak kodér spočítá pomocí vzorce $\vec v' = \vec u\cdot \C$. \n ---------------------------------------------------------- \g Příklad: opakovací kód Kodér vezme kódované slovo $\vec u$ délky $k$ a vytvoří kódové slovo délky $n=2k$ tak, kódové slovo je tvaru $(\vec u,\vec u)$, tj. kódované slovo je zdvojené. Generující matice tohoto kódu je $\G = (\E\,|\,\E)$ a kontrolní matice je také tvaru $\H = (\E\,|\,\E)$. Uvědomte si, jak je kód pomocí $\G$ generován a jak je pomocí $\H$ kontrolován. {\bf Nevýhoda}: příliš mnoho kontrolních bitů za \uv{málo muziky}. \n --------------------------------------------------------- \g Hammingova váha, vzdálenost {\bf Definice}: {\em Hammingova váha\/} slova $\vec v$ je počet jeho nenulových znaků. {\em Hammingova vzdálenost\/} dvou slov $\vec v$ a $\vec w$ je počet pozic, kde jsou znaky odlišné (pro binární kód je to váha slova $\vec v+\vec w$). Kód $K$ {\em objevuje $t$ chyb}, pokud pro každé slovo $\vec u\in K$ a každé slovo $\vec e$ váhy menší nebo rovno $t$ platí $\vec u+\vec e\not\in K$. Kód $K$ {\em opravuje $t$ chyb}, pokud pro každé slovo $\vec u\in K$ a každé slovo $\vec e$ váhy menší nebo rovno $t$ platí: slovo $\vec u$ má od slova $\vec u+\vec e$ nejmenší vzdálenost mezi kódovými slovy. {\bf Tvrzení 1}: Je-li nejmenší vzdálenost mezi kódovými slovy $d$, pak kód objevuje $d-1$ chyb a opravuje $t<{d\over 2}$ chyb. {\bf Tvrzení 2}: Nejmenší vzdálenost mezi kódovými slovy {\em lineárního\/} kódu je rovna nejmenší váze nenulového kódového slova. \n ----------------------------------------------------------- \g Příklady Kód s kontrolním bitem parity má nejmenší váhu nenulového slova 2, takže objevuje $2-1 = 1$ chybu ve slově. Opravuje méně než $2/2$ chyb, tedy neopravuje žádnou chybu. Opakovací kód má rovněž nejmenší váhu nenulového slova 2. Aby kód dokázal opravit jednu chybu ve slově, musí mít nejmenší váhu neulového slova rovnu třem. \n ------------------------------------------------------------ \g Syndrom Dekodér vyhodnotí ${\bf s} = \H\cdot\vec w^T$. Tomuto vektoru ${\bf s}$ říkáme {\em syndrom\/} přijatého slova $\vec w$. Přijaté slovo je kódové, právě když má nulový syndrom. Kód rozpozná chybu $\vec e$, právě když ${\bf s} = \H\cdot\vec e^T$ je nenulový vektor. {\bf Pozorování 1}: Syndrom nezávisí na kódovém slově (jen na chybovém slově): $\H\cdot(\vec v+\vec e)^T = \H\cdot\vec v^T + \H\cdot\vec e^T = {\bf o} + \H\cdot\vec e^T = \H\cdot\vec e^T$. {\bf Pozorování 2}: Lin. kód má minimální vzdálenost dvou slov~$d$, právě když každý výběr $d-1$ sloupců z kontrolní matice $\H$ je lineárně nezávislý. Jmenovitě: kód opravuje jednu chybu když každé dva sloupce kontrolní matice $\H$ jsou LN, tj. jsou nenulové a vzájemně různé (to v~$\Z_2^{n-k}$ stačí). Kontrolní matice s touto vlastností je kontrolní matice {\em Hammingova kódu}. \n ------------------------------------------------------------ \g Hammingův kód Sloupce kontrolní matice $\H$ jsou prvky $\Z_2^{n-k}$. Počet nenulových a vzájemně různých sloupců je maximálně $2^{n-k}-1$. Počet sloupců udává délku kódu $n$, tedy $n=2^{n-k}-1$. Délku kódu je tedy vhodné volit jako mocninu dvou bez jedné. Dostáváme tak Hammingovy kódy: $(7,4)$, $(15,11)$, $(31,26)$, $(63,57)$, \dots. Příklad: Hammingův kód $(7,4)$ -- délka 7, informační bity 4: $$ \H = \pmatrix{0&0&0&1&1&1&1\cr 0&1&1&0&0&1&1\cr 1&0&1&0&1&0&1}, \quad \G = \pmatrix{1&0&0&0&0&1&1\cr 0&1&0&0&1&0&1\cr 0&0&1&0&1&1&0\cr 0&0&0&1&1&1&1}. $$ Výhoda tohoto uspořádání: index bitu, který je potřeba opravit, je zapsán v syndromu jako číslo ve dvojkové soustavě. \n ------------------------------------------------------------- \g Rozšířený Hammingův kód je Hammingův kód, ke kterému kodér přidává kontrolní bit parity. Například $(8,4)$ kód má matice $$ \def\quad{\hskip.7em} \H = \pmatrix{0&0&0&1&1&1&1&0\cr 0&1&1&0&0&1&1&0\cr 1&0&1&0&1&0&1&0\cr 1&1&1&1&1&1&1&1}, \quad \G = \pmatrix{1&0&0&0&0&1&1&1\cr 0&1&0&0&1&0&1&1\cr 0&0&1&0&1&1&0&1\cr 0&0&0&1&1&1&1&0}. $$ Kód opraví jednu chybu (v prvních třech bitech je syndrom jako v~$(7,4)$ kódu a čtvrtý bit musí být 1) a odhalí dvě chyby (v prvních třech bitech syndromu je nenulové číslo a čtvrtý bit je 0). Nejmenší vzdálenost dvou slov v tomto kódu je 4. \n --------------------------------------------------------------- \g Návrh počtu kontrolních bitů Označme $n$ délku binárního kódu, $k$ dimenzi kódu (počet informačních bitů) a $c=n-k$ počet kontrolních bitů. Lineární kód nemůže opravit více rozdílných chyb než je počet nenulových syndromů. Těch je $2^c-1$. Počet různých chyb s váhou jedna je $n$. Proto, chceme-li opravit jednu chybu, musí $2^c-1\ge n$. Počet různých chyb (včetně stavu \uv{bez chyby}) s váhou nejvýše $m$ je rovno $$ {n\choose 0} + {n\choose 1} + \cdots + {n\choose m} $$ Chceme-li opravovat $m$ chyb ve slově, musí tedy počet kontrolních bitů splňovat: $$ 2^c \ge {n\choose 0} + {n\choose 1} + \cdots + {n\choose m} $$ Kódy navržené tak, že zde nastává rovnost, se nazývají {\em perfektní}. \n --------------------------------------------------------------- \g Cyklické kódy jsou běžně užívané samoopravné kódy (např. při zápisu/čtení CD). Viz google: CRC (cyclic redundancy check). {\bf Definice}: Kód $K$ se nazývá {\em cyklický}, pokud * je lineární a navíc * je-li $\vec v$ kódové slovo, pak cyklický posun $\vec v$ je také kódové slovo. Vhodná matematická reprezentace slov délky $n$ jsou polynomy: $$ \vec v = (a_0,a_1,a_2\ldots,a_{n-1}) \quad \leftrightarrow \quad v(x) = a_0 + a_1x + a_2x^2 + \cdots + a_{n-1}x^{n-1} $$ Cyklický posun slova $\vec v$ o jednu pozici popíšeme násobením polynomu $v(x)$ polynomem $x$ a ztotožněním $x^n = x^0$, neboli násobením v okruhu $\Z_p[x]/(x^n - 1)$. Od této chvíle nerozlišujeme mezi pojmem \uv{slovo} a \uv{polynom}. \n ---------------------------------------------------------------- \g Základní vlastnosti cyklického kódu {\bf Definice}: Nenulový polynom cyklického kódu nejmenšího stupně nazýváme {\em generující polynom}. {\bf Tvrzení}: Je-li $K$ cyklický kód délky $n$ a $g$ je jeho generující polynom, pak $$ K=\{f\cdot g;\ \hbox{st}\,f < n - \hbox{st}\,g\} $$ Důkaz: $v = (f_{m-1}x^{m-1} + \cdots + f_1x + f_0)\cdot g$ je lineární kombinace cyklických posunů, takže leží v~$K$.\hb Obráceně, nechť $v\in K$, pak vydělíme $v$ polynomem $g$ se zbytkem:\hb $v = f\cdot g + z$, protože $v\in K$, $f\cdot g\in K$, musí $z\in K$.\hb Protože st$\,z <{}$st$\,g$ a polynom $g$ má nejmenší stupeň, musí $z=0$.\ \n ------------------------------------------------------------------ \g Vlastnosti generujícího polynomu {\bf Tvrzení}: Nechť $g$ je generující polynom $(n,k)$ cyklického kódu $K$. * polynom $g$ má stupeň $n-k$, * $\{g, x\cdot g, x^2\cdot g, \ldots, x^{k-1}\cdot g\}$ je báze kódu, * polynom $x^n-1$ je dělitený polynomem $g$. Důkaz: $K=\{f\cdot g;\ \hbox{st}\,f < n - \hbox{st}\,g\}$, takže $\dim K=n - \hbox{st}\,g$, neboli stupěň $g=n-\dim K$. Puntík druhý: zřejmé. Puntík třetí: polynom $x^n-1$ vydělíme polynomem $g$ se zbytkem. V~polynomech mod $x^n-1$ je zbytek roven $-f\cdot g$, takže leží v kódu a má menší stupeň, než $g$, takže zbytek je nulový. \n ------------------------------------------------------------------ \g Generující polynom: postačující podmínka {\bf Tvrzení}: Aby byl polynom $g$ generující polynom nějakého cyklického kódu, stačí, aby dělil polynom $x^n-1$ beze zbytku. Důkaz: Zjistíme, že lin. obal všech cyklických posunů $g$ neobsahuje nenulový polynom st. menšího než $g$. Nechť $f$ je libovolný polynom. $$ f\cdot g = z \quad\hbox{mod } (x^n-1), \quad \hbox{tj.} \quad f\cdot g = u\cdot(x^n-1) + z $$ Je třeba ověřit, že $z=0$ nebo st$\,z\ge{}$st$\,g$. Protože je $f\cdot g$ dělitelný $g$ a $u\cdot(x^n-1)$ je dělitelný $g$, musí též $z$ být dělitelný $g$, takže $z = v\cdot g$. {\bf Návrh cyklického kódu}: Zvolíme délku bloku $n$, rozložíme polynom $x^n-1$ na součin ireducibilních polynomů a generující polynom~$g$ zvolíme jako součin {\em některých} takto nalezených ireducibilních polynomů. Stupeň $g$ je počet kontrolních bitů kódu. {\bf Úmluva}: Všechny gen. polynomy stejného kódu se liší až na skalární násobek. Volme takový, co má u nejvyšší mocniny jedničku. \n ------------------------------------------------------------------- \g Odhalení souvislé chyby {\em Souvislá chyba délky $t$} je chyba měnící kódové slovo v úseku některých po sobě jdoucích $t$ bitů, jinde je slovo nezměněno. Počet chyb (váha chybového slova) nemusí být $t$, ale je menší nebo rovna~$t$. {\bf Pozorování}: Cyklický $(n,k)$ kód odhaluje všechny souvislé chyby délky $n-k$. Důkaz: Na souvislou chybu $\vec e$ můžeme provést (opakovaně) cyklický posun a získat polynom $\vec e'$, který je stupně menšího než $n-k$. Takže $\vec e'$ ani $\vec e$ není kódové slovo. {\bf Poznámka}: toto je důvod, proč se v praxi používají cyklické kódy. Chyby se totiž rády v konkrétním technickém prostředí soustřeďují do bloků (drupouty, škrábance na CD atd.). Existují cyklické $(n,k)$ kódy, které navíc {\em umějí opravit\/} všechny souvislé chyby délky $(n-k)/2$. \n ----------------------------------------------------------------- \g Příklad: Cyklický Hammingův kód Sestavme $(7,4)$ cyklický kód, který má generující polynom $x^3 + x + 1$. Je to generující polynom, protože dělí polynom $x^7-1$. Kód má následující generující a kontrolní matici $$ \G = \pmatrix {1&1&0&1&0&0&0\cr 0&1&1&0&1&0&0\cr 0&0&1&1&0&1&0\cr 0&0&0&1&1&0&1}, \quad \H = \pmatrix {1&0&1&1&1&0&0\cr 1&1&1&0&0&1&0\cr 0&1&1&1&0&0&1}, $$ takže vidíme, že $\H$ má různé a nenulové sloupce. Je to tedy Hammingův $(7,4)$ kód. Hammingův $(7,4)$ kód, který kóduje podle této $\G$ a používá tuto kontrolní matici $\H$ umí odhalit i tři {\em souvislé} chyby. Od Hammingova kódu ze strany [12] se liší pořadím bitů kódového slova. \n -------------------------------------------------------- \g Generující a kontrolní matice Protože cyklický kód má bázi $g,\ x\cdot g,\ x^2\cdot g,\ \ldots,\ x^{k-1}\cdot g$, kde $g$ je generující polynom, $g(x) = g_0 + g_1x + g_2x^2 + \cdots + g_{n-k}x^{n-k}$, je generující matice tvaru $$ \G = \pmatrix{g_0& g_1& g_2& \ldots& g_{n-k}& 0& 0& \ldots &0& 0\cr 0& g_0& g_1& \ldots& g_{n-k-1} &g_{n-k} & 0& \ldots &0& 0\cr 0& 0& g_0& \ldots& g_{n-k-2} &g_{n-k-1} &g_{n-k} & \ldots &0& 0\cr & & & \ldots & & &&\ldots &&\cr 0&0&0& \ldots & \ldots &g_0 & g_1& \ldots & g_{n-k-1}& g_{n-k}} $$ Polynom $h = (x^n-1) / g$ se nazývá {\em kontrolní polynom}. Dá se ukázat, že matice s koeficienty kontrolního polynomu $h_k, h_{k-1}, \ldots , h_1, h_0$ umístěnými (v tomto pořadí) opakovaně \uv{podél vedlejší diagonály}, je maticí kontrolní. Ta se v případě cyklických kódu v dekóderu příliš nevyužívá. \n ---------------------------------------------------------- \g Kodér a dekodér cyklického kódu {\bf Kódování podle generující matice} není systematické. Kodér z~informačních bitů $\vec u$ vytvoří kódové slovo $\vec u\cdot\G$. Fakticky tedy vytváří kódové slovo ve tvaru $u\cdot g$. Dekodér spočítá {\em syndrom\/} přijatého slova jako zbytek po dělení generujícím polynomem. Je-li nulový, je přijaté slovo kódové. Výsledek dělení obsahuje informační bity. {\bf Pozorování}: Syndrom nezávisí na kódovaném slovu, ale pouze na chybě: $$ f\cdot g + e = s_1 \hbox{ mod } g, \quad e = s_2 \hbox{ mod } g, \quad \hbox{pak}\quad s_1 = s_2. $$ Důkaz: $f\cdot g + e = r_1\cdot g + s_1$, $e = r_2\cdot g + s_2$. $s_1-s_2$ je násobek $g$ se stupněm menším, takže $s_1-s_2=0$. \n ---------------------------------------------------------- \g Systematické kódování {\bf Kodér} z informačních bitů $(u_1,u_2,\ldots,u_k)$ sestaví polynom: $$ u(x) = u_1 x^{n-1} + u_2x^{n-2} + \cdots + u_{k-1}x^{n-k+1} + u_kx^{n-k}, $$ vypočítá $z$ jako zbytek po dělení $u$ polynomem $g$ a odešle kódové slovo $u-z$. Proč je kódové? Je $u = f\cdot g + z$. Protože $f\cdot g$ je násobek $g$, musí i $u-z$ být násobek $g$. Navíc součet $u-z$ nepoškodí posledních $k$ informačních bitů. {\bf Dekodér} spočítá syndrom $s$ jako zbytek po dělení přijatého slova polynomem $g$. Je-li $s=0$, je přijaté slovo kódové. Posledních $k$ bitů obsahuje informaci. O analýze syndromu si povíme za chvíli. \n --------------------------------------------------- \g Zbytek po dělení polynomu polynomem se v případě polynomů nad $\Z_2$ hledá snadno. V příkladu zapisujeme bity v opačném pořadí než dosud, tj. $$ (a_{n-1},a_{n-2},\ldots,a_1,a_0) \leftrightarrow a_{n-1}x^{n-1} + a_{n-2}x^{n-1} + \cdots + a_1x + a_0. $$ {\bf Příklad}: Nechť $g = (1011)$. Chceme kódovat informaci $(1111)$. Sestavíme polynom $u=(1111000)$ a dělíme ho polynomem $g$: \def\p#1 #2 #3 #4 {\hbox{\hbox to.6\hsize{\hbox to 7em{\quad #1\hss}\quad #2\hss}% \hbox to 7em{\quad#3\hss}\quad #4}} \medskip \p kodér: {} dekodér: {} \p 1111000 {} 1111111 {} \p 1011 {} 1011 {} \p 0100000 {} 0100111 {} \p\kern.6em1011 {} \kern.6em1011 {} \p 0001100 {} 0001011 {} \p \kern1.7em1011 {} \kern1.7em1011 {} \p 0000111~=~$z$, $u-z$~=~1111111 0000000~=~$s$~(syndrom) {} \n --------------------------------------------------------- \g Analýza syndromu Sestavíme tabulku chyb a jejich syndromů: \let\lra=\leftrightarrow $\vec e_1 \lra \vec s_1$, $\vec e_2 \lra \vec s_2$, \dots, $\vec e_m \lra \vec s_m$. Tabulku vyplníme (dřív, než začneme kódovat) tak, že pro každou chybu $e_i$ spočítáme zbytek při dělení polynomem $g$ a dostaneme $s_i$. Kdybychom měli v paměti uloženu tuto tabulku, pak pro každý syndrom $\vec s_i$ dekodér najde zpětně $\vec e_i$ a přijaté slovo $\vec w$ opraví takto: $\vec v = \vec w - \vec e_i$. Problém: paměťová náročnost + nutnost pro každé přijaté slovo prohledat tabulku. \n ---------------------------------------------------------- \g Analýza syndromu podle Meggitta Učiňme pozorování na příkladu $(7,4)$ cyklického kódu. Tabulka $\vec e_i \lra \vec s_1$, která obsahuje všechny chyby váhy 1, vypadá takto: \medskip \def\p #1 #2 #3{\hbox{\quad $#1 \quad\lra\quad #2$#3}} \p e_1=x^0 s_1=1 {} \p e_2=x^1 s_2=x {} \p e_3=x^2 s_3=x^2 {} \p e_4=x^3 s_4=x+1 {} \p e_5=x^4 s_5=x^2+x {} \p e_6=x^5 s_6=x^2+x+1 {} \p e_7=x^6 s_7=x^2+1 {\quad\dots\ syndrom posledního bitu} Pro syndromy platí: $s_{i+1} = x\cdot s_i$ mod $g$. Přitom $s_8=s_1$. Je tedy možné \uv{protočit syndromy} postupnou aplikací operace \ $x\cdot s_i$ mod $g$. V jednom okamžiku se z každého syndromu stane syndrom posledního bitu. Děláme-li současně cyklický posun přijatého slova, dostal se opravovaný bit na poslední pozici. Opravíme ho tam. \n ------------------------------------------------ \g Algoritmus podle Meggitta Sestavme seznam všech syndromů, které odpovídají všem chybám, které mají na poslední pozici jedničku (seznam všech syndromů posledního bitu). Uložme tento seznam do paměti dekodéru. Seznam zdaleka neobsahuje všechny syndromy. Nechť délka kódu je $n$. Dekodér provede postupně $n$ cyklických posunů přijatého slova (tím ho dostane nakonec do původního stavu) a současně cyklicky protáčí syndrom podle vzorce $s_{i+1} = x\cdot s_i$ mod~$g$. Kdykoli se sydrom shoduje s některým syndromem posledního bitu (ze seznamu), opraví dekodér poslední bit (cyklicky pounutého) přijatého slova. Opravuje-li kód jedinou chybu, obsahuje seznam jediný syndrom posledního bitu. Opravuje-li dvě chyby, pak seznam obsahuje $n$ syndromů. Výpočet probíhá s lineární složitostí (existuje dobře popsaná hw implementace pomocí hradel). \n ----------------------------------------------------- \g Korekce souvislých chyb Existují cyklické kódy, které opravují souvislé chyby délky $t$. Dá se ukázat, že pro takové kódy platí: pokud při \uv{protáčení syndromu} dospějeme k syndromu stupně menšího než $t$, pak lze naráz opravit v odpovídajícím (cyklicky posunutém) přijatém slově všechny kontrolní bity přímo podle (protočeného) syndromu. Inspirace: podívejte se na první řádek tabulky na str. [26]. \n ----------------------------------------------------- \g Příklady \uv{větších} cyklických kódů * Golay code je perfektní kód opravující tři chyby. Je to cyklický $(23,12)$ kód s generujícím polynomem: $$ 1+x^2+x^4+x^5+x^6+x^{10}+x^{11} $$ * CRC 32 je metoda počítání kontrolních součtů (syndromů) dat libovolné délky s generujícím polynomem: $$ 1 + x + x^2 + x^4 + x^5 + x^7 + x^8 + x^{10} + x^{11} + x^{12} + x^{16} + x^{22} + x^{23} + x^{26} + x^{32} $$ K hlubšímu zkoumání této problematiky můžete použít: Jiří Adámek: Foundations of Coding, A Wiley-Interscience publication, 1991, ISBN 0-471-62187-0. Poznámka: Prof. Jiří Adámek byl v letech 1990--1994 vedoucí naší katedry, nyní působí na University of Braunschweig. \end