Add Hamming codes

[mhostetter]

No description provided.

[abhishekmittal15]

Hey, this seems like an old issue, but if its still relevant I would like to work on it.

[mhostetter]

@abhishekmittal15 thanks! Yes, it's been on my plate for a while, but I would still like to add it.

I am currently in a bit of a refactor of the galois._codes subpackage. That is happening in #413. In addition to generalizing BCH and RS codes, I'm trying to add general classes for linear and cyclic codes, see _linear.py and _cyclic.py. Any feedback on those classes is welcome as well. If I can fully generalize _LinearCode and _CyclicCode, then I might make them public classes and expose them in the public API.

I would recommend branching off of my generalize-bch-and-rs branch (https://github.com/mhostetter/galois/tree/generalize-bch-and-rs), adding a galois/_codes/_hamming.py file, and a Hamming class. Please report back here as often as you'd like with questions or design decisions. I'll be quick to respond.

[abhishekmittal15]

Hi @mhostetter, I am glad to work on this. I will definitely reach out in case of any queries. For now I will setup the development environment locally and in parallel have a look at the implementation of the other codes to get an idea as to how to go about constructing the Hamming class.

[abhishekmittal15]

Theory

I am referring to this to gain more insights about the general version of Hamming Codes.
If we are given the redundancy $r$ and the field size $q$ then the general Hamming code is a linear code $(\frac{q^r -1}{q - 1},\frac{q^r -1}{q-1}-r,3)$
The parity check matrix of the code is just the collection of all non zero columns(r length vector) belonging to $F_q^{r}$.
We can rewrite the parity check matrix in the systematic form and then convert it to a generator matrix, using the below transformation.
$$H = [P_T|I_{n−k}]$$, then
$$G = [I_k|P]$$
So I think this can be implemented. We can detect errors by finding the syndrome from the parity check matrix. I need to have a look at the decoding and figure out how I will do it

Design Proposal for Hamming Class (Imitated the code structure from the other implementations of codes in galois/src/_codes)

I think we can first start implementing it out for binary fields $F_2$ and then extend it to $F_p$ and then finally generalize it to $F_{q^n}$
Parameters
q: Field size.
r: Redundancy. Hamming code will be $(\frac{q^r -1}{q - 1},\frac{q^r -1}{q-1}-r,3)$ for field $F_q$
Properties
n: Block length which is $\frac{q^r -1}{q - 1}$
k: Message length which is $\frac{q^r -1}{q-1}-r$
d_min: Minimum Hamming distance which is a constant(3)
H: Parity check matrix of the code, for now I will generate this by brute forcing over all vectors of the vector space $F_q^r$.
G: Generator matrix of the code. From the galois/_codes/_linear.py I will use the parity_check_to_generator_matrix function to get G.
Functions
encode: Takes a message vector (np.array of size $k$ and elements belong to $F_q$) and returns the Generator Matrix applied on the message
decode: Takes a codeword vector(np.array of size $n$ and elements belong to $F_q$) and returns the message vector. [Need to figure this out]
detect: Takes a codeword vector(np.array of size $n$ and elements belong to $F_q$) , applies the parity check matrix on it and returns an error detected or not based on the obtained syndrome[Here should we return the number of errors we detected also?, this might not be accurate though, because this code ca t detect more than 2 errors].

Additional Feature

Extended Hamming codes. So an extended hamming code is adding an extra bit to the codeword to increase the $d_{min}$ to 4. So the new code is $(\frac{q^r-1}{q-1}+1, \frac{q^r-1}{q-1}-r, 4)$. The parity check matrix now is the original one but an extra zero vector added before the first column and ones vector added as the last row. We can probably take a flag extended as a parameter and based on that construct our generator and parity check matrices.

Let me know your opinions on this @mhostetter, if the design proposal looks fine, I can start implementing it.

Apologies, as the paper I am referring to above is quite condensed so for any theory I have mentioned above I couldnt post any references

[mhostetter]

If we are given ... So I think this can be implemented.

Yes, I agree with the theory you've laid out.

I think we can first start implementing it out for binary fields and then extend it to Fp and then finally generalize it to Fqn

I agree with this approach. Your design approach is very much in line with what I was thinking too. Just a few minor comments below.

Parameters

We can start with __init__(self, q, r), but I would eventually like to be able to construct the code using either (n, k) or code-specific parameters (in this case r and extended). Here is my thought on the __init__ signature.

class Hamming(_LinearCode):
    def __init__(
        self,
        n: int | None = None,
        k: int | None = None,
        field: Type[FieldArray] = GF2,
        r: int | None = None,
        extended: bool = False,
        systematic: bool = True,
    ):
        if n is not None and k is not None:
            # Infer (r, extended) from (n, k, field)
        elif r is not None:
            # Infer (n, k) from (field, r, extended)
        else:
            raise ValueError

So then for binary Hamming codes you could have these call signatures.

galois.Hamming(7, 4)  # Infers r=3 and extended=False
galois.Hamming(8, 4)  # Infers r=3 and extended=True
# OR
galois.Hamming(r=3)  # Infers n=7 and k=4
galois.Hamming(r=3, extended=True)  # Infers n=8 and k=4

And eventually for q-ary Hamming codes, you could have these call signatures.

GF = galois.GF(3)  # This is GF(q)
galois.Hamming(40, 36, field=GF)  # Infers r=4 and extended=False
galois.Hamming(41, 36, field=GF)  # Infers r=4 and extended=True
# OR
galois.Hamming(field=GF, r=4)  # Infers n=40 and k=36
galois.Hamming(field=GF, r=4, extended=True)  # Infers n=41 and k=36

Properties

I basically agree with the ones you listed. I would say keep all the properties from _LinearCode and add r and is_extended (which are two Hamming-specific properties).

A tip: I created a little hack to extend a parent docstring in a child method. It's kind of hacky but it's the only way I could get extended docstrings in children (without modifying the parent) and have them correctly displayed in VS Code (or other IDEs). If you have other ideas, I'm open to them. Below is an example.

Inheriting from _LinearCode

If you inherit from _LinearCode, you should only need to define these abstract methods. If you look through the _LinearCode class, you'll see that encode(), detect(), and decode() call these methods in a standard way.

class Hamming(_LinearCode):

    def _convert_codeword_to_message(self, codeword: FieldArray) -> FieldArray:
        pass

    def _convert_codeword_to_parity(self, codeword: FieldArray) -> FieldArray:
        pass

    def _decode_codeword(self, codeword: FieldArray) -> Tuple[FieldArray, np.ndarray]:
        pass

[abhishekmittal15]

Yes I think your design of the __init__ function is more user friendly, as what q and r is, might not be known to all. I will keep the points you mentioned in mind. Thanks for the suggestions!

[abhishekmittal15]

Hey @mhostetter. Sorry for having to leave my work unfinished, can I still continue working on it if its not taken up by somebody else?

[mhostetter]

Yeah, sure. I have a version I worked on, but it's incomplete. If you get something working, we can merge it in.

[abhishekmittal15]

Ohh great, is your version pushed onto any of the branches, then maybe I can continue off of that

[mhostetter]

No, it's not pushed anywhere. Might be best to start fresh. Use the other FEC codes as an exemplar.

[abhishekmittal15]

Okay, should I branch off from release/0.3x or master?

[mhostetter]

release/0.3.x. Thanks.