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.