Opened 8 years ago

Closed 5 years ago

#14973 closed enhancement (wontfix)

New functions for binary linear codes

Reported by: veronica Owned by:
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: coding theory Keywords: binary codes
Cc: ppurka, dimpase Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: u/ppurka/ticket/14973 (Commits, GitHub, GitLab) Commit: 743826b1c73c946be9b8ff4fdb97819879fc07ac
Dependencies: Stopgaps:

Status badges

Description (last modified by ppurka)

The idea of this work is to add some functions to linear_code.py and new decoding algorithms. Theory and algorithms are taken from: I. Marquez-Corbella. A combinatorial Commutative Algebra Approach to Complete Decoding PhD thesis, University of Valladolid, 2013.

Apply to devel/sage: trac_14973-new_decoding_functions.patch

Attachments (2)

coding_theory.patch (15.7 KB) - added by veronica 8 years ago.
New patch with the GDDA decoding algorithm
trac_14973-new_decoding_functions.patch (45.8 KB) - added by veronica 8 years ago.

Download all attachments as: .zip

Change History (33)

comment:1 Changed 8 years ago by ppurka

  • Cc ppurka added

comment:2 Changed 8 years ago by chapoton

one quick comment: you should also add an example for the function insert_nextnew

comment:3 Changed 8 years ago by burcin

This is just a list of short comments, nothing like a comprehensive review. Anybody else looking at this should feel free to test the code and report problems.

Did you run the tests in this file? I get

Running doctests with ID 2013-07-26-10-31-10-4d8b78a5.
Doctesting 1 file.
sage -t devel/sage/sage/coding/linear_code.py
**********************************************************************
File "devel/sage/sage/coding/linear_code.py", line 2996, in sage.coding.linear_code.LinearCode.newton_radius
Failed example:
    H = matrix(GF(2),[[1,0,0,0,1,0,0,0,0,0],[1,0,1,1,0,1,0,0,0,0],[1,1,0,1,0,0,1,0,0,0],
Exception raised:
    Traceback (most recent call last):
      File "/home/burcin/sage/sage-5.11.beta3/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 485, in _run
        compileflags, 1)
      File "<doctest sage.coding.linear_code.LinearCode.newton_radius[0]>", line 1
        H = matrix(GF(Integer(2)),[[Integer(1),Integer(0),Integer(0),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0)],[Integer(1),Integer(0),Integer(1),Integer(1),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0),Integer(0)],[Integer(1),Integer(1),Integer(0),Integer(1),Integer(0),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0)],
                                                                                                                                                                                                                                                                                                                                                                                  ^
    SyntaxError: unexpected EOF while parsing
**********************************************************************
File "devel/sage/sage/coding/linear_code.py", line 2998, in sage.coding.linear_code.LinearCode.newton_radius
Failed example:
    C = LinearCodeFromCheckMatrix(H)
Exception raised:
    Traceback (most recent call last):
      File "/home/burcin/sage/sage-5.11.beta3/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 486, in _run
        self.execute(example, compiled, test.globs)
      File "/home/burcin/sage/sage-5.11.beta3/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 845, in execute
        exec compiled in globs
      File "<doctest sage.coding.linear_code.LinearCode.newton_radius[1]>", line 1, in <module>
        C = LinearCodeFromCheckMatrix(H)
    NameError: name 'H' is not defined
**********************************************************************
File "devel/sage/sage/coding/linear_code.py", line 3000, in sage.coding.linear_code.LinearCode.newton_radius
Failed example:
    C.newton_radius(t)
Exception raised:
    Traceback (most recent call last):
      File "/home/burcin/sage/sage-5.11.beta3/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 486, in _run
        self.execute(example, compiled, test.globs)
      File "/home/burcin/sage/sage-5.11.beta3/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 845, in execute
        exec compiled in globs
      File "<doctest sage.coding.linear_code.LinearCode.newton_radius[3]>", line 1, in <module>
        C.newton_radius(t)
    NameError: name 'C' is not defined
**********************************************************************
1 item had failures:
   3 of   5 in sage.coding.linear_code.LinearCode.newton_radius
    [374 tests, 3 failures, 5.76 s]
----------------------------------------------------------------------
sage -t devel/sage/sage/coding/linear_code.py  # 3 doctests failed
----------------------------------------------------------------------
Total time for all tests: 5.9 seconds
    cpu time: 4.4 seconds
    cumulative wall time: 5.8 seconds

After fixing that problem, I still have:

Running doctests with ID 2013-07-26-10-31-50-0e819b57.
Doctesting 1 file.
sage -t devel/sage/sage/coding/linear_code.py
**********************************************************************
File "devel/sage/sage/coding/linear_code.py", line 2999, in sage.coding.linear_code.LinearCode.newton_radius
Failed example:
    C.newton_radius(t)
Exception raised:
    Traceback (most recent call last):
      File "/home/burcin/sage/sage-5.11.beta3/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 486, in _run
        self.execute(example, compiled, test.globs)
      File "/home/burcin/sage/sage-5.11.beta3/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 845, in execute
        exec compiled in globs
      File "<doctest sage.coding.linear_code.LinearCode.newton_radius[3]>", line 1, in <module>
        C.newton_radius(t)
    TypeError: newton_radius() takes exactly 1 argument (2 given)
**********************************************************************
1 item had failures:
   1 of   5 in sage.coding.linear_code.LinearCode.newton_radius
    [374 tests, 1 failure, 4.69 s]
----------------------------------------------------------------------
sage -t devel/sage/sage/coding/linear_code.py  # 1 doctest failed
----------------------------------------------------------------------
Total time for all tests: 4.9 seconds
    cpu time: 4.3 seconds
    cumulative wall time: 4.7 seconds

Please document and test __insert_nextnew() as well. All new functions introduced in a patch should be tested.

You should rename covering_rad() to covering_radius().

The documentation needs a spell check. Did you try building the documentation? I'm not sure if all of it is formatted properly.

The output of weight_distribution_coset() and groebner_representation() should be immutable, i.e., a tuple instead of a list. It might be better to reconsider the format of groebner_representation() altogether. A list of lists is not very mathematical. There are quite a few possibilities in Sage to represent various mathematical structures.

Please run your code through a pep8 checker: https://pypi.python.org/pypi/pep8

In Python, you don't need to write CC[len(CC) - 1] to get the last element of a list. You can just say CC[-1].

It seems that all your examples/tests use the same code. Can you add different examples which stress the code properly, covering corner cases, etc.?

comment:4 Changed 8 years ago by mmarco

Burcin, which structure would you consider appropriate for representing the groebner representation? Maybe a dictionary?

comment:5 Changed 8 years ago by mmarco

Are you sure you uploaded the last version of your patch? The version insert_nextnew does not have any doctest. And the function covering_rad should be merged with the existing covering_radius, providing an option to choose between the preexisting algorithm, and the one you implemented.

comment:6 Changed 8 years ago by veronica

Here goes the real patch:

-Right tests (Doctests already run)

-_insert_nextnew() documented and tested

-The functions covering_rad() was merged with covering_radius(), this function was already implemented but required optional GAP package guava. Now you can indicate which method use. Algorithm = "guava" does the same that the old covering_radius() using guava. And Algorithm = None is my implemented function.

-The output of weight_distribution_coset() is now a tuple.

About making output of groebner_representation() immutable: This function has been implemented because in next step I'm going to use it for a decoding algorithm. And actually it's going to be more convenient to change the output to a dictionary, though.

I'll document more examples. I'm testing coset_leaders() to determinate how big can be the length and dimension of the code before the algorithm gets slow.

comment:7 Changed 8 years ago by burcin

With coding_theory.2.patch:

Running doctests with ID 2013-07-28-09-33-28-48923423.
Doctesting 1 file.
Traceback (most recent call last):
  File "/home/burcin/sage/sage-5.11.beta3/local/bin/sage-runtests", line 87, in <module>
    err = DC.run()
  File "/home/burcin/sage/sage-5.11.beta3/local/lib/python2.7/site-packages/sage/doctest/control.py", line 891, in run
    self.run_doctests()
  File "/home/burcin/sage/sage-5.11.beta3/local/lib/python2.7/site-packages/sage/doctest/control.py", line 661, in run_doctests
    self.dispatcher = DocTestDispatcher(self)
  File "/home/burcin/sage/sage-5.11.beta3/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 1339, in __init__
    init_sage()
  File "/home/burcin/sage/sage-5.11.beta3/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 93, in init_sage
    import sage.all_cmdline
  File "/home/burcin/sage/sage-5.11.beta3/local/lib/python2.7/site-packages/sage/all_cmdline.py", line 18, in <module>
    from sage.all import *
  File "/home/burcin/sage/sage-5.11.beta3/local/lib/python2.7/site-packages/sage/all.py", line 124, in <module>
    from sage.coding.all     import *
  File "/home/burcin/sage/sage-5.11.beta3/local/lib/python2.7/site-packages/sage/coding/__init__.py", line 1, in <module>
    import all
  File "/home/burcin/sage/sage-5.11.beta3/local/lib/python2.7/site-packages/sage/coding/all.py", line 1, in <module>
    from ag_code import ag_code
  File "/home/burcin/sage/sage-5.11.beta3/local/lib/python2.7/site-packages/sage/coding/ag_code.py", line 20, in <module>
    import linear_code
  File "/home/burcin/sage/sage-5.11.beta3/local/lib/python2.7/site-packages/sage/coding/linear_code.py", line 1266
    F = self.base_ring()
    ^
IndentationError: expected an indented block

After fixing this, all tests pass.

comment:8 follow-up: Changed 8 years ago by ppurka

Some comments:

  1. The indentation error is not only in the line F = self.base_ring(). All of the existing code in the covering_radius method needs to be indented.
  2. The @rename_keyword should not be introduced at all in the covering_radius code. This is a new keyword to the covering radius method and so you can simply introduce it without any deprecation warnings.
  3. Is all of your code only for linear codes over GF(2)? Then you need to check the inputs to make sure that if other parents are input then it either degrades gracefully and automatically to an older algorithm (for instance in covering_radius), or it gives an error.
  4. Do you have plans to use values of order other than degrevlex?

In fact, I don't understand why ETuple is being used. The only place I am finding it really being used is in comparing of two lists (the compare_tuples_degrevlex function). I raise this point because quite a bit of time would be spent in simply converting vectors to lists and then the lists to ETuples. Later on, you also need the ETuples to be converted back to vectors in the grobner_representation function. If there is a more direct way of doing the comparison you are doing (without all these conversions to ETuple and back), then that should speed up the computations a bit.

comment:9 in reply to: ↑ 8 Changed 8 years ago by veronica

Replying to ppurka:

Some comments:

Thanks for your comments!!

  1. The indentation error is not only in the line F = self.base_ring(). All of the existing code in the covering_radius method needs to be indented.

Yes, it got moved after I runned the tests, I guess. I just fixed it.

  1. The @rename_keyword should not be introduced at all in the covering_radius code. This is a new keyword to the covering radius method and so you can simply introduce it without any deprecation warnings.

Ok I got it. Also fixed

  1. Is all of your code only for linear codes over GF(2)? Then you need to check the inputs to make sure that if other parents are input then it either degrades gracefully and automatically to an older algorithm (for instance in covering_radius), or it gives an error.

So far it is only for linear codes over GF(2). I'll do the check in every function.

  1. Do you have plans to use values of order other than degrevlex?

degrevlex in most of the cases reduce the number of operations to compute the grobner_basis. Even that I'd like to leave it as option to the user, but maybe I should do this only for the function groebner_basis()(still at work) In other cases like grobner_representation() and coset_leaders() I should use only degrevlex.

In fact, I don't understand why ETuple is being used. The only place I am finding it really being used is in comparing of two lists (the compare_tuples_degrevlex function). I raise this point because quite a bit of time would be spent in simply converting vectors to lists and then the lists to ETuples. Later on, you also need the ETuples to be converted back to vectors in the grobner_representation function. If there is a more direct way of doing the comparison you are doing (without all these conversions to ETuple and back), then that should speed up the computations a bit.

You're right Actually the set of coset leaders it doesn't depend on the order, so at least for this function I'm doing the implementation without using ETuple. I also think that should speed up the computations.

grobner_representation() is going to be used in one of the decoding algorithm, so maybe I can also only use degrevlex, I'll discuss it with my mentors.

comment:10 Changed 8 years ago by imarquez

I will just add some comments about the last question: as Veronica already mentioned, for the decoding algorithm that Veronica is implementing (whose code will be public in the following days), the term ordering is important.

Note that for those cosets for which more than one coset leader exists the degree compatible ordering chosen will play an important role.

However, in general I will suggest to leave as default the "degrevlex" ordering for several reasons related to the preprocessing of the mentioned decoding algorithm.

Changed 8 years ago by veronica

New patch with the GDDA decoding algorithm

comment:11 Changed 8 years ago by veronica

Here is the patch with the last details fixed. And I added the GDDA algorithm. This algorithm with Hamming Codes and Random linear codes seems to be faster. For example I have tested(among others):

sage: C = HammingCode(5,GF(2))                                                                                                                                
sage: v = random_vector(GF(2),C.length())  
sage: v                                                                                                                                                       
(1,1,0,1,0,1,0,0,0,0,1,0,1,0,1,0,0,1,1,1,0,1,1,0,0,0,1,1,0,0,1)                                                                                                                      
#using syndrome algorithm
sage: %time C.decode(v)                                                                                                                                       
CPU times: user 847.37 s, sys: 4.45 s, total: 851.82 s                                                                                                        
Wall time: 868.36 s                                                                                                                                           
(1,1,0,0,0,1,0,0,0,0,1,0,1,0,1,0,0,1,1,1,0,1,1,0,0,0,1,1,0,0,1)          

#using nearest neighbor algorithm
sage: %time C.decode(v,"nearest neighbor")                                                                                                                    
CPU times: user 879.19 s, sys: 1.61 s, total: 880.80 s                                                                                                        
Wall time: 880.80 s                                                                                                                                           
(1,1,0,0,0,1,0,0,0,0,1,0,1,0,1,0,0,1,1,1,0,1,1,0,0,0,1,1,0,0,1)        

#using guava algorithm       
sage: %time C.decode(v,"guava")                                                                                                                               
CPU times: user 0.07 s, sys: 0.02 s, total: 0.08 s                                                                                                            
Wall time: 1.00 s                                                                                                                                             
(1,1,0,0,0,1,0,0,0,0,1,0,1,0,1,0,0,1,1,1,0,1,1,0,0,0,1,1,0,0,1)                                                  

#using GDDA algorithm (first time compute grobner representation)
sage: %time C.decode_gdda(v)                                                                                                                                  
CPU times: user 0.73 s, sys: 0.06 s, total: 0.78 s                                                                                                            
Wall time: 0.84 s                                                                                                                                             
(1,1,0,0,0,1,0,0,0,0,1,0,1,0,1,0,0,1,1,1,0,1,1,0,0,0,1,1,0,0,1)    

#using GDDA algorithm (with grobner representation computed)                                                             
sage: %time C.decode_gdda(v)                                                                                                                                  
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s                                                                                                            
Wall time: 0.00 s                                                                                                                                             
(1,1,0,0,0,1,0,0,0,0,1,0,1,0,1,0,0,1,1,1,0,1,1,0,0,0,1,1,0,0,1)            


I've been suggeste to use timeit instead of time for benchmarking, so that's next. But with this results of time we can appreciate the differences among the differents decoding algorithms

comment:12 Changed 8 years ago by veronica

The next patch is presented as result of a GSoC project 2013.

The work contains implementation of new decoding algorithms for linear codes proposed in "Combinatorial Commutative Algebra Approach to Complete Decoding", PhD Thesis, University of Valladolid, 2013 by Irene Marquez-Corbella. Algorithms are called "groebner representation" and "groebner basis" and has been added to sage.coding.decoder.py This algorithms has been hooked up with the decode function in sage.coding.linear_code.py, adding also a block of tests in which is explained the cases where this new algorithms performs better.

The patch contains functions added to sage.coding.linear_code.py such as coset_leaders, error_correcting_capacity, newton_radius, weight_distribution_coset, and new algorithm to covering_radius.

comment:13 Changed 8 years ago by ppurka

  • Description modified (diff)
  • Status changed from new to needs_review

Patchbot apply trac_14973-new_decoding_functions.patch

comment:14 Changed 8 years ago by ppurka

Hmm.. I didn't notice these two issues before:

  1. The syndrome() function is (strangely) duplicated in decoder.py
  1. At some point during the GSOC, we made the output of groebner_basis_singular a list, to make the output similar to the output of the other groebner_basis_fglm function (which was probably named differently). Now, I feel that the generator itself should be returned, i.e., the return statement should be return I.groebner_basis('libsingular:stdfglm') because the output of this function is used sequentially, and used only once. Consequently, all the doctests should be changed to list(groebner_basis_singular..).

Changed 8 years ago by veronica

comment:15 Changed 8 years ago by veronica

I just changed the patch.

  • The syndrome function duplicated has been deleted.
  • groebner_basis_fglm function output is now a generator iterable object.

comment:16 Changed 8 years ago by ppurka

  • Cc dimpase added

comment:17 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:18 Changed 7 years ago by chapoton

  • Status changed from needs_review to needs_work

This needs to be turned into a git branch (and rebased)

comment:19 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:20 Changed 7 years ago by defeo

  • Branch set to u/defeo/ticket/14973
  • Created changed from 07/26/13 03:56:47 to 07/26/13 03:56:47
  • Modified changed from 05/06/14 15:20:58 to 05/06/14 15:20:58

comment:21 Changed 7 years ago by defeo

  • Commit set to d21956ca00caf389801f84ecadc15059e1fb4f8e
  • Status changed from needs_work to needs_review

Gitified, doctested and fixed some minor problems. sage/coding/decoder didn't use to show up in the reference manual, I added it to the "Coding theory" section and fixed some docstring bugs.

There where conflicts while importing the mercurial patches. It'd be better if the original author could check the merge was done right.


New commits:

bbbdf5aAdd new decoding algorithms for linear codes.
fba788bFixed deprecation warnings
d21956cExpose sage/coding/decoder in the ref manual, and doc fixes

comment:22 Changed 7 years ago by ppurka

  • Status changed from needs_review to needs_work
  • Work issues set to resolve merge conflict with 6.3b1

I am working on resolving the (seems trivial) conflict with 6.3beta1.

comment:23 Changed 7 years ago by ppurka

  • Status changed from needs_work to needs_review

I added some commits to fix the merge conflicts and also clean up a bit.

Your changes looked ok to me except for just one change that was not present. You can look at the changes that you made and compare with the changes in the hg patch attached to this ticket, like so.

$ git diff develop d02a468  > coding.patch # alternatively, you can use your HEAD: d21956c
$ <some visual diff tool> coding.patch  trac_14973-new_decoding_functions.patch

I used gvimdiff as the visual diff tool. There are many available like meld, kdiff3, etc.

Last edited 7 years ago by ppurka (previous) (diff)

comment:24 Changed 7 years ago by ppurka

  • Branch changed from u/defeo/ticket/14973 to u/ppurka/ticket/14973

comment:25 Changed 7 years ago by ppurka

  • Commit changed from d21956ca00caf389801f84ecadc15059e1fb4f8e to b1850ba30e81c0772974187818c1c50b6e06d72c
  • Work issues resolve merge conflict with 6.3b1 deleted

New commits:

d02a468merge develop on to #14973; resolved merge conflicts
9f31603fix docstrings in decoder.py
32d9c4ffix some docstrings in linear_code.py
bf4094dremove deprecation message about method to algorithm from sage/coding
eba4566one more merge conflict that was missed
b1850bagroebner -> Groebner

comment:26 Changed 7 years ago by git

  • Commit changed from b1850ba30e81c0772974187818c1c50b6e06d72c to 743826b1c73c946be9b8ff4fdb97819879fc07ac

Branch pushed to git repo; I updated commit sha1. New commits:

743826bfix some documentation build problems

comment:27 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:28 Changed 7 years ago by chapoton

  • Status changed from needs_review to needs_work

needs rebase

comment:29 Changed 5 years ago by jsrn

  • Milestone changed from sage-6.4 to sage-duplicate/invalid/wontfix

See #21339 which is a re-adaptation of this ticket.

comment:30 Changed 5 years ago by jsrn

  • Status changed from needs_work to positive_review

comment:31 Changed 5 years ago by embray

  • Resolution set to wontfix
  • Status changed from positive_review to closed

Determined to be invalid/duplicate/wontfix (closing as "wontfix" as a catch-all resolution).

Note: See TracTickets for help on using tickets.