We have the code words 111000, 100110, 110101 which result in the following generator matrix.
$G=\begin{bmatrix}1&1&1&0&0&0\\1&0&0&1&1&0 \\ 1&1&0&1&0&1\end{bmatrix}$
According to my book, the rows of the control matrix are solution vectors of the system of equations whose rows are formed by the base of the given code, i.e.
\begin{eqnarray} y_1 + y_2 + y_3 = 0\\ y_1 + y_4 + y_5 = 0 \\ y_1 + y_2 + y_4 + y_6 = 0 \\ \end{eqnarray}
If we choose $y_1$, $y_2$ und $y_4$ as free variables, we get the rows of the following matrix as the basis of the solution space:
$H=\begin{bmatrix}1&0&1&0&1&1\\0&1&1&0&0&1 \\ 0&0&0&1&1&1\end{bmatrix}$ where columns 1, 2 and 4 are the identity matrix.
- Why are the colums 1, 2 and 4 the identity matrix?
- How did he use the generator matrix to obtain the parity check matrix?
- Why did he choose $y_1$, $y_2$ und $y_4$ and what does this mean?
I thought the way to get the parity check matrix is the following:
If the generator matrix is in the form $G = [I_k | P]$, then its parity check matrix is $H = [P^T | I_{n-k}]$
So we swap columns 1&3, 2&5 and 3&6
$G'=\begin{bmatrix}1&0&0&0&1&1\\0&1&0&1&0&1 \\ 0&0&1&1&1&1\end{bmatrix}$
$H'=\begin{bmatrix}0&1&1&1&0&0\\1&0&1&0&1&0 \\ 1&1&1&0&0&1\end{bmatrix}$
Then we permutate it back (3&6, 2&5 and 1&3) and obtain:
$H= \begin{bmatrix}0&0&0&1&1&1\\0&1&1&0&0&1 \\ 1&0&1&0&1&1\end{bmatrix}$
Does it matter in which order the identity matrix appears?
Having the generator matrix in systematic form, that is $G=[I_k|P]$, has of course the advantage as stated, which is the easy construction of the parity check matrix $H=[P^T|I_{n-k}]$.
Consider any word $x$ as a row vector, then the syndrome $s=Hx^T=0$ if and only if $x$ is a codeword of the given linear code. Since $H$ is a $(n-k)\times n$ matrix, $x^T$ is a $n \times 1$ vector. It is easy to see, that swapping rows does not have any effect, but swapping columns changes the code, since bit positions are permuted.
Consider the valid codeword $100011$ (first row of $G'$). Using $H$ to check: $H\cdot \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 1 \\1\end{pmatrix}=\begin{pmatrix} 0 \\ 1 \\ 1\end{pmatrix}$, hence the syndrome is not equal to the zero vector. However, performing the same for $H'$ yields to $H'\cdot \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1\end{pmatrix}=\begin{pmatrix} 0 \\ 0 \\ 0\end{pmatrix}$ as intended.