V okruhu polynomů $\mathbb{Z}_2[x] / x^6 - 1$ spočítejte $(1 + x + x^3 + x^4 + x^5)\times(1 + x^2 + x^4 + x^5)$, a to jak zjištěním zbytku po dělění $x^6 - 1$, tak s využitím identity $x^6 = 1$
-
Nejprve vynásobíme $(1 + x + x^3 + x^4 + x^5)\times(1 + x^2 + x^4 + x^5)$ v aritmetice $\mathbb{Z}_2$:
$$\begin{align} (1 + x + x^3 + x^4 + x^5)\times(1 + x^2 + x^4 + x^5) &= 1 + x + x^3 + x^4 + x^5 \\ &\quad + x^2 + x^3 + x^5 + x^6 + x^7\\ &\quad + x^4 + x^5 + x^7 + x^8 + x^9\\ &\quad + x^5 + x^6 + x^8 + x^9 + x^{10}\\ &= 1 + x + x^2 + x^{10} \end{align} $$
Následně zjistíme zbytek po dělení $x^6 - 1$, resp. $x^6 + 1$ (protože v $\mathbb{Z}_2$ je $-1 = 1$):
$$ \begin{split} (&x^{10} + x^2 + x + 1) / (x^6 + 1) = x^4 \\ &\underline{x^{10} + x^4} \\ & x^4 + x^2 + x + 1 \end{split} $$
Píšeme, že nad okruhem polynomů $\mathbb{Z}_2[x] / x^6 - 1$ platí
$$ (1 + x + x^3 + x^4 + x^5)\times(1 + x^2 + x^4 + x^5) = 1 + x + x^2 + x^4 $$
Alternativně si můžeme uvědomit, že kromě $x^6=1$ platí $x^7=x$, $x^8=x^2$, $x^9=x^3$ a $x^{10}=x^4$. Proto
$$\begin{align} (1 + x + x^3 + x^4 + x^5)\times(1 + x^2 + x^4 + x^5) &= 1 + x + x^3 + x^4 + x^5 \\ &\quad + x^2 + x^3 + x^5 + 1 + x\\ &\quad + x^4 + x^5 + x + x^2 + x^3\\ &\quad + x^5 + 1 + x^2 + x^3 + x^4\\ &= 1 + x + x^2 + x^4 \end{align} $$
Tentýž výsledek jsme zjistili podstatně rychleji.
Binární cyklický kód vznikne ze slova 110110 cyklickými posuvy a součty. Určete dimenzi kódu, generující polynom $g(x)$, generující matici $G$, kontrolní polynom $h(x)$ a kontrolní matici $H$.
Napřed vytvoříme všechny cyklicky posunuté značky:
$$ \begin{align} \mathbf{v}_1 &= 1\ 1\ 0\ 1\ 1\ 0 \\ \mathbf{v}_2 &= 0\ 1\ 1\ 0\ 1\ 1 \\ \mathbf{v}_3 &= 1\ 0\ 1\ 1\ 0\ 1 \\ &\phantom{{} = {}} 1\ 1\ 0\ 1\ 1\ 0 = \mathbf{v}_1 \end{align} $$
Značku $\mathbf{v}_4$ a vyšší už zjevně nemusíme uvažovat, čili známe tři kódová slova: $\mathbf{v}_1$, $\mathbf{v}_2$, $\mathbf{v}_3$. Další kódová slova najdeme jejich lineárními kombinacemi a případnými cyklickými posuvy.
$$ \begin{align} \mathbf{v}_1 + \mathbf{v}_2 &= 1\ 0\ 1\ 1\ 0\ 1\ = \mathbf{v}_3 \\ \mathbf{v}_1 + \mathbf{v}_3 &= 0\ 1\ 1\ 0\ 1\ 1\ = \mathbf{v}_2 \\ \mathbf{v}_2 + \mathbf{v}_3 &= 1\ 1\ 0\ 1\ 1\ 0\ = \mathbf{v}_1 \\ \mathbf{v}_1 + \mathbf{v}_1 &= 0\ 0\ 0\ 0\ 0\ 0\ = \mathbf{v}_4 \end{align} $$
Kromě značek, které už jsme znali, nám z lineárních kombinací vyšla jediná nová značka $\mathbf{v}_4$. Množina
$$\{\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3, \mathbf{v}_4\}$$
tedy tvoří lineární cyklický kód.
Mezi značkami si vybereme tu, která odpovídá nenulovému polynomu nejnižšího řádu. V našem případě je to $\mathbf{v}_1$; příslušný polynom prohlásíme za generující polynom:
$$g(x) = 1 + x + x^3 + x^4.$$
Stupeň generujícího polynomu je vždy $n-k$, v našem případě $n-k=4$. Jelikož kódové značky jsou šestiznakové, je $n=6$, čili dimenze kódu je $k=2$.
Báze cyklického kódu je proto tvořena dvěma lineárně nezávislými značkami, resp. polynomy. Obecně můžeme bázi zapsat jako množinu polynomů
$$\{g(x), x g(x), x^2 g(x), \ldots, x^{k-1} g(x)\}.$$
V našem případě je báze rovna
$$\{g(x), x g(x)\} = \{1 + x + x^3 + x^4, x + x^2 + x^4 + x^5\}.$$
Jelikož polynom $a_0 + a_1 x + a_2 x^2 + \cdots + a_m x^m$ můžeme formálně zapsat jako $(a_0, a_1, a_2, \ldots, a_m)\cdot(1, x, x^2, \ldots, x^m)^T$, můžeme bázovou množinu zapsat maticově jako
$$ \begin{pmatrix} 1 + x + x^3 + x^4 \\ x + x^2 + x^4 + x^5 \end{pmatrix} = \underbrace{ \begin{pmatrix} 1 & 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 & 1 \end{pmatrix} }_{\displaystyle G} \cdot \begin{pmatrix} 1 \\ x \\ x^2 \\ x^3 \\ x^4 \\ x^5 \end{pmatrix} $$
Generující matice je tedy:
$$ G = \begin{pmatrix} 1 & 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 & 1 \end{pmatrix} $$
Proces kódování nyní můžeme popsat jak známou maticovou formou
$$\mathbf{v} = G^T \mathbf{u},$$
tak polynomiální formou
$$v(x) = g(x) u(x).$$
Pozn.: Vidíme, že naše matice není v systematickém tvaru, čili kód není systematický. Na druhou stranu víme, že ke každému lineárnímu kódu existuje ekvivalentní systematický kód. Jeho konstrukci procvičíme později.
Pro kontrolní polynom $h(x)$ platí
$$g(x) h(x) = x^n - 1.$$
Proto
$$ \begin{split} h(x) = (&x^6 + 1)\ /\ (x^4 + x^3 + x + 1) = x^2 + x + 1 \\ &\underline{x^6 + x^5 + x^3 + x^2}\\ &\phantom{x^6 + {}}x^5 + x^3 + x^2 + 1\\ &\phantom{x^6 + {}}\underline{x^5 + x^4 + x^2 + x}\\ &\phantom{x^6 + x^5 +{}}x^4 + x^3 + x + 1\\ &\phantom{x^6 + x^5 +{}}\underline{x^4 + x^3 + x + 1}\\ &\phantom{x^6 + x^5 + x^4 + x^3 + x +{}}0 \end{split} $$
Pozn.: Všimněme si, že $h(x)$ skutečně dělí $x^n-1$ beze zbytku.
Jak se kontrolní polynom používá? Kódová značka vyjádřená polynomem $v(x)$ je násobkem generujícího polynomu, tj. $v(x) = g(x) u(x)$. Při kontrole značky proto můžeme spočítat $v(x)/g(x)$ a zjistit, zda je zbytek po dělení nulový. Alternativně můžeme polynom $v(x)$ vynásobit kontrolním polynomem:
$$ v(x)h(x) = u(x)g(x)h(x) = u(x) \big(x^n - 1\big) = 0. $$
Připomeňme, že v okruhu polynomů modulo $x^n-1$ platí $x^n = 1$, tedy $x^n - 1 = 1 - 1 = 0$.
Značku tedy můžeme zkontrolovat součinem s kontrolním polynomem.
Alternativně můžeme přejít k maticovému zápisu. Pro kontrolní polynom $h(x) = h_0 + h_1 x + h_2 x^2 + \cdots + h_k x^k$ sestavíme kontrolní matici $H$ ve tvaru:
$$ H = \begin{pmatrix} 0 & \cdots & 0 & 0 & 0 & h_k & h_{k-1} & \cdots & h_2 & h_1 & h_0 \\ 0 & \cdots & 0 & 0 & h_k & h_{k-1} & \cdots & h_2 & h_1 & h_0 & 0 \\ 0 & \cdots & 0 & h_k & h_{k-1} & \cdots & h_2 & h_1 & h_0 & 0 & 0 \\ \vdots & \raise1pt{.}\kern2mu\raise4pt{.}\kern2mu\raise7pt{\Rule{0pt}{7pt}{0pt}.} & & & & & & & \raise1pt{.}\kern2mu\raise4pt{.}\kern2mu\raise7pt{\Rule{0pt}{7pt}{0pt}.} & & \vdots \\ 0 & h_k & h_{k-1} & \cdots & h_2 & h_1 & h_0 & 0 & \cdots & & 0 \\ h_k & h_{k-1} & \cdots & h_2 & h_1 & h_0 & 0 & 0 & \cdots & & 0 \end{pmatrix} $$
V našem případě, kdy $h(x) = 1 + x + x^2$:
$$ H = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 \end{pmatrix} $$
Kontrolu značky $\mathbf{v}$ tak můžeme provést jak násobením kontrolní maticí:
$$\mathbf{s} = H\mathbf{v},$$
tak násobením kontrolním polynomem:
$$s(x) = h(x) v(x).$$
Pokud vyjde nulový vektor, případně nulový polynom, je kódová značka $\mathbf{v}$ zřejmě v pořádku.
Vytvořte binární cyklický kód s generujícím polynomem $g(x) = 1 + x + x^3$ pro čtyřprvkové informační značky. Kódování proveďte jednak pomocí generující matice, jednak pomocí generujícího polynomu.
Stupeň generujícího polynomu je 3, tj. kód bude mít tři zabezpečovací znaky. Celkem bude mít kód 7 = 3 + 4 znaky, tj. jde o kód (7, 4).
Maticí $G$ popíšeme bázi prostoru kódu. Připomeňme, že báze kódu je dána polynomy $g(x)$, $x g(x)$, $x^2 g(x)$, $x^3 g(x)$. Proto
$$ \begin{pmatrix} g(x) \\ x g(x) \\ x^2 g(x) \\ x^3 g(x) \end{pmatrix} = \underbrace{\begin{pmatrix} 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{pmatrix}}_{\displaystyle G} \cdot \begin{pmatrix} 1 \\ x \\ x^2 \\ x^3 \end{pmatrix} $$
Příklad kódování značky 1001:
$$ \mathbf{v} = \begin{pmatrix} 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{pmatrix}^T \cdot \begin{pmatrix} 1 \\ 0 \\ 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 1 & 1 & 0 & 0 & 1 & 0 & 1 \end{pmatrix}^T $$
K témuž výsledku bychom dospěli s využitím polynomiální podoby značky. Připomeňme, že proces kódování je vyjádřen vztahem $v(x) = u(x) g(x)$, tj.
$$ v(x) = (1 + x^3) \times (1 + x + x^3) = 1 + x + x^3 + x^3 + x^4 + x^6 = 1 + x + x^4 + x^6 $$
Koeficienty polynomu $v(x)$ jsou samozřejmě identické v prvky vektoru $\mathbf{v}$, který jsme získali pomocí generující matice.
Napište všechny kódové značky výše definovaného kódu.
K řešení úkolu potřebujeme jeno zakódovat všechny existující značky $\mathbf{u}$:
| $\mathbf{u}$ | $\mathbf{v}$ | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
Všimněme si, že značky mají podobu "samé nuly", "samé jedničky", "1101 a všechny cyklické posuvy", "10111 a všechny cyklické posuvy". Kód je tedy cyklický.
Symbolicky popište jednotlivé bity výše definovaného kódu a zjistěte, jak z kódu $\mathbf{v}$ dekódovat zprávu $\mathbf{u}$.
Ze sloupců generující matice snadno zapíšeme vztahy:
$$ \begin{align} v_1 &= u_1 \\ v_2 &= u_1 + u_2 \\ v_3 &= u_2 + u_3 \\ v_4 &= u_1 + u_3 + u_4 \\ v_5 &= u_2 + u_4 \\ v_6 &= u_3 \\ v_7 &= u_4 \end{align} $$
V kódových znacích se explicitně vyskytují znaky zprávy $u_1$, $u_3$, $u_4$. Znak zprávy $u_2$ se v kódové značce explicitně nevyskytuje. Kód proto není systematický, ani není s žádným systematickým kódem ekvivalentní. Pro dekódování proto potřebujeme provést inverzní operaci ke kódování. Ta se nejjednodušeji zapíše v polynomiální tvaru:
$$u(x) = v(x) / g(x).$$
Vytvořte binární systematický cyklický kód s generujícím polynomem $g(x) = 1 + x + x^3$ pro kódování čtyřprvkových zpráv.. Napište všechny kódové značky a vhodně zvolte generující matici $G$.
Při tvorbě systematického cyklického kódu je vhodné očíslovat znaky zprávy opačně, tj. značíme $\mathbf{u} = (u_3, u_2, u_1, u_0)^T$. Značce odpovídá polynom
$$ u(x) = u_3 x^3 + u_2 x^2 + u_1 x + u_0. $$
Kódové značce $\mathbf{v} = (v_6, v_5, v_4, v_3, v_2, v_1, v_0)^T$ obdobně odpovídá polynom $v(x) = v_6 x^6 + \cdots + v_1 x + v_0$. Získáme jej takto:
- Vypočteme $u(x) x^{n-k}$, tj. v našem případě $u(x) x^3$.
- Vydělíme $(u(x) x^{n-k}) / g(x)$ a zjistíme zbytek $r(x)$.
- Určíme $v(x) = u(x) x^{n-k} + r(x)$.
Příklad kódování zprávy 1101:
$$ \begin{align} u(x) &= x^3 + x^2 + 1 \\ u(x) x^{n-k} &= u(x) x^3 = x^6 + x^5 + x^3 \end{align} $$
$$ \begin{split} (&x^6 + x^5 + x^3) / (x^3 + x + 1) = x^3 + x^2 + x + 1 \\ &\underline{x^6 + x^4 + x^3} \\ &\phantom{x^6 + {}}x^5 + x^4 \\ &\phantom{x^6 + {}}\underline{x^5 + x^3 + x^2} \\ &\phantom{x^6 + x^5 + {}}x^4 + x^3 + x^2 \\ &\phantom{x^6 + x^5 + {}}\underline{x^4 + x^2 +x}\\ &\phantom{x^6 + x^5 + x^4 +{}}x^3 + x\\ &\phantom{x^6 + x^5 + x^4 +{}}\underline{x^3 + x + 1}\\ &\phantom{x^6 + x^5 + x^4 + x^3 + x +{}}1 = r(x) \end{split} $$
Celkem:
$$v(x) = x^6 + x^5 + x^3 + 1,$$
čili
$$\mathbf{v} = (1, 1, 0, 1, 0, 0, 1)^T.$$
Obdobně určíme ostatní kódové značky:
| $\mathbf{u}$ | $\mathbf{v}$ | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Opět si všimněme, že kód je složen ze značek "samé nuly", "samé jedničky", "všechny cyklické posuvy 1011" a "všechny cyklické posuvy 11101". Kód je tedy cyklický. Dále je vidět, že "vzorce" 1011 a 11101 jsou v podstatě stejné jako u nesystematické varianty, jen jsou napsané obráceně. To souvisí s obráceným postupem přiřazení polynomu značce.
Rovněž je zřejmé, že kód je systematický. Pro sestavení generující matice vybereve takové lineárně nezávislé značky $\mathbf{v}$, aby měla generující matice systematický tvar, tj.
$$ G = \left(\begin{array}{cccc|ccc} 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \end{array} \right) $$
Všimněme si, že generující matice $G=(I|B)$ má stejný tvar jako generující matice Hammingova (7, 4) kódu. My jsme při konstrukci Hammingova kódu psali řádky matice $B$ jako binární rozvoje čísel 3, 5, 6, 7 (protože jsme potřebovali binární rozvoje s alespoň dvěma jedničkami), ale toto pořadí jsme si zvolili čistě pro přehlednost. Pokud tedy v Hammingově kódu zvolíme pořadí řádek v matici B jako 5, 7, 6, 3, získáme kód, který je navíc cyklický.
Prověřte detekci shlukové chyby systematickým cyklickým kódem (7, 4) a porovnejte ji s chováním Hammingova kódu.
Připomeňme si napřed, co je to shluková chyba (burst error). Zjednodušeně řečeno, pokud se při přenosu zpráva poškodí, první poškozený znak je na pozici $A$, poslední poškozený znak je na pozici $B$, potom jde o shlukovou chybu délky $B-A+1$. Jinými slovy, pokud popíšeme chybu chybovým vektorem $\mathbf{e}$, pak bude první nenulový znak na pozici $A$, posledný nenulový znak na pozici $B$. V binárním (7, 4) kódu mohou vypadat chybové vektory shlukové chyby délky 3 například takto (pro $A=2$, $B=4$):
0 1 1 1 0 0 0
0 1 0 1 0 0 0
Aby kód detekoval shlukovou chybu délky L, musí ji umět detekovat kdekoliv v kódové značce, tj. pro libovolné $A$. Pro tyto účely budeme uvažovat i cyklický posuv chyby, tj. i případ, kdy shluk poškozených znaků "začíná na konci značky a končí na jejím začátku". Všechny chybové vektory shlukové chyby délky 3 jsou tedy:
1 1 1 0 0 0 0 1 0 1 0 0 0 0
0 1 1 1 0 0 0 0 1 0 1 0 0 0
0 0 1 1 1 0 0 0 0 1 0 1 0 0
0 0 0 1 1 1 0 0 0 0 1 0 1 0
0 0 0 0 1 1 1 0 0 0 0 1 0 1
1 0 0 0 0 1 1 1 0 0 0 0 1 0
1 1 0 0 0 0 1 0 1 0 0 0 0 1
Zopakujme, že cyklický $(n,k)$ kód s generujícím polynomem $g(x)$ stupně $n-k$ umí detekovat shlukové chyby až do délky $n-k$ včetně. Cyklický kód (7, 4), který jsme odvodili v předchozím příkladu, by měl detekovat shlukové chyby do délky 3 včetně. Připomeňme, že generující a kontrolní matice jsou
$$ G = \left(\begin{array}{cccc|ccc} 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \end{array} \right) $$
$$ H = \left(\begin{array}{cccc|ccc} 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1 \end{array} \right) $$
Snadno určíme syndromy $\mathbf{s} = H\mathbf{e}$ pro všechny shlukové chyby délky 3:
| $\mathbf{e}$ (délka 3) | $\mathbf{s}$ | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
| $\mathbf{e}$ (délka 3) | $\mathbf{s}$ | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 |
Vidíme, že ve všech případech vyšel syndrom nenulový. Připomeňme, že náš cyklický kód má Hammingovu vzdálenost 3, čili je schopen detekovat libovolnou dvojnásobnou či jednonásobnou chybu (ne nutně shlukovou). Ověřili jsme tak, že cyklický kód detekuje shlukové chyby až do délky 3.
Srovnejme toto chování se standardním Hammingovým kódem. Jeho kontrolní matici jsme konstruovali tak, aby byl každý sloupec jiný, aby byly sloupečky s jedinou jedničkou na pravé straně matice (a tvořily jednotkovou podmatici). Dále, čistě pro pořádek, jsme sloupečky psali jako binární reprezentace přirozených čísel ve vzestupném pořadí. Kontrolní a generující matice tedy vypadaly takto:
$$ G_\text{Hamming} = \left(\begin{array}{cccc|ccc} 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{array} \right) $$
$$ H_\text{Hamming} = \left(\begin{array}{cccc|ccc} 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1 \end{array} \right) $$
Pokud zkusíme spočítat syndromy pro shlukové chyby délky 3, dostaneme výrazně odlišný výsledek:
| Hammingův kód | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| $\mathbf{e}$ (délka 3) | $\mathbf{s}$ | ||||||||
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| Hammingův kód | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| $\mathbf{e}$ (délka 3) | $\mathbf{s}$ | ||||||||
| 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
Všimněme si, že pro některé chybové vektory vyšel nulový syndrom. To je zcela ve shodě s tvrzením, že kód s Hammingovou vzdáleností 3 (Hammingův kód) nedokáže odhalit všechny trojnásobné chyby.
Vytvořte binární cyklický (6, 4) kód v systematickém i nesystematickém tvaru.
Pro $n=6$ a $k=4$ je stupeň generujícího polynomu $n-k=2$. Generující polynom $g(x)$ musí navíc beze zbytku dělit polynom $x^6-1$ nad tělesem $\mathbb{Z}_2$. Najdeme jej zkusmo - pokusíme se vydělit $x^6-1$ všemi existujícími polynomy stupně $2$, tj. $x^2$, $x^2 + 1$, $x^2 + x$, $x^2 + x + 1$:
-
Pro $x^2$:
$$ \begin{split} (&x^6 + 1) / (x^2) = x^4 \\ &\underline{x^6\phantom{{}+1}} \\ &\phantom{x^6 + {}}1 \end{split} $$
Zbytek není roven 0, tj. $x^2$ nemůže sloužit jako generující polynom.
-
Pro $x^2 + 1$:
$$ \begin{split} (&x^6 + 1) / (x^2 + 1) = x^4 + x^2 + 1\\ &\underline{x^6 + x^4} \\ &\phantom{x^6 + {}}x^4 + 1 \\ &\phantom{x^6 + {}}\underline{x^4 + x^2} \\ &\phantom{x^6 + x^4 + {}}x^2 + 1 \\ &\phantom{x^6 + x^4 + {}}\underline{x^2 + 1}\\ &\phantom{x^6 + x^4 + x^2 +{}}0 \end{split} $$
Zbytek je roven 0, tj. $x^2 + 1$ může sloužit jako generující polynom.
-
Pro $x^2 + x$:
$$ \begin{split} (&x^6 + 1) / (x^2 + x) = x^4 + x^3 + x^2 + x + 1\\ &\underline{x^6 + x^5} \\ &\phantom{x^6 + {}}x^5 + 1 \\ &\phantom{x^6 + {}}\underline{x^5 + x^4} \\ &\phantom{x^6 + x^5 + {}}x^4 + 1 \\ &\phantom{x^6 + x^5 + {}}\underline{x^4 + x^3}\\ &\phantom{x^6 + x^5 + x^4 +{}}x^3 + 1\\ &\phantom{x^6 + x^5 + x^4 +{}}\underline{x^3 + x^2}\\ &\phantom{x^6 + x^5 + x^4 + x^3 + {}}x^2 + 1\\ &\phantom{x^6 + x^5 + x^4 + x^3 + {}}\underline{x^2 + x}\\ &\phantom{x^6 + x^5 + x^4 + x^3 + x^2 + {}}x + 1 \end{split} $$
Zbytek není roven 0, tj. $x^2 + x$ nemůže sloužit jako generující polynom.
-
Pro $x^2 + x + 1$:
$$ \begin{split} (&x^6 + 1) / (x^2 + x + 1) = x^4 + x^3 + x + 1\\ &\underline{x^6 + x^5 + x^4} \\ &\phantom{x^6 + {}}x^5 + x^4 + 1 \\ &\phantom{x^6 + {}}\underline{x^5 + x^4 + x^3} \\ &\phantom{x^6 + x^5 + {}}x^3 + 1 \\ &\phantom{x^6 + x^5 + {}}\underline{x^3 + x^2 + x}\\ &\phantom{x^6 + x^5 + x^3 +{}}x^2 + x + 1\\ &\phantom{x^6 + x^5 + x^3 +{}}\underline{x^2 + x + 1}\\ &\phantom{x^6 + x^5 + x^3 + x^2 + x + {}}0 \end{split} $$
Zbytek je roven 0, tj. $x^2 + x + 1$ může sloužit jako generující polynom.
Zjistili jsme, že polynomy $g_1(x) = x^2 + 1$ a $g_2(x) = x^2 + x + 1$ splňují požadavky na generující polynom. K nim příslušné kontrolní polynomy jsou $h_1(x) = x^4 + x^2 + 1$ a $h_2(x) = x^4 + x^3 + x + 1$. Mohli bychom proto zapsat generující a kontrolní matice nesystematických kódů:
$$ G_1 = \begin{pmatrix} 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 \end{pmatrix} \qquad H_1 = \begin{pmatrix} 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \end{pmatrix} $$
$$ G_2 = \begin{pmatrix} 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 \end{pmatrix} \qquad H_2 = \begin{pmatrix} 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 0 \end{pmatrix} $$
K tvorbě systematických kódů potřebujeme zakódovat značky 1000, 0100, 0010, 0001.
Jelikož pro $g_1(x) = x^2 + 1$ platí:
$$ \begin{align} 1000:\qquad x^5 \ \text{mod}\ (x^2 + 1) &= x\\ 0100:\qquad x^4 \ \text{mod}\ (x^2 + 1) &= 1\\ 0010:\qquad x^3 \ \text{mod}\ (x^2 + 1) &= x\\ 0001:\qquad x^2 \ \text{mod}\ (x^2 + 1) &= 1 \end{align} $$
můžeme napsat generující a kontrolní matice systematického kódu
$$ G_{1\ \text{system}} = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 \end{pmatrix} \qquad H_{1\ \text{system}} = \begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \end{pmatrix} $$
Pro $g_2(x) = x^2 + x + 1$ platí:
$$ \begin{align} 1000:\qquad x^5 \ \text{mod}\ (x^2 + x + 1) &= x + 1\\ 0100:\qquad x^4 \ \text{mod}\ (x^2 + x + 1) &= x\\ 0010:\qquad x^3 \ \text{mod}\ (x^2 + x + 1) &= 1\\ 0001:\qquad x^2 \ \text{mod}\ (x^2 + x + 1) &= x + 1 \end{align} $$
můžeme napsat generující a kontrolní matice systematického kódu
$$ G_{2\ \text{system}} = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 \end{pmatrix} \qquad H_{2\ \text{system}} = \begin{pmatrix} 1 & 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 \end{pmatrix} $$