A proper class for Hamming codes

[sagetrac-dlucas]

codes.HammingCode is not a constructor for a class, but a method which builds a generic linear code.

This ticket proposes a class implementation of Hamming codes, using the API introduced in #18099 which properly sets Hamming codes as a class. It also comes with a new generic encoder for codes built from a parity check matrix.

CC: @wdjoyner @ppurka @ClementPernet

Component: coding theory

Author: David Lucas

Branch/Commit: 2b6875a

Reviewer: Clément Pernet

Issue created by migration from https://trac.sagemath.org/ticket/19930

[sagetrac-dlucas]

Branch: u/dlucas/hamming_code

[sagetrac-dlucas]

comment:2

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

Alongside with the new classes, I also made the (very small) following changes:

• an isinstance test in codecan/autgroup_can_label.pyx was based on the old API and thus was only working with instances of class LinearCode. I changed it so it works now with any linear code, specific code families included.

• the method __cmp__ in AbstractLinearCode was quite useless (imho), so I removed it.

David

---

New commits:

25707e7	Cleaned up index of modules
4bb269a	Merge branch 'cleanup_index_coding' into hamming_code
c8c9cc9	Added a new encoder based on parity check matrix
23c12cb	New class for Hamming codes
c92e42c	Fixed broken doctests in codecan folder, and changed an old insinstance test
3b48dcb	Fixed broken doctests, removed `__cmp__` method

[sagetrac-dlucas]

Author: David Lucas

[sagetrac-dlucas]

Commit: 3b48dcb

[sagetrac-git]

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

a2177eb

Fixed import related to Hamming code in graphs/generators/smallgraphs.py

[sagetrac-git]

Changed commit from 3b48dcb to a2177eb

[sagetrac-git]

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

cc237db	Update to 7.1beta0
cc49f28	Added references for computation of parity check matrix in non-binary field

[sagetrac-git]

Changed commit from a2177eb to cc49f28

[sagetrac-dlucas]

comment:5

I updated this ticket to latest beta.
I also added a note on parity_check_matrix method which points to some references on how to build Hamming codes over anything else than a binary field, as this is definitely non-standard.

Also note that with this ticket, the implementation of codes.LinearCodeFromCheckMatrix can be improved so it does not rely on the dual code but on the encoder introduced here (which saves computation at construction time). See follow-up ticket #19975 for this issue.

---

New commits:

cc237db	Update to 7.1beta0
cc49f28	Added references for computation of parity check matrix in non-binary field

[sagetrac-git]

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

ca8396a

Updated to 7.1beta1 and fixed merge conflict

[sagetrac-git]

Changed commit from cc49f28 to ca8396a

[sagetrac-git]

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

055be55

Updated to 7.1beta3 and fixed conflicts

[sagetrac-git]

Changed commit from ca8396a to 055be55

[sagetrac-dlucas]

comment:8

I updated to latest beta and fixed merge conflicts. This is still open for review.

[sagetrac-git]

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

f8807be

Changed deprecated imports

[sagetrac-git]

Changed commit from 055be55 to f8807be

[sagetrac-git]

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

0dff97b

Updated to 7.1beta5 and fixed conflict

[sagetrac-git]

Changed commit from f8807be to 0dff97b

[sagetrac-dlucas]

comment:12

I updated to latest beta and fixed merge conflict. This is still open for review.

[ClementPernet]

comment:14

When comparing 2 Hamming codes in docstrings, you replaced the code comparaison by a comparison on the echelon form of their respective generating matrices.

I suggest to avoid calling directly echelon_form method, and rather compare their systematic generator matrices (which is equivalent but seems clearer).

C1.generator_matrix_systematic()==C2.generator_matrix_systematic()

[ClementPernet]

comment:15

lines 156 to 161 of hamming_code.py: this code seems very odd to me. I do not see what you are trying to do here.

• the two branches of the if then else block are identical.
• The series of swaps being performed result in a cyclic rotation of the first m/2 rows and the last one. Is this really what is intended?

If, as I presume, you're trying to simply flip the order of the rows, then, try something like

H = H[::-1,:]

[ClementPernet]

comment:16

The rest of the modifications are ok to me. So once these 2 issues have been addressed, I'll be happy to give a positive review.

[ClementPernet]

Reviewer: Clément Pernet

[sagetrac-git]

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

99e5bf9	Update to latest beta
bd7ee36	Small changes to doctests
2b6875a	Made code in parity-check_matrix smaller

[sagetrac-git]

Changed commit from 0dff97b to 2b6875a

[sagetrac-dlucas]

comment:18

Hello,

I made the changes.

I also removed a test from AbstractLinearCode's __eq__ which was comparing the matrices of two codes. As it was not testing __eq__ for codes at all, I simply deleted it.

David

[ClementPernet]

comment:19

All good. Positive review.

[vbraun]

Changed branch from u/dlucas/hamming_code to 2b6875a