An unknown encoding device for a binary linear block code has 4 bits of input-data pins and 8 bits of output data pins. If we send the messages
$$u_1=(1 1 0 0),\, u_2=(1010),\, u_3=(1001),\, u_4=(0001).$$
to the input, we can observe the following corresponding output vectors
$$x_1=(10101010),\, x_2=(11001100),\, x_3=(11110000),\, x_4=(00001111).$$
(1) Find the generator matrix $\mathbf G $,and parity check matrix $\mathbf H$.
(2) Decode the following received vectors on a binary symmetric channel (with a crossover probability $ < 1/2$) by using syndrome decoding:
$$_1 = (01101011),\,_2 = (00010110).$$
(3) Decode again using the maximum-likelihood decoding.
For the question (1),my formula is as below
$\mathbf C=\mathbf M \mathbf G$,so $$\begin{align} \mathbf C & = \mathbf M \mathbf G \\ \begin{bmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0\\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\ \end{bmatrix} & = \begin{bmatrix} 1 & 2 & 2 \\ 2 & 3 & 4 \\ 4 & 4 & 2 \\ \end{bmatrix} \times \mathbf G\\ \mathbf M^{-1} \times \mathbf C& =\mathbf G \\ \begin{bmatrix} 1 & 1 & 1 & 1 & -1 & -1 & -1 & -1\\ 0 & -1 & 0 & -1 & 2 & 1 & 2 & 1\\ 0 & 0 & -1 & -1 & 2 & 2 & 1 & 1\\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\ \end{bmatrix} &= \mathbf G \end{align}$$
I am not very sure about it,because i know $\mathbf G = [\mathbf F | \mathbf I]$,$\mathbf F$ is coefficient matrix and $\mathbf I$ is identity matrix,and $\mathbf H = [\mathbf I | \mathbf F^T]$. However, i can't let the second half of $\mathbf G$ become $\mathbf I$,so i wonder that is my calculation and thinking right?
About the (2) and (3),i have know idea how to calculate it,can anyone teach me?
Question (1):
If $C$ is a code in $\mathbb{Z}_2^8$, then the generator matrix $G\in\mathbb{Z}_2^{4\times 8}$ is defined by $$C=\{aG\mid a\in\mathbb{Z}_2^4\}.$$ To find the generator matrix, you take the standard basis $e_1,\dots,e_4$ of the vector space $\mathbb{Z}_2^4$, express the input vectors $u_1,\dots,u_4$ using this basis and compute the rows of $G$. Here, we have \begin{align} u_1&=e_1+e_2,\\ u_2&=e_1+e_3,\\ u_3&=e_1+e_4,\\ u_4&=e_4. \end{align} Since $u_4G=x_4$ and $u_4=e_4=(0,0,0,1)$, we immediately get the fourth row of $G$, which is $x_4$. Thus, we have $e_4G=x_4$ and since $x_3=u_3G=e_1G+e_4G=e_1G+x_4$, we then obtain $e_1G=x_3+x_4$, i.e., we also have the first row of $G$. Analogously, we get the second and third row of $G$. In summary, we have $$G=\begin{pmatrix} 1&1&1&1&1&1&1&1\\ 0&1&0&1&0&1&0&1\\ 0&0&1&1&0&0&1&1\\ 0&0&0&0&1&1&1&1 \end{pmatrix}.$$ The echelon form of $G$ is $$\begin{pmatrix} 1&0&0&1&0&1&1&0\\ 0&1&0&1&0&1&0&1\\ 0&0&1&1&0&0&1&1\\ 0&0&0&0&1&1&1&1 \end{pmatrix}.$$ If the generator matrix has the form $[I_4\mid P]$, where $P$ is a $4\times 4$ matrix in this case, then we say that $G$ is in standard form. If you have this form, then you can get the parity check matrix $H$ with $H=[-P^T|I_4]$. But not all generator matrices are in standard form as you can see in this example. Therefore, we use a little trick and swap columns in the echelon form of $G$ to obtain $\widetilde{G}$, which is in standard form. Thus, we swap the third and fourth column to get $$\widetilde{G}=\begin{pmatrix} 1&0&0&0&1&1&1&0\\ 0&1&0&0&1&1&0&1\\ 0&0&1&0&1&0&1&1\\ 0&0&0&1&0&1&1&1 \end{pmatrix},$$ which has the desired form $[I_4|P]$. Hence, we obtain the corresponding parity check matrix $\widetilde{H}$ with $$\widetilde{H}=\begin{pmatrix} 1&1&1&0&1&0&0&0\\ 1&1&0&1&0&1&0&0\\ 1&0&1&1&0&0&1&0\\ 0&1&1&1&0&0&0&1 \end{pmatrix}.$$ But this is not yet the parity check matrix we are looking for. Since we swapped the fourth and fifth column to obtain $\widetilde{G}$, we have to swap these columns in $\widetilde{H}$ to get $H$. Thus, we have $$H=\begin{pmatrix} 1&1&1&1&0&0&0&0\\ 1&1&0&0&1&1&0&0\\ 1&0&1&0&1&0&1&0\\ 0&1&1&0&1&0&0&1 \end{pmatrix}.$$