2
$\begingroup$

From this Wiki page: given a Goppa code $\Gamma(g, L)$ and a binary word $v=(v_0,...,v_{n-1})$, its syndrome is defined as $$s(x)=\sum_{i=0}^{n-1}\frac{v_i}{x-L_i} \mod g(x).$$ To do error correction, Patterson's algorithm goes as follows:

  • Calculate $$v(x)=\sqrt{s(x)^{-1}-x}\mod g(x)$$ (this assumes that $s(x)\ne 0$, which is always the case unless $v$ belongs to $\Gamma(g,L)$ and no correction is required).

  • Use the EEA to obtain the polynomials $a(x)$ and $b(x)$ such that $$ a(x)=b(x)v(x)\mod g(x)$$

  • Calculate the polynomial $p(x)=a(x)+xb(x)^2$. Assuming that the original word is decodable, this should be the same as the factorized error locator polynomial $$\sigma(x)=\prod_{i\in B}(x-L_i) $$ where $B=\{i \text{ s.t. } e_i\ne 0\}$.

  • Assuming that the original word is decodable (that is, $|B|<d$ where $d$ is the minimum distance of the code), we simply calculate the roots of $\sigma(x)$: if $L_i$ is a root, then an error as occurred in the $i$-th position.

I only have one question: how do we show that the polynomial $p(x)$ obtained in the third step corresponds exactly to $\sigma(x)$ as defined above?

$\endgroup$

1 Answer 1

4
$\begingroup$

First note that $$\frac{\sigma'(x)}{\sigma(x)}=\sum_{i\in B}\frac 1{x-L_i}$$ and that if we write $C$ for the bit positions of a codeword, the Goppa code is defined by $$\sum_{i\in C}\frac 1{x-L_i}\equiv 0\pmod{g(x)}$$ so that $$\frac{\sigma'(x)}{\sigma(x)}\equiv\sum_{i\in B\ominus C}\frac 1{x-L_i}\pmod{g(x)}$$ and the right hand side is just $s(x)$.

We split $\sigma(x)$ into odd and even degree monomials so that we can find polynomials $\sigma_{odd}$ and$\sigma_{even}$ such that $$\sigma(x)=x\sigma_{odd}(x^2)+\sigma_{even}(x^2). \qquad (1)$$ Because we are in a field of a characteristic 2, polynomials with only square terms are squares of other polynomials of degree at most $(\deg g-1)/2$ and we aim to recover $a(x)$ and $b(x)$ satisfying this degree bound such that $a(x)^2=\sigma_{even}(x^2)$ and $b(x)^2=\sigma_{odd}$.

Differentiating (1) gives $$\sigma'(x)=\sigma_{odd}(x^2)$$ and so $$\frac{\sigma(x)}{\sigma'(x)}=x+\frac{\sigma_{even}(x^2)}{\sigma_{odd}(x^2)}$$ which tells us that $$\frac1{s(x)}-x\equiv \frac{\sigma_{even}(x^2)}{\sigma_{odd}(x^2)}\pmod{g(x)}.$$ Thus the polynomial $v(x)$ is equivalent to the rational function $a(x)/b(x)$ that we seek modulo $g(x)$. The extended Euclidean algorithm will return two polynomials such that $$\frac{c(x)}{d(x)}\equiv v(x)\pmod{g(x)}$$ with $\deg c$ and $\deg d$ both less than $(\deg g)/2$ and these polynomials must be equal to our sought after $a(x)$ and $b(x)$ otherwise $a(x)d(x)-b(x)c(x)$ is a polynomial of degree less than $d$ and divisible by $g(x)$. Having recovered $a(x)$ and $b(x)$ we can now construct $\sigma(x)=a(x)^2+xb(x)^2$ which is the definition of $p(x)$ that is usually given.

$\endgroup$
3
  • $\begingroup$ thanks. you beat me to it. $\endgroup$
    – kodlu
    Jun 3, 2022 at 17:42
  • $\begingroup$ @kodlu Apologies for jumping at this; I just love clever ideas like Patterson's. $\endgroup$
    – Daniel S
    Jun 3, 2022 at 17:47
  • $\begingroup$ no apology needed, I like your contributions... $\endgroup$
    – kodlu
    Jun 3, 2022 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.