Linear Codes : Error detection

432 Views Asked by At

The code words of a linear code $C$ have the length $n=5$.

Writing the code words into a matrix to get the linear independent ones, we get the following: \begin{equation*}\begin{pmatrix}0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0\end{pmatrix}\rightarrow \ldots \rightarrow \begin{pmatrix}1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0\end{pmatrix}\end{equation*}

So the dimension of $C$ is $m=2$.

Wir have also the minimum distance $d(C) =3$.

The generator matrix of $C$ is \begin{equation*}G=\begin{pmatrix}1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \end{pmatrix}\end{equation*}

The canonical generator matrix is \begin{equation*}G'=\begin{pmatrix}1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 \end{pmatrix}\end{equation*}

And the canonical parity check matrix is \begin{equation*}H'=\begin{pmatrix}1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1\end{pmatrix}\end{equation*}

Now there is the following question:

How many errors are at least detected at the code $C$ if $11100$ is received?

Could you give me a hint for that?

1

There are 1 best solutions below

8
On

It's easy enough by hand in this case: we only have 4 code words (dimension 2 over binary and $2^2=4$) all of which are enumerated in your first matrix as its rows. We have received $r=11100$. Compute the distances to the code words:

$$d(00000,r)=3, d(01101,r)=2, d(10111,r)=3, d(11010,r)=2$$, so we detect (at least) $2$ errors. ($2$ being the most likely tpyically). We cannot correct $r$ because there are two code words at distance $2$. Minimum distance $3$ tells us we can correct 1 error and detect at most 2.