BCH kód: Porovnání verzí
Smazaný obsah Přidaný obsah
m místo algoritmus Forney použito označení Forneyův vzorec, +drobné opravy v formalizaci |
m Forney algoritmus/vzorec ve zbytku textu |
||
Řádek 307:
:…
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>.
Řádek 322:
:<math>e_k={\Omega(\alpha^{-i_k})\over \Lambda'(\alpha^{-i_k})}</math>.
=== Zdůvodnění
Algoritmus je založen na [[Lagrangeova_interpolace|Lagrangeově interpolaci]] a technikách [[vytvořující funkce (posloupnost)|vytvořujících funkcí]].
Řádek 330:
Pak <math>S(x)\Lambda(x)=\sum_{j=0}^{\infty}\sum_{i=0}^j s_{j-i+c}\lambda_i x^j</math>.
Již jsme použili <math>\sum_{i=0}^v s_{v-i+j}\lambda_i</math> při výpočtu <math>\lambda_i</math>,
takže víme, že koeficienty u <math>x^j</math> jsou 0 pro <math>v\le j
Zkoumejme dál význam jednotlivých koeficientů:
:<math>S(x)=\sum_{i=0}^{
:<math>S(x)\Lambda(x)=S(x)\prod_{\ell=1}^t (\alpha^{i_\ell}x-1)=\sum_{j=1}^t e_j\alpha^{c\,i_j} {1-(x\alpha^{i_j})^{
Můžeme získat následující formu polynomu :
:<math>S(x)\Lambda(x)=\sum_{j=1}^t e_j\alpha^{c\,i_j} (1-(x\alpha^{i_j})^{
Chceme spočítat neznámé <math>e_j</math>, a můžene zjednodušit kontext odstraněním <math>(x\alpha^{i_j})^{
To vede k definici polynomu vyhodnocujícího chyby
:<math>\Omega(x) = S(x)\,\Lambda(x) \pmod{x^{
:<math>\Omega(x) = \sum_{j=1}^t e_j\alpha^{c\,i_j} \prod_{\ell\in\{1,\dots,t\}\setminus\{j\}} (\alpha^{i_\ell}x-1)</math>
Řádek 371:
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ěmě syndromy.
Tak jak jsme si popsali u
Spustíme rozšířený 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>.
Řádek 378:
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
=== Zdůvodnění nejen dekódování založeném na rozšířeném Euklidově algoritmu ===
Řádek 395:
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
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
=== Příklad dekódování ===
| |||