Opened 3 years ago

Closed 3 years ago

#19930 closed enhancement (fixed)

A proper class for Hamming codes

Reported by: dlucas Owned by:
Priority: major Milestone: sage-7.1
Component: coding theory Keywords:
Cc: wdj, ppurka, cpernet Merged in:
Authors: David Lucas Reviewers: Clément Pernet
Report Upstream: N/A Work issues:
Branch: 2b6875a (Commits) Commit: 2b6875adf5689fd87a0d9bc74fce262a5ca18be5
Dependencies: Stopgaps:

Description

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.

Change History (20)

comment:1 Changed 3 years ago by dlucas

  • Branch set to u/dlucas/hamming_code

comment:2 Changed 3 years ago by dlucas

  • Authors set to David Lucas
  • Commit set to 3b48dcb4a7a10e578dfa5ae277191dafcece83ff
  • Status changed from new to needs_review

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:

25707e7Cleaned up index of modules
4bb269aMerge branch 'cleanup_index_coding' into hamming_code
c8c9cc9Added a new encoder based on parity check matrix
23c12cbNew class for Hamming codes
c92e42cFixed broken doctests in codecan folder, and changed an old insinstance test
3b48dcbFixed broken doctests, removed __cmp__ method

comment:3 Changed 3 years ago by git

  • Commit changed from 3b48dcb4a7a10e578dfa5ae277191dafcece83ff to a2177eb9f5c401bc433bd81c94cbc0ea97ed321b

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

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

comment:4 Changed 3 years ago by git

  • Commit changed from a2177eb9f5c401bc433bd81c94cbc0ea97ed321b to cc49f28e7e3b2de8088d472588167034168820bb

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

cc237dbUpdate to 7.1beta0
cc49f28Added references for computation of parity check matrix in non-binary field

comment:5 Changed 3 years ago by dlucas

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:

cc237dbUpdate to 7.1beta0
cc49f28Added references for computation of parity check matrix in non-binary field

comment:6 Changed 3 years ago by git

  • Commit changed from cc49f28e7e3b2de8088d472588167034168820bb to ca8396a9968a77a55025217aed2ff2e7eb164bf7

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

ca8396aUpdated to 7.1beta1 and fixed merge conflict

comment:7 Changed 3 years ago by git

  • Commit changed from ca8396a9968a77a55025217aed2ff2e7eb164bf7 to 055be557ec49c3ef1fbc9a6f7367487e0df63baf

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

055be55Updated to 7.1beta3 and fixed conflicts

comment:8 Changed 3 years ago by dlucas

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

comment:9 Changed 3 years ago by git

  • Commit changed from 055be557ec49c3ef1fbc9a6f7367487e0df63baf to f8807bed026d67ad62aaad84ccc70c99464a274a

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

f8807beChanged deprecated imports

comment:10 Changed 3 years ago by jsrn

  • Cc wdj ppurka added

comment:11 Changed 3 years ago by git

  • Commit changed from f8807bed026d67ad62aaad84ccc70c99464a274a to 0dff97b48d12b6d2caf4917a20b6d51feca24b7d

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

0dff97bUpdated to 7.1beta5 and fixed conflict

comment:12 Changed 3 years ago by dlucas

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

comment:13 Changed 3 years ago by cpernet

  • Cc cpernet added

comment:14 Changed 3 years ago by cpernet

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()

comment:15 Changed 3 years ago by cpernet

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,:]

comment:16 Changed 3 years ago by cpernet

  • Reviewers set to Clément Pernet

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.

comment:17 Changed 3 years ago by git

  • Commit changed from 0dff97b48d12b6d2caf4917a20b6d51feca24b7d to 2b6875adf5689fd87a0d9bc74fce262a5ca18be5

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

99e5bf9Update to latest beta
bd7ee36Small changes to doctests
2b6875aMade code in parity-check_matrix smaller

comment:18 Changed 3 years ago by dlucas

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

comment:19 Changed 3 years ago by cpernet

  • Status changed from needs_review to positive_review

All good. Positive review.

comment:20 Changed 3 years ago by vbraun

  • Branch changed from u/dlucas/hamming_code to 2b6875adf5689fd87a0d9bc74fce262a5ca18be5
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.