BCH kód: Porovnání verzí
Smazaný obsah Přidaný obsah
m Ještě oprava chyby formátování. |
|||
Řádek 416:
Exponenty <math>\alpha</math> odpovídají pozicím chyb.
Nemusíme v tomto případě počítat chybové hodnoty, protože jedinou možnou hodnotou je hodnota 1.
=== Příklad dekódování s nečitelnými znaky ===
Předpokládejme nyní, stejný případ, ale přijaté slovo má dva nečitelné znaky [ 1 {{barva|red|0}} 0 ? 1 1 ? 0 0 {{barva|red|1}} 1 0 1 0 0 ].
Nahradíme nečitelné znaky (např.) nulami, vytvořme polynom potlačující vliv nečitelných znaků <math>\Gamma(x)=(\alpha^8x-1)(\alpha^{11}x-1)</math>.
Najděme syndromy <math>s_1=\alpha^{-7}</math>, <math>s_2=\alpha^{1}</math>, <math>s_3=\alpha^{4}</math>,
<math>s_4=\alpha^{2}</math>, <math>s_5=\alpha^{5}</math> a <math>s_6=\alpha^{-7}</math>.
(Používáme logaritmické vyjádření, které je vzhledem k isomorfismu GF(2<sup>4</sup>) nezávislé na reprezentaci pro sčítání.
Možné reprezentace jednotlivých mocnin jsou například hexadecimálními číslicemi 1,2,4,8,3,6,C,B,5,A,7,E,F,D,9 se sčítáním založeném na bitovém xor.)
Vytvořme polynom syndromů <math>S(x)=\alpha^{-7}+\alpha^{1}x+\alpha^{4}x^2+\alpha^{2}x^3+\alpha^{5}x^4+\alpha^{-7}x^5</math>,
spočtěme <math>S(x)\Gamma(x)=\alpha^{-7}+\alpha^{4}x+\alpha^{-1}x^2+\alpha^{6}x^3+\alpha^{-1}x^4+\alpha^{5}x^5+\alpha^{7}x^6+\alpha^{-3}x^7</math>.
Spusťme rozšířšný euklidův algoritmus:
<math>
\begin{pmatrix}S(x)\Gamma(x)\\ x^6\end{pmatrix}=
\begin{pmatrix}\alpha^{-7}+\alpha^{4}x+\alpha^{-1}x^2+\alpha^{6}x^3+\alpha^{-1}x^4+\alpha^{5}x^5+\alpha^{7}x^6+\alpha^{-3}x^7\\ x^6\end{pmatrix}=
</math>
<math>
\begin{pmatrix}\alpha^{7}+\alpha^{-3}x&1\\ 1&0\end{pmatrix}
\begin{pmatrix}x^6\\
\alpha^{-7}+\alpha^{4}x+\alpha^{-1}x^2+\alpha^{6}x^3+\alpha^{-1}x^4+\alpha^{5}x^5+(\alpha^{7}+\alpha^{7})x^6+(\alpha^{-3}+\alpha^{-3})x^7\end{pmatrix}=
</math>
<math>
\begin{pmatrix}\alpha^{7}+\alpha^{-3}x&1\\ 1&0\end{pmatrix}
\begin{pmatrix}\alpha^4+\alpha^{-5}x&1\\ 1&0\end{pmatrix}
\begin{pmatrix}
\alpha^{-7}+\alpha^{4}x+\alpha^{-1}x^2+\alpha^{6}x^3+\alpha^{-1}x^4+\alpha^{5}x^5\\
\alpha^{-3}+(\alpha^{-7}+\alpha^{3})x+(\alpha^{3}+\alpha^{-1})x^2+\\
(\alpha^{-5}+\alpha^{-6})x^3+(\alpha^3+\alpha^{1})x^4+(\alpha^{-6}+\alpha^{-6})x^5+(\alpha^0+1)x^6\end{pmatrix}=
</math>
<math>
\begin{pmatrix}(1+\alpha^{-4})+(\alpha^{1}+\alpha^{2})x+\alpha^{7}x^2&\alpha^{7}+\alpha^{-3}x
\\
\alpha^4+\alpha^{-5}x&1\end{pmatrix}
\begin{pmatrix}
\alpha^{-7}+\alpha^{4}x+\alpha^{-1}x^2+
\alpha^{6}x^3+\alpha^{-1}x^4+\alpha^{5}x^5\\
\alpha^{-3}+\alpha^{-2}x+\alpha^{0}x^2+
\alpha^{-2}x^3+\alpha^{-6}x^4\end{pmatrix}=
</math>
<math>
\begin{pmatrix}\alpha^{-3}+\alpha^{5}x+\alpha^{7}x^2&\alpha^{7}+\alpha^{-3}x
\\
\alpha^4+\alpha^{-5}x&1\end{pmatrix}
\begin{pmatrix}\alpha^{-5}+\alpha^{-4}x&1\\ 1&0\end{pmatrix}
\begin{pmatrix}
\alpha^{-3}+\alpha^{-2}x+\alpha^{0}x^2+
\alpha^{-2}x^3+\alpha^{-6}x^4\\
(\alpha^{7}+\alpha^{-7})+
(\alpha^{-7}+\alpha^{-7}+\alpha^{4})x+\\
(\alpha^{-5}+\alpha^{-6}+\alpha^{-1})x^2+\\
(\alpha^{-7}+\alpha^{-4}+\alpha^{6})x^3+\\
(\alpha^{4}+\alpha^{-6}+\alpha^{-1})x^4+
(\alpha^{5}+\alpha^{5})x^5\end{pmatrix}=
</math>
<math>
\begin{pmatrix}\alpha^{7}x+\alpha^{5}x^2+\alpha^{3}x^3&\alpha^{-3}+\alpha^{5}x+\alpha^{7}x^2\\
\alpha^{3}+\alpha^{-5}x+\alpha^{6}x^2&\alpha^4+\alpha^{-5}x\end{pmatrix}
\begin{pmatrix}
\alpha^{-3}+\alpha^{-2}x+\alpha^{0}x^2+
\alpha^{-2}x^3+\alpha^{-6}x^4\\
\alpha^{-4}+\alpha^{4}x+\alpha^{2}x^2+
\alpha^{-5}x^3\end{pmatrix}
</math>
Dostali jsme se k polynomu stupně 3, a vzhledem k tomu, že
<math>
\begin{pmatrix}-(\alpha^4+\alpha^{-5}x)&\alpha^{-3}+\alpha^{5}x+\alpha^{7}x^2\\
\alpha^{3}+\alpha^{-5}x+\alpha^{6}x^2&-(\alpha^{7}x+\alpha^{5}x^2+\alpha^{3}x^3)\end{pmatrix}
\begin{pmatrix}\alpha^{7}x+\alpha^{5}x^2+\alpha^{3}x^3&\alpha^{-3}+\alpha^{5}x+\alpha^{7}x^2\\
\alpha^{3}+\alpha^{-5}x+\alpha^{6}x^2&\alpha^4+\alpha^{-5}x\end{pmatrix}
=\begin{pmatrix}1&0\\ 0&1\end{pmatrix}
</math>
dostáváme
<math>
\begin{pmatrix}-(\alpha^4+\alpha^{-5}x)&\alpha^{-3}+\alpha^{5}x+\alpha^{7}x^2\\
\alpha^{3}+\alpha^{-5}x+\alpha^{6}x^2&-(\alpha^{7}x+\alpha^{5}x^2+\alpha^{3}x^3)\end{pmatrix}
\begin{pmatrix}S(x)\Gamma(x)\\ x^6\end{pmatrix}=
\begin{pmatrix}
\alpha^{-3}+\alpha^{-2}x+\alpha^{0}x^2+\\
\alpha^{-2}x^3+\alpha^{-6}x^4\\
\alpha^{-4}+\alpha^{4}x+\alpha^{2}x^2+\\
\alpha^{-5}x^3\end{pmatrix}
</math>
a tedy
<math>
S(x)\Gamma(x)(\alpha^{3}+\alpha^{-5}x+\alpha^{6}x^2)-
(\alpha^{7}x+\alpha^{5}x^2+\alpha^{3}x^3)x^6=
\alpha^{-4}+\alpha^{4}x+\alpha^{2}x^2+\alpha^{-5}x^3
</math>.
Nechť <math>\Lambda(x)=\alpha^{3}+\alpha^{-5}x+\alpha^{6}x^2</math>.
Netrapme se tím, že absolutní člen není 1.
Nalezněme hrubou silou kořeny polynomu <math>\Lambda</math> jsou jimi <math>\alpha^2</math> a <math>\alpha^{10}</math>
(po nalezení prvního můžeme vydělit <math>\Lambda</math> polynomem <math>(x-\alpha^2)</math> a kořen polynomu stupně 1 nalezneme snadno).
Označme <math>\Xi(x)=\Gamma(x)\Lambda(x)=\alpha^3+\alpha^4x^2+\alpha^2x^3+\alpha^{-5}x^4</math> a <math>\Omega(x)=S(x)\Xi(x)\bmod x^6=\alpha^{-4}+\alpha^4x+\alpha^2x^2+\alpha^{-5}x^3</math>.
Velikosti chyb hledáme ve tvaru <math>e_j=\Omega(\alpha^{-i_j})/\Xi'(\alpha^{-i_j})</math>, kde <math>\alpha^{-i_j}</math> jsou kořeny polynomu <math>\Xi(x)</math>.
<math>\Xi'(x)=\alpha^{2}x^2</math>. Dostáváme <math>e_1=\Omega(\alpha^4)/\Xi'(\alpha^{4})=(\alpha^{-4}+\alpha^{-7}+\alpha^{-5}+\alpha^{7})/\alpha^{-5}=\alpha^{-5}/\alpha^{-5}=1</math>,
<math>e_2=\Omega(\alpha^7)/\Xi'(\alpha^{7})=(\alpha^{-4}+\alpha^{-4}+\alpha^{1}+\alpha^{1})/\alpha^{1}=0</math>,
<math>e_3=\Omega(\alpha^{10})/\Xi'(\alpha^{10})=(\alpha^{-4}+\alpha^{-1}+\alpha^{7}+\alpha^{-5})/\alpha^{7}=\alpha^{7}/\alpha^{7}=1</math>
<math>e_4=\Omega(\alpha^{2})/\Xi'(\alpha^{2})=(\alpha^{-4}+\alpha^{6}+\alpha^{6}+\alpha^{1})/\alpha^{6}=\alpha^{6}/\alpha^{6}=1</math>.
To že <math>e_3=e_4=1</math> by nás nemělo překvapit.
Opravený kód tedy má být [ 1 {{barva|green|1}} 0 {{barva|green|1}} 1 1 {{barva|green|0}} 0 0 {{barva|green|0}} 1 0 1 0 0].
Ješťě ukažmě průběh výpočtu v případě, kdy je v přijatém kódu pouze jedna chyba [ 1 {{barva|red|0}} 0 ? 1 1 ? 0 0 0 1 0 1 0 0 ].
Opět nahradíme nečitelné znaky nulami, spočteme <math>\Gamma(x)=(\alpha^8x-1)(\alpha^{11}x-1)</math> a syndromy
<math>s_1=\alpha^{4}</math>, <math>s_2=\alpha^{-7}</math>, <math>s_3=\alpha^{1}</math>,
<math>s_4=\alpha^{1}</math>, <math>s_5=\alpha^{0}</math> a <math>s_6=\alpha^{2}</math>.
Sestavíme polynom syndromů <math>S(x)=\alpha^{4}+\alpha^{-7}x+\alpha^{1}x^2+\alpha^{1}x^3+\alpha^{0}x^4+\alpha^{2}x^5</math>,
a <math>S(x)\Gamma(x)=\alpha^{4}+\alpha^{7}x+\alpha^{5}x^2+\alpha^{3}x^3+\alpha^{1}x^4+\alpha^{-1}x^5+\alpha^{-1}x^6+\alpha^{6}x^7</math>.
Spusťme rozšířený Euklidův algoritmus:
<math>
\begin{pmatrix}S(x)\Gamma(x)\\ x^6\end{pmatrix}=
\begin{pmatrix}\alpha^{4}+\alpha^{7}x+\alpha^{5}x^2+\alpha^{3}x^3+\alpha^{1}x^4+\alpha^{-1}x^5+\alpha^{-1}x^6+\alpha^{6}x^7\\
x^6\end{pmatrix}=
</math>
<math>
\begin{pmatrix}\alpha^{-1}+\alpha^{6}x&1\\ 1&0\end{pmatrix}
\begin{pmatrix}x^6\\
\alpha^{4}+\alpha^{7}x+\alpha^{5}x^2+\alpha^{3}x^3+\alpha^{1}x^4+\alpha^{-1}x^5+(\alpha^{-1}+\alpha^{-1})x^6+(\alpha^{6}+\alpha^{6})x^7
\end{pmatrix}=
</math>
<math>
\begin{pmatrix}\alpha^{-1}+\alpha^{6}x&1\\ 1&0\end{pmatrix}
\begin{pmatrix}\alpha^{3}+\alpha^{1}x&1\\ 1&0\end{pmatrix}
\begin{pmatrix}
\alpha^{4}+\alpha^{7}x+\alpha^{5}x^2+\alpha^{3}x^3+\alpha^{1}x^4+\alpha^{-1}x^5\\
\alpha^{7}+(\alpha^{-5}+\alpha^{5})x+
(\alpha^{-7}+\alpha^{-7})x^2+
(\alpha^{6}+\alpha^{6})x^3+\\
(\alpha^{4}+\alpha^{4})x^4+
(\alpha^{2}+\alpha^{2})x^5+
(\alpha^{0}+1)x^6
\end{pmatrix}=
</math>
<math>
\begin{pmatrix}(1+\alpha^{2})+(\alpha^{0}+\alpha^{-6})x+\alpha^{7}x^2&\alpha^{-1}+\alpha^{6}x\\
\alpha^{3}+\alpha^{1}x&1\end{pmatrix}
\begin{pmatrix}\alpha^{4}+\alpha^{7}x+\alpha^{5}x^2+\alpha^{3}x^3+\alpha^{1}x^4+\alpha^{-1}x^5\\
\alpha^{7}+\alpha^{0}x
\end{pmatrix}
</math>
Dostali jsme se k polynomu stupně 3, a vzhledem k tomu, že
<math>
\begin{pmatrix}-(1)&\alpha^{-1}+\alpha^{6}x\\
\alpha^{3}+\alpha^{1}x&-(\alpha^{-7}+\alpha^{7}x+\alpha^{7}x^2)\end{pmatrix}
\begin{pmatrix}\alpha^{-7}+\alpha^{7}x+\alpha^{7}x^2&\alpha^{-1}+\alpha^{6}x\\
\alpha^{3}+\alpha^{1}x&1\end{pmatrix}
=\begin{pmatrix}1&0\\ 0&1\end{pmatrix}
</math>
dostáváme
<math>
\begin{pmatrix}-(1)&\alpha^{-1}+\alpha^{6}x\\
\alpha^{3}+\alpha^{1}x&-(\alpha^{-7}+\alpha^{7}x+\alpha^{7}x^2)\end{pmatrix}
\begin{pmatrix}S(x)\Gamma(x)\\ x^6\end{pmatrix}=
\begin{pmatrix}\alpha^{4}+\alpha^{7}x+\alpha^{5}x^2+\alpha^{3}x^3+\alpha^{1}x^4+\alpha^{-1}x^5\\
\alpha^{7}+\alpha^{0}x
\end{pmatrix}
</math>
a tedy
<math>
S(x)\Gamma(x)(\alpha^{3}+\alpha^{1}x)-
(\alpha^{-7}+\alpha^{7}x+\alpha^{7}x^2)x^6=
\alpha^{7}+\alpha^{0}x.
</math>
Nechť <math>\Lambda(x)=\alpha^{3}+\alpha^{1}x</math>.
Netrapme se tím, že absolutní člen není 1. Kořenem polynomu je <math>\alpha^{3-1}</math>.
Označme <math>\Xi(x)=\Gamma(x)\Lambda(x)=\alpha^{3}+\alpha^{-7}x+\alpha^{-4}x^2+\alpha^{5}x^3</math> a <math>\Omega(x)=S(x)\Xi(x)\bmod x^6=\alpha^{7}+\alpha^{0}x</math>.
Velikosti chyb hledáme ve tvaru <math>e_j=\Omega(\alpha^{-i_j})/\Xi'(\alpha^{-i_j})</math>, kde <math>\alpha^{-i_j}</math> jsou kořeny polynomu <math>\Xi(x)</math>.
<math>\Xi'(x)=\alpha^{-7}+\alpha^{5}x^2</math>.
Dostáváme <math>e_1=\Omega(\alpha^4)/\Xi'(\alpha^{4})=(\alpha^{7}+\alpha^{4})/(\alpha^{-7}+\alpha^{-2})=\alpha^{3}/\alpha^{3}=1</math>,
<math>e_2=\Omega(\alpha^7)/\Xi'(\alpha^{7})=(\alpha^{7}+\alpha^{7})/(\alpha^{-7}+\alpha^{4})=0/\alpha^{5}=0</math>,
<math>e_3=\Omega(\alpha^2)/\Xi'(\alpha^2)=(\alpha^{7}+\alpha^{2})/(\alpha^{-7}+\alpha^{-6})=\alpha^{-3}/\alpha^{-3}=1</math>.
To že <math>e_3=1</math> by nás nemělo překvapit.
Opravený kód tedy má být [ 1 {{barva|green|1}} 0 {{barva|green|1}} 1 1 {{barva|green|0}} 0 0 0 1 0 1 0 0].
== Citace ==
| |||