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 

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

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)

GSoC Aug 18th - 25th

For this week I have implemented a new decoding algorithm for binary linear codes using Grobner
Basis of the ideal associated to the code.
In the binary case I have decided to use the FGLM algorithm from singular to compute the Grobner
Basis, this algorithm is very fast.  So first I have to construct the ideal associated to the code.
Then, I create a test-set for the code. And use this one to apply the descent decoding algorithm.
More details about this algorithm :  Theory
The process of computing the grobner basis and the test-set is only executed once, and after that, the decoding process is very fast.(Decoding algorithms with pre-computed information)
I have done some tests to analyze the time it takes with the different decoding algorithms and differents types of binary linear codes:
Results of experiments:  Testing Algorithm

Also I have documented the functions with examples and more. The code of this algorithm and functions is in the commit:
https://bitbucket.org/vsuaste/coding-theory/commits/4d5c8255eaec112b191eb095873eaf09e5708ed4

With this algorithm I finished algorithms for binary codes. So from now, I have started trying to generalize the algorithms for the case of codes over any finite field.
In this case we expect to gain some speed with a new version of FGLM algorithm implemented specificaly for general case of codes.

GSoC Aug 12th -16th

For this week I have fixed some details about documentation:
https://bitbucket.org/vsuaste/coding-theory/commits/6b81bda12ea08dbb5fd11d35f786f240#comment-379372

I have implemented a new function for computing grobner basis for a binary linear Code.
I noticed that my results and the results using package 4ti2 are not the same, and this is because of the order of the variables. 4ti2 consider xn> ... >x0 and the order I use is x0>x1>x2...
In sage you can compute the grobner basis of an ideal, but you can specify the order of the variables. By default it uses x0>x1>x2>...
Fortunately this detail doesn't matter for our purposes(decoding algorithm) as long as the monomial order is a degree order and therefore a weight compatible order.
Here it goes an Example
And code: Code
(Once I finish the documentation for this one I'll uploaded to bitbucket, also the output format will be changed because of the way I'll use it for the decoding algorithm using grobner basis)

GSoC Results of GDDA new decoging algorithm

As part of the evaluation for GSoC project I present the results obtained so far.

I have implemented a new decoding algorithm GDDA (gradient descent decoding algorithm) based on the grobner representation of a code.
The idea of this algorithm is that once computed the grobner representation the decoding step is pretty straight and it doesn't takes time. That's why I save the grobner representation as attribute of the code, so you only have to compute it once.
I also modified the format of the output for grobner_representation method. Now returns a dictionary representing Matphi function instead of a List.

GDDA and Grobner representation code

Here I leave you the comparison I've made of the GDDA  with decoding algorithms already implemented in Sage such as "sydrome", "nearest neighbor" and guava.
The results are very interesting. I've tried with Hamming Codes, Extended Golay Code and random linear codes.
In the case with Hamming Code the GDDA resulted to be faster than "syndrome" ,"nearest neighbor" and "guava "algorithms, even considering the time it takes to compute grobner representation.
In case with random linear code GDDA resulted to be fasted that "syndrome" and "nearest neighbor" again even considering the time it takes to GDDA computing grobner representation.
With Extended Golay Code "syndrome" and "nearest neighbot" resulted to be faster than GDDA.

GDDA Comparison

GSoC Sixth Week (July 20-27)

This week I've been documented and tested the functions I have so far, with the final purpose of opening  the ticket. Which I have done. Here I leave you the link:
http://trac.sagemath.org/ticket/14973

About the function "covering_rad()": I merged it with the existing one "covering_radius()". By parameter "algorithm" you can indicate wich one you want to use. "Algorithm = guava" use the pre existing  method (requires GAP optional packages guava). And "algorithm = None" is my implemented functions which doesn't requires optional packages.
Code

I also changed the subroutine "insert_next" because I ordered the list every time I inserted a new element, I didn't need it. So now every time I insert a new element simply it looks for the right place with respect to the specified order.
Code

GSoC Preparing Ticket

By now I'm preparing the ticket for Sage.
Here I leave you the documentation I have so far. It suppose to be parte of LinearCode class in linear_code.py
Please let me know any comment about the way I do it. I tried to follow what developers guide says but I could be missing something.

Possible Ticket documented

I also leave you the .py file, because in the preview(above) somethings get changed. (for example you can't see the different color in commented lines...)

documentation.py

Note: About the functions I have, all of them receive a degree ordering (instance of TermOrder class).
I'm thinking change it, and instead it could receive a string with the name of the degree ordering, then I create an instance of TermOrder in the function. I think would be much more intuitive.

GSoC Report (Third Week)

This time I implemented a function that given a linear code and a degree ordering it returs the set of coset leaders.
The important thing about this functions is that after we have it, we can calculate parameters of the code almost directly, such as: newton radius, covering radius and weight distribution of the cosets. I implemented them as well.

The algorithm and expalantion goes here : Algorithm

The code of the function goes here: Code

And, I already tested it with some examples in Sage : Examples

Notes: The algorithm for computing coset leaders is almost the same for computing the grobner representation(Second Week) . So the idea is that if the grobner representation is computed, we save the set of the coset leaders as an atribute of the code. In this way we don't have to compute the set of coset leaders every time we want some of the parameters I mentioned before. We only have to do it once.

GSoC Fifth Week (14-19 July)

This week the main goal was to implement the function that given a Binary Linear Code it returns

a reduced Grobner basis. 

We want the Grobner basis to later compute the test-set(see definition in the pdf). This structure is the last thing we'll need to then start programming the new decoding algorithm, which is the main objective of this project. 

Here I attach the explanation of the algorithm and also the way I use the implemented function. With some examples tested in Sage.  Algorithm  

Example tested with Sage

Here is the implementation of the function: Code

So far, I've tried to use what is already implemented in Sage. But one problem I presented with this function is that I need the permutations of one vector with given hamming weight. And I did it using "IntegerVectorsModPermutationGroup" nevertheless this part is very consuming time. And for codes which have a big length is not going to work. So, for the next week I'm planning to find another way of implementing this. At least for the binary case, which I think should be posible with bitwise operations.  

GSoC Second Week (June 24-29)

The work for this week was to implement a function which, given a linear binary code, returns the Groebner representation of itselt. This Groebner representation will after, help us to compute the groebner basis of the ideal asociated to the linear code. You can check the details about this Groebner representation and algorithm here: Algorithm

The process for this function implementation was as follow:
-Understand what it is already implemented about monomial orderings
-Implement sub-functions as insert_next, next_term and member (see pdf above)
-Implement funciton groebner_representation

Code of this funcions: Code

Also, this algorithm has been tested with examples. This work you can see it at cloud sage. My project "Grobner_Project" is public but only my mentors and I can modify it.
After complete this algorithm for computing the Grober basis I'll make the patch.

GSoC First Week (June 14-21)

My project submitted to GSoC has been accepted!

Great start!!
In order to get involved with Sage development the first week of work I had the opportunity to attend Sage Days 48 .
This workshop was very inspiring for me. I meet other sage developers and their work.
I learnt about the different ways to contributing sage and the easiest way to do it.
What I most liked it was the introduction to Sage @ cloud. Here you can find a description of this project and what you can do with it: Sage Cloud

This tool has become esencial in my project.
Advantages I have with Sage cloud:
-multiple open windows (with synchronized files! :) ) So you can test what you just changed in the source code, without being opening and closing windows and files.
-all you can do with a terminal
-share the project with my mentors
-I can work everywhere without needing my laptop.
 In conclusion, so far, it has been very very convenient. And, I'm still discovering and exploring how to take advantage of this awesome tool.

I leave you the link of the presentation by William Stein in case you want(you should) to know more about it.
http://www.youtube.com/watch?v=MZ4gF33cLfQ&feature=youtu.be

Submitting first patch to SAGE

I already got my trac account.  And I just sent the next patch to SAGE for ticket #12532.

trac_12532_transformation_symbolic_vector.patch

SAGE experiment

This time I decided to work with ticket #12532 (an easy one) in order to get envolve with SAGE developer process.  http://trac.sagemath.org/sage_trac/ticket/12532

In the next worksheet you can see how I proceded to understand how plot3d works in SAGE and why it doesn't works in the case the ticket mentions.

worksheet_plot3d.sws

And in the next report you can see what I have modified in the source code to patch it.

report_ticket#12532.pdf

My trac-account is in process.  As soon as I get it I'll try to send the patch.

School projects

Steganography project

In this project I implemented the pixel diference and LSB method for hiding information (image and text) 

steganography.cpp

Game Project

This was my first experience with programming. I implemented a game copying the idea of "bomberman".

game.cpp

Experience as software developer

Here it is part of one project I participed.

In this project the company wanted to make advertising for its clients. So they required a sofware for creating the advertising starting from some statistics about the client's profile.

The code below is the part I contribute to the team involved in this work.

C++/Qt

codeDrawer.cpp

Project description for GSoC 2013

I leave you my proposal for "Implementation of new decoding algorithm" project.

Project Description