BCH kód: Porovnání verzí

a determinant je nulový, dokud není <math>v</math> minimální možné.

 

Algoritmus udržuje &Lambda; odpovídající počátečnímu úseku posloupnosti syndromů.

Postupně prodlužuje délku úseku a koriguje &Lambda;.

že minimalizuje násobení proměnnými na úkor stejného počtu násobení konstantami.

 

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.

:…

 

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

 

:<math>e_k={\Omega(\alpha^{-i_k})\over \Lambda'(\alpha^{-i_k})}</math>.

 

 

Algoritmus je založen na [[Lagrangeova_interpolace|Lagrangeově interpolaci]] a technikách [[vytvořující funkce (posloupnost)|vytvořujících funkcí]].

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

 

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

 

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

 

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

(Tento generátor je použit v [[QR kód|QR kódech]].)

Nemusíme v tomto případě počítat chybové hodnoty, protože jedinou možnou hodnotou je hodnota 1.

 

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

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