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