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