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