Opened 3 years ago

Closed 3 years ago

#20335 closed enhancement (fixed)

A new structure for BCH codes

Reported by: dlucas Owned by:
Priority: major Milestone: sage-7.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) 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 3 years ago by dlucas

  • Branch set to u/dlucas/bch_code

comment:2 Changed 3 years ago by dlucas

  • Authors set to David Lucas
  • Commit set to 1449cb42df209bdbcdd0de14bfaae429b72f376f
  • Dependencies set to #20100
  • Status changed from new to needs_review

I pushed the code, this is now open for review.


Last 10 new commits:

b034726Fixed doctests in code_constructions.py
fbfcb9fChanged imports in binary_code.pyx
da37321Merged with #20100 and fixed conflicts
4bd9d47WIP
beadf6dMerge branch 'develop' into cyclic_code
0ee7bb6It is now possible to choose the primitive element to use as a root
b7a338eMerge branch 'cyclic_code' into bch_code
32ca611Changed signature of BCHCode class and deprecated the old BCHCode method
baa5680Added decoder for BCH codes
1449cb4Added decoder for cyclic code

comment:3 Changed 3 years ago by git

  • Commit changed from 1449cb42df209bdbcdd0de14bfaae429b72f376f to 26dcbac4d661fa3ee3fbe9c1fc21dd67620a9bed

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

26dcbacUpdated to latest beta, fixed conflicts, changed dependency

comment:4 Changed 3 years ago by dlucas

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 3 years ago by jsrn

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 in-review work and I don't have time :-(

comment:6 Changed 3 years ago by dlucas

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 3 years ago by git

  • Commit changed from 26dcbac4d661fa3ee3fbe9c1fc21dd67620a9bed to 7994411012fac36db9974dd51f4fef938df56067

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

61976d3cyclic_code.py now uses relative_finite_field_extension.py
6335358Fixed doctests in code_constructions.py
7366cbeEnhanced module documentation, class' and global method's documentation
c328827Removed __ne__ methods
141bb64Enhanced documentation of various methods in CyclicCode
a210e73Improved documentation of both encoders
e459f10Helper methods are now private methods
922e688Merge branch 'u/dlucas/cyclic_code' of git://trac.sagemath.org/sage into 20100_cyclic_codes
b3c4425Merge branch 'u/jsrn/cyclic_code' of git://trac.sagemath.org/sage into bch_codes
7994411Fixed broken doctests

comment:8 Changed 3 years ago by dlucas

I fixed merged conflicts, merged with the latest version of #20100 and fixed broken doctests.

Still open for review.

comment:9 Changed 3 years ago by cheuberg

  • Status changed from needs_review to needs_work

does no longer merge cleanly.

comment:10 Changed 3 years ago by jlavauzelle

  • Branch changed from u/dlucas/bch_code to u/jlavauzelle/bch_code

comment:11 Changed 3 years ago by jlavauzelle

  • Commit changed from 7994411012fac36db9974dd51f4fef938df56067 to c9f6835ff9d5d3daaac23bba0061f74053804df9
  • Milestone changed from sage-7.2 to sage-7.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:

b88510fFixed conflicts
efc89ecUpdated to latest beta (7.6.beta2).
0e82ba9Fixed surrounding_bch_code() and BCH constructor. Other minor fixes (doc, imports).
c18043fMade all doctests pass. Shorter output for BCH codes.
c9f6835Improved the doc of BCH codes. Cleaned the code.

comment:12 Changed 3 years ago by danielaugot

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 3 years ago by danielaugot

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 3 years ago by danielaugot

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 Reed-Solomon Code over GF(256)
sage: C.generator_matrix() * R.parity_check_matrix().transpose() == 0
True

comment:15 Changed 3 years ago by danielaugot

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 3 years ago by danielaugot

Now, some corner cases

sage: C = codes.BCHCode(GF(16),15,15)
sage: C.dimension() == 1

comment:17 Changed 3 years ago by danielaugot

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 3 years ago by git

  • Commit changed from c9f6835ff9d5d3daaac23bba0061f74053804df9 to f7b7280f2699c0b5bc771d6831b29dc94b2b8f9b

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

f7b7280Add tests and fixed minor bugs.

comment:19 Changed 3 years ago by jlavauzelle

Hi Daniel,

I pushed your suggestions.

Julien

comment:20 Changed 3 years ago by jlavauzelle

  • Authors changed from David Lucas to David Lucas, Julien Lavauzelle
  • Reviewers set to Daniel Augot

comment:21 Changed 3 years ago by danielaugot

L221

``designed_distance`` must be between 2 and ``length`` (inclusive),

should be

``designed_distance`` must be between 1 and ``length`` (inclusive)

comment:22 Changed 3 years ago by git

  • Commit changed from f7b7280f2699c0b5bc771d6831b29dc94b2b8f9b to d4ab8f72f622525cd2edfb9cb74023bf3ddcf558

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

d4ab8f7Fixed doc

comment:23 Changed 3 years ago by git

  • Commit changed from d4ab8f72f622525cd2edfb9cb74023bf3ddcf558 to 5064ef3d7bd8b6e33c7f27eaf1627d9c585f59fa

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

5064ef3Last fix, I hope

comment:24 Changed 3 years ago by git

  • Commit changed from 5064ef3d7bd8b6e33c7f27eaf1627d9c585f59fa to 32f9cc08aa000b6c9c1c4d77f3fd67f492ea7d2b

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

32f9cc0Last fix, finally

comment:25 Changed 3 years ago by danielaugot

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 3 years ago by danielaugot

  • Status changed from needs_review to positive_review

comment:27 Changed 3 years ago by danielaugot

  • Status changed from positive_review to needs_review

Small error L308

comment:28 Changed 3 years ago by jsrn

Please merge in #20908 and add as a dependency.

comment:29 Changed 3 years ago by jlavauzelle

Ok, anyway we need to test the decoder a bit more.

comment:30 Changed 3 years ago by git

  • Commit changed from 32f9cc08aa000b6c9c1c4d77f3fd67f492ea7d2b to d48aec7fb761dc71b73650efbd4192166a08db1a

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

8185e87Updated to latest beta and fixed conflicts
b77de0fAdded new file that introduces the new parity-check code class. Initializes code class, generator matrix encoder class, straightforward encoder class and minimum distance method.
0b0d2f8Correcting mistakes. Two errors are still waiting for correction: ParityCheckCodeStraightforwardEncoder.unencode_nocheck and ParityCheckCodeGeneratorMatrixEncoder.__init__
62abcd7Fixed merge conflict.
1aa4b4eFixed doctests. Shorter output. Generator matrix encoder inherits from the generic one. Fixed encoders. Cleaned the code.
19e299eMerged 21328 and fixed broken doctests
f64841fMove cyclic code heading
5295039Merge with #20908
8d476b6Lazy imports of BCH decoders
d48aec7Improved decoders and associated doctests for cyclic and BCH codes.

comment:31 Changed 3 years ago by jlavauzelle

  • Dependencies changed from #20100 to #20100, #20908

comment:32 Changed 3 years ago by git

  • Commit changed from d48aec7fb761dc71b73650efbd4192166a08db1a to 99234ce72f96874130c8c175177c2dff2bcb1edc

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

99234ceImproved the doc for the underlying GRS code of a BCH code

comment:33 Changed 3 years ago by jlavauzelle

Daniel,

I added some documentation on the underlying GRS code. You can tell me if you agree with it.

Julien

comment:34 Changed 3 years ago by danielaugot

The maths describing the underlying GRS codes are OK. The wording could be improved, for more brevity and clarity.

Last edited 3 years ago by danielaugot (previous) (diff)

comment:35 Changed 3 years ago by git

  • Commit changed from 99234ce72f96874130c8c175177c2dff2bcb1edc to bf2c3bbf44824e38c0374026cd8e7536b7b99291

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

bf2c3bbMade maths cleaner

comment:36 Changed 3 years ago by jlavauzelle

OK I did it. Thanks Daniel.

Julien

comment:37 Changed 3 years ago by danielaugot

The writing and the layout is OK.

comment:38 Changed 3 years ago by danielaugot

  • Status changed from needs_review to positive_review

comment:39 Changed 3 years ago by vbraun

  • Branch changed from u/jlavauzelle/bch_code to bf2c3bbf44824e38c0374026cd8e7536b7b99291
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.