# 01 - Hamming Codes (Theory)

The first assignment will help you to understand how Hamming Codes work and how to convert the matrices.
Thus, we will have a deeper look onto the extended Hamming Code $(8, 4)$.
The code is capable of detecting a single-bit error and correct it and, by using an additional (overall) parity bit, it can detect (but not to correct) double-bit errors.

Create the non-systematic generator matrix $G_{4,8}'$ and the parity-check matrix $H'_{4,8}$.
Follow the rules for optimal codes from the Hamming Code specifications.

1. Construct $G'$ by adding the binary representation in the correct order (SEC-DED).
Each binary representation should have exactly $k$ bits with the least significant bit (LSB) at the bottom.
1. Mark the columns containing the parity bits with $p_{1} \cdots p_{r}$ and the data bits with $d_{1} \cdots d_{k}$.
2. Derive $H'$ from $G'$ considering the order of the data and parity bits.
Take into account that you need the transpose of the corresponding row bits from $G'$.
1. If not already done extend $H'$ to match the matrix definition $H'_{4,8}$.
2. Mark the columns holding the parity bits with $p_{1} \cdots p_{r}$ and the data bits with $d_{1} \cdots d_{k}$.

Create the systematic generator matrix $G_{4,8}$ and the parity-check matrix $H_{4,8}$.
Use your previously generated $G'_{4,8}$ as start matrix.

1. Convert $G'$ into standard form (RREF) using row-reduction only.
2. For each row, write down the calculation steps necessary for the conversion.
1. Write down the resulting matrix after each row processed.
3. Derive $H$ from $G$.
1. For both matrices, mark the columns holding the parity bits with $p_{1} \cdots p_{r}$ and the data bits with $d_{1} \cdots d_{k}$.

Encode the following words $\overrightarrow{a}$ using the non-systematic generator matrix $G'_{4,8}$ created in Task 1:

1. $\overrightarrow{a} = (0100)$
2. $\overrightarrow{a} = (1001)$
3. $\overrightarrow{a} = (0011)$
4. $\overrightarrow{a} = (1101)$

Since we use a SEC-DED code, the increased error detection capabilities are achieved by adding an overall parity bit that is calculated upon all $n$ bits of the encoded word. You can check your result against the parity table to see, if the values match for $p_{4}$ at the corresponding position.

Decode the following words $\overrightarrow{x}$ using the systematic parity-check matrix $H_{4,8}$ created in Task 2:

1. $\overrightarrow{x} = (11001101)$
2. $\overrightarrow{x} = (10011001)$
3. $\overrightarrow{x} = (11011011)$
4. $\overrightarrow{x} = (11010101)$

Were these words transmitted successfully? If this is not the case, write down the number of detected errors and attempt to correct them.
1. Check if the overall parity bit $p_{4}$ is correct.
2. Calculate the syndrome vector $\overrightarrow{z}$ and write down the matching pattern.