Opened 6 years ago
Closed 6 years ago
#19930 closed enhancement (fixed)
A proper class for Hamming codes
Reported by:  dlucas  Owned by:  

Priority:  major  Milestone:  sage7.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, GitHub, GitLab)  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 6 years ago by
 Branch set to u/dlucas/hamming_code
comment:2 Changed 6 years ago by
 Commit set to 3b48dcb4a7a10e578dfa5ae277191dafcece83ff
 Status changed from new to needs_review
comment:3 Changed 6 years ago by
 Commit changed from 3b48dcb4a7a10e578dfa5ae277191dafcece83ff to a2177eb9f5c401bc433bd81c94cbc0ea97ed321b
Branch pushed to git repo; I updated commit sha1. New commits:
a2177eb  Fixed import related to Hamming code in graphs/generators/smallgraphs.py

comment:4 Changed 6 years ago by
 Commit changed from a2177eb9f5c401bc433bd81c94cbc0ea97ed321b to cc49f28e7e3b2de8088d472588167034168820bb
comment:5 Changed 6 years ago by
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 nonstandard.
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 followup ticket #19975 for this issue.
New commits:
cc237db  Update to 7.1beta0

cc49f28  Added references for computation of parity check matrix in nonbinary field

comment:6 Changed 6 years ago by
 Commit changed from cc49f28e7e3b2de8088d472588167034168820bb to ca8396a9968a77a55025217aed2ff2e7eb164bf7
Branch pushed to git repo; I updated commit sha1. New commits:
ca8396a  Updated to 7.1beta1 and fixed merge conflict

comment:7 Changed 6 years ago by
 Commit changed from ca8396a9968a77a55025217aed2ff2e7eb164bf7 to 055be557ec49c3ef1fbc9a6f7367487e0df63baf
Branch pushed to git repo; I updated commit sha1. New commits:
055be55  Updated to 7.1beta3 and fixed conflicts

comment:8 Changed 6 years ago by
I updated to latest beta and fixed merge conflicts. This is still open for review.
comment:9 Changed 6 years ago by
 Commit changed from 055be557ec49c3ef1fbc9a6f7367487e0df63baf to f8807bed026d67ad62aaad84ccc70c99464a274a
Branch pushed to git repo; I updated commit sha1. New commits:
f8807be  Changed deprecated imports

comment:10 Changed 6 years ago by
 Cc wdj ppurka added
comment:11 Changed 6 years ago by
 Commit changed from f8807bed026d67ad62aaad84ccc70c99464a274a to 0dff97b48d12b6d2caf4917a20b6d51feca24b7d
Branch pushed to git repo; I updated commit sha1. New commits:
0dff97b  Updated to 7.1beta5 and fixed conflict

comment:12 Changed 6 years ago by
I updated to latest beta and fixed merge conflict. This is still open for review.
comment:13 Changed 6 years ago by
 Cc cpernet added
comment:14 Changed 6 years ago by
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 6 years ago by
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 6 years ago by
 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 6 years ago by
 Commit changed from 0dff97b48d12b6d2caf4917a20b6d51feca24b7d to 2b6875adf5689fd87a0d9bc74fce262a5ca18be5
comment:18 Changed 6 years ago by
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 6 years ago by
 Status changed from needs_review to positive_review
All good. Positive review.
comment:20 Changed 6 years ago by
 Branch changed from u/dlucas/hamming_code to 2b6875adf5689fd87a0d9bc74fce262a5ca18be5
 Resolution set to fixed
 Status changed from positive_review to closed
I pushed the patch, this is now open for review.
Alongside with the new classes, I also made the (very small) following changes:
isinstance
test incodecan/autgroup_can_label.pyx
was based on the old API and thus was only working with instances of classLinearCode
. I changed it so it works now with any linear code, specific code families included.__cmp__
inAbstractLinearCode
was quite useless (imho), so I removed it.David
New commits:
Cleaned up index of modules
Merge branch 'cleanup_index_coding' into hamming_code
Added a new encoder based on parity check matrix
New class for Hamming codes
Fixed broken doctests in codecan folder, and changed an old insinstance test
Fixed broken doctests, removed __cmp__ method