Zobrazení zdroje stránky BCH kód

V [[kódování|teorii kódování]] tvoří '''BCH kódy''' skupinu [[cyklický kód|cyklických]] [[samoopravný kód|samoopravných kódů]], které jsou konstruovány pomocí [[konečné těleso|konečných těles]]. BCH kódy byly vynalezeny v roce 1959 [[Alexis Hocquenghem|Hocquenghemem]], a nezávisle v roce 1960 [[Raj Chandra Bose|Bosem]] a [[D.K. Ray-Chaudhuri|Ray-Chaudhurim]].<ref>{{Harvnb|Reed|Chen|1999|p=189}}</ref> Zkratka ''BCH'' je tvořena počátečními jmény těchto objevitelů.

Klíčovou vlastností BCH kódů je možnost v průběhu návrhu kódu přesně kontrolovat počet opravitelných chyb ve výsledném kódu. Další výhodou BCH kódů je jednoduchost jejich dekódování pomocí [[algebra]]ických metod známých jako [[syndrome decoding]]. To zjednodušuje návrh dekodérů s použitím malého výkonnostně slabého hardwaru.

BCH kódy jsou používány například v satelitní komunikaci,<ref>{{Cite web|title=Phobos Lander Coding System: Software and Analysis|url=http://ipnpr.jpl.nasa.gov/progress_report/42-94/94V.PDF|accessdate=25 February 2012}}</ref> [[Kompaktní disk|CD]] a [[DVD]] přehrávačích, [[Pevný disk|pevných discích]], [[Solid-state drive|flash discích]]<ref>{{Cite web|title=Sandforce SF-2500/2600 Product Brief|url=http://www.sandforce.com/index.php?id=133&parentId=2&top=1|accessdate=25 February 2012}}</ref> a [[QR kód]]ech.

== Konstrukce ==
Nechť ''A'' je [[konečné těleso|GF(q<sup>a</sup>)]]. BCH kód kóduje slova pevné délky ''k'' nad vstupní abecedou ''A'' tak,
že kódové slovo předem dané délky ''n'' vznikne doplněním vstupního slova dalšími znaky nad abecedou ''A''.
Konstrukce kódu je založena na nadtělese ''B'' [[konečné těleso|GF(q<sup>b</sup>)]] tělesa ''A'' v němž existuje prvek α
jehož řád je alespoň délka ''n'' kódových slov, tedy ''a''|''b'' a ord(α)≥''n''.
Nechť ''c'' a ''d'' jsou [[Celé číslo|celá čísla]].
Kódová slova jsou taková slova ''v''<sub>1</sub>''v''<sub>2</sub>…''v''<sub>n</sub>, kde [[polynom]]
''v''<sub>1</sub>x<sup>n-1</sup>+''v''<sub>2</sub>x<sup>n-2</sup>+…+''v''<sub>n-1</sub>x<sup>1</sup>+''v''<sub>n</sub>
má kořeny α<sup>c</sup>, α<sup>c+1</sup>, …, α<sup>c+d-2</sup>.

Při konstrukci je nalezen polynom ''g''(x) nejmenšího stupně, který má uvedené kořeny. Tomuto polynomu říkáme generující polynom.
Je-li ''m'' jeho stupeň, pak je takto možno kódovat slova délky ''k''=''n''-''m''.
Kódové slovo vznikne tak, že zjistíme zbytek ''R''(x) při dělení polynomu
''V''(x)=''v''<sub>1</sub>x<sup>n-1</sup>+''v''<sub>2</sub>x<sup>n-2</sup>+…+''v''<sub>k</sub>x<sup>m</sup> polynomem ''P''(x).

Kódové slovo vznikne z polynomu ''V''(x)-''R''(x), tak že ''v''<sub>i</sub> bude tvořeno koeficientem u x<sup>n-i</sup>.

Konstrukce garantuje [[Hammingova vzdálenost|Hammingovu vzdálenost]] kódových slov alespoň ''d''. Užitečnou vlastností BCH kódů je,
že zpráva je pouze doplněna zabezpečovacím podslovem, ale začátek zprávy je nezměněn.

== Speciální případy BCH kódů ==
* BCH kód s ''c''=1 je nazýván ''doslovný'' kód.
* BCH kód s ''n''=q<sup>''b''/''a''</sup>−1 je nazýván ''primitivní'' kód.
* BCH kód s ''n''<q<sup>''b''/''a''</sup>−1 je nazýván ''zkrácený'' kód.
* BCH kód s ''A''=Z<sub>q</sub> je nazýván ''základní'' BCH kód.
* BCH kód s ''A''=Z<sub>2</sub> je nazýván ''binární'' BCH kód.
* BCH kód s ''A''=''B'' je nazýván ''Reed Solomonův'' kód.<ref>{{Harvnb|Gill|unknown|p=3}}</ref>

Běžně jsou používány primitivní doslovné základní BCH kódy.

Může se stát, že pro vhodnou volbu ''c'' dostaneme řád generujícího polynomu menší než při volbě ''c''=1.
Taková volba pak přináší více prostoru pro data (a kód přestává být doslovný).

Pro [[Reedovy–Solomonovy kódy]] jsou všechny volby ''c'' stejně dobré, protože minimální polynom pro každé α<sup>i</sup> je prvního řádu.
Používány jsou především Reed Solomonovy kódy s ''c''=0.

Kódy s ''b''>''a''>1 nejsou pravděpodobně používány.

=== Příklad základních primitivních doslovných BCH kódů ===
Nechť <math>q=2</math> a <math>b=4</math> (tedy <math>n=15</math>). Uvažujme různé hodnoty <math>d.</math>

Existuje primitivní prvek <math>\alpha\in GF(16)</math> splňující
<math>\alpha^4+\alpha+1=0 (*),</math>
jeho minimální polynom nad <math>Z_2</math> je
:<math>m_1(x) = x^4+x+1.</math>

Poznamenejme, že v <math>GF(2^4),</math> platí <math>(a+b)^2 = a^2 + ab + ab + b^2 = a^2 + b^2,</math> proto
<math>m_1(\alpha^2) = m_1(\alpha)^2 = 0.</math>

Tudíž <math>\alpha^2</math> je kořen polynomu <math>m_1(x),</math> a
:<math>m_2(x) = m_1(x) = x^4+x+1.</math>

Abychom spočítali <math>m_3(x),</math> poznamenejme, že opakovanou aplikací (*), dostáváme následující rovnice:
* <math>1 = 0\alpha^3 + 0\alpha^2 + 0\alpha + 1</math>
* <math>\alpha^3 = 1\alpha^3 + 0\alpha^2 + 0\alpha + 0</math>
* <math>\alpha^6 = 1\alpha^3 + 1\alpha^2 + 0\alpha + 0</math>
* <math>\alpha^9 = 1\alpha^3 + 0\alpha^2 + 1\alpha + 0</math>
* <math>\alpha^{12} = 1\alpha^3 + 1\alpha^2 + 1\alpha + 1</math>

Pět pravých stran délky čtyři musí být lineárně závislých a tak najdeme lineární závislost <math>\alpha^{12}+\alpha^9+\alpha^6+\alpha^3+1=0.</math>

Protože neexistuje závislost nižšího řádu, je minimálním polynomem pro <math>\alpha^3</math> polynom
:<math>m_3(x) = x^4+x^3+x^2+x+1.</math>

Budeme-li pokračovat obdobně, získáme

:<math>m_4(x) = m_2(x) = m_1(x) = x^4+x+1,\,</math>
:<math>m_5(x) = x^2+x+1,\,</math>
:<math>m_6(x) = m_3(x) = x^4+x^3+x^2+x+1,\,</math>
:<math>m_7(x) = x^4+x^3+1.\,</math>

BCH kódy s <math>d=1,2,3</math> mají generující polynom

:<math>g(x) = m_1(x) = x^4+x+1.\,</math>

Kód má minimální Hammingovu vzdálenost alespoň 3 a opravuje nejvýš 1 chybu. Protože generující polynom je stupně 4, má tento kód 11 datových bitů a 4 zabezpečovací bity.

BCH kódy s <math>d=4,5</math> mají generující polynom

:<math>g(x) = {\rm nsn}(m_1(x),m_3(x)) = (x^4+x+1)(x^4+x^3+x^2+x+1) = x^8+x^7+x^6+x^4+1.\,</math>

Jeho minimální Hammingova vzdálenost je alespoň 5 a opravuje nejvýš 2 chyby. Protože generující polynom je stupně 8, má tento kód 7 datových bitů a 8 zabezpečovacích bitů.

BCH kódy s <math>d=6,7</math> mají generující polynom

:<math>
\begin{align}
g(x) & {} = {\rm nsn}(m_1(x),m_3(x),m_5(x)) \\
& {} = (x^4+x+1)(x^4+x^3+x^2+x+1)(x^2+x+1) \\
& {} = x^{10}+x^8+x^5+x^4+x^2+x+1.
\end{align}
</math>

Má minimální Hammingovu vzdálenost alespoň 7 a opravuje nejvýš 3 chyby. Tento kód má 5 datových bitů a 10 zabezpečovacích bitů.

BCH kód s <math>d\ge8</math> má generující polynom

:<math>
\begin{align}
g(x) & {} = {\rm nsn}(m_1(x),m_3(x),m_5(x),m_7(x)) \\
& {} = (x^4+x+1)(x^4+x^3+x^2+x+1)(x^2+x+1)(x^4+x^3+1) \\
& {} = x^{14}+x^{13}+x^{12}+\cdots+x^2+x+1.
\end{align}
</math>

Kód má minimální Hammingovu vzdálenost 15 a opravuje nejvýš 7 chyb. Má 1 datový bit a 14 zabezpečovacích bitů.
Tento kód má tedy jen dvě kódová slova: 000000000000000 a 111111111111111.

=== Vlastnosti ===
1. Generující polynom BCH kódu má stupeň nejvýš <math>(d-1)(b/a).</math>
Navíc, pokud <math>A=Z_2</math> a <math>c=1,</math> pak generující polynom má stupeň nejvýš <math>db/2a.</math>

:Důkaz: každý minimální polynom <math>m_i(x)</math> má stupeň nejvýš <math>b/a.</math>
Proto minimální společný násobek <math>d-1</math> z nich má stupeň nejvýš <math>(d-1)(b/a).</math>
Navíc, pokud <math>A=Z_2,</math> pak <math>m_i(x) = m_{2i}(x)</math> pro každé <math>i.</math>
Proto, <math>g(x)</math> je [[nejmenší společný násobek]] nejvýš <math>d/2</math> minimálních polynomů <math>m_i(x)</math> pro liché indexy <math>i,</math>
každý z nich je stupně nejvýš <math>b/a.</math>

2. BCH kód má minimální Hammingovu vzdálenost alespoň <math>d.</math>

Důkaz: Předpokládejme, že <math>p(x)</math> je kód (jemu odpovídající polynom) s méně než <math>d</math> nenulovými koeficienty. Potom nechť

:<math>p(x) = b_1x^{k_1} + \cdots + b_{d-1}x^{k_{d-1}},\text{ kde }k_1<k_2<\cdots<k_{d-1}.</math>

Připomeňme, že <math>\alpha^c,\ldots,\alpha^{c+d-2}</math> jsou kořeny <math>g(x),</math> tudíž i jeho násobku <math>p(x).</math>
Z toho plyne, že <math>b_1,\ldots,b_{d-1}</math> splňuje následující rovnice pro <math>i=c,\ldots,c+d-2:</math>
:<math>p(\alpha^i) = b_1\alpha^{ik_1} + b_2\alpha^{ik_2} + \cdots + b_{d-1}\alpha^{ik_{d-1}} = 0.</math>

V maticovém tvaru dostáváme
:<math>\begin{bmatrix}
\alpha^{ck_1} & \alpha^{ck_2} & \cdots & \alpha^{ck_{d-1}} \\
\alpha^{(c+1)k_1} & \alpha^{(c+1)k_2} & \cdots & \alpha^{(c+1)k_{d-1}} \\
\vdots & \vdots && \vdots \\
\alpha^{(c+d-2)k_1} & \alpha^{(c+d-2)k_2} & \cdots & \alpha^{(c+d-2)k_{d-1}} \\
\end{bmatrix}
\begin{bmatrix}
b_1 \\ b_2 \\ \vdots \\ b_{d-1}
\end{bmatrix}
= 
\begin{bmatrix}
0 \\ 0 \\ \vdots \\ 0
\end{bmatrix}.
</math>

Determinant této matice je roven
:<math>\left(\prod_{i=1}^{d-1}\alpha^{ck_i}\right)\det\begin{pmatrix}
1 & 1 & \cdots & 1 \\
\alpha^{k_1} & \alpha^{k_2} & \cdots & \alpha^{k_{d-1}} \\
\vdots & \vdots && \vdots \\
\alpha^{(d-2)k_1} & \alpha^{(d-2)k_2} & \cdots & \alpha^{(d-2)k_{d-1}} \\
\end{pmatrix} = \left(\prod_{i=1}^{d-1}\alpha^{ck_i}\right) \det(V).</math>

Matice <math>V</math> je [[Vandermondova matice]], a její determinant je
:<math>\det(V) = \prod_{1\le i<j\le d-1} (\alpha^{k_j}-\alpha^{k_i}),</math>
což je nenulové. Odtud vyplývá, že <math>b_1,\ldots,b_{d-1}=0,</math> a tudíž <math>p(x)=0.</math>

3. Kód, kde délka kódových slov ''n'' je rovna řádu prvku α je cyklický. Speciálně pak každý primitivní kód je cyklický.

Důkaz: Kód generovaný pomocí polynomů délky <math>n</math> je cyklický právě když generující polynom dělí <math>x^n-1.</math>
Protože <math>g(x)</math> je minimální polynom s kořeny <math>\alpha^c,\ldots,\alpha^{c+d-2},</math>
stačí zkontrolovat, že každé z <math>\alpha^c,\ldots,\alpha^{c+d-2}</math> je kořen polynomu <math>x^n-1.</math>
To plyne přímo z toho, že <math>\alpha</math> je podle definice <math>n</math>tá odmocnina z jedné.

== Dekódování ==
Existuje mnoho algoritmů pro dekódování BCH kódů. Nejběžnější používají následující schéma:
# Spočtěme pro přijaté slovo syndromy ''s<sub>j</sub>''.
# Ze syndromů určeme počet chyb ''t'' a polynom pro lokalizaci chyb ''Λ(x)''.
# Nalezněme kořeny polynomu pro lokalizaci chyb ''x<sub>j</sub>'' a jejich logaritmy ''-i<sub>j</sub>'', tak že α<sup>−i<sub>j</sub></sup>=x<sub>j</sub>.
# Spočtěme chybové hodnoty ''e<sub>i</sub>'' v pozicích ''i<sub>j</sub>''.
# Opravme chyby.

V průběhu algoritmu může dekódovací algoritmus určit, že přijaté slovo obsahuje příliš mnoho chyb a nemůže být opraveno.
Například, pokud vhodná hodnota pro ''t'' není nalezena, korekce selže.
V případě zkráceného kódu, může být vypočtena pozice chyby mimo kódové slovo.
Pokud přijaté slovo má více chyb než kód dokáže opravit, dekodér může vrátit zdánlivě korektní zprávu, která se liší od zprávy odeslané.

Pokud jsou některá písmena zprávy nečitelná, můžeme jejich pozici považovat za pozici chyby.
Nalezení chyby na neznámé pozici vyžaduje stejně informací jako opravení dvou chyb na známých pozicích.

=== Výpočet syndromů ===
Přijaté slovo <math>R</math> je součet korektního kódového slova <math>C</math> a neznámého chybového slova <math>E.</math>
Hodnoty syndromů jsou získány dosazením hodnot <math>\alpha^c,\ldots,\alpha^{c+d-2}</math> do <math>R</math> vnímaného jakožto polynom.
Proto jsou syndromy<ref>{{Harvnb|Lidl|Pilz|1999|p=229}}</ref>
:<math>s_{j} = R(\alpha^{j}) = C(\alpha^{j}) + E(\alpha^{j}),</math>
pro <math>j</math> od <math>c</math> do <math>c+d-2.</math>
Protože <math>\alpha^{j}</math> jsou kořeny <math>g(x),</math> jehož je
<math>C(x)</math> násobek, <math>C(\alpha^{j}) = 0.</math>
Zkoumání hodnot syndromů proto izoluje chybový vektor,
takže můžeme začít v jeho hledání.

Pokud v přenosu nevznikly chyby, je <math>s_j = 0</math> pro každé <math>j.</math>
V takovém případě dekódování končí.

=== Výpočet polynomu pro lokalizaci chyb ===
Pokud jsou některé syndromy nenulové, jsou v přijaté zprávě chyby. Dekodér musí zjistit, kolik jich je a kde se vyskytují.

Předpokládejme, že

:<math>E(x) = e_1 x^{i_1} + e_2 x^{i_2} + \cdots + e_v x^{i_v} \, .</math>
Není zřejmé, jak začít řešit rovnice s neznámými <math>e_k</math> a <math>i_k</math> vysvětlující syndromy.

Prvním krokem je nalezení polynomu pro lokalizaci chyb
:<math>\Lambda(x)=\prod_{j=1}^v (x\alpha^{i_j}-1)</math> kompatibilního se spočtenými syndromy a s minimálním možným <math>v.</math>

Dva populární algoritmy pro tuto úlohu jsou:
# [[BCH kód#Peterson–Gorenstein–Zierler algoritmus|Algoritmus Peterson–Gorenstein–Zierler]]<ref>{{Harvnb|Gorenstein|Peterson|Zierler|1960}}</ref>
# [[BCH kód#Algoritmus Berlekamp–Massey|Algoritmus Berlekamp–Massey]]

Cílem obou algoritmů je nalézt
: <math> \Lambda(x) = \lambda_0 + \lambda_1 x + \lambda_2 x^2 + \cdots + \lambda_v x^v </math>
takové, aby pro každé <math>j</math> od <math>c</math> do <math>c+d-2-v</math> platilo
:<math> \sum_{i=0}^v \lambda_i s_{j+v-i} = 0.</math>
Navíc požadujeme <math>\lambda_0 = 1.</math>


==== Zdůvodnění rovnic pro výpočet polynomu pro lokalizaci chyb ====
Vzhledem k tomu, že <math>\alpha^{-i_k}</math> je kořenem polynomu <math>\Lambda(x),</math> musí být
:<math> 0 = \sum_{i=0}^v \lambda_i \alpha^{-i\cdot i_k}.</math>
Po pronásobení <math>e_k\alpha^{(j+v)i_k}</math> dostáváme
:<math> 0 = \sum_{i=0}^v \lambda_i e_k\alpha^{(j+v-i)i_k}.</math>
Po sečtení přes jednotlivé chyby pak
:<math> 0 = \sum_{i=0}^v \lambda_i \sum_{k=0}^v e_k\alpha^{(j+v-i)i_k},</math>
neboli
:<math> 0 = \sum_{i=0}^v \lambda_i s_{j+v-i}.</math>

==== Algoritmus Peterson–Gorenstein–Zierler ====
Algoritmus řeší [[Soustava rovnic|soustavu rovnic]] hrubou silou. Nachází jediné ''v'' a Λ, které může vyhovovat, správně by měl nakonec zkontrolovat, zda skutečně vyhovují i pro ve výpočtu nepoužité syndromy.

Začněme s ''v=[t=(d-1)/2]''.

* Nejprve sestavme matici
::<math>S_{v \times v}=\begin{bmatrix}s_c&s_{c+1}&\dots&s_{c+v-1}\\
s_{c+1}&s_{c+2}&\dots&s_{c+v}\\
\vdots&\vdots&\ddots&\vdots\\
s_{c+v-1}&s_{c+v}&\dots&s_{c+2v-2}\end{bmatrix},
</math>

* pak vektor <math>c_{v \times 1}</math>
::<math>C_{v \times 1}=\begin{bmatrix}s_{c+v}\\
s_{c+v+1}\\
\vdots\\
s_{c+2v-1}\end{bmatrix}.
</math>

* Nechť neznámé koeficienty polynomu <math>\Lambda</math> jsou
::<math>\Lambda_{v \times 1} = \begin{bmatrix}\lambda_{v}\\
\lambda_{v-1}\\
\vdots\\
\lambda_{1}\end{bmatrix}.
</math>

* Pokud má <math>S_{v \times v}</math> nenulový determinant, pak maticová rovnice
::<math>S_{v \times v} \Lambda_{v \times 1}  = -C_{v \times 1\,} </math>

:má řešení. Nalezněme tedy koeficienty polynomu <math>\Lambda</math> a skončeme.

* Jinak pokud <math>v = 0,</math> deklarujme nulový polynom lokalizace chyb a skončeme.
* Jinak snižme <math>v</math> o <math>1</math> a vraťme se k sestavení matice <math>S_{v\times v}.</math>

V případě <math>v</math> větším než je počet chyb (můžeme dodefinovat nadbytečná <math>e_k</math> nulou).
Pak
::<math>S_{v\times v}
=\begin{bmatrix}\alpha^{0i_1}&\alpha^{0i_2}&\dots&\alpha^{0i_v}\\
\alpha^{1i_1}&\alpha^{1i_2}&\dots&\alpha^{1i_v}\\
\vdots&\vdots&\ddots&\vdots\\
\alpha^{(v-1)i_1}&\alpha^{(v-1)i_2}&\dots&\alpha^{(v-1)i_v}\end{bmatrix}
\begin{bmatrix}e_1\alpha^{ci_1}&0&\dots&0\\
0&e_2\alpha^{ci_2}&\dots&0\\
\vdots&\vdots&\ddots&\vdots\\
0&0&\dots&e_v\alpha^{ci_v}\end{bmatrix}
\begin{bmatrix}\alpha^{0i_1}&\alpha^{1i_1}&\dots&\alpha^{(v-1)i_1}\\
\alpha^{0i_2}&\alpha^{1i_2}&\dots&\alpha^{(v-1)i_2}\\
\vdots&\vdots&\ddots&\vdots\\
\alpha^{0i_v}&\alpha^{1i_v}&\dots&\alpha^{(v-1)i_v}\end{bmatrix},
</math>
a determinant je nulový, dokud není <math>v</math> minimální možné.

==== Algoritmus Berlekamp–Massey ====
Algoritmus udržuje Λ odpovídající počátečnímu úseku posloupnosti syndromů.
Postupně prodlužuje délku úseku a koriguje Λ.

=== Nalezení kořenů polynomu pro lokalizaci chyb ===
Není znám algoritmus, který by hledal kořeny jinak než hrubou silou postupným dosazováním prvků tělesa ''B''.
Algoritmus [[Chien search]] optimalizuje výpočet tím,
že minimalizuje násobení proměnnými na úkor stejného počtu násobení konstantami.

=== Výpočet chybových hodnot ===
Jakmile jsou známy polohy chyb, zbývá určit velikosti chyb na těchto místech.
Odečtením nalezených velikostí chyb dostaneme z přijatého slova kódové slovo.

V případě [[Binární kód|binárního kódu]] a původně neznámé polohy chyby stačí negovat příslušný bit.
V případě nečitelných dat je pro účely hledání chyby nahrazeno nečitelné písmeno nulou a pokračujeme jako v obecném případě.
V obecném případě mohou být velikosti chyb <math>e_j</math> určeny řešením soustavy lineárních rovnic

:<math>s_c = e_1 \alpha^{c\,i_1} + e_2 \alpha^{c\,i_2} + \ldots</math>
:<math>s_{c+1} = e_1 \alpha^{(c + 1)\,i_1} + e_2 \alpha^{(c + 1)\,i_2} + \ldots</math>
:…

==== Forneyův vzorec ====
Existuje ale efektivnější metoda známá jako '''Forneyův vzorec'''.

Nechť <math>S(x)=\sum_{i=0}^{d-2} s_{c+i}x^i.</math>
Nechť <math>v\le d-1,</math> <math>\lambda_0\neq 0</math> a <math>\Lambda(x)=\sum_{i=0}^v\lambda_ix^i=\lambda_0\cdot\prod_{k=0}^{v} (\alpha^{-i_k}x-1).</math>

Nechť <math>\Omega(x) = S(x)\,\Lambda(x) \pmod{x^{d-1}}</math> je polynom vyhodnocující chyby.<ref name="Gill-Forney">{{Harvnb|Gill|unknown|p=47}}</ref>

Nechť <math>\Lambda'(x) = \Sigma_{i=1}^v i \cdot \lambda_i x^{i-1},</math> kde <math>i\cdot x</math> zde značí <math>\textstyle\sum_{k=1}^i x</math>
místo násobení v příslušném tělese.

Pokud je možno syndromy vysvětlit chybovým slovem, které může být nenulové jedině na pozicích <math>i_k</math>, pak jsou velikosti chyb
:<math>e_k=-{\alpha^{i_k}\Omega(\alpha^{-i_k})\over \alpha^{c\cdot i_k}\Lambda'(\alpha^{-i_k})}.</math>

Pro doslovné kódy, ''c'' = 1, takže můžeme výraz vykrátit na:
:<math>e_k=-{\Omega(\alpha^{-i_k})\over \Lambda'(\alpha^{-i_k})}.</math>

==== Zdůvodnění Forneyova vzorce ====
Algoritmus je založen na [[Lagrangeova interpolace|Lagrangeově interpolaci]] a technikách [[vytvořující funkce (posloupnost)|vytvořujících funkcí]].

Prozkoumejme <math>S(x)\Lambda(x).</math>
Pro jednoduchost dodefinujme <math>\lambda_k=0</math> pro <math>k>v</math> a <math>s_k=0</math> pro <math>k>c+d-2.</math>

Pak <math>S(x)\Lambda(x)=\sum_{j=0}^{\infty}\sum_{i=0}^j s_{j-i+c}\lambda_i x^j.</math>
Vztah <math>\sum_{i=0}^v s_{v-i+j}\lambda_i=0</math> jsme již odvodili dříve,
takže víme pro důkaz nepodstatnou informaci, že koeficienty u <math>x^j</math> jsou 0 pro <math>v\le j\le d-2.</math>

Zkoumejme dál význam jednotlivých koeficientů:
:<math>S(x)=\sum_{i=0}^{d-2}\sum_{j=1}^v e_j\alpha^{(c+i)\cdot i_j} x^i=\sum_{j=1}^v e_j\alpha^{c\,i_j}\sum_{i=0}^{d-2}(\alpha^{i_j})^i x^i = \sum_{j=1}^v e_j\alpha^{c\,i_j} {(x\alpha^{i_j})^{d-1}-1\over x\alpha^{i_j}-1},</math>

:<math>S(x)\Lambda(x)=S(x)\lambda_0\prod_{\ell=1}^v (\alpha^{i_\ell}x-1)=\lambda_0\sum_{j=1}^v e_j\alpha^{c\,i_j} {(x\alpha^{i_j})^{d-1}-1\over x\alpha^{i_j}-1}\prod_{\ell=1}^v (\alpha^{i_\ell}x-1).</math>
Můžeme získat následující formu polynomu :
:<math>S(x)\Lambda(x)=\lambda_0\sum_{j=1}^v e_j\alpha^{c\,i_j} ((x\alpha^{i_j})^{d-1}-1)\prod_{\ell\in\{1,\dots,v\}\setminus\{j\}} (\alpha^{i_\ell}x-1).</math>
Chceme spočítat neznámé <math>e_j,</math> a můžeme zjednodušit kontext odstraněním <math>(x\alpha^{i_j})^{d-1}</math> členů.
To vede k definici polynomu vyhodnocujícího chyby
:<math>\Omega(x) = S(x)\,\Lambda(x) \pmod{x^{d-1}}.</math>

Díky předpokladu <math>v\le d-1</math> dostáváme
:<math>\Omega(x) = -\lambda_0\sum_{j=1}^v e_j\alpha^{c\,i_j} \prod_{\ell\in\{1,\dots,v\}\setminus\{j\}} (\alpha^{i_\ell}x-1).</math>

Zaměřme se na <math>\Omega(\alpha^{-i_k}).</math> Díky <math>\Lambda</math> (trik Lagrangeovy interpolace) suma degeneruje na jediný sčítanec
:<math>\Omega(\alpha^{-i_k})=-\lambda_0e_k\alpha^{c\cdot i_k}\prod_{\ell\in\{1,\dots,v\}\setminus\{k\}}(\alpha^{i_\ell}\alpha^{-i_k}-1)
.</math>
K nalezení <math>e_k</math> již stačí zbavit se nadbytečného součinu.
Můžeme jej spočítat přímo z již známých kořenů <math>\alpha^{-i_j}</math> polynomu <math>\Lambda,</math> ale můžeme využít jednodušší výraz.

Protože [[formální derivace]] <math>\Lambda'(x)=\lambda_0\sum_{j=1}^v \alpha^{i_j}\prod_{\ell\in\{1,\dots,v\}\setminus\{j\}}(\alpha^{i_\ell}x-1).</math>

Získáváme v bodě <math>\alpha^{-i_k}</math> opět jediný sčítanec
:<math>\Lambda'(\alpha^{-i_k})=
\lambda_0\alpha^{i_k}\prod_{\ell\in\{1,\dots,v\}\setminus\{k\}}(\alpha^{i_\ell}\alpha^{-i_k}-1).
</math>

Takže konečně
:<math>e_k=-{\alpha^{i_k}\Omega(\alpha^{-i_k})\over \alpha^{c\cdot i_k}\Lambda'(\alpha^{-i_k})}</math>

Tato formule je zjednodušením v případě, kdy formální derivaci <math>\Lambda</math> počítáme z tvaru <math>\Lambda(x)=\sum_{i=1}^v\lambda_ix^i</math> pomocí
:<math>\Lambda'(x) = \Sigma_{i=1}^v i \cdot \lambda_i x^{i-1},</math>

kde <math>i\cdot x</math> značí <math>\textstyle\sum_{k=1}^i x</math> místo násobení v příslušném tělese.

=== Dekódování založené na rozšířeném Euklidově algoritmu ===
Celý proces hledání lokalizačního polynomu Λ i hledání velikosti chyb je možno založit na
# [[rozšířený Eukleidův algoritmus|Rozšířeném Eukleidově algoritmu]]. Navíc přitom můžeme opravovat i nečitelné znaky na neznámých pozicích.

Nechť <math>k_1, ... ,k_k</math> jsou pozice nečitelných znaků. Sestavíme tomu odpovídající polynom <math>\Gamma(x)=\prod_{i=1}^k(x\alpha^{k_i}-1).</math>
Dodefinujme nečitelná místa nulou a spočtěme syndromy.
Tak jak jsme si popsali u Forneyova vzorce nechť <math>S(x)=\sum_{i=0}^{d-2}s_{c+i}x^i.</math>

Spustíme rozšířený [[Eukleidův algoritmus|Euklidův algoritmus]] na hledání nejmenšího společného dělitele polynomů <math>S(x)\Gamma(x)</math> a <math>x^{d-1}.</math> Naším cílem ale nebude nalézt nejmenšího společného dělitele, ale polynom <math>r(x)</math> stupně nejvýš <math>\lfloor (d+k-3)/2\rfloor</math> a polynomy <math>a(x), b(x)</math> tak, aby <math>r(x)=a(x)S(x)\Gamma(x)+b(x)x^{d-1}.</math>
Nízký stupeň polynomu <math>r(x)</math> zajistí, že pro <math>a(x)</math> budou platit zobecněné (o polynom opravující nečitelné znaky) definiční vztahy které jsme kladli na <math>\Lambda.</math>

Při definici <math>\Xi(x)=a(x)\Gamma(x)</math> a použití <math>\Xi</math> na místě <math>\Lambda</math> ve Fourney algoritmu pak dostaneme odhad velikosti chyb.

Hlavní výhodou algoritmu je, že zároveň spočítá ve Forneyově vzorci potřebné <math>\Omega(x)=S(x)\Xi(x)\bmod x^{d-1}=r(x).</math>

=== Zdůvodnění nejen dekódování založeném na rozšířeném Euklidově algoritmu ===
Naší snahou je nalézt kódové slovo, které se od přijatého slova na čitelných pozicích liší co nejméně. Při vyjádření přijatého slova jako součtu nejbližšího kódového slova a chybového slova tak hledáme chybové slovo s nejmenším počtem nenulových souřadnic na čitelných pozicích. Syndrom <math>s_i</math> klade na chybové slovo podmínku <math>s_i=\sum_{j=0}^{n-1}e_j\alpha^{ij}.</math>
Tyto podmínky můžeme zapisovat samostatně, nebo můžeme vytvořit polynom <math>S(x)=\sum_{i=0}^{d-2}s_{c+i}x^i</math> a klást podmínky na koeficienty u mocnin <math>0</math> až <math>d-2.</math>
<math>S(x){\textstyle{\{0,\ldots,\,d-2\}\atop =}}E(x)=\sum_{i=0}^{d-2}\sum_{j=0}^{n-1}e_j\alpha^{ij}\alpha^{cj}x^i.</math>

Víme-li, že na pozici <math>k_1</math> je nečitelný znak, můžeme množinu syndromů <math>\{s_c,\ldots,s_{c+d-2}\}</math> nahradit množinou syndromů <math>\{t_c,\ldots,t_{c+d-3}\}</math> definovaných vztahem <math>t_i=\alpha^{k_1}s_i-s_{i+1}.</math>
Pokud platí pro chybové slovo podmínky kladené množinou syndromů <math>\{s_c,\ldots,s_{c+d-2}\},</math> pak <math>t_i=\alpha^{k_1}s_i-s_{i+1}=\alpha^{k_1}\sum_{j=0}^{n-1}e_j\alpha^{ij}-\sum_{j=0}^{n-1}e_j\alpha^j\alpha^{ij}=\sum_{j=0}^{n-1}e_j(\alpha^{k_1}-\alpha^j)\alpha^{ij}.</math>
Nová množina syndromů má vůči chybovému vektoru <math>f_j=e_j(\alpha^{k_1}-\alpha^j)</math> stejný vztah jako měla původní množina syndromů vůči chybovému vektoru <math>e_j.</math>
Všimněme si, že s výjimkou souřadnice <math>k_1,</math> kde je <math>f_{k_1}=0,</math> je <math>f_j</math> nenulové,
právě když je <math>e_j</math> nenulové. Co se týče hledání pozic chyb, můžeme proto takto upravit množinu syndromů postupným zohledněním pozic neznámých znaků. Výsledná množina syndromů bude kratší o počet <math>k</math> nečitelných znaků.

Při formulaci v řeči polynomů nám náhrada množiny syndromů <math>\{s_c,\ldots,s_{c+d-2}\}</math> množinou syndromů <math>\{t_c,\ldots,t_{c+d-3}\}</math> vede k <math>T(x)=\sum_{i=0}^{d-3}t_{c+i}x^i=\alpha^{k_1}\sum_{i=0}^{d-3}s_{c+i}x^i-\sum_{i=1}^{d-2}s_{c+i}x^{i-1}.</math>
Odtud <math>xT(x){\textstyle{\{1,\ldots,\,d-2\}\atop =}}(x\alpha^{k_1}-1)S(x).</math>

Po nahrazení <math>S(x)</math> pomocí <math>S(x)\Gamma(x)</math> pak proto budeme hledat shodu u koeficientů <math>k,\ldots,d-2.</math>

Obdobně jako odstraňování vlivu nečitelných znaků můžeme vnímat i hledání chybných pozic. Pokud najdeme <math>v</math> souřadnic tak, že odstranění jejich vlivu povede k tomu, že zbylé syndromy budou nulové, existuje chybový vektor jenž má nenulové hodnoty pouze v těchto souřadnicích. Pokud označíme <math>\Lambda(x)</math> polynom odstraňující vliv těchto souřadnic, dostaneme <math>S(x)\Gamma(x)\Lambda(x){\textstyle{\{k+v,\ldots,\,d-2\}\atop =}}0.</math>

V Euklidově algoritmu se snažíme odstranit nejvýš <math>(d-1-k)/2</math> chyb (na čitelných místech), protože při větším počtu chyb může být více kódových slov od přijatého slova stejně daleko. Proto musí pro hledané <math>\Lambda(x)</math> nastat ve výše uvedeném vztahu rovnost u všech souřadnic počínaje <math>k+\lfloor(d-1-k)/2\rfloor.</math>

Ve Forney vzorci (pro nalezení velikosti chyb) nezáleželo na tom, zda je <math>\Lambda(x)</math> vynásobena nenulovou konstantou, proto je podmínka <math>\lambda_0=1</math> zbytečná.
Může se stát, že Euklidův algoritmus najde <math>\Lambda(x)</math> stupně většího než <math>(d-1-k)/2,</math>
který má tolik různých kořenů, jako je jeho stupeň, a pomocí Forney algoritmu bude možno opravit chyby v polohách všech jeho kořenů, přesto opravovat takto nalezené chyby je nebezpečné. Obvykle při nalezení <math>\Lambda(x)</math> většího stupně odmítáme chyby opravovat. Stejně tak oprava chyb selže, pokud má <math>\Lambda(x)</math> vícenásobné kořeny či jejich počet neodpovídá stupni <math>\Lambda(x).</math>
Selhání také může detekovat to, když Forney vzorec vrátí chybu z rozdílu těles <math>B\setminus A.</math>

=== Příklady dekódování ===

==== Dekódování binárního kódu bez nečitelných znaků ====
Nechť <math>d=7</math> a používáme dříve uvedený kód s <math>g(x) = x^{10} + x^8 + x^5 + x^4 + x^2 + x + 1</math> v GF(2<sup>4</sup>).
(Tento generátor je použit v [[QR kód]]ech.)
Nechť přenášená zpráva je <nowiki>[1 1 0 1 1]</nowiki>, nebo jako polynom <math>M(x) = x^4 + x^3 + x + 1.</math>
Zabezpečovací symboly jsou spočteny dělením <math>x^{10} M(x)</math> polynomem <math>g(x)</math>
a přičtením (odečtením) zbytku <math>x^9 + x^4 + x^2</math> neboli <nowiki>[ 1 0 0 0 0 1 0 1 0 0 ]</nowiki> k <math>x^{10} M(x).</math>
Přidáním ke zprávě tak dostáváme přenášené kódové slovo <nowiki>[ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0 ]</nowiki>.

Předpokládejme, že dva bity byly poškozeny v průběhu přenosu, takže přijaté slovo je [ 1 {{Barva|red|0}} 0 1 1 1 0 0 0 {{Barva|red|1}} 1 0 1 0 0 ].
Jakožto polynom tedy:
:<math>R(x) = C(x) + x^{13} + x^5 = x^{14} + x^{11} + x^{10} + x^9 + x^5 + x^4 + x^2</math>
Abychom chyby opravili, spočteme nejprve syndromy.
Přitom <math>\alpha = 0010,</math> dostaneme <math>s_1 = R(\alpha^1) = 1011,</math> <math>s_2 = 1001,</math> <math>s_3 = 1011,</math> <math>s_4 = 1101,</math> <math>s_5 = 0001</math> a <math>s_6 = 1001.</math>
K zápisu bychom mohli používat hexadecimální číslice, ale držme se v tomto úvodním příkladu [[Dvojková soustava|dvojkové soustavy]].

Následně aplikujme Petersonův algoritmus.
:<math>\left [ S_{3 \times 3} | C_{3 \times 1} \right ] =
\begin{bmatrix}s_1&s_2&s_3&s_4\\
s_2&s_3&s_4&s_5\\
s_3&s_4&s_5&s_6\end{bmatrix} =
\begin{bmatrix}1011&1001&1011&1101\\
1001&1011&1101&0001\\
1011&1101&0001&1001\end{bmatrix} \Rightarrow
\begin{bmatrix}0001&0000&1000&0111\\
0000&0001&1011&0001\\
0000&0000&0000&0000\end{bmatrix}</math>
Protože {{Math|''S''<sub>3×3</sub>}} je singulární, což není překvapením, protože slovo obsahuje pouze dvě chyby.
Nyní levý horní roh matice je identický s [''S''<sub>2×2</sub> ''C''<sub>2×1</sub>],
což vede k řešení <math>\lambda_2 = 1000,</math> <math>\lambda_1 = 1011.</math>
Výsledný polynom pro lokalizaci chyb je <math>\Lambda(x) = 1000 x^2 + 1011 x + 0001.</math>
Polynom má kořeny <math>0100 = \alpha^{-13}</math> a <math>0111 = \alpha^{-5}.</math>
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.

==== Dekódování s nečitelnými znaky a maximálním opravitelným počtem chyb ====
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 stejně jako v předchozím případě 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šířený 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].

==== Dekódování s nečitelnými znaky a malým počtem chyb ====
Ještě ukažme 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ě nejvýš 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].

== Reference ==
<references />

== Literatura ==
=== Hlavní literatura ===
* {{Citation
 |first= A.
 |last= Hocquenghem
 |author-link= Alexis Hocquenghem
 |title=Codes correcteurs d'erreurs
 |language= French
 |journal= Chiffres
 |location= Paris
 |volume=2
 |pages= 147–156
 |date= September 1959
 |issn=
 |doi=}}
* {{Citation
 |first= R. C.
 |last= Bose
 |author-link= R. C. Bose
 |first2= D. K.
 |last2= Ray-Chaudhuri
 |author2-link= D. K. Ray-Chaudhuri
 |title= On A Class of Error Correcting Binary Group Codes
 |journal= [[Information and Control]]
 |volume= 3
 |issue=1
 |pages= 68–79
 |date= March 1960
 |issn= 0890-5401
 |doi=}}

=== Sekundární literatura ===
* {{Citation
 |first= W. J.
 |last= Gilbert
 |first2= W. K.
 |last2= Nicholson
 |title= Modern Algebra with Applications
 |edition= 2nd
 |publisher= John Wiley
 |year= 2004
 |url=
 |isbn=
 |doi=}} 
* {{Citation
 |last             = Gill
 |first            = John
 |title            = EE387 Notes #7, Handout #28
 |year             = unknown
 |accessdate       = April 21, 2010
 |pages            = 42–45
 |publisher        = Stanford University
 |url              = http://www.stanford.edu/class/ee387/handouts/notes7.pdf
 |doi              = 
 |archiveurl       = https://web.archive.org/web/20140630172526/http://web.stanford.edu/class/ee387/handouts/notes7.pdf
 |archivedate      = 30-06-2014
 |titul            = Archivovaná kopie
 |datum přístupu = 17-12-2012
 |url archivu      = https://web.archive.org/web/20140630172526/http://web.stanford.edu/class/ee387/handouts/notes7.pdf
 |datum archivace  = 30-06-2014
 |nedostupné      = ano
}}
* {{Citation
 |last= Gorenstein
 |first= Daniel
 |authorlink= Daniel Gorenstein
 |last2= Peterson
 |first2= W. Wesley
 |authorlink2= W. Wesley Peterson
 |last3= Zierler
 |first3 = Neal
 |authorlink3= Neal Zierler
 |title= Two-Error Correcting Bose-Chaudhuri Codes are Quasi-Perfect
 |journal= Information and Control
 |volume= 3
 |issue= 3
 |pages= 291–294
 |year= 1960
 |doi= }}
* {{Citation
 |first= Rudolf
 |last= Lidl
 |first2= Günter
 |last2= Pilz
 |title= Applied Abstract Algebra
 |edition= 2nd
 |publisher= John Wiley
 |year= 1999
 |url=
 |isbn=
 |doi=}}
* {{Citation
 |first= S.
 |last= Lin
 |first2= D.
 |last2= Costello
 |title= Error Control Coding: Fundamentals and Applications
 |publisher= Prentice-Hall
 |location= Englewood Cliffs, NJ
 |year= 2004
 |isbn=
 |doi= }}
* {{Citation
 |first= F. J.
 |last=MacWilliams
 |first2= N. J. A.
 |last2= Sloane
 |authorlink2= N. J. A. Sloane
 |title= The Theory of Error-Correcting Codes
 |location= New York, NY
 |publisher= North-Holland Publishing Company
 |year= 1977
 |isbn=
 |doi=}} 
* {{Citation
 |first= Irving S.
 |last= Reed
 |authorlink= Irving S. Reed
 |first2= Xuemin
 |last2= Chen
 |title= Error-Control Coding for Data Networks
 |location= Boston, MA
 |publisher= [[Kluwer Academic Publishers]]
 |year= 1999
 |isbn= 0-7923-8528-4
 |doi=}}
* {{Citation
 |first            = Atri
 |last             = Rudra
 |title            = CSE 545, Error Correcting Codes: Combinatorics, Algorithms and Applications
 |publisher        = University at Buffalo
 |url              = http://www.cse.buffalo.edu/~atri/courses/coding-theory/
 |accessdate       = April 21, 2010
 |doi              = 
 |archiveurl       = https://web.archive.org/web/20100702120650/http://www.cse.buffalo.edu/~atri/courses/coding-theory/
 |archivedate      = 02-07-2010
 |titul            = Archivovaná kopie
 |datum přístupu = 17-12-2012
 |url archivu      = https://web.archive.org/web/20100702120650/http://www.cse.buffalo.edu/~atri/courses/coding-theory/
 |datum archivace  = 02-07-2010
 |nedostupné      = ano
}}

{{Autoritní data}}

{{DEFAULTSORT:Bch Code}}
[[Kategorie:Detekce a oprava chyb]]
[[Kategorie:Teorie kódování]]