Score:1

# Patterson's decoding algorithm for Goppa codes

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| 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?

Score:2

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.

thanks. you beat me to it.
@kodlu Apologies for jumping at this; I just love clever ideas like Patterson's.
no apology needed, I like your contributions...
I sit in a Tesla and translated this thread with Ai: