Verze z 4. 1. 2013, 23:42 editovat Hippo.69 (diskuse \| příspěvky) 220 editací m Interpunkce na konci <math>. ← Přejít na předchozí porovnání		Verze z 5. 1. 2013, 14:39 editovat zrušit editaci Hippo.69 (diskuse \| příspěvky) 220 editací Oprava znaménka ve Forney vzorci, vysvětlení Forney vzorce kompatibilní s následným použitím, interpunkce kolem matematiky. Přejít na další porovnání →
Řádek 150: \begin{bmatrix} 0 \\ 0 \\ \vdots \\ 0 \end{bmatrix}. </math> Řádek 159: \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 Řádek 192: 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 Řádek 207: 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. Řádek 219: 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▼ ▲takové, aby pro každé <math>j</math> od <math>c</math> do <math>c+d-2-v</math> :<math> \sum_{i=0}^v \lambda_i s_{j+v-i} = 0.</math> Navíc požadujeme <math>\lambda_0 = 1.</math> Řádek 313 ⟶ 311: 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 ~~Pak~~ :<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 ==== Řádek 333 ⟶ 332: 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~~Vztah <math>\sum_{i=0}^v s_{v-i+j}\lambda_i=0</math> ~~při~~jsme ~~výpočtu~~již ~~<math>\lambda_i~~odvodili dříve,~~</math>~~ 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} {1-(x\alpha^{i_j})^{d-1}-1\over 1-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} {1-(x\alpha^{i_j})^{d-1}-1\over 1-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} (1-(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ůžene 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 Lagrange interpolace) suma degeneruje na jediný sčítanec :<math>\Omega(\alpha^{-i_k})=~~e_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í

BCH kód: Porovnání verzí