BCH kód

V teorii kódování tvoří BCH kódy skupinu cyklických samoopravných kódů, které jsou konstruovány pomocí konečných těles. BCH kódy byly vynalezeny v roce 1959 Hocquenghemem, a nezávisle v roce 1960 Bosem a Ray-Chaudhurim.^[1] 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í algebraický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,^[2] CD a DVD přehrávačích, pevných discích, flash discích^[3] a QR kódech.

Konstrukce

Nechť A je GF(q^a). 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 GF(q^b) 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á čísla. Kódová slova jsou taková slova v₁v₂…v_n, kde polynom v₁x^n-1+v₂x^n-2+…+v_n-1x¹+v_n má kořeny α^c, α^c+1, …, α^c+d-2.

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₁x^n-1+v₂x^n-2+…+v_kx^m polynomem P(x).

Kódové slovo vznikne z polynomu V(x)-R(x), tak že v_i bude tvořeno koeficientem u x^n-i.

Konstrukce garantuje 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^b/a−1 je nazýván primitivní kód.
• BCH kód s n<q^b/a−1 je nazýván zkrácený kód.
• BCH kód s A=Z_q je nazýván základní BCH kód.
• BCH kód s A=Z₂ je nazýván binární BCH kód.
• BCH kód s A=B je nazýván Reed Solomonův kód.^[4]

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é αⁱ 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ť ${\displaystyle q=2}$ a ${\displaystyle b=4}$ (tedy ${\displaystyle n=15}$). Uvažujme různé hodnoty ${\displaystyle d.}$

Existuje primitivní prvek ${\displaystyle \alpha \in GF(16)}$ splňující ${\displaystyle \alpha ^{4}+\alpha +1=0(*),}$ jeho minimální polynom nad ${\displaystyle Z_{2}}$ je

${\displaystyle m_{1}(x)=x^{4}+x+1.}$

Poznamenejme, že v ${\displaystyle GF(2^{4}),}$ platí ${\displaystyle (a+b)^{2}=a^{2}+ab+ab+b^{2}=a^{2}+b^{2},}$ proto ${\displaystyle m_{1}(\alpha ^{2})=m_{1}(\alpha )^{2}=0.}$

Tudíž ${\displaystyle \alpha ^{2}}$ je kořen polynomu ${\displaystyle m_{1}(x),}$ a

${\displaystyle m_{2}(x)=m_{1}(x)=x^{4}+x+1.}$

Abychom spočítali ${\displaystyle m_{3}(x),}$ poznamenejme, že opakovanou aplikací (*), dostáváme následující rovnice:

• ${\displaystyle 1=0\alpha ^{3}+0\alpha ^{2}+0\alpha +1}$
• ${\displaystyle \alpha ^{3}=1\alpha ^{3}+0\alpha ^{2}+0\alpha +0}$
• ${\displaystyle \alpha ^{6}=1\alpha ^{3}+1\alpha ^{2}+0\alpha +0}$
• ${\displaystyle \alpha ^{9}=1\alpha ^{3}+0\alpha ^{2}+1\alpha +0}$
• ${\displaystyle \alpha ^{12}=1\alpha ^{3}+1\alpha ^{2}+1\alpha +1}$

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

Protože neexistuje závislost nižšího řádu, je minimálním polynomem pro ${\displaystyle \alpha ^{3}}$ polynom

${\displaystyle m_{3}(x)=x^{4}+x^{3}+x^{2}+x+1.}$

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

${\displaystyle m_{4}(x)=m_{2}(x)=m_{1}(x)=x^{4}+x+1,\,}$

${\displaystyle m_{5}(x)=x^{2}+x+1,\,}$

${\displaystyle m_{6}(x)=m_{3}(x)=x^{4}+x^{3}+x^{2}+x+1,\,}$

${\displaystyle m_{7}(x)=x^{4}+x^{3}+1.\,}$

BCH kódy s ${\displaystyle d=1,2,3}$ mají generující polynom

${\displaystyle g(x)=m_{1}(x)=x^{4}+x+1.\,}$

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 ${\displaystyle d=4,5}$ mají generující polynom

${\displaystyle 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.\,}$

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 ${\displaystyle d=6,7}$ mají generující polynom

${\displaystyle {\begin{aligned}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{aligned}}}$

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 ${\displaystyle d\geq 8}$ má generující polynom

${\displaystyle {\begin{aligned}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{aligned}}}$

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ýš ${\displaystyle (d-1)(b/a).}$ Navíc, pokud ${\displaystyle A=Z_{2}}$ a ${\displaystyle c=1,}$ pak generující polynom má stupeň nejvýš ${\displaystyle db/2a.}$

Důkaz: každý minimální polynom ${\displaystyle m_{i}(x)}$ má stupeň nejvýš ${\displaystyle b/a.}$

Proto minimální společný násobek ${\displaystyle d-1}$ z nich má stupeň nejvýš ${\displaystyle (d-1)(b/a).}$ Navíc, pokud ${\displaystyle A=Z_{2},}$ pak ${\displaystyle m_{i}(x)=m_{2i}(x)}$ pro každé ${\displaystyle i.}$ Proto, ${\displaystyle g(x)}$ je nejmenší společný násobek nejvýš ${\displaystyle d/2}$ minimálních polynomů ${\displaystyle m_{i}(x)}$ pro liché indexy ${\displaystyle i,}$ každý z nich je stupně nejvýš ${\displaystyle b/a.}$

2. BCH kód má minimální Hammingovu vzdálenost alespoň ${\displaystyle d.}$

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

${\displaystyle p(x)=b_{1}x^{k_{1}}+\cdots +b_{d-1}x^{k_{d-1}},{\text{ kde }}k_{1}<k_{2}<\cdots <k_{d-1}.}$

Připomeňme, že ${\displaystyle \alpha ^{c},\ldots ,\alpha ^{c+d-2}}$ jsou kořeny ${\displaystyle g(x),}$ tudíž i jeho násobku ${\displaystyle p(x).}$ Z toho plyne, že ${\displaystyle b_{1},\ldots ,b_{d-1}}$ splňuje následující rovnice pro ${\displaystyle i=c,\ldots ,c+d-2:}$

${\displaystyle p(\alpha ^{i})=b_{1}\alpha ^{ik_{1}}+b_{2}\alpha ^{ik_{2}}+\cdots +b_{d-1}\alpha ^{ik_{d-1}}=0.}$

V maticovém tvaru dostáváme

${\displaystyle {\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}}.}$

Determinant této matice je roven

${\displaystyle \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).}$

Matice ${\displaystyle V}$ je Vandermondova matice, a její determinant je

${\displaystyle \det(V)=\prod _{1\leq i<j\leq d-1}(\alpha ^{k_{j}}-\alpha ^{k_{i}}),}$

což je nenulové. Odtud vyplývá, že ${\displaystyle b_{1},\ldots ,b_{d-1}=0,}$ a tudíž ${\displaystyle p(x)=0.}$

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 ${\displaystyle n}$ je cyklický právě když generující polynom dělí ${\displaystyle x^{n}-1.}$ Protože ${\displaystyle g(x)}$ je minimální polynom s kořeny ${\displaystyle \alpha ^{c},\ldots ,\alpha ^{c+d-2},}$ stačí zkontrolovat, že každé z ${\displaystyle \alpha ^{c},\ldots ,\alpha ^{c+d-2}}$ je kořen polynomu ${\displaystyle x^{n}-1.}$ To plyne přímo z toho, že ${\displaystyle \alpha }$ je podle definice ${\displaystyle n}$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:

1. Spočtěme pro přijaté slovo syndromy s_j.
2. Ze syndromů určeme počet chyb t a polynom pro lokalizaci chyb Λ(x).
3. Nalezněme kořeny polynomu pro lokalizaci chyb x_j a jejich logaritmy -i_j, tak že α^−i_j=x_j.
4. Spočtěme chybové hodnoty e_i v pozicích i_j.
5. 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 ${\displaystyle R}$ je součet korektního kódového slova ${\displaystyle C}$ a neznámého chybového slova ${\displaystyle E.}$ Hodnoty syndromů jsou získány dosazením hodnot ${\displaystyle \alpha ^{c},\ldots ,\alpha ^{c+d-2}}$ do ${\displaystyle R}$ vnímaného jakožto polynom. Proto jsou syndromy^[5]

${\displaystyle s_{j}=R(\alpha ^{j})=C(\alpha ^{j})+E(\alpha ^{j}),}$

pro ${\displaystyle j}$ od ${\displaystyle c}$ do ${\displaystyle c+d-2.}$ Protože ${\displaystyle \alpha ^{j}}$ jsou kořeny ${\displaystyle g(x),}$ jehož je ${\displaystyle C(x)}$ násobek, ${\displaystyle C(\alpha ^{j})=0.}$ 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 ${\displaystyle s_{j}=0}$ pro každé ${\displaystyle j.}$ 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

${\displaystyle E(x)=e_{1}x^{i_{1}}+e_{2}x^{i_{2}}+\cdots +e_{v}x^{i_{v}}\,.}$

Není zřejmé, jak začít řešit rovnice s neznámými ${\displaystyle e_{k}}$ a ${\displaystyle i_{k}}$ vysvětlující syndromy.

Prvním krokem je nalezení polynomu pro lokalizaci chyb

${\displaystyle \Lambda (x)=\prod _{j=1}^{v}(x\alpha ^{i_{j}}-1)}$ kompatibilního se spočtenými syndromy a s minimálním možným ${\displaystyle v.}$

Dva populární algoritmy pro tuto úlohu jsou:

1. Algoritmus Peterson–Gorenstein–Zierler^[6]
2. Algoritmus Berlekamp–Massey

Cílem obou algoritmů je nalézt

${\displaystyle \Lambda (x)=\lambda _{0}+\lambda _{1}x+\lambda _{2}x^{2}+\cdots +\lambda _{v}x^{v}}$

takové, aby pro každé ${\displaystyle j}$ od ${\displaystyle c}$ do ${\displaystyle c+d-2-v}$ platilo

${\displaystyle \sum _{i=0}^{v}\lambda _{i}s_{j+v-i}=0.}$

Navíc požadujeme ${\displaystyle \lambda _{0}=1.}$

Zdůvodnění rovnic pro výpočet polynomu pro lokalizaci chyb

Vzhledem k tomu, že ${\displaystyle \alpha ^{-i_{k}}}$ je kořenem polynomu ${\displaystyle \Lambda (x),}$ musí být

${\displaystyle 0=\sum _{i=0}^{v}\lambda _{i}\alpha ^{-i\cdot i_{k}}.}$

Po pronásobení ${\displaystyle e_{k}\alpha ^{(j+v)i_{k}}}$ dostáváme

${\displaystyle 0=\sum _{i=0}^{v}\lambda _{i}e_{k}\alpha ^{(j+v-i)i_{k}}.}$

Po sečtení přes jednotlivé chyby pak

${\displaystyle 0=\sum _{i=0}^{v}\lambda _{i}\sum _{k=0}^{v}e_{k}\alpha ^{(j+v-i)i_{k}},}$

neboli

${\displaystyle 0=\sum _{i=0}^{v}\lambda _{i}s_{j+v-i}.}$

Algoritmus Peterson–Gorenstein–Zierler

Algoritmus řeší 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

${\displaystyle 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}},}$

• pak vektor ${\displaystyle c_{v\times 1}}$

${\displaystyle C_{v\times 1}={\begin{bmatrix}s_{c+v}\\s_{c+v+1}\\\vdots \\s_{c+2v-1}\end{bmatrix}}.}$

• Nechť neznámé koeficienty polynomu ${\displaystyle \Lambda }$ jsou

${\displaystyle \Lambda _{v\times 1}={\begin{bmatrix}\lambda _{v}\\\lambda _{v-1}\\\vdots \\\lambda _{1}\end{bmatrix}}.}$

• Pokud má ${\displaystyle S_{v\times v}}$ nenulový determinant, pak maticová rovnice

${\displaystyle S_{v\times v}\Lambda _{v\times 1}=-C_{v\times 1\,}}$

má řešení. Nalezněme tedy koeficienty polynomu ${\displaystyle \Lambda }$ a skončeme.

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

V případě ${\displaystyle v}$ větším než je počet chyb (můžeme dodefinovat nadbytečná ${\displaystyle e_{k}}$ nulou). Pak

${\displaystyle 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}},}$

a determinant je nulový, dokud není ${\displaystyle v}$ 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í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 ${\displaystyle e_{j}}$ určeny řešením soustavy lineárních rovnic

${\displaystyle s_{c}=e_{1}\alpha ^{c\,i_{1}}+e_{2}\alpha ^{c\,i_{2}}+\ldots }$

${\displaystyle s_{c+1}=e_{1}\alpha ^{(c+1)\,i_{1}}+e_{2}\alpha ^{(c+1)\,i_{2}}+\ldots }$

…

Forneyův vzorec

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

Nechť ${\displaystyle S(x)=\sum _{i=0}^{d-2}s_{c+i}x^{i}.}$ Nechť ${\displaystyle v\leq d-1,}$ ${\displaystyle \lambda _{0}\neq 0}$ a ${\displaystyle \Lambda (x)=\sum _{i=0}^{v}\lambda _{i}x^{i}=\lambda _{0}\cdot \prod _{k=0}^{v}(\alpha ^{-i_{k}}x-1).}$

Nechť ${\displaystyle \Omega (x)=S(x)\,\Lambda (x){\pmod {x^{d-1}}}}$ je polynom vyhodnocující chyby.^[7]

Nechť ${\displaystyle \Lambda '(x)=\Sigma _{i=1}^{v}i\cdot \lambda _{i}x^{i-1},}$ kde ${\displaystyle i\cdot x}$ zde značí ${\displaystyle \textstyle \sum _{k=1}^{i}x}$ 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 ${\displaystyle i_{k}}$, pak jsou velikosti chyb

${\displaystyle e_{k}=-{\alpha ^{i_{k}}\Omega (\alpha ^{-i_{k}}) \over \alpha ^{c\cdot i_{k}}\Lambda '(\alpha ^{-i_{k}})}.}$

Pro doslovné kódy, c = 1, takže můžeme výraz vykrátit na:

${\displaystyle e_{k}=-{\Omega (\alpha ^{-i_{k}}) \over \Lambda '(\alpha ^{-i_{k}})}.}$

Zdůvodnění Forneyova vzorce

Algoritmus je založen na Lagrangeově interpolaci a technikách vytvořujících funkcí.

Prozkoumejme ${\displaystyle S(x)\Lambda (x).}$ Pro jednoduchost dodefinujme ${\displaystyle \lambda _{k}=0}$ pro ${\displaystyle k>v}$ a ${\displaystyle s_{k}=0}$ pro ${\displaystyle k>c+d-2.}$

Pak ${\displaystyle S(x)\Lambda (x)=\sum _{j=0}^{\infty }\sum _{i=0}^{j}s_{j-i+c}\lambda _{i}x^{j}.}$ Vztah ${\displaystyle \sum _{i=0}^{v}s_{v-i+j}\lambda _{i}=0}$ jsme již odvodili dříve, takže víme pro důkaz nepodstatnou informaci, že koeficienty u ${\displaystyle x^{j}}$ jsou 0 pro ${\displaystyle v\leq j\leq d-2.}$

Zkoumejme dál význam jednotlivých koeficientů:

${\displaystyle 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},}$

${\displaystyle 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).}$

Můžeme získat následující formu polynomu :

${\displaystyle 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).}$

Chceme spočítat neznámé ${\displaystyle e_{j},}$ a můžeme zjednodušit kontext odstraněním ${\displaystyle (x\alpha ^{i_{j}})^{d-1}}$ členů. To vede k definici polynomu vyhodnocujícího chyby

${\displaystyle \Omega (x)=S(x)\,\Lambda (x){\pmod {x^{d-1}}}.}$

Díky předpokladu ${\displaystyle v\leq d-1}$ dostáváme

${\displaystyle \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).}$

Zaměřme se na ${\displaystyle \Omega (\alpha ^{-i_{k}}).}$ Díky ${\displaystyle \Lambda }$ (trik Lagrangeovy interpolace) suma degeneruje na jediný sčítanec

${\displaystyle \Omega (\alpha ^{-i_{k}})=-\lambda _{0}e_{k}\alpha ^{c\cdot i_{k}}\prod _{\ell \in \{1,\dots ,v\}\setminus \{k\}}(\alpha ^{i_{\ell }}\alpha ^{-i_{k}}-1).}$

K nalezení ${\displaystyle e_{k}}$ již stačí zbavit se nadbytečného součinu. Můžeme jej spočítat přímo z již známých kořenů ${\displaystyle \alpha ^{-i_{j}}}$ polynomu ${\displaystyle \Lambda ,}$ ale můžeme využít jednodušší výraz.

Protože formální derivace ${\displaystyle \Lambda '(x)=\lambda _{0}\sum _{j=1}^{v}\alpha ^{i_{j}}\prod _{\ell \in \{1,\dots ,v\}\setminus \{j\}}(\alpha ^{i_{\ell }}x-1).}$

Získáváme v bodě ${\displaystyle \alpha ^{-i_{k}}}$ opět jediný sčítanec

${\displaystyle \Lambda '(\alpha ^{-i_{k}})=\lambda _{0}\alpha ^{i_{k}}\prod _{\ell \in \{1,\dots ,v\}\setminus \{k\}}(\alpha ^{i_{\ell }}\alpha ^{-i_{k}}-1).}$

Takže konečně

${\displaystyle e_{k}=-{\alpha ^{i_{k}}\Omega (\alpha ^{-i_{k}}) \over \alpha ^{c\cdot i_{k}}\Lambda '(\alpha ^{-i_{k}})}}$

Tato formule je zjednodušením v případě, kdy formální derivaci ${\displaystyle \Lambda }$ počítáme z tvaru ${\displaystyle \Lambda (x)=\sum _{i=1}^{v}\lambda _{i}x^{i}}$ pomocí

${\displaystyle \Lambda '(x)=\Sigma _{i=1}^{v}i\cdot \lambda _{i}x^{i-1},}$

kde ${\displaystyle i\cdot x}$ značí ${\displaystyle \textstyle \sum _{k=1}^{i}x}$ 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

1. Rozšířeném Eukleidově algoritmu. Navíc přitom můžeme opravovat i nečitelné znaky na neznámých pozicích.

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

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

Při definici ${\displaystyle \Xi (x)=a(x)\Gamma (x)}$ a použití ${\displaystyle \Xi }$ na místě ${\displaystyle \Lambda }$ ve Fourney algoritmu pak dostaneme odhad velikosti chyb.

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

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 ${\displaystyle s_{i}}$ klade na chybové slovo podmínku ${\displaystyle s_{i}=\sum _{j=0}^{n-1}e_{j}\alpha ^{ij}.}$ Tyto podmínky můžeme zapisovat samostatně, nebo můžeme vytvořit polynom ${\displaystyle S(x)=\sum _{i=0}^{d-2}s_{c+i}x^{i}}$ a klást podmínky na koeficienty u mocnin ${\displaystyle 0}$ až ${\displaystyle d-2.}$ ${\displaystyle 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}.}$

Víme-li, že na pozici ${\displaystyle k_{1}}$ je nečitelný znak, můžeme množinu syndromů ${\displaystyle \{s_{c},\ldots ,s_{c+d-2}\}}$ nahradit množinou syndromů ${\displaystyle \{t_{c},\ldots ,t_{c+d-3}\}}$ definovaných vztahem ${\displaystyle t_{i}=\alpha ^{k_{1}}s_{i}-s_{i+1}.}$ Pokud platí pro chybové slovo podmínky kladené množinou syndromů ${\displaystyle \{s_{c},\ldots ,s_{c+d-2}\},}$ pak ${\displaystyle 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}.}$ Nová množina syndromů má vůči chybovému vektoru ${\displaystyle f_{j}=e_{j}(\alpha ^{k_{1}}-\alpha ^{j})}$ stejný vztah jako měla původní množina syndromů vůči chybovému vektoru ${\displaystyle e_{j}.}$ Všimněme si, že s výjimkou souřadnice ${\displaystyle k_{1},}$ kde je ${\displaystyle f_{k_{1}}=0,}$ je ${\displaystyle f_{j}}$ nenulové, právě když je ${\displaystyle e_{j}}$ 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 ${\displaystyle k}$ nečitelných znaků.

Při formulaci v řeči polynomů nám náhrada množiny syndromů ${\displaystyle \{s_{c},\ldots ,s_{c+d-2}\}}$ množinou syndromů ${\displaystyle \{t_{c},\ldots ,t_{c+d-3}\}}$ vede k ${\displaystyle 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}.}$ Odtud ${\displaystyle xT(x){\textstyle {\{1,\ldots ,\,d-2\} \atop =}}(x\alpha ^{k_{1}}-1)S(x).}$

Po nahrazení ${\displaystyle S(x)}$ pomocí ${\displaystyle S(x)\Gamma (x)}$ pak proto budeme hledat shodu u koeficientů ${\displaystyle k,\ldots ,d-2.}$

Obdobně jako odstraňování vlivu nečitelných znaků můžeme vnímat i hledání chybných pozic. Pokud najdeme ${\displaystyle v}$ 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 ${\displaystyle \Lambda (x)}$ polynom odstraňující vliv těchto souřadnic, dostaneme ${\displaystyle S(x)\Gamma (x)\Lambda (x){\textstyle {\{k+v,\ldots ,\,d-2\} \atop =}}0.}$

V Euklidově algoritmu se snažíme odstranit nejvýš ${\displaystyle (d-1-k)/2}$ 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é ${\displaystyle \Lambda (x)}$ nastat ve výše uvedeném vztahu rovnost u všech souřadnic počínaje ${\displaystyle k+\lfloor (d-1-k)/2\rfloor .}$

Ve Forney vzorci (pro nelezení velikosti chyb) nezáleželo na tom, zda je ${\displaystyle \Lambda (x)}$ vynásobena nenulovou konstantou, proto je podmínka ${\displaystyle \lambda _{0}=1}$ zbytečná. Může se stát, že Euklidův algoritmus najde ${\displaystyle \Lambda (x)}$ stupně většího než ${\displaystyle (d-1-k)/2,}$ 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í ${\displaystyle \Lambda (x)}$ většího stupně odmítáme chyby opravovat. Stejně tak oprava chyb selže, pokud má ${\displaystyle \Lambda (x)}$ vícenásobné kořeny či jejich počet neodpovídá stupni ${\displaystyle \Lambda (x).}$ Selhání také může detekovat to, když Forney vzorec vrátí chybu z rozdílu těles ${\displaystyle B\setminus A.}$

Příklady dekódování

Dekódování binárního kódu bez nečitelných znaků

Nechť ${\displaystyle d=7}$ a používáme dříve uvedený kód s ${\displaystyle g(x)=x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1}$ v GF(2⁴). (Tento generátor je použit v QR kódech.) Nechť přenášená zpráva je [1 1 0 1 1], nebo jako polynom ${\displaystyle M(x)=x^{4}+x^{3}+x+1.}$ Zabezpečovací symboly jsou spočteny dělením ${\displaystyle x^{10}M(x)}$ polynomem ${\displaystyle g(x)}$ a přičtením (odečtením) zbytku ${\displaystyle x^{9}+x^{4}+x^{2}}$ neboli [ 1 0 0 0 0 1 0 1 0 0 ] k ${\displaystyle x^{10}M(x).}$ Přidáním ke zprávě tak dostáváme přenášené kódové slovo [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0 ].

Předpokládejme, že dva bity byly poškozeny v průběhu přenosu, takže přijaté slovo je [ 1 0 0 1 1 1 0 0 0 1 1 0 1 0 0 ]. Jakožto polynom tedy:

${\displaystyle R(x)=C(x)+x^{13}+x^{5}=x^{14}+x^{11}+x^{10}+x^{9}+x^{5}+x^{4}+x^{2}}$

Abychom chyby opravili, spočteme nejprve syndromy. Přitom ${\displaystyle \alpha =0010,}$ dostaneme ${\displaystyle s_{1}=R(\alpha ^{1})=1011,}$ ${\displaystyle s_{2}=1001,}$ ${\displaystyle s_{3}=1011,}$ ${\displaystyle s_{4}=1101,}$ ${\displaystyle s_{5}=0001}$ a ${\displaystyle s_{6}=1001.}$ K zápisu bychom mohli používat hexadecimální číslice, ale držme se v tomto úvodním příkladu dvojkové soustavy.

Následně aplikujme Petersonův algoritmus.

${\displaystyle \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}}}$

Protože S_3×3 je singulární, což není překvapením, protože slovo obsahuje pouze dvě chyby. Nyní levý horní roh matice je identický s [S_2×2 C_2×1], což vede k řešení ${\displaystyle \lambda _{2}=1000,}$ ${\displaystyle \lambda _{1}=1011.}$ Výsledný polynom pro lokalizaci chyb je ${\displaystyle \Lambda (x)=1000x^{2}+1011x+0001.}$ Polynom má kořeny ${\displaystyle 0100=\alpha ^{-13}}$ a ${\displaystyle 0111=\alpha ^{-5}.}$ Exponenty ${\displaystyle \alpha }$ 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 0 0 ? 1 1 ? 0 0 1 1 0 1 0 0 ]. Nahradíme nečitelné znaky (např.) nulami, vytvořme polynom potlačující vliv nečitelných znaků ${\displaystyle \Gamma (x)=(\alpha ^{8}x-1)(\alpha ^{11}x-1).}$ Najděme syndromy ${\displaystyle s_{1}=\alpha ^{-7},}$ ${\displaystyle s_{2}=\alpha ^{1},}$ ${\displaystyle s_{3}=\alpha ^{4},}$ ${\displaystyle s_{4}=\alpha ^{2},}$ ${\displaystyle s_{5}=\alpha ^{5}}$ a ${\displaystyle s_{6}=\alpha ^{-7}.}$ (Používáme logaritmické vyjádření, které je vzhledem k isomorfismu GF(2⁴) 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ů ${\displaystyle S(x)=\alpha ^{-7}+\alpha ^{1}x+\alpha ^{4}x^{2}+\alpha ^{2}x^{3}+\alpha ^{5}x^{4}+\alpha ^{-7}x^{5},}$ spočtěme ${\displaystyle 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}.}$

Spusťme rozšířený euklidův algoritmus: ${\displaystyle {\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}}=}$

${\displaystyle {\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}}=}$

${\displaystyle {\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}}=}$

${\displaystyle {\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}}=}$