Patterson Algorithm

[Panos Phronimos]

Hello,

I am trying to implement Patterson's Algorithm for decoding Goppa codes.

I am stuck in the part that I have to find two polynomials a(x) and b(x) so that a(x)=b(x)R(x)mod(g(x))
where g(x) is the goppa poly and deg(a(x)) must be <= t/2.
I know that i have to use extended Euclidean Algorithm and i have decoded several random examples but
i can't find a general solution for any given equation.

P.S. A paper i advised proposed the following code:
(d,u,v) = xgcd(PR(1),PR(R.list())); #Where PR is a polynomial ring over an extension of GF(2)
a = g*u; b = g*v;
But I don't think is working correctly in the way i implemented it!


Thanks in advance!

[Johan S. H. Rosenkilde]

Hi Panos

The snippet you gave  certainly does not work since it will compute the gcd of 1 and something else, which is - of course - 1.

What you need is to compute the *half gcd* of R and g, i.e. run the Extended Euclidean algorithm about half-way and then stop. The Bezout relation from that iteration will give you what you want:

   u_i * R + v_i * g = r_i

i.e.

   r_i == u_i * R mod g

For Patterson's algorithm, the restriction you need, if I recall correctly, is something like deg r_i > deg u_i. Use this as stopping-criteria for your half-gcd and you should be good.

A half-gcd as described above is already included in Sage for the Gao-decoding algorithm of Reed-Solomon codes. It's implemented in sage/coding/grs.py and called partial_xgcd.

If you're implementation becomes nice, Goppa codes is really something we need in Sage. Consider opening a ticket and feel free to cc me on it.

Good luck,
Best,
Johan

[Panos Phronimos]

Thanks Johan,

I finally implement the decoder using lattice basis reduction (using LLL)
The only thing left is to reduce the execution time of the decoder by finding the most efficient way to locate the errors via the error locator poynomial (something better than chien search)
If you are interesting in Goppa codes there is a module named codinglib at bitbucket witch is very helpful and a really great base.

[Johan S. H. Rosenkilde]

Hi Panos,

> I finally implement the decoder using lattice basis reduction (using LLL)

I presume you mean F[x]-lattice basis reduction, i.e. row reduction of
F[x] matrices (the LLL is for integer matrices).

> The only thing left is to reduce the execution time of the decoder by
> finding the most efficient way to locate the errors via the error locator

> poynomial (something better than chien search).

Look up "multi-point evaluation" for asymptotically fast algorithms.

> If you are interesting in Goppa codes there is a module named codinglib at
> bitbucket witch is very helpful and a really great base.

I know - I'm the author ;-) But thanks.

Best,
Johan

--

[Juan Grados]

Panos,

I had write patterson algorithm here http://juaninf.blogspot.com.br/2013/04/function-make-div-with-id-mycell-sage.html.

--
You received this message because you are subscribed to the Google Groups "sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscribe@googlegroups.com.
To post to this group, send email to sage-s...@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.

--

---------------------------------------------------------------------
MSc. Juan del Carmen Grados Vásquez
Laboratório Nacional de Computação Científica 
Tel: +55 21 97633 3228

(http://www.lncc.br/)
http://juaninf.blogspot.com
---------------------------------------------------------------------