02 - Hamming Codes (Implementation)

The preliminary requirements for this assignment:
1. Git installed (see Dev > Git),
2. Python installed (see Dev > Python),
3. The template cloned (see Dev > template),
4. The first assignment handed in (see Assignment 1 - Hamming Codes (Theory)).

In this assignment you’ll have to implement an encoder and decoder for a 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 occurs. Also, the implementation has to be done in Python using the template provided in ./src/hamming_code.py. You will implement and run the program on your computer.

Deadline for submission: Sunday, November 17th 2019, 23:59 // 11:59 pm
Please upload your solution into your own Gitlab repository.

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 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \end{matrix} \right) \]

Task 1

Do not use external packages like NumPy or other for matrices and vector arithmetic!
Everything can be done with simple plain python.

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 below the sub-tasks.
    Use row reduction and column/row swapping (we need all options this time).

    1. Use the pre-defined method __convert_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.

Transformation steps to implement

Task 2

Implement the encoder in the function encode() in ./src/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 odd 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 ./src/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 odd parity.

    2. Calculate the syndrome vector. Remove $p_{5}$ 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 ./src/test.py.

  1. First, import everything 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, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0)$

    2. $(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1)$

    3. $(1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0)$

    4. $(1, 1, 1, 1, 1, 0, 1, 1, 0, 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 for codes being corrected and for an uncorrectable code.

Do not exchange source code! Keep it private!
We do not tolerate plagiarism.
Plagiarism of any form will get you disqualified from the lab.