02 - Hamming Codes (Implementation)

In this assignment you’ll have to implement a customized systematic Hamming Code $(10, 6)$ with additional parity bit. The implementation has to be capable of encoding and decoding input words, detecting errors and correcting single-bit errors if they occur. Also, the implementation has to be done in Python using the template provided in ./hamming_code.py. You will implement and run the program on your computer.

Generator matrix

Use the following non-systematic generator matrix $G'_{6,10}$ for your implementation: \[ G' = \left( \begin{matrix} 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ \end{matrix} \right) \]

Task 1

Make yourself familiar with the project structure and classes, then do the following steps:

1. Add above matrix $G'_{6,10}$ to your class HammingCode.
2. Bring $G'_{6,10}$ into the systematic form through implementing and executing the transformation steps listed here.
   1. Use the pre-defined method __convert_to_g() for your implementation.
3. Derive $H_{4,10}$ from the generated matrix $G_{6,10}$.
   1. Use the pre-defined method __derive_h() for your implementation.

Task 2

Implement the encoder in the function encode() in ./hamming_code.py:

1. Add the missing logic for encoding given input words.
   Do not overwrite the existing signature of the method (tests depend on that).
2. Don’t forget to calculate and add the additional parity bit $p_{5}$ using even parity.
3. Make sure to return the final code as a Tuple and not as a List.
4. Test your implementation with unit-tests (see Task 4).

Task 3

Implement the decoder in the function decode() in ./hamming_code.py:

1. Add the missing logic for decoding given input words.
   Do not overwrite the existing signature of the method (tests depend on that).
   1. Calculate the additional parity bit of the encoded word using even parity.
   2. Calculate the syndrome vector without including $p_{5}$ (separate it beforehand).
   3. Check the syndrome vector against $H_{4,10}$ and conclude if the encoded word had an error.
      • If the encoded word was without an error, return the decoded word and VALID.
      • If the encoded word had a single error, return the corrected decoded word and CORRECTED.
      • If the encoded word had multiple errors, return None and UNCORRECTABLE.
2. Make sure to return the final code as a Tuple and not as a List.
3. Test your implementation with unit-tests (see Task 4).

Task 4

Now we are looking into unit-tests and update the file ./test_hamming_code.py.

1. First, import the subclasses needed from hamming_code.py.
2. For every given test case, implement the corresponding logic.
   Use asserts and pre-defined expectations (e.g. simple variable holding the value) for the checks.
3. Encode the following codes (you can check them in a single function):
   1. $(0, 1, 1, 0, 1, 1)$
   2. $(0, 0, 0, 0, 0, 0)$
   3. $(1, 0, 1, 1, 0, 1)$
   4. $(1, 1, 1, 1, 1, 0)$
4. Decode the following codes:
   1. $(0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0)$
   2. $(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1)$
   3. $(1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1)$
   4. $(1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1)$
5. Analyze the output.
   Does the output of decode() match the input of encode() before?
6. Bring up at least two more test cases (one for codes being corrected and one for an uncorrectable code).