Problem 5 - Information Theory

Let $\boldsymbol{x}$ be a 4-dimensional vector and $H$ be a $2 \times 4$ matrix on the field $GF(2)$ where $H$ is defined by:

$$H = \left( \begin{tabular}{cccc} 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ \end{tabular}\right).$$

Define a set $C$ by:

$$C = \{ \boldsymbol{x} \; \vert \; H \boldsymbol{x} = \boldsymbol{0}, \; \boldsymbol{x} \in GF(2)^4\}.$$

1.

Enumerate all elements in $C$.

2.

Regarding the 4-dimensional vector space on $GF(2)$ as an additive group, $C$ is its subgroup. Give the decomposition into cosets with respect to $C$, and describe briefly meaning of this decomposition from the viewpoint of information science.

$$\left( \begin{tabular}{cccc} 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ ... ...{tabular}\right) = \left( \begin{tabular}{c} 0 \\ 0 \\ \end{tabular}\right)$$

holds for:

$$\begin{tabular}{c c c c} $x_1$ & $x_2$ & $x_3$ & $x_4$ \\ \hlin... ... 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ \end{tabular}$$

Those elements are the (transposate vectors of the) vectors of $C$.

The four cosets are composed of the (transposate vectors of the) following vectors:

$$\begin{tabular}{c c c c \vert c c c c} \multicolumn{4}{c\vert}{co... ...1 & 1 & 1 & 0 \\ \multicolumn{4}{c\vert}{} & 1 & 0 & 0 & 1 \\ \end{tabular}$$

Assume that we want to send the information $10$. We can divide the $H$ matrix into two matrices:

$$H_1 = \left( \begin{tabular}{cc} 1 & 0 \\ 0 & 1 \\ \end{tabul... ...\; H_2 = \left( \begin{tabular}{cc} 1 & 1 \\ 0 & 1 \\ \end{tabular} \right)$$

$H_2 \left( \begin{tabular}{c} 1 \\ 0 \\ \end{tabular} \right) = \left( \begin{tabular}{c} 1 \\ 0 \\ \end{tabular}\right)$ gives us the bits which are sent with the information $10$ to check the validity of the received information. These bits are added to the information to form the sent package $1010$. When we received the information, we look for the coset in which it fits and we add the corresponding coset prefix. If the coset prefix is $0000$, it means that the information has not been altered; If the coset prefix is $0001$, it means that the fouth bit has been altered.