Finding code words given generator matrix and constructing syndrome table

Question

Given a ternary (3,2) code with generator matrix $$ \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \\ \end{pmatrix} $$ Write down the Code words and thus construct table of coset leaders and their syndromes.

Answer 1

In a $(n,k)$ binary linear block code, the generator matrix $G$ specifies the codewords of the code $C$ by $C\equiv\{\bar{c}\in\mathbb{F}_3^n:\bar{c}=Gc,c\in\mathbb{F}_3^k\}$, consequently, the codewords of the presented code will be

• $c_1=\begin{pmatrix}0 \\ 0\end{pmatrix}\rightarrow\bar{c}_1=\begin{pmatrix}1 & 0 \\ 0 & 1 \\ 1 & 1\end{pmatrix}\begin{pmatrix}0 \\ 0\end{pmatrix}=\begin{pmatrix}0 \\ 0 \\ 0\end{pmatrix}$

• $c_2=\begin{pmatrix}1 \\ 0\end{pmatrix}\rightarrow\bar{c}_2=\begin{pmatrix}1 & 0 \\ 0 & 1 \\ 1 & 1\end{pmatrix}\begin{pmatrix}1 \\ 0\end{pmatrix}=\begin{pmatrix}1 \\ 0 \\ 1\end{pmatrix}$

• $c_3=\begin{pmatrix}0 \\ 1\end{pmatrix}\rightarrow\bar{c}_3=\begin{pmatrix}1 & 0 \\ 0 & 1 \\ 1 & 1\end{pmatrix}\begin{pmatrix}0 \\ 1\end{pmatrix}=\begin{pmatrix}0 \\ 1 \\ 1\end{pmatrix}$

• $c_4=\begin{pmatrix}1 \\ 1\end{pmatrix}\rightarrow\bar{c}_4=\begin{pmatrix}1 & 0 \\ 0 & 1 \\ 1 & 1\end{pmatrix}\begin{pmatrix}1 \\ 1\end{pmatrix}=\begin{pmatrix}1 \\ 1 \\ 2\end{pmatrix}$

• $c_5=\begin{pmatrix}2 \\ 0\end{pmatrix}\rightarrow\bar{c}_5=\begin{pmatrix}1 & 0 \\ 0 & 1 \\ 1 & 1\end{pmatrix}\begin{pmatrix}2 \\ 0\end{pmatrix}=\begin{pmatrix}2 \\ 0 \\ 2\end{pmatrix}$

• $c_6=\begin{pmatrix}0 \\ 2\end{pmatrix}\rightarrow\bar{c}_6=\begin{pmatrix}1 & 0 \\ 0 & 1 \\ 1 & 1\end{pmatrix}\begin{pmatrix}0 \\ 2\end{pmatrix}=\begin{pmatrix}0 \\ 2 \\ 2\end{pmatrix}$

• $c_7=\begin{pmatrix}2 \\ 2\end{pmatrix}\rightarrow\bar{c}_7=\begin{pmatrix}1 & 0 \\ 0 & 1 \\ 1 & 1\end{pmatrix}\begin{pmatrix}2 \\ 2\end{pmatrix}=\begin{pmatrix}2 \\ 2 \\ 1\end{pmatrix}$

• $c_8=\begin{pmatrix}2 \\ 1\end{pmatrix}\rightarrow\bar{c}_8=\begin{pmatrix}1 & 0 \\ 0 & 1 \\ 1 & 1\end{pmatrix}\begin{pmatrix}2 \\ 1\end{pmatrix}=\begin{pmatrix}2 \\ 1 \\ 0\end{pmatrix}$

• $c_9=\begin{pmatrix}1 \\ 2\end{pmatrix}\rightarrow\bar{c}_9=\begin{pmatrix}1 & 0 \\ 0 & 1 \\ 1 & 1\end{pmatrix}\begin{pmatrix}1 \\ 2\end{pmatrix}=\begin{pmatrix}1 \\ 2 \\ 0\end{pmatrix}$

Now to get the syndrome table with the coset leaders, the parity check matrix of the code must be obtained, that is the matrix that $H^TG=0$, that in this case is

$H=\begin{pmatrix}2 \\ 2 \\ 1\end{pmatrix}$

Now the syndrome of a received vector is defined as $s = x^TH$, so for the case of this code, it will just be scalar value. The syndrome cosets then will be one for the vectors $x$ that have syndrome $0$, which by definition of the parity check matrix will be the set of codewords, while the other two cosests will be those of syndrome $1$ or $2$. The coset leader is defined as the words with smallest weight inside the coset, so

• $(s=0)$-Coset $\rightarrow$ coset leader $\begin{pmatrix}0 \\ 0 \\ 0\end{pmatrix}$

• $(s=1)$-Coset $\rightarrow$ coset leader $\begin{pmatrix}0 \\ 0 \\ 1\end{pmatrix}$

• $(s=2)$-Coset $\rightarrow$ coset leader $\begin{pmatrix}1 \\ 0 \\ 0\end{pmatrix}$

Note that there can be various coset leaders, as a coset may contain several words with the same weight, then you just chose one, as I have done here.

Note also that the notation that I have used for the derivtion of the things here is transposed compared with the standard notation of linear codes, where the generator matrix is defined as an $(k,n)$ matrix, and not as you did with the $(n,k)$ matrix. I did it this way basing on the input you gave for solving the problem. However, both formulations are equivalent one considering the words to be column vectors and the other as row vectors, so there is no conflict on solving the problem with the notation presented here.