BCH code: Difference between revisions

Revision as of 03:02, 15 October 2019

Revision as of 05:33, 15 October 2019

Line 289:

It is based on [[Lagrange polynomial|Lagrange interpolation]] and techniques of [[generating function]]s.

Consider <math>S(x)\Lambda(x),</math> and for the sake of simplicity suppose <math>\lambda_k = 0</math> for <math>k > v,</math> and <math>s_k = 0</math> for <math>k > c + d - 2.</math> Then

:<math>S(x)\Lambda(x) = \sum_{j=0}^{\infty}\sum_{i=0}^j s_{j-i+1}\lambda_i x^j.</math>

:<math>\begin{align}

Line 307:

Thanks to <math>v\leqslant d-1</math> we have

:<math>\Omega(x) = -\lambda_0\sum_{j=1}^v e_j\alpha^{c i_j} \prod_{\ell\in\{1,\cdots,v\}\setminus\{j\}} \left (\alpha^{i_\ell}x - 1 \right ).</math>

Thanks to <math>\Lambda</math> (the Lagrange interpolation trick) the sum degenerates to only one summand for <math>x = \alpha^{-i_k}</math>

:<math>\Omega \left (\alpha^{-i_k} \right ) = -\lambda_0e_klambda_0 e_k\alpha^{c\cdot i_k}\prod_{\ell\in\{1,\cdots,v\}\setminus\{k\}} \left (\alpha^{i_\ell}\alpha^{-i_k} - 1 \right ). </math>

To get <math>e_k</math> we just should get rid of the product. We could compute the product directly from already computed roots <math>\alpha^{-i_j}</math> of <math>\Lambda,</math> but we could use simpler form.

As [[formal derivative]]

:<math>\Lambda'(x) = \lambda_0\sum_{j=1}^v \alpha^{i_j}\prod_{\ell\in\{1,\cdots,v\}\setminus\{j\}} \left (\alpha^{i_\ell}x -1 1\right ),</math>

we get again only one summand in

:<math>\Lambda'\left(\alpha^{-i_k}\right) = \lambda_0\alpha^{i_k}\prod_{\ell\in\{1,\cdots,v\}\setminus\{k\}} \left (\alpha^{i_\ell}\alpha^{-i_k} -1 1\right ).</math>

So finally

:<math>e_k = -\frac{\alpha^{i_k}\Omega \left (\alpha^{-i_k} \right )}{\alpha^{c\cdot i_k}\Lambda' \left (\alpha^{-i_k} \right )}.</math>

This formula is advantageous when one computes the formal derivative of <math>\Lambda</math> form

:<math>\Lambda(x) = \sum_{i=1}^v \lambda_ixlambda_i x^i</math>

yielding: