# How to calculate the generator matrix,parity check matrix and the maximum likelihood decoding

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?

• This math.stackexchange.com/a/1196428/296687 might be helpful for the syndrome decoding. – user160919 Aug 17 '18 at 14:55
• @user160919 The OP does not seem to understand very much about binary codes or arithmetic operations in the binary field (as evidenced by his so-called solution to part (1) and the additional questions asked by him with regard to our respective answers) and so the reference you provide for syndrome decoding is not going to be very useful to him, or at least not at this time. – Dilip Sarwate Aug 18 '18 at 15:08
• @DilipSarwate finally,i understand what are you explaining about,i will post a specific calculation processing later – Shine Sun Aug 18 '18 at 15:13
• @user160919 So the syndrome decoding is ,in fact, received vectors $\times H^T$?if the answer is 0 vector,the received signal itself is actually a codeword? – Shine Sun Aug 19 '18 at 12:10
• Yes, if $xH^T$ is the zero vector, then $x$ is a codeword. Do you see why? – user160919 Aug 21 '18 at 6:44

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}.$$
• What is your $\mathbf P$ matrix? – Shine Sun Aug 18 '18 at 15:37
• You said that $G=[I_4|P]$,but you use$\widetilde G =[I_4|P]$ after that.And it seems that $G$ is not equivalent to $\widetilde G$,why can you just change two column to build $[I_4|P]$,it should not legal in calculate the echelon form – Shine Sun Aug 18 '18 at 15:44
• i can't use the echelon form to let G become this ,can you write for more detail about it?$$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}.$$ – Shine Sun Aug 21 '18 at 11:46
• Do you mean that you can't compute the echelon form of $G$? – user160919 Aug 21 '18 at 12:05