domingo, 1 de septiembre de 2013

GSoC Aug 26th - 31th

For this week the work was to implement a fglm alternative algorithm for computing grobner basis of the ideal associated to a linear code over a finite field. So far I had worked only with the binary case.

It's well known that the problem of complete decoding for a linear code is a NP-hard computational, so for codes of long length or over finite fields with big cardinality the time for decoding is big.(grows exponentially)
Still I'm working in the optimization of the code to reduce as much as possible the time of decoding.
One problem I'm facing is how to generate (in the wisest way) all vectors over the finite field of given weight and certain length. Permutations and combinations in general are operations that take long times plus the fact that the number of vectors grows exponentially with the length of the code.

Here the code. Still missing documentation and details for presentation:  Code
Here an example:

sage: C = RandomLinearCode(6,3,GF(4,'a'))
sage: v = random_vector(GF(4,'a'),C.length())
sage: v
(0, a, a, a + 1, a, a + 1)

#time it takes with syndrome algorithm vs fglm algorithm
sage: %timeit C.decode(v)  #syndrome algorithm
1000 loops, best of 3: 709 us per loop

sage: %timeit C.decode_fq(v) #using my implemented fglm
1 loops, best of 3: 609 ms per loop

#solutions of syndrome and fglm algorithm are different
sage: d = C.decode(v)
sage: d
(0, 1, 0, a + 1, a, a + 1)

sage: d1 = C.decode_fq(v)
sage: d1
(0, 1, a + 1, a + 1, a + 1, a + 1)

#check that both d and d1 belong to the same coset
sage: y1 = v-d
sage: y2 = v-d1
sage: H = C.check_mat()
sage: H*y1
(0, a + 1, a)
sage: H*y2
(0, a + 1, a)

No hay comentarios:

Publicar un comentario