A new structure for Cyclic codes

[dlucas]

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.

[dlucas]

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:

​77f0629	Merged #19897
​37bb7ac	Updated introductory thematic tutorial with a paragraph on decoders and message spaces
​1220403	Merge branch 'develop' into grs_decoders
​4340598	Removed deprecated import
​b840682	Updated to 7.1beta3 and fixed conflict
​d70d6aa	Removed __ne__ methods
​1808bb1	Some fixes to the decoder. Merged with GRS decoders branch to have fast examples
​9c5405f	Fixed a bug because of which it was impossible to build a PC matrix when the subfield was the prime field
​f3ca628	Merge branch 'subfield_subcode' into cyclic_code
​6bcc1e7	Class for cyclic and two encoders for this class

[git]

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

​d9618bf

Fixed bug in defining_set

[dlucas]

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

[git]

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

​a074cb8	Changed my helper methods into private methods
​6ad583f	Fixed bug in KeyEquation decoder's decode_to_code, added sanity checks, enhanced doctests
​fca099e	Added new sanity check on the output of BW and Gao decoder
​57dbfbf	Rewrote random_element method
​7953d60	Proper sanity checks for output of decode_to_* methods
​8673ac5	Optimized a bit polynomial division in Gao and BW
​e1b6b09	Merged now postive reviewed #19666 and fixed conflicts
​5093dce	Update to 7.1beta5
​f3b4b11	Fixed typo in Guruswami-Sudan doc
​bab6bf7	Merge branch 'grs_decoders' into cyclic_code

[dlucas]

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

[git]

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

​c302015	Update to 7.1beta6
​0e148fd	Fixed some broken doctests
​c7350e2	Changed some doctests in code_construction
​9de5ebf	Updated to 7.1
​b034726	Fixed doctests in code_constructions.py
​fbfcb9f	Changed imports in binary_code.pyx

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

[git]

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

​beadf6d	Merge branch 'develop' into cyclic_code
​0ee7bb6	It is now possible to choose the primitive element to use as a root

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

[git]

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

​97484cf	Merged into 7.3beta5, fixed conflicts, removed old field_embedding.py file
​ea19a06	Removed subfield_subcode.py
​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

[dlucas]

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

[jsrn]

Fixed merge conflicts.

---

New commits:

​922e688

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

[git]

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

​6041c17	Merge branch 'u/jsrn/cyclic_code' of trac.sagemath.org:sage into 20100_cyclic_codes
​7be49e6	Fix some import errors

[jlavauzelle]

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:

​b961f67	Fixed typos. Replaced local `_cyclotomic_coset` function. Added some input checking.
​5d2aef4	Fixed some bad newlines in strings.

[git]

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

​e2e127b	Merge branch 'develop' into fix_cyclic_code
​8bde363	Fixed the wrong merge.
​4c2e8c8	Add subfield subcode decoder in the doc of decoders_catalog.py.

[git]

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

​ff71364	Added a self._polynomial_ring attribute. Corrected __eq__ and __contains__.
​84796b5	Fixed minor bugs and typos.

[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

[git]

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

​5cff1df

Fix a colon miss.

[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

[danielaugot]

Proper test for the base ring to be finite field.

---

New commits:

​c419639

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

[git]

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

​66a0d47

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

[git]

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

​e8286a5

proper error message

[git]

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

​260e413

proper error message II

[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

[git]

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

​293f2a3

replaced the Hartmann-Tzeng reference by Roth

[jlavauzelle]

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

[jlavauzelle]

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:

​45619f8	Merged latest beta (7.4.beta2).
​ffa627b	Fixed double reference to [R06].
​18f4629	Improved the documentation. Improved the way the generator polynomial is made monic.

[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

[git]

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

​7c077ce	Modified defining_set() and primitive_element() methods. Fixed some doc.
​7c4ff2b	Removed __ne__. Changed bch_bound() to make it more clear and efficient. Fixed doc also.

[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

[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.)

[ylchapuy]

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

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

[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

[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?

[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

[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 :-)

[git]

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

​2bcf6d4	Replaced primitive_element by primitive_root.
​adb1807	Replaced bch_bound() algorithm with a more readable one. Added sanity-check for it.
​238d19a	Removed spaces. Romoved useless imports.

[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

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

[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

[git]

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

​9790560	Fixed infinite loop.
​932e940	Merged with latest beta (7.4.beta3) and fixed conflicts.
​82e192d	Better argument cehcking in __init__.
​2def8b1	Better line continuations.
​0739aed	Use sorted() instead of .sort().
​816b67d	Better use of cached methods.
​a4fb63e	Fixed a small bug in defining_set().

[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

[danielaugot]

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

[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

[git]

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

​a3d67df	Merged with latest beta (7.4.beta4).
​ff499ff	Merged with latest beta (7.4.beta5).
​369e36c	Fixed bug in the constructor related to primitive_root.

[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

[git]

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

​176db58

Fixed doctests.

[jlavauzelle]

Well, I forgot to fix doctests. Done now.

[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)])

[git]

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

​83af4e0	Better imports. Improved exceptions. Used multiplicative_order() method.
​073af73	Improved _complete_list. One-lined some loops. Used proper log function.

[jlavauzelle]

Hi Yann,

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

Julien

[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 ]

[git]

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

​0f4fe27

Improved code style.

[jlavauzelle]

Hi Yann,

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

Julien

[git]

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

​2161696	Merged to latest beta (7.4.beta6).
​75a222d	Rewrote doctest of two deprecated functions for best test coverage.
​6f235d6	Doctests now pass.

[jlavauzelle]

Hi,

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

Still open for review.

Julien

[git]

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

​e74c828	Updated to latest beta (7.4.rc0).
​8ee0d57	Updated to latest beta (7.4).

[ylchapuy]

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.

[vbraun]

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

[git]

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

​3bf1515	Updated to latest beta (7.5.beta0).
​75144a4	Fixed references.

[git]

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

​cc97a23	Merged with latest beta (7.5.beta2) and fixed conflicts.
​d6f6bde	Shorter print for cyclic codes

[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