Standard Generator Matrix for Linear Code/Examples/(4, 2) code in Z3/Example 1

From ProofWiki
Jump to navigation Jump to search

Example of Standard Generator Matrix for Linear Code

Let $G$ be the standard generator matrix:

$G := \begin{pmatrix} 1 & 0 & 2 & 1 \\ 0 & 1 & 1 & 2 \end{pmatrix}$


$G$ generates the linear code $C$:

$C = \set {0000, 0112, 0221, 1021, 1100, 1212, 2012, 2121, 2200}$


The minimum distance of $C$ is $2$, so $C$ detects $1$ transmission error and corrects $0$ transmission errors.


Proof

Multiplying $G$ by the $9$ vectors $00, 01, 02, 10, 11, 12, 20, 21, 22$ in turn gives:

\(\ds \begin{pmatrix} 0 & 0 \end{pmatrix} \begin{pmatrix} 1 & 0 & 2 & 1 \\ 0 & 1 & 1 & 2 \end{pmatrix}\) \(=\) \(\ds \begin{pmatrix} 0 & 0 & 0 & 0 \end{pmatrix}\)
\(\ds \begin{pmatrix} 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 2 & 1 \\ 0 & 1 & 1 & 2 \end{pmatrix}\) \(=\) \(\ds \begin{pmatrix} 0 & 1 & 1 & 2 \end{pmatrix}\)
\(\ds \begin{pmatrix} 0 & 2 \end{pmatrix} \begin{pmatrix} 1 & 0 & 2 & 1 \\ 0 & 1 & 1 & 2 \end{pmatrix}\) \(=\) \(\ds \begin{pmatrix} 0 & 2 & 2 & 1 \end{pmatrix}\)
\(\ds \begin{pmatrix} 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 0 & 2 & 1 \\ 0 & 1 & 1 & 2 \end{pmatrix}\) \(=\) \(\ds \begin{pmatrix} 1 & 0 & 2 & 1 \end{pmatrix}\)
\(\ds \begin{pmatrix} 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 2 & 1 \\ 0 & 1 & 1 & 2 \end{pmatrix}\) \(=\) \(\ds \begin{pmatrix} 1 & 1 & 0 & 0 \end{pmatrix}\)
\(\ds \begin{pmatrix} 1 & 2 \end{pmatrix} \begin{pmatrix} 1 & 0 & 2 & 1 \\ 0 & 1 & 1 & 2 \end{pmatrix}\) \(=\) \(\ds \begin{pmatrix} 1 & 2 & 1 & 2 \end{pmatrix}\)
\(\ds \begin{pmatrix} 2 & 0 \end{pmatrix} \begin{pmatrix} 1 & 0 & 2 & 1 \\ 0 & 1 & 1 & 2 \end{pmatrix}\) \(=\) \(\ds \begin{pmatrix} 2 & 0 & 1 & 2 \end{pmatrix}\)
\(\ds \begin{pmatrix} 2 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 2 & 1 \\ 0 & 1 & 1 & 2 \end{pmatrix}\) \(=\) \(\ds \begin{pmatrix} 2 & 1 & 2 & 1 \end{pmatrix}\)
\(\ds \begin{pmatrix} 2 & 2 \end{pmatrix} \begin{pmatrix} 1 & 0 & 2 & 1 \\ 0 & 1 & 1 & 2 \end{pmatrix}\) \(=\) \(\ds \begin{pmatrix} 2 & 2 & 0 & 0 \end{pmatrix}\)

all arithmetic being modulo $3$.


As can be seen, $2$ of the codewords have weight $2$, while the other codewords which are not $0000$ have more.

From Minimum Distance of Linear Code is Smallest Weight of Non-Zero Codeword, the minimum distance of $C$ is $2$.

From Error Detection Capability of Linear Code, $C$ can detect $2 - 1 = 1$ transmission errors.

From Error Correction Capability of Linear Code, $C$ can correct $\floor {\dfrac {2 - 1} 2} = 0$ transmission errors.

$\blacksquare$


Sources