Opened 4 years ago

Closed 3 years ago

#20100 closed enhancement (fixed)

A new structure for Cyclic codes

Reported by: dlucas Owned by:
Priority: major Milestone: sage-7.5
Component: coding theory Keywords: sd75
Cc: jsrn, cpernet Merged in:
Authors: David Lucas, Julien Lavauzelle Reviewers: Daniel Augot, Yann Laigle-Chapuy
Report Upstream: N/A Work issues:
Branch: d6f6bde (Commits) Commit: d6f6bdeb62e886638cb06f5ffa9ab752493779c3
Dependencies: #20284 Stopgaps:

Description

This ticket proposes a new implementation for cyclic codes.

It contains:

  • a new code class, CyclicCode,
  • a dedicated encoder to compute the generator matrix of a Cyclic Code, and
  • an encoder whose message space is a polynomial ring.

This new structure has the following features:

  • it is now possible to build a cyclic code in three different ways:
    • either by using the generator polynomial, which is passed as an argument,
    • either by using the defining set, which is passed as an argument (and can even be partial), or
    • by passing a linear code as argument. In that case, a generator polynomial will be computed (if possible) and used to reformat the input code as a cyclic code.
  • it also comes with a method to compute the BCH bound, either from a constructed code or directly from the necessary parameters.

Attachments (1)

proof_cyclic_code.pdf (121.5 KB) - added by jlavauzelle 3 years ago.
A proof of the cyclic code criteria in the "find_generator_polynomial()" method.

Download all attachments as: .zip

Change History (74)

comment:1 Changed 4 years ago by dlucas

  • Branch set to u/dlucas/cyclic_code

comment:2 Changed 4 years ago by dlucas

  • Authors set to David Lucas
  • Commit set to 6bcc1e724a6d0cbf249a2bb3fa4ef3f313100c9d
  • Dependencies set to #20039

I pushed my work, as it is almost done. There's still one bug to fix, documented in defining_set's broken docstring.


Last 10 new commits:

77f0629Merged #19897
37bb7acUpdated introductory thematic tutorial with a paragraph on decoders and message spaces
1220403Merge branch 'develop' into grs_decoders
4340598Removed deprecated import
b840682Updated to 7.1beta3 and fixed conflict
d70d6aaRemoved __ne__ methods
1808bb1Some fixes to the decoder. Merged with GRS decoders branch to have fast examples
9c5405fFixed a bug because of which it was impossible to build a PC matrix when the subfield was the prime field
f3ca628Merge branch 'subfield_subcode' into cyclic_code
6bcc1e7Class for cyclic and two encoders for this class

comment:3 Changed 4 years ago by git

  • Commit changed from 6bcc1e724a6d0cbf249a2bb3fa4ef3f313100c9d to d9618bf3fe7b4958b5a8589ed08196a7c0468f7c

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

d9618bfFixed bug in defining_set

comment:4 Changed 4 years ago by dlucas

  • Status changed from new to needs_review

Ok, found it and fixed it. It's now open for review.

comment:5 Changed 4 years ago by git

  • Commit changed from d9618bf3fe7b4958b5a8589ed08196a7c0468f7c to bab6bf7098c5720a19f153ea7a6a91bea8a71834

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

a074cb8Changed my helper methods into private methods
6ad583fFixed bug in KeyEquation decoder's decode_to_code, added sanity checks, enhanced doctests
fca099eAdded new sanity check on the output of BW and Gao decoder
57dbfbfRewrote random_element method
7953d60Proper sanity checks for output of decode_to_* methods
8673ac5Optimized a bit polynomial division in Gao and BW
e1b6b09Merged now postive reviewed #19666 and fixed conflicts
5093dceUpdate to 7.1beta5
f3b4b11Fixed typo in Guruswami-Sudan doc
bab6bf7Merge branch 'grs_decoders' into cyclic_code

comment:6 Changed 4 years ago by dlucas

I merged with latest beta, fixed conflicts with GRS branch, this is still open for review.

comment:7 Changed 3 years ago by git

  • Commit changed from bab6bf7098c5720a19f153ea7a6a91bea8a71834 to fbfcb9f2c59429050ddb23584d563594518baee5

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

c302015Update to 7.1beta6
0e148fdFixed some broken doctests
c7350e2Changed some doctests in code_construction
9de5ebfUpdated to 7.1
b034726Fixed doctests in code_constructions.py
fbfcb9fChanged imports in binary_code.pyx

comment:8 Changed 3 years ago by dlucas

I fixed the broken doctests in code_constructions.py. They occured because the old implementation of CyclicCode allowed to use generator polynomials which do not divide x^n - 1, n being the length of the code. I fixed this by replacing these polynomials (say, g) by gcd(g, x^n - 1).

This is still open for review.

comment:9 Changed 3 years ago by dlucas

  • Milestone changed from sage-7.1 to sage-7.2

comment:10 Changed 3 years ago by git

  • Commit changed from fbfcb9f2c59429050ddb23584d563594518baee5 to 0ee7bb69199de36738353c30ebb0104620502997

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

beadf6dMerge branch 'develop' into cyclic_code
0ee7bb6It is now possible to choose the primitive element to use as a root

comment:11 Changed 3 years ago by dlucas

I updated to the latest beta. I also added a new optional argument: primitive_element. If filled, it will be used as the "base root" for the consecutive root sequence of the generator polynomial over the splitting field.

comment:12 Changed 3 years ago by git

  • Commit changed from 0ee7bb69199de36738353c30ebb0104620502997 to e459f107bb0b8c36149ec6a8ba9ef52c7e46aa06

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

97484cfMerged into 7.3beta5, fixed conflicts, removed old field_embedding.py file
ea19a06Removed subfield_subcode.py
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

comment:13 Changed 3 years ago by dlucas

  • Dependencies changed from #20039 to #20284
  • Milestone changed from sage-7.2 to sage-7.3

Hello,

I updated this ticket to latest beta version (7.3b5) and made some changes:

  • I removed dependency to #20039.
  • I improved documentation in many places, by defining terms more precisely.
  • I removed now useless __ne__ methods
  • I changed helper methods and made them private methods.

This is open for review.

David

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

comment:14 Changed 3 years ago by jsrn

  • Cc jsrn added

comment:15 Changed 3 years ago by jsrn

  • Branch changed from u/dlucas/cyclic_code to u/jsrn/cyclic_code

comment:16 Changed 3 years ago by jsrn

  • Commit changed from e459f107bb0b8c36149ec6a8ba9ef52c7e46aa06 to 922e688a2da5f855ed52bd8de4e0d55325e90179

Fixed merge conflicts.


New commits:

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

comment:17 Changed 3 years ago by git

  • Commit changed from 922e688a2da5f855ed52bd8de4e0d55325e90179 to 7be49e607bc0000d4d60ad8f6ee23a24395192cb

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

6041c17Merge branch 'u/jsrn/cyclic_code' of trac.sagemath.org:sage into 20100_cyclic_codes
7be49e6Fix some import errors

comment:18 Changed 3 years ago by jlavauzelle

  • Branch changed from u/jsrn/cyclic_code to u/jlavauzelle/cyclic_code

comment:19 Changed 3 years ago by jlavauzelle

  • Commit changed from 7be49e607bc0000d4d60ad8f6ee23a24395192cb to 5d2aef43433b313c026c20dfa518705eaf9fb2be
  • Milestone changed from sage-7.3 to sage-7.4
  • Status changed from needs_review to needs_work

Hi,

As some sd75 participants may want to follow this ticket, I push some changes:

  • I fixed some typos;
  • I removed the probabilistic algorithm from the find_generator_polynomial() method, because it didn't always output the right result;
  • As we discussed quickly with Johan, only single-root cyclic codes are now implemented (that is, n and q must be coprimes);
  • I removed your local _cyclotomic_cosets() method;
  • I added some sanity checks;
  • maybe other things

That's still a work in progress. Especially, it remarked that (non exhaustive):

  • __eq__ sometimes gives fake negatives (or type II errors). For example, when building cyclic codes from the same (mathematically speaking) generator polynomial, but belonging to two different instances of PolynomialRing.
  • I don't remember why we let the user choose the primitive element (does the code really depend on that?)
  • BCH bound computation will be hard to review :)
  • the defining set looks to depend on the choice of beta, the n-th root of unity.
  • I don't understand what is the _known_generator_matrix attribute
  • it seems weird that the CyclicCodeVectorEncoder encodes with a polynomial multiplication.

As I said, it's definitely a WIP.

Julien


New commits:

b961f67Fixed typos. Replaced local `_cyclotomic_coset` function. Added some input checking.
5d2aef4Fixed some bad newlines in strings.

comment:20 Changed 3 years ago by git

  • Commit changed from 5d2aef43433b313c026c20dfa518705eaf9fb2be to 4c2e8c8263f4fe955083256c693bac7b2dba031c

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

e2e127bMerge branch 'develop' into fix_cyclic_code
8bde363Fixed the wrong merge.
4c2e8c8Add subfield subcode decoder in the doc of decoders_catalog.py.

comment:21 Changed 3 years ago by git

  • Commit changed from 4c2e8c8263f4fe955083256c693bac7b2dba031c to 84796b51bf88eba9c93a97e35b5d297249e37f63

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

ff71364Added a self._polynomial_ring attribute. Corrected __eq__ and __contains__.
84796b5Fixed minor bugs and typos.

comment:22 Changed 3 years ago by jlavauzelle

Hi,

I made some minor changes after merging the right 'develop' branch. I think now it compiles well (at least, in my machine; Joe Fields reported a compiling problem with guava in the previous push that I couldn't reproduce).

I reviewed almost all the code, i.e. all but the BCH bound. It looks quite fine now, but as it's a quite big patch, it clearly need a second review (besides, someone must review my own commits).

Julien

comment:23 Changed 3 years ago by jlavauzelle

  • Authors changed from David Lucas to David Lucas, Julien Lavauzelle
  • Status changed from needs_work to needs_review

comment:24 Changed 3 years ago by git

  • Commit changed from 84796b51bf88eba9c93a97e35b5d297249e37f63 to 5cff1dfdb1dd9f347a247e3577660c84b8b3e0f9

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

5cff1dfFix a colon miss.

comment:25 Changed 3 years ago by danielaugot

Hi David and Julien,

Using codes.CyclicCode.<TAB> I went through all methods which are worth mentionning. I will just first make a few remarks about them and their associated docstrings.

  • codes.CyclicCode?
    • "generator_pol" : in the sentence "the unique monic polynomial which divides every codeword" the meaning of "divides" is not mathematically clear. If you mean division in F[X]/(X^n-1), then you need to furthermore say it has lowest degree to make it unique.
    • "D": recall it is a set of (positive ? reduced mod n ?) integers
    • method (3): a few words should be said about the default root of unity used in building the generator polynomial
  • codes.CyclicCode.bch_bound?
    • is it possible to use BCH_bound to honor the authors ?
  • codes.CyclicCode.defining_set? is very neat. For more completeness, I think it would be nice to briefly recall it depends on the choice of the primitive root (which is not shown or discussed in the examples).
  • codes.CyclicCode.dual_code() not a docstring problem, and more a design problem. As I just tested it, the resulting code is not a member of the CyclicCode class.
  • codes.CyclicCode.primitive_element? in the string "Returns the primitive element that was used as a root the generator polynomial over the extension field.", the words "that was used" are not very clear, since it is not mentionned by which method it has been used. For instance it should be clear from the docstring what is the result when calling codes.CyclicCode using an arbritrary code.
  • somehow the class inherits C.variable_name. Wouldn't it be a neat to use it to get the variable for the underlying polynomial ring ?

I will go through the implementation this afternoon.

Daniel

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

comment:26 Changed 3 years ago by danielaugot

  • Branch changed from u/jlavauzelle/cyclic_code to u/danielaugot/cyclic_code

comment:27 Changed 3 years ago by danielaugot

  • Commit changed from 5cff1dfdb1dd9f347a247e3577660c84b8b3e0f9 to c419639a5e12161c1cb790773645514a7ae2b926

Proper test for the base ring to be finite field.


New commits:

c419639in case (1) of the constructor, test if we have a field

comment:28 Changed 3 years ago by git

  • Commit changed from c419639a5e12161c1cb790773645514a7ae2b926 to 66a0d4782e69884be03ab79dae718d1dfaa5d611

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

66a0d47test for a finite field in the (3) case of the constructor

comment:29 Changed 3 years ago by git

  • Commit changed from 66a0d4782e69884be03ab79dae718d1dfaa5d611 to e8286a5ab4e6f0580e955f7e45f158ae0b652d61

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

e8286a5proper error message

comment:30 Changed 3 years ago by git

  • Commit changed from e8286a5ab4e6f0580e955f7e45f158ae0b652d61 to 260e413df6b65b3fe97661e4ab5cfc4749708a59

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

260e413proper error message II

comment:31 Changed 3 years ago by danielaugot

About the internals and the implementation (I)

  • codes.CyclicCode, case (3). Why do you check if primitive_element is nice ? Why do not you force it, since the user did not provide any such element in case (3)?
  • find_generator_polynomial I would be happy to have a proof that the proposed algorithm is correct.
  • find_generator_polynomial should return a monic polynomial. That would avoid doing the work in the constructor.
  • parity_check_matrix is cached in the case of cyclic codes and not for general linear codes.
  • defining_set: it would be nice to be able to give an alternate root as an argument, to see the defining set in another disguise.
  • In many places, we have the following unpleasant code
                s = 1
                while not (q ** s - 1) % n == 0:
                    s += 1
    

to find the degree of the extension field where lies the nth-root of unity. Sage can compute the splitting field by itself, as follows

sage: K.<x>=PolynomialRing(GF(2))
sage: pol=x^31-1
sage: F=pol.splitting_field('y')
sage: F
Finite Field in y of size 2^5

I guess this could be used to have a more pleasant and mathematicall oriented coding style.

C'est tout pour ce soir.

Daniel

comment:32 Changed 3 years ago by git

  • Commit changed from 260e413df6b65b3fe97661e4ab5cfc4749708a59 to 293f2a343d8b7d7373d94f0161bb8bf34ee5bfbd

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

293f2a3replaced the Hartmann-Tzeng reference by Roth

comment:33 Changed 3 years ago by jlavauzelle

  • Branch changed from u/danielaugot/cyclic_code to u/jlavauzelle/cyclic_code

Changed 3 years ago by jlavauzelle

A proof of the cyclic code criteria in the "find_generator_polynomial()" method.

comment:34 follow-up: Changed 3 years ago by jlavauzelle

  • Commit changed from 293f2a343d8b7d7373d94f0161bb8bf34ee5bfbd to 18f4629702ae81d08cc23d13ce382c5fcc1c12c5

Hi,

I merged the latest beta (7.4.beta2). I also improved the doc according to Daniel's comments.

About your remarks:

  • calling the method BCH_bound instead of bch_bound would not respect naming conventions;
  • I didn't made the dual_code() fix yet;
  • the problem with the variable name is not easy. A solution could be to internally force it to be x (however the code is built), but we don't want this to happen:
    sage: R = PolynomialRing(GF(2), 'y')
    sage: y = R.gen()
    sage: g = y + 1
    sage: C = codesCyclicCode(g, 5)
    sage: C.generator_polynomial() == g
    False
    
  • in the third construction (3), the user can provide a primitive_element;
  • I give a proof of my criteria in attachment;
  • I agree for the optional alternate root as an argument of defining_set. Not done yet;
  • concerning the use of the splitting_field() method, I'm worrying about its computation cost, as we may only want the extension degree. But I agree your code is more pleasant to read.

Still a WIP (but reviews are welcome).

Julien


New commits:

45619f8Merged latest beta (7.4.beta2).
ffa627bFixed double reference to [R06].
18f4629Improved the documentation. Improved the way the generator polynomial is made monic.

comment:35 in reply to: ↑ 34 Changed 3 years ago by jsrn

Replying to jlavauzelle:

  • concerning the use of the splitting_field() method, I'm worrying about its computation cost, as we may only want the extension degree. But I agree your code is more pleasant to read.

In all places where we computate s, we immediately construct the splitting field as well, AFAICS. So we could indeed just use Daniel's loop (otherwise you are right, Julien, that computing the degree is much much faster. But in that case the loop should be wrapped as a function call).

Best, Johan

comment:36 Changed 3 years ago by git

  • Commit changed from 18f4629702ae81d08cc23d13ce382c5fcc1c12c5 to 7c4ff2b6e739ae9acc00f70405af09d60cf11b9e

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

7c077ceModified defining_set() and primitive_element() methods. Fixed some doc.
7c4ff2bRemoved __ne__. Changed bch_bound() to make it more clear and efficient. Fixed doc also.

comment:37 Changed 3 years ago by jlavauzelle

Hi,

I fixed issues in defining_set() and in primitive_element(). I also completely changed bch_bound() because it was not very clear and not that much efficient. I think now it's a bit faster.

Now it's really open for review.

Julien

comment:38 Changed 3 years ago by jsrn

Writing a BCH-bound algorithm that is compact and fast yet readable is a fun challenge :-) Here is my proposal, which is shorter than yours and to my mind more readable. I also added the small optimisation that the arithmetic step size doesn't need to be considered beyond n/2.

On a related note, shouldn't bch_bound always just output bch_parameters?

def bch_bound(n, D, arithmetic=False):
    def longest_streak(step):
        max_len = 1
        max_offset = 0
        j = 0
        while j < n:
            h = j
            while isD[h*step % n]:
                h += 1
            if h - j > max_len:
                max_offset = j
                max_len = h - j
            j = h + 1
        return (max_len, max_offset)

    isD = [ 1 if d in D else 0 for d in range(n) ]
    if not arithmetic:
        one_len, offset = longest_streak(1)
        return (one_len + 1, (1, offset))
    else:
        step, (max_len, offset) = max([ (step, longest_streak(step)) for step in range(1,n//2) ],
                                      key=lambda (step,(step_len,_)): step_len)
        return (max_len + 1, (step, offset))

(This is not a review: I didn't look much at the rest of the code.)

comment:39 follow-up: Changed 3 years ago by ylchapuy

For both implementation of the bch_bound, I could be annoying and set D = range(n) ...

comment:40 in reply to: ↑ 39 ; follow-up: Changed 3 years ago by jsrn

Replying to ylchapuy:

For both implementation of the bch_bound, I could be annoying and set D = range(n) ...

In which case, in O(n^2), the algorithm returns n+1 as minimum distance of the corresponding code. That input doesn't make much sense from a coding point of view, since it corresponds to the zero code of length n. Which according to some definitions has minimum distance n+1.

comment:41 Changed 3 years ago by danielaugot

Hi

I am a bit concerned with the terminology primitive_element where I think it should be primitive_root or primitive_root_of_unity.

In the finite field realm, primitive_element really means a generator of the cyclic group of all invertible elements.

Even wikipedia says so https://en.wikipedia.org/wiki/Primitive_element_(finite_field).

On the other side, https://en.wikipedia.org/wiki/Root_of_unity#primitive really means what you want.

So primitive_element here does not respect the standard finite field terminology.

Daniel

comment:42 in reply to: ↑ 40 ; follow-up: Changed 3 years ago by ylchapuy

Replying to jsrn:

Replying to ylchapuy:

For both implementation of the bch_bound, I could be annoying and set D = range(n) ...

In which case, in O(n^2), the algorithm returns n+1 as minimum distance of the corresponding code. That input doesn't make much sense from a coding point of view, since it corresponds to the zero code of length n. Which according to some definitions has minimum distance n+1.

You may have to wait a bit more than O(n^2): while table_D[i*j % n] == 1: ... and table_D is all 1

From a coding point of view, I do agree this doesn't make sense, but is the user aware of that?

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

comment:43 Changed 3 years ago by danielaugot

Hi Yann

thank you for looking at this ! And please be annoying : since our codes may be tortured with various operations for combining codes, it could well happen that someone ends with such a situation.

Concerning the cyclic code on length n which are {0}, I think n+1 is a correct math answer for the minimum distance d. At least it gives the MDS bound k+d=n+1.

So both Yann's remark and Johan's answer are correct.

Best,

Daniel

comment:44 in reply to: ↑ 42 Changed 3 years ago by jsrn

Replying to ylchapuy:

You may have to wait a bit more than O(n^2): while table_D[i*j % n] == 1: ... and table_D is all 1

Hehe, yeah good point :-)

comment:45 Changed 3 years ago by git

  • Commit changed from 7c4ff2b6e739ae9acc00f70405af09d60cf11b9e to 238d19abb6d5516072ddd51c51fb50724c1b5fac

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

2bcf6d4Replaced primitive_element by primitive_root.
adb1807Replaced bch_bound() algorithm with a more readable one. Added sanity-check for it.
238d19aRemoved spaces. Romoved useless imports.

comment:46 Changed 3 years ago by jlavauzelle

Hi,

Thanks for all your comments! According to them, I made some changes:

  • Johan, I picked your proposal (a way more readable, I didn't know it was possible to add optional parameters to the max() function, that's nice :)). I just replaced n//2 by n//2+1 in a loop.
  • I added some sanity-checks and fixed the problem raised by Yann (thanks!). As you said, n+1 seems a good bound (at least) for the minimum distance of the zero code.
  • I replaced primitive_element by primitive_root.

Still open for review.

Julien

comment:47 Changed 3 years ago by ylchapuy

You may still come to an infinite loop if you skip the gcd. Try e.g. bch_bound(6, [0,2,4], True). Also the key trick is nice but useless, just reorder the tuple to (longest_streak(step), step) and be happy with the lexicographic order.

I might read the rest of this if I find some more time.

comment:48 Changed 3 years ago by ylchapuy

Some remarks:

  • arguments are silently ignored if you feed __init__ too much (e.g. give a polynomial and a code)
  • line continuations are considered bad style in Python, prefer parentheses, braces, etc (see https://www.python.org/dev/peps/pep-0008/#id19)
  • use sorted instead of .sort() when possible
  • why do your own caching and not using @cached_method (e.g. for check_polynomial)
  • instead of self._known_generator_matrix you could just check self.generator_matrix.cache is not None

comment:49 Changed 3 years ago by git

  • Commit changed from 238d19abb6d5516072ddd51c51fb50724c1b5fac to a4fb63ec915f9ccc3c6fce6bf720a82b5ca4d425

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

9790560Fixed infinite loop.
932e940Merged with latest beta (7.4.beta3) and fixed conflicts.
82e192dBetter argument cehcking in __init__.
2def8b1Better line continuations.
0739aedUse sorted() instead of .sort().
816b67dBetter use of cached methods.
a4fb63eFixed a small bug in defining_set().

comment:50 Changed 3 years ago by jlavauzelle

Hi Yann,

Thanks again for you helpful comments (especially concerning the python/sage tricks). I pushed the corresponding fixes.

I also merged with the latest beta.

Julien

comment:51 Changed 3 years ago by danielaugot

  • Cc cpernet added

So much for the 7.4beta3. develop does not compile, because linbox fails to compile on my fedora24. I can not test the ticket.

comment:52 Changed 3 years ago by danielaugot

Hi

Line 425, there is this:

            if primitive_root is not None:
                if (primitive_root not in Fsplit or
                    multiplicative_order(primitive_root) != n):
                    raise ValueError("primitive_root has to be an element of multiplicative order n in the extension field used to compute the generator polynomial")

where primitive_root has been provided by the user in case (3) of the constructor. But Fsplit has been constructed line 420:

            while not (q ** s - 1) % n == 0:
                s += 1

            if s == 1: # splitting field is F
                Fsplit = F
            else: # must compute a splitting field
                Fsplit, F_to_Fsplit = F.extension(Integer(s), map = True)

this implies that the user may have provided his own, mathematically correct primitive_root with his own finite field, which then will not be accepted by the code on line 425, because Fsplit may be different from the field of user's primitive_root (from sage point of view)

The following example triggers the problem

sage: F=GF(16,'a')
sage: K=GF(256,'X')
sage: alpha=K.primitive_element()
sage: C=codes.CyclicCode(length = 255, field = F, D = [1,2], primitive_root=alpha)

and casts the error

ValueError: primitive_root has to be an element of multiplicative order n in the extension field used to compute the generator polynomial

It would be better to check first for the primitive_root, and then build Fsplit according to the one given by the user and build Fsplit later if needed.

Daniel

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

comment:53 Changed 3 years ago by git

  • Commit changed from a4fb63ec915f9ccc3c6fce6bf720a82b5ca4d425 to 369e36c41171b098750d97067ae874159638e974

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

a3d67dfMerged with latest beta (7.4.beta4).
ff499ffMerged with latest beta (7.4.beta5).
369e36cFixed bug in the constructor related to primitive_root.

comment:54 Changed 3 years ago by jlavauzelle

Hi Daniel,

Thanks for the comment. You're completely right, I fixed the bug and merged with the latest beta.

Still open for review.

Julien

comment:55 Changed 3 years ago by git

  • Commit changed from 369e36c41171b098750d97067ae874159638e974 to 176db5803d68b293dd76e74b04a0600beb64a3fb

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

176db58Fixed doctests.

comment:56 Changed 3 years ago by jlavauzelle

Well, I forgot to fix doctests. Done now.

comment:57 Changed 3 years ago by ylchapuy

Hi,

  • futurize imports (see e.g. #20945)
  • you should avoid bare except (even if RelativeFiniteFieldExtension(GF(5), GF(7)) fails in a strange way, which should probably be another ticket), at least check assertions with AssertionError
  • you should add doctests for exceptions too

finally other more cosmetic remarks:

  • _complete_list is always used after .coefficients(sparse = False), you could go one step further with
    def _to_complete_list(poly, list_len):
        L = poly.coefficients(sparse = False)
        return L + [poly.base_ring().zero()] * (list_len - len(L))
    
    ( for parity_check_polynomial try h.reverse())
  • regarding comment:31 , why not Zmod(n)(q).multiplicative_order()
  • use root.log(alpha) (special cased for each field) instead of discrete_log (generic)
  • here are some one liner you could use:
    • g = gcd(R(row.list()) for row in G)
    • if any(vector(c[k:] + c[:k]) not in code for k in range(n)):
    • H = matrix([l[-i:] + l[:-i] for i in range(n-k)])
    • G = matrix([l[-i:] + l[:-i] for i in range(k)])

comment:58 Changed 3 years ago by git

  • Commit changed from 176db5803d68b293dd76e74b04a0600beb64a3fb to 073af73cf1b5d2ee2bc89a71b833816dfabcb5cb

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

83af4e0Better imports. Improved exceptions. Used multiplicative_order() method.
073af73Improved _complete_list. One-lined some loops. Used proper log function.

comment:59 Changed 3 years ago by jlavauzelle

Hi Yann,

Thanks again for the helpful comments. I did the modification.

Julien

comment:60 Changed 3 years ago by ylchapuy

Hi,

almost good, here are some more remarks:

  • line 413, probably ValueError as e but what is the point of catching an exception to reraise it?
  • found with flake8:
    cyclic_code.py:60:1: F401 '.decoder.Decoder' imported but unused
    cyclic_code.py:66:1: F401 'sage.rings.polynomial.polynomial_ring.PolynomialRing_general' imported but unused
    cyclic_code.py:67:1: F401 'sage.rings.finite_rings.finite_field_constructor.GF' imported but unused
    cyclic_code.py:69:1: F401 'sage.categories.homset.Hom' imported but unused
    cyclic_code.py:70:1: F401 'sage.groups.generic.discrete_log' imported but unused
    cyclic_code.py:71:1: F401 'sage.misc.functional.multiplicative_order' imported but unused
    cyclic_code.py:103:5: F841 local variable 'x' is assigned to but never used
    cyclic_code.py:433:13: F841 local variable 'x' is assigned to but never used
    cyclic_code.py:725:9: F841 local variable 'R' is assigned to but never used
    

plus many PEP8 comments, mainly:

  • no space around = for keyword arguments
  • whitespace after [ or before ]

comment:61 Changed 3 years ago by git

  • Commit changed from 073af73cf1b5d2ee2bc89a71b833816dfabcb5cb to 0f4fe2758369ccdb0763047b4fb5c769bb53d2f5

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

0f4fe27Improved code style.

comment:62 Changed 3 years ago by jlavauzelle

Hi Yann,

I didn't know flake8, great tool. I improved the coding style according to it.

Julien

comment:63 Changed 3 years ago by git

  • Commit changed from 0f4fe2758369ccdb0763047b4fb5c769bb53d2f5 to 6f235d690bfc58af7670d5218248e8283f58d900

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

2161696Merged to latest beta (7.4.beta6).
75a222dRewrote doctest of two deprecated functions for best test coverage.
6f235d6Doctests now pass.

comment:64 Changed 3 years ago by jlavauzelle

  • Keywords sd75 added

Hi,

I updated to the latest beta (7.4.beta6).

Still open for review.

Julien

comment:65 Changed 3 years ago by git

  • Commit changed from 6f235d690bfc58af7670d5218248e8283f58d900 to 8ee0d57a00d86f9945f75b1c497df907288e0ddd

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

e74c828Updated to latest beta (7.4.rc0).
8ee0d57Updated to latest beta (7.4).

comment:66 Changed 3 years ago by ylchapuy

  • Milestone changed from sage-7.4 to sage-7.5
  • Reviewers set to Daniel Augot, Yann Laigle-Chapuy
  • Status changed from needs_review to positive_review

Previous comments have been taken into account, tests pass (failures on gentoo seem unrelated), coverage for the new file is 100%, doc builds and looks OK.

All good for me.

comment:67 Changed 3 years ago by vbraun

  • Status changed from positive_review to needs_work

Conflicts; Please wait for next beta and then fix the references:

[dochtml] [coding   ] /mnt/disk/home/release/Sage/local/lib/python2.7/site-packages/sage/coding/cyclic_code.py:docstring of sage.coding.cyclic_code:1: WARNING: citation not found: R06
[dochtml] [coding   ] /mnt/disk/home/release/Sage/local/lib/python2.7/site-packages/sage/coding/cyclic_code.py:docstring of sage.coding.cyclic_code:24: WARNING: citation not found: R06

comment:68 Changed 3 years ago by git

  • Commit changed from 8ee0d57a00d86f9945f75b1c497df907288e0ddd to 75144a48e59efeaa4a022eaa4853e7880ba13825

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

3bf1515Updated to latest beta (7.5.beta0).
75144a4Fixed references.

comment:69 Changed 3 years ago by jlavauzelle

  • Status changed from needs_work to needs_review

comment:70 Changed 3 years ago by git

  • Commit changed from 75144a48e59efeaa4a022eaa4853e7880ba13825 to d6f6bdeb62e886638cb06f5ffa9ab752493779c3

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

cc97a23Merged with latest beta (7.5.beta2) and fixed conflicts.
d6f6bdeShorter print for cyclic codes

comment:71 Changed 3 years ago by jlavauzelle

Hi,

I updated to the latest beta (7.5.beta2) and fixed conflicts.

Following #21691, I also produced shorter printing for cyclic codes (basically, I removed the generator polynomial which can have a quite long printing).

Best,

Julien

comment:72 Changed 3 years ago by danielaugot

  • Status changed from needs_review to positive_review

comment:73 Changed 3 years ago by vbraun

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