Opened 6 years ago
Closed 5 years ago
#20335 closed enhancement (fixed)
A new structure for BCH codes
Reported by:  dlucas  Owned by:  

Priority:  major  Milestone:  sage7.6 
Component:  coding theory  Keywords:  
Cc:  Merged in:  
Authors:  David Lucas, Julien Lavauzelle  Reviewers:  Daniel Augot 
Report Upstream:  N/A  Work issues:  
Branch:  bf2c3bb (Commits, GitHub, GitLab)  Commit:  bf2c3bbf44824e38c0374026cd8e7536b7b99291 
Dependencies:  #20100, #20908  Stopgaps: 
Description
This ticket proposes a new implementation for BCH codes.
It contains:
 a new code class,
BCHCode
,  a decoder for BCH codes using the underlying GRS code of a BCH code
 an decoder for Cyclic codes using the surrounding BCH code of a Cyclic Code
Change History (39)
comment:1 Changed 6 years ago by
 Branch set to u/dlucas/bch_code
comment:2 Changed 6 years ago by
 Commit set to 1449cb42df209bdbcdd0de14bfaae429b72f376f
 Dependencies set to #20100
 Status changed from new to needs_review
comment:3 Changed 6 years ago by
 Commit changed from 1449cb42df209bdbcdd0de14bfaae429b72f376f to 26dcbac4d661fa3ee3fbe9c1fc21dd67620a9bed
Branch pushed to git repo; I updated commit sha1. New commits:
26dcbac  Updated to latest beta, fixed conflicts, changed dependency

comment:4 Changed 6 years ago by
I updated this ticket to 7.3b1 and fixed conflicts. I also removed the code related to subfield subcodes as the field embedding mechanism is now in a separate ticket.
comment:5 Changed 6 years ago by
There's some new merge conflicts on this ticket. All of them trivial. I would push myself but I'm in the process of making an actis ticket with all our inreview work and I don't have time :(
comment:6 Changed 6 years ago by
Yup, this is a quite old ticket, and I have quite a lot of them to update. I'm compiling 7.4beta0 atm, will fix this one just after.
David
comment:7 Changed 6 years ago by
 Commit changed from 26dcbac4d661fa3ee3fbe9c1fc21dd67620a9bed to 7994411012fac36db9974dd51f4fef938df56067
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
61976d3  cyclic_code.py now uses relative_finite_field_extension.py

6335358  Fixed doctests in code_constructions.py

7366cbe  Enhanced module documentation, class' and global method's documentation

c328827  Removed __ne__ methods

141bb64  Enhanced documentation of various methods in CyclicCode

a210e73  Improved documentation of both encoders

e459f10  Helper methods are now private methods

922e688  Merge branch 'u/dlucas/cyclic_code' of git://trac.sagemath.org/sage into 20100_cyclic_codes

b3c4425  Merge branch 'u/jsrn/cyclic_code' of git://trac.sagemath.org/sage into bch_codes

7994411  Fixed broken doctests

comment:8 Changed 6 years ago by
I fixed merged conflicts, merged with the latest version of #20100 and fixed broken doctests.
Still open for review.
comment:9 Changed 6 years ago by
 Status changed from needs_review to needs_work
does no longer merge cleanly.
comment:10 Changed 6 years ago by
 Branch changed from u/dlucas/bch_code to u/jlavauzelle/bch_code
comment:11 Changed 6 years ago by
 Commit changed from 7994411012fac36db9974dd51f4fef938df56067 to c9f6835ff9d5d3daaac23bba0061f74053804df9
 Milestone changed from sage7.2 to sage7.6
 Status changed from needs_work to needs_review
Hi all,
For our review day, I push a cleaned version on this BCH code ticket. It's been modified according to the cyclic code ticket, I also fixed some merge issues and made doctests pass.
Yet I didn't check David's code in depth so I think it still need a review. Of course I can do that.
Julien
New commits:
b88510f  Fixed conflicts

efc89ec  Updated to latest beta (7.6.beta2).

0e82ba9  Fixed surrounding_bch_code() and BCH constructor. Other minor fixes (doc, imports).

c18043f  Made all doctests pass. Shorter output for BCH codes.

c9f6835  Improved the doc of BCH codes. Cleaned the code.

comment:12 Changed 6 years ago by
In the description of the class, you ask for 0 \le b \leq n
, shouldn't it be 0 \leq b \le n
?
comment:13 Changed 6 years ago by
Proposed test for bch_to_grs
sage: C = codes.BCHCode(GF(2), 15, 3) sage: RS = C.bch_to_grs() sage: C.generator_matrix() * RS.parity_check_matrix().transpose() == 0
The pass is passed on this example.
comment:14 Changed 6 years ago by
Another interesting example or test (an extremal MDS code)
sage: C = codes.BCHCode(GF(16),17,7) sage: C [17, 6] BCH Code over GF(16) with designed distance 7 sage: C.minimum_distance() 12 # Good ! The code is MDS. Let us see if the framework finds the underlying GRS sage: R=C.bch_to_grs() sage: R [17, 11, 7] Generalized ReedSolomon Code over GF(256) sage: C.generator_matrix() * R.parity_check_matrix().transpose() == 0 True
comment:15 Changed 6 years ago by
Another test (which is brilliantly passed)
sage: C = codes.BCHCode(GF(16),15,7) sage: R = C.bch_to_grs() sage: codes.CyclicCode(code=R) == codes.CyclicCode(code=C)
comment:16 Changed 6 years ago by
Now, some corner cases
sage: C = codes.BCHCode(GF(16),15,15) sage: C.dimension() == 1
comment:17 Changed 6 years ago by
Corner case again. After having changing L111 into
if not (designed_distance <= length and designed_distance >= 1):
the following extreme case seems to work
sage: C = codes.BCHCode(GF(16),15,1) sage: C.dimension() sage: C.generator_polynomial() sage: C.defining_set()
but
sage: C.dual_code()
fails, which is a pity, since the other, more complicated calls, succeed.
comment:18 Changed 6 years ago by
 Commit changed from c9f6835ff9d5d3daaac23bba0061f74053804df9 to f7b7280f2699c0b5bc771d6831b29dc94b2b8f9b
Branch pushed to git repo; I updated commit sha1. New commits:
f7b7280  Add tests and fixed minor bugs.

comment:19 Changed 6 years ago by
Hi Daniel,
I pushed your suggestions.
Julien
comment:20 Changed 6 years ago by
 Reviewers set to Daniel Augot
comment:21 Changed 6 years ago by
L221
``designed_distance`` must be between 2 and ``length`` (inclusive),
should be
``designed_distance`` must be between 1 and ``length`` (inclusive)
comment:22 Changed 6 years ago by
 Commit changed from f7b7280f2699c0b5bc771d6831b29dc94b2b8f9b to d4ab8f72f622525cd2edfb9cb74023bf3ddcf558
Branch pushed to git repo; I updated commit sha1. New commits:
d4ab8f7  Fixed doc

comment:23 Changed 6 years ago by
 Commit changed from d4ab8f72f622525cd2edfb9cb74023bf3ddcf558 to 5064ef3d7bd8b6e33c7f27eaf1627d9c585f59fa
Branch pushed to git repo; I updated commit sha1. New commits:
5064ef3  Last fix, I hope

comment:24 Changed 6 years ago by
 Commit changed from 5064ef3d7bd8b6e33c7f27eaf1627d9c585f59fa to 32f9cc08aa000b6c9c1c4d77f3fd67f492ea7d2b
Branch pushed to git repo; I updated commit sha1. New commits:
32f9cc0  Last fix, finally

comment:25 Changed 6 years ago by
All above tests pass, and some of them have been included in the examples. The dual_code()
issue is not from this class.
I set the ticket to positive review.
comment:26 Changed 6 years ago by
 Status changed from needs_review to positive_review
comment:27 Changed 6 years ago by
 Status changed from positive_review to needs_review
Small error L308
comment:28 Changed 6 years ago by
Please merge in #20908 and add as a dependency.
comment:29 Changed 6 years ago by
Ok, anyway we need to test the decoder a bit more.
comment:30 Changed 6 years ago by
 Commit changed from 32f9cc08aa000b6c9c1c4d77f3fd67f492ea7d2b to d48aec7fb761dc71b73650efbd4192166a08db1a
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
8185e87  Updated to latest beta and fixed conflicts

b77de0f  Added new file that introduces the new paritycheck code class. Initializes code class, generator matrix encoder class, straightforward encoder class and minimum distance method.

0b0d2f8  Correcting mistakes. Two errors are still waiting for correction: ParityCheckCodeStraightforwardEncoder.unencode_nocheck and ParityCheckCodeGeneratorMatrixEncoder.__init__

62abcd7  Fixed merge conflict.

1aa4b4e  Fixed doctests. Shorter output. Generator matrix encoder inherits from the generic one. Fixed encoders. Cleaned the code.

19e299e  Merged 21328 and fixed broken doctests

f64841f  Move cyclic code heading

5295039  Merge with #20908

8d476b6  Lazy imports of BCH decoders

d48aec7  Improved decoders and associated doctests for cyclic and BCH codes.

comment:31 Changed 6 years ago by
 Dependencies changed from #20100 to #20100, #20908
comment:32 Changed 6 years ago by
 Commit changed from d48aec7fb761dc71b73650efbd4192166a08db1a to 99234ce72f96874130c8c175177c2dff2bcb1edc
Branch pushed to git repo; I updated commit sha1. New commits:
99234ce  Improved the doc for the underlying GRS code of a BCH code

comment:33 Changed 6 years ago by
Daniel,
I added some documentation on the underlying GRS code. You can tell me if you agree with it.
Julien
comment:34 Changed 6 years ago by
The maths describing the underlying GRS codes are OK. The wording could be improved, for more brevity and clarity.
comment:35 Changed 6 years ago by
 Commit changed from 99234ce72f96874130c8c175177c2dff2bcb1edc to bf2c3bbf44824e38c0374026cd8e7536b7b99291
Branch pushed to git repo; I updated commit sha1. New commits:
bf2c3bb  Made maths cleaner

comment:36 Changed 6 years ago by
OK I did it. Thanks Daniel.
Julien
comment:37 Changed 6 years ago by
The writing and the layout is OK.
comment:38 Changed 6 years ago by
 Status changed from needs_review to positive_review
comment:39 Changed 5 years ago by
 Branch changed from u/jlavauzelle/bch_code to bf2c3bbf44824e38c0374026cd8e7536b7b99291
 Resolution set to fixed
 Status changed from positive_review to closed
I pushed the code, this is now open for review.
Last 10 new commits:
Fixed doctests in code_constructions.py
Changed imports in binary_code.pyx
Merged with #20100 and fixed conflicts
WIP
Merge branch 'develop' into cyclic_code
It is now possible to choose the primitive element to use as a root
Merge branch 'cyclic_code' into bch_code
Changed signature of BCHCode class and deprecated the old BCHCode method
Added decoder for BCH codes
Added decoder for cyclic code