(6, 3) code from parity check matrix

For a systematic $(n,k)$ linear block code, $G=[I_k\mid P]$ and $H=[P^T\mid I_{n-k}]$, with $GH^T=0$. A codeword is $\mathbf{c}=\mathbf{m}G$, and for a received vector $\mathbf{r}$ the syndrome is $\mathbf{s}=\mathbf{r}H^T$. All arithmetic is modulo 2.

a) Generator matrix

$$H=\begin{bmatrix}1&0&1&1&0&0\\1&1&0&0&1&0\\0&1&1&0&0&1\end{bmatrix}=[P^T\mid I_3],\qquad P^T=\begin{bmatrix}1&0&1\\1&1&0\\0&1&1\end{bmatrix}$$

Transposing:

$$P=\begin{bmatrix}1&1&0\\0&1&1\\1&0&1\end{bmatrix},\qquad G=[I_3\mid P]=\begin{bmatrix}1&0&0&1&1&0\\0&1&0&0&1&1\\0&0&1&1&0&1\end{bmatrix}$$

b) Codeword for message 110

$$\mathbf{c}=\mathbf{m}G=1\cdot(100110)\oplus1\cdot(010011)\oplus0\cdot(001101)=110101$$

Parity bits directly: $p_1=m_1\oplus m_3=1\oplus0=1$, $p_2=m_1\oplus m_2=1\oplus1=0$, $p_3=m_2\oplus m_3=1\oplus0=1$.

Codeword = 110 101

Check: $\mathbf{c}H^T$: row 1: $1+0+0+1=0$, row 2: $1+1+0+0=0$, row 3: $1+0+0+1=0$. Syndrome $000$, so it is valid.

All codewords (for reference; $d_{min}=3$, corrects 1 error):

c) Check received word 110111

$$\mathbf{s}=\mathbf{r}H^T,\quad \mathbf{r}=(1\,1\,0\,1\,1\,1)$$

Each syndrome bit is one row of $H$ dotted with $\mathbf{r}$:

$$\mathbf{s}=(0\ 1\ 0)\neq\mathbf{0}$$

The syndrome is non-zero, so the received word has an error.

Locating it: $\mathbf{s}=010$ equals the 5th column of $H$ $(0,1,0)^T$, so assuming a single error, bit 5 is wrong: $\mathbf{e}=000010$.

$$\hat{\mathbf{c}}=\mathbf{r}\oplus\mathbf{e}=110111\oplus000010=110101$$

Answer: $G$ as above; codeword for 110 is 110101; received 110111 is in error (syndrome 010), corrected codeword 110101, message 110.