Problem 8 - Information Theory

Consider a 6-dimensional vector $\boldsymbol{x}$ and a matrix

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

on $GF(2) = \mathbb{Z}_2$.

1.

Find a $3 \times 6$ matrix $G$ satisfying $HG^T = 0$.

2.

Enumerate all $\boldsymbol{x}$ satisfying $H \boldsymbol{x} = 0$.

3.

Show that $\{ \boldsymbol{x} \; \vert \; H \boldsymbol{x} = 0 \}$ is a subgroup in the 6-dimensional space $GF(2)$ with respect to addition, and compute the decomposition into cosets.

According to the particular form of $H$, we can say that this is a parity-check matrix and that we are asking to find the correspondent generator matrix $G$ which verifies the parity-check theorem: $HG^T = 0$. If $H = \left[ I_{r \times r} \; \vert \; -P^T \right]$, then $G = \left[ P_{k \times r} \; \vert \; I_{k \times k}\right]$, where the matrix $P$ is called the parity-bit generator.

$$H G^T = \left( \begin{tabular}{cccccc} 1 & 0 & 0 & 1 & 0 & 1 \\ ... ...abular}{ccc} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{tabular} \right)$$

The vectors $\boldsymbol{x}$ satisfying $H \boldsymbol{x} = 0$ are given by:

$$H \boldsymbol{x} = \left( \begin{tabular}{cccccc} 1 & 0 & 0 & 1 &... ...\right) = \left( \begin{tabular}{c} 0 \\ 0 \\ 0 \\ \end{tabular} \right),$$

i.e.

$$\begin{tabular}{cccccc} $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$ & $... ... 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ \end{tabular}$$

We can check that

1.

$000000 \in C$;

2.

$(\forall x,y \in C^2)(x+y \in C)$;

3.

$(\forall x \in C)(\exists y \in C)(x+y=0)$.

Therefore, $C$ is a subgroup of $GF(2)^6$ whose decomposition in coset occording to $C$ is

$$\begin{tabular}{c\vert cccccc \vert c\vert cccccc} coset & $x_1$ ... ...0 & 1 \\ & 1 & 0 & 0 & 0 & 0 & 0 & & 1 & 0 & 1 & 0 & 0 & 0 \\ \end{tabular}$$