Definition:Linear Code
Definition
Let $p$ be a prime number.
Let $\Z_p$ be the set of residue classes modulo $p$.
Let $\map V {n, p}$ denote the set of sequences of length $n$ of elements of $\Z_p$.
A linear $\tuple {n, k}$-code is a $k$-dimensional subspace $C$ of $\map V {n, p}$ considered as a vector space over $\Z_p$ of $n$ dimensions.
Master Code
$\map V {n, p}$ is itself a linear $\tuple {n, n}$-code, and is referred to on $\mathsf{Pr} \infty \mathsf{fWiki}$ as a master code (for a linear $\tuple {n, k}$-code over $\Z_p$).
Codeword
The elements of $\map V {n, p}$ are referred to as codewords.
A codeword is usually written without punctuation, so that, for example:
- $\tuple {\eqclass 1 p, \eqclass 0 p, \eqclass 1 p}$
is presented as:
- $101$
Examples
Elements of $\map V {3, 2}$
The master code $\map V {3, 2}$ of length $3$ of elements of $\Z_2$ consists of:
- $\map V {3, 2} = \set {000, 001, 010, 011, 100, 101, 110, 111}$
Elements of $\map V {2, 3}$
The master code $\map V {2, 3}$ of length $2$ of elements of $\Z_3$ consists of:
- $\map V {2, 3} = \set {00, 01, 02, 10, 11, 12, 20, 21, 22}$
Linear $\tuple {2, 2}$-code of $\map V {3, 2}$
The set:
- $C := \set {000, 001, 010, 011}$
is a linear $\tuple {2, 2}$-code of elements of $\Z_2$.
Linear $\tuple {1, 1}$-code of $\map V {2, 3}$
The set:
- $C := \set {11, 22, 33}$
is a linear $\tuple {2, 1}$-code of elements of $\Z_3$.
Examples of Non-Linear Codes
Subset of $\map V {6, 2}$ which is not a Linear Code
Let $\map V {6, 2}$ denote the set of sequences of length $6$ of elements of $\Z_2$.
For all $x \in \Z_p$, let $\overline x$ denote $1 + x \pmod 2$ so that:
- $\overline 0 = 1$
- $\overline 1 = 0$
Let $C \subseteq \map V {6, 2}$ be the set of elements of $\map V {6, 2}$ of the form:
- $x y z \overline x \overline y \overline z$
Then $C$ is not a linear code.
Also defined as
Some sources define a linear code as being over $\Z_2$, that is, that it be a binary code.
Also see
- Master Code forms Vector Space: $\map V {n, p}$ is a vector space over $\Z_p$ of $n$ dimensions
- Results about linear codes can be found here.
Sources
- 1996: John F. Humphreys: A Course in Group Theory ... (previous) ... (next): Chapter $6$: Error-correcting codes: Definition $6.2$
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): coding: 1.
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): linear code