Navrhněte binární lineární kód, který umožní zakódovat šestiprvkové informační části tak, aby bylo možné současně opravovat jednoduché a odhalovat dvojité chyby.

Požadovaným parametrům vyhovuje kód s Hammingovou vzdáleností $d_0 = 4$:

Příkladem takového kódu je rozšířený Hammingův kód (standardní má $d_0=3$, rozšířený o paritní bit má $d_0=4$). Nejprve tedy vyrobíme zákadní Hammingův kód, který později rozšíříme o paritní bit.

Standardní Hammingův $(n,k)$ kód kóduje $k$ informačních znaků $n$-znakovým kódem. To znamená, že navíc obsahuje $r=n-k$ zabezpečovacích znaků. Pro opravu jednonásobné chyby musí platit, že počet nenulových syndromů ($2^r-1$) je větší nebo roven délce kódu $n=k+r$, tj.

$$2^r \ge k + r + 1.$$

Pro $k=6$ postupně zjišťujeme:

$$r = 1: \qquad 2^1 < 6 + 1 + 1$$

$$r = 2: \qquad 2^2 < 6 + 2 + 1$$

$$r = 3: \qquad 2^3 < 6 + 3 + 1$$

$$r = 4: \qquad 2^4 > 6 + 4 + 1$$

Začneme tedy sestavením Hammingova kódu se čtyřmi zabezpečovacími znaky, tj. kódu $(10,6)$. Připomeňme, že generující matice $G$ v systematickém tvaru má v levé části jednotkovou matici, v pravé části pomocou matici $B$. Řádky $B$ musí mít alespoň dvě jedničky; sestavíme je tak, že postupně píšeme binární podoby čísel 1, 2, 3, ... a vynecháváme ty, které obsahují jen jednu jedničku:

$$ G_{(10,6)} = (I_6 | B_4) = \left( \begin{array}{cccccc|cccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \end{array} \right) $$

Všimněme si, že v matici $B_4$ jsme nevyčerpali všechny možnosti, tj. náš kód není perfektní.

Nyní stačí řádky generující matice doplnit o paritní bit, čímž získáme rozšířený Hammingův kód požadovaných vlastností:

$$ G_{(11,6)} = (I_6 | B_5) = \left( \begin{array}{cccccc|cccc|c} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \end{array} \right) $$

Kontrolní matici můžeme vytvořit dvojím způsobem, oba jsou rovnocenné.

První: zapíšeme kontrolní matici k původní generující matici $G_{(10,6)} = (I_6|B_4)$ jako $H_{(10,6)}=(-B^T_4|I_4)$. Tu doplníme o nulový sloupec vpravo (tj. do standardních Hammingových kontrolních rovnic paritní bit nezasahuje) a o řádku plnou jedniček (kontrolní rovnice pro paritní bit):

$$ H_{(11,6)} = \left( \begin{array}{cccccc|cccc|c} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0\\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0\\ \hline 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{array} \right) $$

Alternativně můžeme vzít rovnou matici $G_{(11,6)}=(I_6 | B_5)$ a přepsat ji do kontrolní matice $H'{(11,6)}=(-B^T_5 | I_5)$:

$$ H'_{(11,6)} = \left( \begin{array}{cccccc|ccccc} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0\\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0\\ 1 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \end{array} \right) $$

Kódem z předchozí úlohy zakódujte zprávu 110000.

$$\mathbf{u} = (1\ 1\ 0\ 0\ 0\ 0)^T$$

$$ \begin{align} \mathbf{v} = G_{(11,6)}^T\cdot\mathbf{u} &= \left( \begin{array}{cccccc|cccc|c} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \end{array} \right) \cdot \left( \begin{array}{c} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{array} \right) \\ &= \,\Big( \begin{array}{cccccc|cccc|c} 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \end{array} \Big)^T \end{align} $$

(Návod: sečteme ty řádky matice $G^T$, kde je ve sloupci $\mathbf{v}$ jednička.)

Kódovou značku z předchozí úlohy poškoďte na první pozici, chybu detekujte a opravte.

Chybový vektor označíme $\mathbf{e}$ a děláme, jako že ho neznáme. Kódová značka poškozená na první pozici je:

$$\mathbf{w} = \mathbf{v} + \mathbf{e} = (0\ 1\ 0\ 0\ 0\ 0\ 0\ 1\ 1\ 0\ 0)^T$$

Výpočet syndromu, například kontrolní maticí $H_{(11,6)}$:

$$ \begin{align} \mathbf{s} = H_{(11,6)}\cdot\mathbf{w} = &\left( \begin{array}{cccccc|cccc|c} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0\\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0\\ \hline 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{array} \right) \cdot\\ \cdot &\,\left( \begin{array}{cccccc|cccc|c} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \end{array} \right)^T=\\ = & \left( \begin{array}{cccccc|cccc|c} 0 \\ 0 \\ 1 \\ 1 \\ 1 \end{array} \right) \end{align} $$

(Návod: sečteme ty sloupce matice $H$, kde se v řádce $\mathbf{w}$ vyskytují jedničky.)

Výsledkem je první sloupec matice $H_{(11,6)}$, čili k chybě došlo na první pozici. Proto určíme chybový vektor jako

$$\mathbf{e} = (1\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0)^T$$

a následně opravíme chybu:

$$\mathbf{v} = \mathbf{w} - \mathbf{e} = (1\ 1\ 0\ 0\ 0\ 0\ 0\ 1\ 1\ 0\ 0)^T$$

Díky systematičnosti kódu zahodíme posledních pět zabecpečovacích bitů, čímž extrahujeme vysílanou zprávu

$$\mathbf{u} = (1\ 1\ 0\ 0\ 0\ 0)^T$$

Poznámka: Kdybychom byli použili matici $H'_{(11,6)}$, získali bychom

$$ \begin{align} \mathbf{s'} = H'_{(11,6)}\cdot\mathbf{w} = &\left( \begin{array}{cccccc|ccccc} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0\\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0\\ 1 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \end{array} \right) \cdot\\ \cdot &\,\left( \begin{array}{cccccc|ccccc} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \end{array} \right)^T=\\ = & \left( \begin{array}{cccccc|cccc|c} 0 \\ 0 \\ 1 \\ 1 \\ 1 \end{array} \right) \end{align} $$

Jde o první sloupec matice $H'_{(11,6)}$, čili znovu usoudíme, že k chybě došlo na první pozici. Pozor! V tomto případě vyšly syndromy $\mathbf{s}$ a $\mathbf{s'}$ stejné, protože první sloupce matic $H_{(11,6)}$ a $H'_{(11,6)}$ jsou rovněž stejné. Obecně ale syndromy mohou vyjít různé!

Opět kódujte zprávu 110000. Tentokrát poškoďte kódovou značku na 2. a 8. pozici. Detekujte chybu.

Chybový vektor označíme $\mathbf{e}$ a děláme, jako že ho neznáme. Kódová značka poškozená na druhé a osmé pozici je:

$$\mathbf{w} = \mathbf{v} + \mathbf{e} = (1\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 1\ 0\ 0)^T$$

Výpočet syndromu, například kontrolní maticí $H_{(11,6)}$:

$$ \begin{align} \mathbf{s} = H_{(11,6)}\cdot\mathbf{w} = &\left( \begin{array}{cccccc|cccc|c} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0\\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0\\ \hline 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{array} \right) \cdot\\ \cdot &\,\left( \begin{array}{cccccc|cccc|c} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \end{array} \right)^T=\\ = & \left( \begin{array}{cccccc|cccc|c} 0 \\ 0 \\ 0 \\ 1 \\ 0 \end{array} \right) \end{align} $$

(Návod: sečteme ty sloupce matice $H$, kde se v řádce $\mathbf{w}$ vyskytují jedničky.)

Výsledkem je sloupec, který v matici $H_{(11,6)}$ nenajdeme, čili došlo k neopravitelné chybě. Z vlastností kódu usoudíme, že jde o chybu dvojnásobnou.

Samostatně ověřte, že ke stejnému závěru dojdeme i použitím matice $H'_{(11,6)}$.

Sdělovací kanál přenáší 120 znaků za vteřinu. Binární zdroj generuje 100 znaků za vteřinu. Navrhněte lineární kód, který umožní opravovat jednoduché chyby.

Ke splnění požadavku potřebujeme kód s Hammingovou vzdáleností 3.

Pokud bychom použili opakovací kód, tj. každý znak třikrát zopakovali, potřebovali bychom přenosovou rychlost 300 znaků za vteřinu. My máme ale k dispozici jen 120 znaků za vteřinu.

Použijeme proto úspornější kód požadovaných vlastností - nějaký Hammingův kód.

Pokud bychom použili (7, 4), kód, potřebovali bychom

$$100\times\frac{7}{4} = 175\ \text{znaků za vteřinu,}$$

což je také moc. Zkoumejme proto tzv. informační poměr $k/n$ Hammingových kódů:

$r = n-k$	$n = 2^r - 1$	$k = n - r$	$k/n$	$100\times n/k$
2	3	1	0,333	300,00
3	7	4	0,571	175,00
4	15	11	0,733	136,36
5	31	26	0,839	119,23
6	63	57	0,905	110,53
7	127	120	0,945	105,83
8	255	247	0,969	103,24

Z posledního sloupce tabulky vidíme, že kvůli kapacitě kanálu lze uvažovat jen o kódech s alespoň 5 zabezpečovacími bity. To je vidět i z informačního poměru $k/n$, který požadujeme větší než 100 / 120 = 0,833.

Se zvyšujícím se počtem zabezpečovacích znaků pochopitelně klesají nároky na kapacitu přenosového kanálu. Na druhou stranu roste délka kódového slova, tj. zvyšuje se riziko, že v přenosu kódové značky dojde k více než jedné chybě. Zkoumejme proto pravděpodobnost dvoj- a vícenásobné chyby ve slově délky $n$.

Je-li pravděpodobnost chyby v přenosu jednoho znaku rovna $p$, je pravděpodobnost bezchybného přenosu slova rovna

$$p_0 = (1-p)^n,$$

pravděpodobnost jednonásobné chyby je

$$p_1 = np(1-p)^{n-1}.$$

Pravděpodobnost dvoj- a vícenásobné chyby je tak rovna

$$p_{2+} = 1 - p_0 - p_1.$$

Podívejme se na pravděpodobnost $p_{2+}$ kritické chyby pro různá $n$ a $p$:

Co to fakticky znamená? Dejme tomu, že pravděpodobnost chyby při přenosu jednoho znaku je $p = 10^{-6}$, rychlost generování znaků je $g = 100$ znaků za vteřinu. To znamená, že dojde k chybě jednou za $1/p = 10^6$ vyslaných znaků, čili jednou za

$$\frac{1}{3600 \times g \times p} = 2{,}78\ \text{hodin},$$

čili asi k 8,64 chybám za den. Pokud znaky nezabezpečujeme, chybné znaky se přenesou bez povšimnutí.

Pokud použijeme Hammingův kód (31, 26), je podle výše uvedených vztahů pravděpodobnost bezchybného přenosu slova $p_0 = 0{,}999969$, pravděpodobnost jednonásobné chyby v kódové značce $p_1 = 3{,}1\times 10^{-5}$, pravděpodobnost horší (nedetekované a neopravené) chyby $p_{2+} = 4{,}65\times 10^{-10}$.

To znamená, že k nedetekované a neopravené chybě dojde jednou za

$$\frac{1}{p_{2+}}\ \text{kódových značek,}$$

čili jednou za

$$\frac{n}{p_{2+}}\ \text{odeslaných bitů.}$$

Rychlost odesílání znaků ze zdroje prostřednictvím (n, k) kódu je

$$g\times\frac{n}{k},$$

čili k nedetekované a neopravené chybě dojde jednou za

$$ \frac{n}{p_{2+}} / \frac{gn}{k} \ \text{vteřin}. $$

Po dosazení zjistíme, že k nedetekované a neopravené chybě dojde jednou za 17,7 roku.

Stejným způsobem zjistíme, že k jednonásobné (a tedy opravené) chybě dochází jednou za 2,3 hodiny, čili poněkud častěji než při nezabezpečeném přenosu přímo ze zdroje. Důvod je prostý - s Hammingovým kódem posíláme rychleji více znaků, čili k chybě by logicky mělo docházet častěji.

Kdybychom za stejných okolností ($p = 10^{-6}$) použili například Hammingův kód (255, 247), zjistili bychom, že k nedetekované a neopravené chybě dojde jednou za 2,4 roku. Že bude výsledek horší než při použití kódu (31, 26) se dalo tušit už z výše uvedené tabulky pravděpodobností $p_{2+}$ - i tam se vzrůstající délkou kódové značky roste pravděpodobnost chyby.

Proto usoudíme, že budeme pokud možno dávat přednost kratším kódovým značkám a plnému využití přenosové kapacity kanálu.

Navrhněte ternární Hammingův kód se dvěma zabezpečujícími znaky.

Při návrhu vyjdeme z konstrukce kontrolní matice. Víme, že by měla mít dva řádky (počet kontrolních znaků) a že sloupce by se od sebe měly lišit, tj. jeden nesmí být násobkem druhého. Napišme si nejdřív všechny sloupce dvou znaků z abecedy {0, 1, 2}:

0	0	0	1	1	1	2	2	2
0	1	2	0	1	2	0	1	2

V kontrolní matici nesmí být nulový sloupec. Do kontrolní matice budeme postupně zařazovat sloupce zleva doprava, přičemž vynecháme násobky již zařazených:

	0		1	1	1
	1		0	1	2

(Uvědomme si, že v ternární aritmetice je 2 × 2 = 1, tj. 2 × ( 1, 2) = ( 2, 1 ) apod.)

Dále víme, že kontrolní matice je výhodná v systematickém tvaru $H = (B\ |\ I)$. Sloupce tedy zapíšeme v požadovaném pořadí:

$$ H = \left( \begin{array}{cc|cc} 1 & 1 & 1 & 0\\ 1 & 2 & 0 & 1 \end{array} \right) $$

Generující matice má systematický tvar $G = (-B^T\ |\ I)$:

$$ G = \left( \begin{array}{cc|cc} 1 & 0 & -1 & -1\\ 0 & 1 & -1 & -2 \end{array} \right) = \left( \begin{array}{cc|cc} 1 & 0 & 2 & 2\\ 0 & 1 & 2 & 1 \end{array} \right) $$

Zkusme pro ilustraci zakódovat zprávu 20, kód poškodit a následně opravit:

$$\mathbf{u} = \begin{pmatrix} 2 \\ 0\end{pmatrix}$$

$$\mathbf{v} = G^T\cdot\mathbf{u} = \begin{pmatrix} 2 & 0 & 1 & 1\end{pmatrix}^T$$

Při přenosu došlo k chybě na první pozici:

$$\mathbf{w} = \begin{pmatrix} 0 & 0 & 1 & 1\end{pmatrix}^T$$

Spočítáme syndrom jako lineární kombinaci sloupců kontrolní matice:

$$\mathbf{s} = H\cdot\mathbf{w} = 1\begin{pmatrix} 1 \\ 0\end{pmatrix} + 1\begin{pmatrix} 0 \\ 1\end{pmatrix} = \begin{pmatrix} 1 \\ 1\end{pmatrix}$$

Syndrom je jedno-násobkem prvního sloupce matice $H$, a proto

$$\mathbf{e} = \begin{pmatrix} 1 & 0 & 0 & 0\end{pmatrix}^T$$

Jelikož platí $\mathbf{w} = \mathbf{v} + \mathbf{e}$, musí platit

$$ \mathbf{v} = \mathbf{w} - \mathbf{e} = \begin{pmatrix} 0 \\ 0 \\ 1 \\ 1\end{pmatrix} - \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0\end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 1 \\ 1\end{pmatrix} + \begin{pmatrix} 2 \\ 0 \\ 0 \\ 0\end{pmatrix} = \begin{pmatrix} 2 \\ 0 \\ 1 \\ 1\end{pmatrix} $$

čímž po odříznutí dvou kontrolních znaků dostáváme původní zprávu 20.