Standard Generator Matrix for Linear Code/Examples/(6, 3) code in Z2
Example of Standard Generator Matrix for Linear Code
Let $G$ be the standard generator matrix:
- $G := \begin{pmatrix}
1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 \end{pmatrix}$
$G$ generates the linear code $C$:
- $C = \set {000000, 100110, 010101, 110011, 001011, 101101, 011110, 111000}$
The minimum distance of $C$ is $3$, so $C$ detects $2$ transmission errors and corrects $1$ transmission error.
Proof
Multiplying $G$ by the $8$ vectors $000, 001, 010, 011, 100, 101, 110, 111$ in turn gives:
| \(\ds \begin{pmatrix} 0 & 0 & 0 \end{pmatrix} \begin{pmatrix}
1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 \end{pmatrix}\) |
\(=\) | \(\ds \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}\) | ||||||||||||
| \(\ds \begin{pmatrix} 0 & 0 & 1 \end{pmatrix} \begin{pmatrix}
1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 \end{pmatrix}\) |
\(=\) | \(\ds \begin{pmatrix} 0 & 0 & 1 & 0 & 1 & 1 \end{pmatrix}\) | ||||||||||||
| \(\ds \begin{pmatrix} 0 & 1 & 0 \end{pmatrix} \begin{pmatrix}
1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 \end{pmatrix}\) |
\(=\) | \(\ds \begin{pmatrix} 0 & 1 & 0 & 1 & 0 & 1 \end{pmatrix}\) | ||||||||||||
| \(\ds \begin{pmatrix} 0 & 1 & 1 \end{pmatrix} \begin{pmatrix}
1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 \end{pmatrix}\) |
\(=\) | \(\ds \begin{pmatrix} 0 & 1 & 1 & 1 & 1 & 0 \end{pmatrix}\) | ||||||||||||
| \(\ds \begin{pmatrix} 1 & 0 & 0 \end{pmatrix} \begin{pmatrix}
1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 \end{pmatrix}\) |
\(=\) | \(\ds \begin{pmatrix} 1 & 0 & 0 & 1 & 1 & 0 \end{pmatrix}\) | ||||||||||||
| \(\ds \begin{pmatrix} 1 & 0 & 1 \end{pmatrix} \begin{pmatrix}
1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 \end{pmatrix}\) |
\(=\) | \(\ds \begin{pmatrix} 1 & 0 & 1 & 1 & 0 & 1 \end{pmatrix}\) | ||||||||||||
| \(\ds \begin{pmatrix} 1 & 1 & 0 \end{pmatrix} \begin{pmatrix}
1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 \end{pmatrix}\) |
\(=\) | \(\ds \begin{pmatrix} 1 & 1 & 0 & 0 & 1 & 1 \end{pmatrix}\) | ||||||||||||
| \(\ds \begin{pmatrix} 1 & 1 & 1 \end{pmatrix} \begin{pmatrix}
1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 \end{pmatrix}\) |
\(=\) | \(\ds \begin{pmatrix} 1 & 1 & 1 & 0 & 0 & 0 \end{pmatrix}\) |
all arithmetic being modulo $2$.
As can be seen, $2$ of the codewords have weight $3$, and $3$ have weight $4$.
From Minimum Distance of Linear Code is Smallest Weight of Non-Zero Codeword, the minimum distance of $C$ is $3$.
From Error Detection Capability of Linear Code, $C$ can detect $3 - 1 = 2$ transmission errors.
From Error Correction Capability of Linear Code, $C$ can correct $\dfrac {3 - 1} 2 = 1$ transmission error.
$\blacksquare$
Example
The received word $100111$ has $1$ transmission error and so can be corrected.
The received word $100001$ has $2$ transmission errors and so cannot be corrected.
Sources
- 1996: John F. Humphreys: A Course in Group Theory ... (previous) ... (next): Chapter $6$: Error-correcting codes: Example $6.13$