Improve implementation of BinaryHammingCode decoder
The current BinaryHammingCode decoding function works correctly but is slower than necessary: whenever it flips a bit, it recomputes the entire syndrome.
Rather, it could compute the syndrome to begin with, and then just search for the position whose corresponding column in the parity check matrix matches that syndrome (that position must be the one to flip to make the entire syndrome zero).
Comments (6)
-
reporter -
repo owner There's no specific decoder for Binary Hamming codes anymore. Should I reimplement it? Not sure it's necessary as the class actually build Hamming codes over GF(q), so it's a very specific decoder. Your call.
-
reporter Asymptotically, the syndrome decoder instantiated to correct 1 error has the correct running time. I vote for that solution. Is that the current one?
-
repo owner Not exactly.
HammingCode
's default decoder is theSyndrome
decoder indeed, butmaximum_error_rate
defaults ton-k
.So the instance of the decoder created by
HammingCode.decode_to_code(word)
is not instantiated with 1 error.I can override
decode_to_code
for Hamming codes to default to this behaviour though. -
reporter Hmm, that's a good question. Since the covering radius of Hamming codes is known and is 1, then once the
covering_radius_upper_bound
stuff is in place, theSyndromeDecoder
should by itself just correct 1 error. That speaks against doing something special forHammingCode
now. However, theupper/lower_bound
stuff might be in the far future, which speaks for making an easy fix forHammingCode
in this instance.I vote for not doing anything for Hamming code for now. Due to the early-termination you implemented in
SyndromeDecoder
, the table building will already only check radius 2 in vain, which means the complexity becomes O(q^2) instead of O(q). I'm ok with that for the time being. -
repo owner - changed status to resolved
I agree. So I close this issue.
- Log in to comment
See also
#74