Improve implementation of BinaryHammingCode decoder

[Johan Rosenkilde]

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

[Johan Rosenkilde]

See also #74

[David Lucas]

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.

[Johan Rosenkilde]

Asymptotically, the syndrome decoder instantiated to correct 1 error has the correct running time. I vote for that solution. Is that the current one?

[David Lucas]

Not exactly. HammingCode's default decoder is the Syndrome decoder indeed, but maximum_error_rate defaults to n-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.

[Johan Rosenkilde]

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, the SyndromeDecoder should by itself just correct 1 error. That speaks against doing something special for HammingCode now. However, the upper/lower_bound stuff might be in the far future, which speaks for making an easy fix for HammingCode 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.

[David Lucas]

I agree. So I close this issue.