Algoritmul de decodare al lui Patterson pentru codurile Goppa

Din această pagină Wiki: dat un cod Goppa $\Gamma(g, L)$ și un cuvânt binar $v=(v_0,...,v_{n-1})$, sindromul său este definit ca $$s(x)=\sum_{i=0}^{n-1}\frac{v_i}{x-L_i} \mod g(x).$$ Pentru a corecta erorile, algoritmul lui Patterson merge după cum urmează:

• calculati $$v(x)=\sqrt{s(x)^{-1}-x}\mod g(x)$$ (acest lucru presupune că $s(x)\ne 0$, ceea ce este întotdeauna cazul, cu excepția cazului în care $v$ aparține lui $\Gamma(g,L)$ și nu este necesară nicio corecție).

• Utilizați EEA pentru a obține polinoamele $a(x)$ și $b(x)$ astfel încât $$ a(x)=b(x)v(x)\mod g(x)$$

• Calculați polinomul $p(x)=a(x)+xb(x)^2$. Presupunând că cuvântul original este decodabil, acesta ar trebui să fie același cu cel factorizat localizator de erori polinom $$\sigma(x)=\prod_{i\in B}(x-L_i) $$ Unde $B=\{i \text{ s.t. } e_i\ne 0\}$.

• Presupunând că cuvântul original este decodabil (adică $|B|<d$ Unde $d$ este distanța minimă a codului), pur și simplu calculăm rădăcini ale $\sigma(x)$: dacă $L_i$ este o rădăcină, apoi o eroare așa cum a apărut în cel $i$-a poziție.

Am o singură întrebare: cum arătăm că polinomul $p(x)$ obtinut in a treia etapa corespunde exact cu $\sigma(x)$ asa cum este definit mai sus?

Mai întâi rețineți că $$\frac{\sigma'(x)}{\sigma(x)}=\sum_{i\in B}\frac 1{x-L_i}$$ si asta daca scriem $C$ pentru pozițiile de biți ale unui cuvânt de cod, codul Goppa este definit de $$\sum_{i\in C}\frac 1{x-L_i}\equiv 0\pmod{g(x)}$$ astfel încât $$\frac{\sigma'(x)}{\sigma(x)}\equiv\sum_{i\in B\ominus C}\frac 1{x-L_i}\pmod{g(x)}$$ iar partea dreaptă este doar $s(x)$.

Ne-am despărțit $\sigma(x)$ în monomii de grade par și impar, astfel încât să putem găsi polinoame $\sigma_{impar}$ și$\sigma_{pari}$ astfel încât $$\sigma(x)=x\sigma_{impar}(x^2)+\sigma_{par}(x^2). \qquad (1)$$ Deoarece ne aflăm într-un câmp cu o caracteristică 2, polinoamele cu termeni doar pătrați sunt pătrate ale altor polinoame de grad cel mult $(\deg g-1)/2$ și ne propunem să ne redresăm $a(x)$ și $b(x)$ satisfăcând acest grad legat astfel încât $a(x)^2=\sigma_{even}(x^2)$ și $b(x)^2=\sigma_{impar}$.

Diferențierea (1) dă $$\sigma'(x)=\sigma_{impar}(x^2)$$ Așadar $$\frac{\sigma(x)}{\sigma'(x)}=x+\frac{\sigma_{par}(x^2)}{\sigma_{impar}(x^2)}$$ care ne spune că $$\frac1{s(x)}-x\equiv \frac{\sigma_{par}(x^2)}{\sigma_{impar}(x^2)}\pmod{g(x)}.$ $ Astfel polinomul $v(x)$ este echivalentă cu funcția rațională $a(x)/b(x)$ pe care îl căutăm modulo $g(x)$. Algoritmul euclidian extins va returna două polinoame astfel încât $$\frac{c(x)}{d(x)}\equiv v(x)\pmod{g(x)}$$ cu $\deg c$ și $\deg d$ ambele mai putin de $(\grade g)/2$ iar aceste polinoame trebuie să fie egale cu cele căutate $a(x)$ și $b(x)$ in caz contrar $a(x)d(x)-b(x)c(x)$ este un polinom de grad mai mic decât $d$ și divizibil cu $g(x)$. Revenit $a(x)$ și $b(x)$ acum putem construi $\sigma(x)=a(x)^2+xb(x)^2$ care este definiţia $p(x)$ care este de obicei dat.