KIV / TI - Teoretická informatika
Cvičení 8 - Úvod do teorie kódování

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:

znakkódová značkaznakkódová značka
A0F1100
B1000G1101
C1001H1110
D1010I11110
E1011J11111

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:

znakkódová značkaznakkódová značka
A0D21
B1E22
C20F?

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.

znakkódová značkaznakkódová značka
A2F12
B00G010
C02H112
D10I0110
E11J0111
K0112

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:

  1. všechna slova splňující podmínku $x_2+x_3=x_5$,
  2. všechna slova splňující podmínku $x_2+x_3=1$,
  3. všechna slova se dvěma jedničkami,
  4. 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:

+01
001
110
×01
000
101

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.

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  1. 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í.

  2. 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$$

  3. 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$.

  4. 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).

  5. 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:

  6. 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$:

+012
0012
1120
2201
×012
0000
1012
2021

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":

+01234
001234
112340
223401
334012
440123
×01234
000000
101234
202413
303142
404321

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.