sábado, 21 de septiembre de 2013

GSoC 15th - 21th september

Week for documentation.
Decoding functions for linear codes were changed to decoder.py in sage.coding
Method 'decode' from linear_code.py was modified so now the new decoding algorithms are supported.
Examples and documentation were added to each function.

https://bitbucket.org/vsuaste/coding-theory/commits/21fdf54936c34a51434ae8c93af9a708987c8820
https://bitbucket.org/vsuaste/coding-theory/commits/b710a5169e67221344f11956c0226d1a1fc97bd7

https://bitbucket.org/vsuaste/coding-theory/commits/827bf6bdb252a5771129c62d96a5668bf4a90d18
https://bitbucket.org/vsuaste/coding-theory/commits/f714bc2d14a18c02d80a3add36742d39a2d6fa30

Also I'm still working in a function that it could be added. This is about minimal support words of the code. Here some explanation: Theory

....Getting ready the final patch with alphabetical ordered functions.

GSoC 9th - 14th September

For this week the work was to implement the generalized function for computing the coset leaders
of the code. Now works with codes over any finite field.
With this function now covering_radius and newton_radius works for any finite field
as well.
Considering that for computing covering_radius is only needed one coset leader of each coset, I have added a parameter to coset leaders function which controls if  it has to compute all coset leaders or computes only one coset leader for each coset.
Here is the code already documented: Code

And here some examples: theory, examples 

domingo, 8 de septiembre de 2013

GSoC 1st - 8th September

This week a new optimization for the FGLM adapted algorithm has been added.
As expected, this new algoritm is faster for computing the grobner basis of the ideal associated to the linear code in the way we need it for the decoding algorithm.
Here is part of the comparisson of the groebner basis computation.

sage: C = RandomLinearCode(9,3,GF(4,'a'))                                                                                                                    
sage: I = C.create_ideal()                                                                                                                                   
sage: %time gB = I.groebner_basis('libsingular:stdfglm')                                                                                                     
CPU times: user 370.84 s, sys: 2.36 s, total: 373.19 s                                                                                                       
Wall time: 375.74 s                                                                                                                                       
sage: %time gb=C.groebner_basis_fglm()  #FGLM adapted algorithm                                                                                                                           
CPU times: user 16.36 s, sys: 0.10 s, total: 16.45 s                                                                                                         
Wall time: 16.78 s                                                                                                                                           
   
sage: C = RandomLinearCode(10,3,GF(5))
sage: %time gb = C.groebner_basis_fglm()#FGLM adapted algorithm
CPU times: user 581.37 s, sys: 2.21 s, total: 583.58 s
Wall time: 590.37 s
sage: I = C.create_ideal()
sage: %time gB = I.groebner_basis()
CPU times: user 1331.38 s, sys: 1.14 s, total: 1332.53 s
Wall time: 1336.74 s

In order to make this comparisson was necessary implement the function for creating the ideal associated to the code.  Code

Documentation of the FGLM adapted algorithm for linear codes over finite field in the general case and all other functions, including the new decoding algorithm has been documented a tested. The link to the repository:
https://bitbucket.org/vsuaste/coding-theory/commits/e3dc1a07f7d304700053981596493646ca06428f

Here some examples in which the new decoding algorithm is faster than syndrome decoding of sage:
sage: C = HammingCode(2,GF(7))
sage: C
Linear code of length 8, dimension 6 over Finite Field of size 7
sage: v = random_vector(GF(7),C.length())
sage: %time C.decode(v)    #syndrome algorithm
CPU times: user 2.10 s, sys: 0.03 s, total: 2.13 s
Wall time: 2.19 s
(0, 4, 5, 4, 1, 2, 5, 4)
sage: %time C.decode_fq(v)  #new decoding algorithm
CPU times: user 0.81 s, sys: 0.02 s, total: 0.83 s
Wall time: 0.87 s
(0, 5, 5, 1, 4, 1, 4, 6)

sage: C = HammingCode(2,GF(11))
sage: v = random_vector(GF(11), C.length())
sage: v
(0, 10, 0, 8, 10, 0, 2, 5, 2, 10, 10, 4)
sage: %time C.decode_fq(v) # new decoding algorithm
CPU times: user 53.32 s, sys: 1.45 s, total: 54.76 s
Wall time: 56.19 s
(0, 1, 0, 10, 8, 0, 0, 2, 3, 8, 8, 5)
sage: %time C.decode(v) ###syndrome algorithm still running after hours.....

sage: C = HammingCode(3,GF(4,'a'))
sage: v = random_vector(GF(4,'a'),C.length())
sage: v
(a + 1, a + 1, 0, a + 1, 0, 1, a + 1, a + 1, a + 1, a + 1, 0, 1, a, 1, a, 0, a + 1, 0, a, a + 1, 0)
sage: %time C.decode_fq(v) #new decoding algorithm
CPU times: user 81.18 s, sys: 1.36 s, total: 82.55 s
Wall time: 84.30 s
(0, 0, 0, a + 1, 0, 1, 0, 0, 0, 0, 0, 0, a, 1, 1, 0, a + 1, 0, a, a + 1, 1)
sage: %time C.decode(v) ###syndrome algorithm still running after hours.....

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)