Existuje binární prefixové kódování abecedy A, B, C, ..., J (10 znaků), které znak A kóduje značkou 0 a ostatní značky mají délku nejvýše 5?
Řešení: Délky $d_1$, $d_2$, ..., $d_K$ všech kódových značek libovolného n-árního prefixového kódu musí splňovat Kraftovu nerovnost:
$$n^{-d_1} + n^{-d_2} + \cdots + n^{-d_K} \le 1.$$
My požadujeme, aby délka kódové značky znaku A měla délku 1 ($d_1 = 1$), ostatní délku nejvýše 5 ($d_i \le 5$ pro $i=2, 3, \dots, 10$). Zřejmě platí
$$2^{-d_1} + 2^{-d_2} + \cdots + 2^{-d_K} \ge 2^{-1} + 9\times 2^{-5} = \frac{1}{2} + \frac{9}{32} = \frac{25}{32},$$
což je menší než 1, a proto by takové kódóvání mohlo existovat. Příklad:
| znak | kódová značka | znak | kódová značka |
|---|---|---|---|
| A | 0 | F | 1100 |
| B | 1000 | G | 1101 |
| C | 1001 | H | 1110 |
| D | 1010 | I | 11110 |
| E | 1011 | J | 11111 |
Konkrétně pro toto kódování je
$$n^{-d_1} + n^{-d_2} + \cdots + n^{-d_K} = 2^{-1} + 7\times 2^{-4} + 2\times 2^{-5} = 1.$$
Existuje ternární prefixový kód znaků A, B, C, D, E, F s předepsanými délkami kódových značek 1, 1, 2, 2, 2, 2?
Řešení: Pokusíme-li se sestavit kód metodou pokus-omyl, navrhneme například toto:
| znak | kódová značka | znak | kódová značka |
|---|---|---|---|
| A | 0 | D | 21 |
| B | 1 | E | 22 |
| C | 20 | F | ? |
Pro znak F už neumíme kódovou značku najít. Neúspěch metody pokus-omyl ale není důkazem. K němu využijeme Kraftovu nerovnost. Platí
$$n^{-d_1} + n^{-d_2} + \cdots + n^{-d_K} = 2\times 3^{-1} + 4\times 3^{-2} = \frac{2}{3} = \frac{4}{9} = \frac{10}{9} > 1,$$
a proto takové kódování nemůže existovat.
Najděte nejkratší prefixový ternární kód pro abecedu A, B, C, ..., K (11 znaků) s pravděpodobnostmi 0.2, 0.18, 0.15, 0.12, 0.1, 0.08, 0.07, 0.04, 0.04, 0.01, 0.01.
Řešení: Nejkratší prefixový kód vzniká Huffmanovým postupem. V první fázi sestavíme následujícím způsobem strom.
Znaky seřadíme podle pravděpodobnosti výskytu a rozdělíme je na skupiny po $n-1$ znacích, kde $n$ je základ abecedy kódu; pro ternární kód ($n=3$) tedy tvoříme skupiny po dvou znacích (na obrázku modrá čára). Pokud má poslední skupina pouze jeden znak, sloučíme ji s předposlední (na obrázku červená čára).
Z poslední skupiny vytvoříme "shluk", jehož pravděpodobnost je součtem pravděpodobností složek. Tento shluk zařadíme do seřazené posloupnosti znaků na své místo a v procesu pokračujeme tak dlouho, dokud to jde. Pravděpodobnost výsledného shluku je samozřejmě 1.
Stavba Huffmanova stromu
V druhé fázi postupujeme od kořene stromu k listům. Jednotlivým větvím vycházejícím z kořene přiřadíme počáteční znak kódové značky, tj. nějaký ze znaků $0$, $1$, ..., $n-1$ (na obrázku níže zelené znaky). Rekurzivně zpracujeme všechny následníky kořene: na začátek kódové značky uzlu přitom zařadíme kódový řetězec z nadřazeného uzlu (na obrázku níže červené znaky). Takto projdeme celý strom.
Tvorba kódových značek
Uvedeným postupem přiřadíme každému znaku vstupní abecedy kódovou značku. Z postupu je zřejmé, že libovolná kódová značka není prefixem jiné kódové značky, jde tedy o prefixový kód.
| znak | kódová značka | znak | kódová značka |
|---|---|---|---|
| A | 2 | F | 12 |
| B | 00 | G | 010 |
| C | 02 | H | 012 |
| D | 10 | I | 0110 |
| E | 11 | J | 0111 |
| K | 0112 |
Uvažujme lineární prostor $Z_2^5$, tj. pětisložkové vektory $x_1 x_2 x_3 x_4 x_5$ nad tělesem $Z_2$ (čili z nul a jedniček). Zjistěte, zda jsou následující podmnožiny lineárními kódy:
- všechna slova splňující podmínku $x_2+x_3=x_5$,
- všechna slova splňující podmínku $x_2+x_3=1$,
- všechna slova se dvěma jedničkami,
- všechna slova s méně než třemi jedničkami.
Řešení: Připomeňme si, že operace + a × jsou nad tělesem $Z_2$ definovány takto:
| + | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
| × | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
Dále platí: jsou-li vektory $\mathbf{u}$, $\mathbf{v}$ prvky lineárního prostoru, potom i jejich libovolná lineární kombinace je prvkem lineárního prostoru, tj.
$$\forall \mathbf{u}\in Z_2^5, \forall \mathbf{v}\in Z_2^5, \forall \alpha\in Z_2, \forall\beta\in Z_2:\quad \alpha \mathbf{u} + \beta \mathbf{v} \in Z_2^5$$
V případě tělesa $Z_2$ se situace zjednodušuje, jelikož $\alpha$ a $\beta$ mohou nabývat pouze hodnot 0 a 1. Stačí tak ověřit, zda do lineárního prostoru patří nulový vektor a součet libovolných dvou prvků vektorového prostoru.
-
Všechna slova splňující podmínku $x_2+x_3=x_5$.
Pro $x_1 x_2 x_3 x_4 x_5 = 00000$ zjevně platí, že $x_2+x_3=x_5$.
Dále musíme ověřit, že pro libovolné dva prvky $\mathbf{x}$ a $\mathbf{y}$ splňující uvedenou podmínku splňuje podmínku i jejich součet $\mathbf{z}$. Symbolicky si součet zapíšeme:
$x_1$ $x_2$ $x_3$ $x_4$ $x_5$ $+$ $y_1$ $y_2$ $y_3$ $y_4$ $y_5$ $z_1$ $z_2$ $z_3$ $z_4$ $z_5$ Pro vektor $\mathbf{z}$ platí:
$$z_2 = x_2 + y_2$$
$$z_3 = x_3 + y_3$$
$$z_5 = x_5 + y_5 = (x_2 + x_3) + (y_2 + y_3) = (x_2 + y_2) + (x_3 + y_3) = z_1 + z_3$$
Tedy i pro součet $\mathbf{z} = \mathbf{x} + \mathbf{y}$ platí omezující podmínka. Jde o lineární kód.
-
Všechna slova splňující podmínku $x_2+x_3=1$.
Nulový vektor $x_1 x_2 x_3 x_4 x_5 = 00000$ nesplňuje podmínku. Není to lineární kód.
-
Všechna slova se dvěma jedničkami.
Nulový vektor $x_1 x_2 x_3 x_4 x_5 = 00000$ nesplňuje podmínku. Není to lineární kód.
-
Všechna slova s méně než třemi jedničkami.
Nulový vektor $x_1 x_2 x_3 x_4 x_5 = 00000$ splňuje podmínku.
Vektory $11000$ a $00110$ podmínku splňují, ale jejich součet $11110$ už ne. Není to lineární kód.
Víme, že všechny pětice $x_1 x_2 x_3 x_4 x_5$, pro které $x_2 + x_3 = x_5$, tvoří lineární kód. Určete jeho dimenzi, bázi, kontrolní rovnice, generující a kontrolní matici. Zakódujte slovo 0101 a výsledný kód zkontrolujte.
Ve značce je 5 prvků, z toho jeden je závislý ostatních. Čtyři si ale můžeme zvolit libovolně. Proto je dimenze kódu 4. Také můžeme říkat, že kód má čtyři informační bity a jeden kontrolní.
Báze musí mít čtyři lineárně nezávislé prvky. Pokud si řekneme že $x_1 x_2 x_3 x_4$ jsou informační bity, stačí zvolit čtyři lineárně nezávislé čtveřice informačních bitů a ke každé dopočítat kontrolní bit $x_5$. Příklad:
$$\mathbf{b}_1 = 1\ 0\ 0\ 0\ 0$$
$$\mathbf{b}_2 = 0\ 1\ 0\ 0\ 1$$
$$\mathbf{b}_3 = 0\ 0\ 1\ 0\ 1$$
$$\mathbf{b}_4 = 0\ 0\ 0\ 1\ 0$$
Je-li dimenze kódu 4 a značky jsou pětiprvkové, musí existovat právě jedna (= 5 - 4) kontrolní rovnice. Ta je pochopitelně řečena hned definicí kódu, tj. $x_2 + x_3 = x_5$.
Jednotlivé řádky generující matice $G$ tvoří bázi lineárního kódu. Proto v generující matici pouze sepíšeme značky $\mathbf{b}_1$ až $\mathbf{b}_4$:
$$G = \left(\begin{array}{cccc|c} 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 1 & 0 \end{array}\right)$$
Díky zvoleným bázovým prvkům je kód dokonce systematický, tj. jeho generující matice má vlevo jednotkovou podmatici $I$, vpravo pomocnou matici $B$ (v našem případě degenerovanou na sloupec).
Kontrolní matice pouze formálně sepisuje kontrolní rovnice přepsané do homogenního tvaru. Ten získáme snadno. V rovnici $x_2+x_3=x_5$ převedeme všechny proměnné na jednu stranu, čili $x_2 + x_3 - x_5 = 0$. Protože v tělesu $Z_2$ je opačným prvkem k jedničce rovněž jednička, přepíšeme rovnici na ekvivalentní tvar
$$x_2 + x_3 + x_5 = 0.$$
Tuto rovnici jen přepíšeme do maticové podoby:
$$H = \left(\begin{array}{cccc|c} 0 & 1 & 1 & 0 & 1 \end{array}\right)$$
Označíme-li si délku kódových značek jako $n$ (v našem případě 5) a dimenzi kódu jako $k$ (v našem případě 4), má kontrolní matice $n$ sloupců a $n-k$ řádků. Generující matice má opět $n$ sloupců, ale $k$ řádků.
Je-li generující matice kódu systematická, tj. platí $G = (\, I_k\, |\, B\, )$, kde $I_k$ je jednotková matice velikosti $k\times k$, má kontrolní matice tvar $H = (\, -B^T\, |\, I_{n-k}\, )$. V našem případě je podmatice $B$ sloupec, v matici $H$ ji najdeme jako řádku. Jednotková podmatice v kontrolní matici v tomto případě degenerovala na rozměry $1\times 1$, čili je tvořena jednou jedničkou.
Graficky si můžeme matice systematických lineárních kódů ukázat takto:
-
Slovo $\mathbf{u} = 0101$ zakódujeme násobením generující maticí $G$:
$$ \mathbf{v} = G^T\mathbf{u} = \begin{pmatrix} 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 1 & 0 \end{pmatrix}^T \cdot \begin{pmatrix} 0\\ 1\\ 0\\ 1 \end{pmatrix} = \begin{pmatrix} 0 & 1 & 0 & 1 & 1 \end{pmatrix}^T. $$
Násobení sloupce $\mathbf{u}$ maticí $G^T$ je vlastně lineární kombinací jejích řádků. Řádky matice $G^T$, které máme zkombinovat, jsou dány nenulovými prvky sloupce $\mathbf{u}$. Pro přehlednost je vhodné zapsat si výsledek (sloupec $\mathbf{v}$) v transponované podobě.
Výsledný kód $\mathbf{v}$ zkontrolujeme vynásobením kontrolní maticí:
$$ \begin{align} H\mathbf{v} = {}&\begin{pmatrix} 0 & 1 & 1 & 0 & 1 \end{pmatrix} {}\cdot{}\\ {}\cdot{}&\begin{pmatrix} 0 & 1 & 0 & 1 & 1 \end{pmatrix}^T = \begin{pmatrix} 0 \end{pmatrix}. \end{align} $$
Násobení sloupce $\mathbf{v}$ maticí $H$ je vlastně lineární kombinací jejích sloupců. Sloupce matice $H$, které máme zkombinovat, jsou dány nenulovými prvky sloupce $\mathbf{v}$. Pro přehlednost je vhodné zapsat si sloupec $\mathbf{v}$ v transponované podobě a pod maticí $H$.
Je dána generující matice $G$ nad tělesem $Z_3$. Určete kontrolní matici $H$ lineárního kódu generovaného maticí $G$.
$$G = \begin{pmatrix} 1 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 1 & 1\\ 1 & 1 & 0 & 0 & 0\end{pmatrix}$$
Řešení: Pro pořádek si napišme definici operací + a × nad tělesem $Z_3$:
| + | 0 | 1 | 2 |
|---|---|---|---|
| 0 | 0 | 1 | 2 |
| 1 | 1 | 2 | 0 |
| 2 | 2 | 0 | 1 |
| × | 0 | 1 | 2 |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 |
| 2 | 0 | 2 | 1 |
Z tabulek si pro přehlednost vypíšeme opačné prvky (vzhledem k operaci +) a inverzní prvky (vzhledem k operaci ×):
| opačné prvky | ||
| $-0$ | $\equiv$ | $0$ |
| $-1$ | $\equiv$ | $2$ |
| $-2$ | $\equiv$ | $1$ |
| inverzní prvky | ||
| $1^{-1}$ | $\equiv$ | $1$ |
| $2^{-1}$ | $\equiv$ | $2$ |
Generující matice $G$ generuje třírozměrný (má tři řádky) podprostor pětirozměrného (má pět sloupců) lineárního prostoru $Z_3^5$.
Kontrolní matice $H$ k němu tvoří ortogonální doplněk, tj. ortogonální podprostor dimenze 2 (= 5 - 3).
Je-li $\mathbf{u}$ tříprvkový sloupcový vektor (zpráva, kterou kódujeme), je výsledký kód roven $\mathbf{v}=G^T \mathbf{u}$. Pro každý kód pak musí platit $H\mathbf{v}=\mathbf{0}$. Proto
$$H\mathbf{v} = HG^T\mathbf{u} = \mathbf{0}\quad \Rightarrow \quad HG^T = \mathbf{0},$$
čili řádky matic $G$ a $H$ jsou navzájem ortogonální.
K hledání matice $H$ můžeme použít následující postup. Nechť $(h_1\ h_2\ h_3\ h_4\ h_5)$ je řádek matice $H$. Vynásobíme-li jej postupně se všemi řádky matice $G$, dostaneme soustavu tří rovnic:
$$\begin{align} h_1 + h_2 + h_3 + h_4 + h_5 &= 0\\ \phantom{h_1 + {}}h_2 + h_3 + h_4 + h_5 &= 0\\ h_1 + h_2 \phantom{{}+ h_3 + h_4 + h_5} &= 0\end{align}$$
Úpravou dostaneme:
$$\begin{align} h_1 &= 0\\ h_2 &= 0\\ h_3 + h_4 + h_5 &= 0\end{align}$$
Připomeňme, že nás zajímají netriviální, tj. nenulová řešení. Z posledního rovnice plyne, že dva z prvků $h_3$, $h_4$, $h_5$ si můžeme libovolně zvolit. Zvolíme-li např. $h_4=0$, $h_5=1$, dostaneme $h_3=2$; z rovnic již víme, že $h_1=h_2=0$. Tak jsme určili jednu řádku matice $H$. Druhou řádku určíme například z volby $h_4=1$, $h_5=0$; zapíšeme již celkovou matici H:
$$H=\left(\begin{array}{ccc|cc} 0 & 0 & 2 & 1 & 0\\ 0 & 0 & 2 & 0 & 1 \end{array}\right)$$
Díky "systematickému" tvaru kontrolní matice (napravo má jednotkou podmatici velikosti 2 × 2) můžeme snadno zapsat alternativní generující matici kódu v systematickém tvaru:
$$G'=\left(\begin{array}{ccc|cc} 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 1 \end{array}\right)$$
Alternativní řešení: Ke stejnému řešení bychom dospěli, kdybychom původní generující matici převedli na systematický tvar a k němu vytvořili kontrolní matici:
$$G = \begin{pmatrix} 1 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 1 & 1\\ 1 & 1 & 0 & 0 & 0\end{pmatrix} \sim \begin{pmatrix} 1 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 1 & 1\\ 0 & 0 & 2 & 2 & 2\end{pmatrix} \sim \begin{pmatrix} 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 1 & 1 & 1\\ 0 & 0 & 1 & 1 & 1\end{pmatrix} \sim \left(\!\!\begin{array}{ccc|cc} 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 1\end{array}\!\!\right) = G' $$
Kódy nad $Z_5$
Zadání: Nad tělesem $Z_5$ vypočtěte $3\times 4 + 2\times 2 + 2\times 3\times 4$.
Řešení: Nejprve si pro přehlednost sestavíme tabulky operací + a × ve smyslu "modulo 5":
| + | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 |
| 1 | 1 | 2 | 3 | 4 | 0 |
| 2 | 2 | 3 | 4 | 0 | 1 |
| 3 | 3 | 4 | 0 | 1 | 2 |
| 4 | 4 | 0 | 1 | 2 | 3 |
| × | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 |
| 2 | 0 | 2 | 4 | 1 | 3 |
| 3 | 0 | 3 | 1 | 4 | 2 |
| 4 | 0 | 4 | 3 | 2 | 1 |
Z tabulek si pro přehlednost opět vypíšeme opačné prvky (vzhledem k operaci +) a inverzní prvky (vzhledem k operaci ×):
| opačné prvky | ||
| $-0$ | $\equiv$ | $0$ |
| $-1$ | $\equiv$ | $4$ |
| $-2$ | $\equiv$ | $3$ |
| $-3$ | $\equiv$ | $2$ |
| $-4$ | $\equiv$ | $1$ |
| inverzní prvky | ||
| $1^{-1}$ | $\equiv$ | $1$ |
| $2^{-1}$ | $\equiv$ | $3$ |
| $3^{-1}$ | $\equiv$ | $2$ |
| $4^{-1}$ | $\equiv$ | $4$ |
Nyní snadno spočítáme:
$$Z_5:\quad 3\times 4 + 2\times 2 + 2\times 3\times 4 = 2 + 4 + 1\times 4 = 1 + 4 = 0$$
Alternativně můžeme využít znalosti, že operace + a × jsou sestaveny jako (modulo 5): můžeme napřed určit výsledek v tělesu celých čísel a poté jej operací (modulo 5) převést do tělesa $Z_5$.
$$Z:\quad 3\times 4 + 2\times 2 + 2\times 3\times 4 = 12 + 4 + 24 = 40$$
$$40\ \text{mod}\ 5 = 0$$
Zadání: Může být matice $A$ uvedená níže generující maticí lineárního kódu? Pokud ano, převeďte ji na systematický tvar.
$$A = \begin{pmatrix} 1 & 4 & 1 & 1 & 1\\ 2 & 4 & 0 & 0 & 1\\ 0 & 2 & 1 & 1 & 1\end{pmatrix}$$
Řešení: Jediným požadavkem na generující matici lineárního kódu je lineární nezávislost řádek. O ní se přesvědčíme řádkovými úpravami matice s cílem převést ji na stupňovitý tvar:
$$A = \begin{pmatrix} 1 & 4 & 1 & 1 & 1\\ 2 & 4 & 0 & 0 & 1\\ 0 & 2 & 1 & 1 & 1 \end{pmatrix} \sim \begin{pmatrix} 1 & 4 & 1 & 1 & 1\\ 0 & 1 & 3 & 3 & 4\\ 0 & 2 & 1 & 1 & 1 \end{pmatrix} \sim \begin{pmatrix} 1 & 4 & 1 & 1 & 1\\ 0 & 1 & 3 & 3 & 4\\ 0 & 0 & 0 & 0 & 3 \end{pmatrix} $$
Všechny řádky jsou nenulové, a proto jsou řádky matice $A$ lineárně nezávislé. Matice $A$ může být generující maticí lineárního kódu.
Poslední úprava matice nicméně ukazuje, že řádkovými úpravami ji nepůjde upravit na systematický tvar. K tomu bychom potřebovali prohodit třetí a pátý sloupec:
$$ \begin{pmatrix} 1 & 4 & 1 & 1 & 1\\ 0 & 1 & 4 & 3 & 3\\ 0 & 0 & 3 & 0 & 0 \end{pmatrix} \sim \begin{pmatrix} 1 & 4 & 1 & 1 & 1\\ 0 & 1 & 4 & 3 & 3\\ 0 & 0 & 1 & 0 & 0 \end{pmatrix} \sim \begin{pmatrix} 1 & 4 & 0 & 1 & 1\\ 0 & 1 & 0 & 3 & 3\\ 0 & 0 & 1 & 0 & 0 \end{pmatrix} \sim \left(\!\!\begin{array}{ccc|cc} 1 & 0 & 0 & 4 & 4\\ 0 & 1 & 0 & 3 & 3\\ 0 & 0 & 1 & 0 & 0 \end{array}\!\!\right) = G' $$
Kontrolní matici k systematickému kódu vytvoříme snadno. Připomeňme, že pro generující matici $G'=(I|B)$ má kontrolní matice tvar $H'=(-B^T|I)$, tedy
$$ H' = \left(\begin{array}{ccc|cc} -4 & -3 & 0 & 1 & 0\\ -4 & -3 & 0 & 0 & 1 \end{array}\right) \equiv \left(\begin{array}{ccc|cc} 1 & 2 & 0 & 1 & 0\\ 1 & 2 & 0 & 0 & 1 \end{array}\right) $$
Abychom získali kontrolní matici k původnímu kódu, musíme vrátit třetí a pátý sloupec na své místo:
$$ H = \left(\begin{array}{ccccc} 1 & 2 & 0 & 1 & 0\\ 1 & 2 & 1 & 0 & 0 \end{array}\right) $$
Zkusme si pro ilustraci zakódovat slovo $\mathbf{u}=012$ a provést kontrolu kódu. Nejprve maticemi $A$ a $H$:
$$\text{kódování:}\qquad A^T\mathbf{u} = \begin{pmatrix} 1 & 4 & 1 & 1 & 1\\ 2 & 4 & 0 & 0 & 1\\ 0 & 2 & 1 & 1 & 1 \end{pmatrix}^T \cdot \begin{pmatrix} 0\\ 1\\ 2 \end{pmatrix} = \begin{pmatrix} 2 & 3 & 2 & 2 & 3 \end{pmatrix}^T = \mathbf{v} $$
$$ \begin{align} \text{kontrola:}\qquad H\mathbf{v} = {} &\begin{pmatrix} 1 & 2 & 0 & 1 & 0\\ 1 & 2 & 1 & 0 & 0 \end{pmatrix} \cdot{}\\ {}\cdot{}& \,\,\begin{pmatrix} 2 & 3 & 2 & 2 & 3 \end{pmatrix}^T = %\begin{pmatrix} %(2 + 6 + 0 + 2 + 0)\ \text{mod}\ 5\\ %(2 + 6 + 2 + 0 + 0)\ \text{mod}\ 5 %\end{pmatrix} %= \begin{pmatrix} 0\\ 0 \end{pmatrix} \end{align} $$
Zkusme ještě matice $G'$ a $H'$:
$$\text{kódování:}\qquad {G'}^T\mathbf{u} = \begin{pmatrix} 1 & 0 & 0 & 4 & 4\\ 0 & 1 & 0 & 3 & 3\\ 0 & 0 & 1 & 0 & 0 \end{pmatrix}^T \cdot \begin{pmatrix} 0\\ 1\\ 2 \end{pmatrix} = \begin{pmatrix} 0 & 1 & 2 & 3 & 3 \end{pmatrix}^T = \mathbf{v} $$
$$ \begin{align} \text{kontrola:}\qquad H'\mathbf{v} = {} & \begin{pmatrix} 1 & 2 & 0 & 1 & 0\\ 1 & 2 & 0 & 0 & 1 \end{pmatrix} \cdot\\ {}\cdot{} & \,\, \begin{pmatrix} 0 & 1 & 2 & 3 & 3 \end{pmatrix}^T = %\begin{pmatrix} %(0 + 2 + 0 + 3 + 0)\ \text{mod}\ 5\\ %(0 + 2 + 0 + 0 + 3)\ \text{mod}\ 5 %\end{pmatrix} %= \begin{pmatrix} 0\\ 0 \end{pmatrix} \end{align} $$
V obou případech násobení kódové značky kontrolní maticí vyšel nulový sloupec - kontrola tedy proběhla v pořádku. Všimněme si, že kódová slova vzniklá maticemi $A$ a $G'$ jsou zcela odlišná. To má dva důvody. První: matici $A$ jsme upravovali řádkovými úpravami, čímž se sice nemění množina kódových slov, ale mění se vzájemné přiřazení mezi zprávami $\mathbf{u}$ a jejich kódovanými podobami $\mathbf{v}$. Druhý: v matici $A$ jsme navíc prohazovali sloupce, čímž se v kódových slovech prohazují znaky. Vzniká tak ekvivalentní kód.