\chyph

\hoffset=-1cm \voffset=-1.2cm \hsize=18cm

\ifx\pdfoutput\undefined \else
\pdfpagewidth=21cm
\pdfpageheight=15cm
\fi


\headline={\setfonts[/10]\rm\hfill [\the\pageno]}
\footline={}

\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�}.


\end

\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 Tvrzen�}: Je-li $K$ cyklic�, $g\in K$ a je-li $f$ libovoln� polynom, pak
$f\cdot g\in K$.
V�po�et $f\cdot g$ je proveden v $\Z_p[x]/(x^n-1)$.

D�kaz: $(b_mx^m + \cdots + b_1x + b_0)\cdot g$ v $\Z_p[x]/(x^n-1)$ 
je line�rn� kombinace cyklick�ch posun� polynomu $g$.

{\bf Definice}: Nenulov� polynom cyklick�ho k�du nejmen��ho stupn�
naz�v�me {\em generuj�c� polynom}.

Z�ejm� pro generuj�c� polynom plat�: $K=\{f\cdot g;\ f$ je lib. polynom$\}$.

\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�s 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: nech� $v\in K$. 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$.\hb
Proto�e st$\,v<n$, je st$\,f< m = n -{}$st$\,g$. Libovoln� $v\in K$ lze
zapsat jako 
$$
  v = (f_{m-1}x^{m-1} + \cdots + f_1x + f_0)\cdot g
$$
neboli jako line�rn� kombinaci prvk� 
$\{g, x\cdot g, x^2\cdot g, \ldots, x^{k-1}\cdot g\}$.
Tyto prvky jsou LN, tak�e tvo�� b�zi k�du $K$. Je tedy $m=k$
a st$\,g = n - k$.

Punt�k t�et�: d�litelnost ov���me analogicky (mus� $z=0$).

\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 Sytematick� 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�o 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
