Patterson's decoding algorithm for Goppa codes

jp flag

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?

ru flag

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.

kodlu avatar
sa flag
thanks. you beat me to it.
Daniel S avatar
ru flag
@kodlu Apologies for jumping at this; I just love clever ideas like Patterson's.
kodlu avatar
sa flag
no apology needed, I like your contributions...

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.