Linear code

In mathematics, a (binary) linear code of length ${\displaystyle 1\leq n}$ and rank ${\displaystyle 1\leq k\leq n}$ is a linear subspace ${\displaystyle C}$ with dimension ${\displaystyle k}$ of the vector space

${\displaystyle \mathbb {F} _{2}^{n}}$.

Aside: ${\displaystyle \mathbb {F} _{2}=\{0,1\}}$ is the field of two elements and ${\displaystyle \mathbb {F} _{2}^{n}}$ is the set of all n-tuples of length ${\displaystyle n}$ over ${\displaystyle \mathbb {F} _{2}}$. Occasionally some other finite field ${\displaystyle \mathbb {F} _{q}}$ containing ${\displaystyle q>2}$ elements is used, in which case the code is said to be a "q-ary" code (rather than a binary code). Special exceptions to the general adjective "q-ary" are binary and ternary codes (corresponding to q=2 and q=3 respectively).

Properties

By virtue of the fact that the code is a subspace of ${\displaystyle \mathbb {F} _{2}^{n}}$ , the sum ${\displaystyle c_{1}+c_{2}}$  of two codewords in ${\displaystyle C}$  is also a codeword (ie an element of the subspace ${\displaystyle C}$ ). Thus the entire code (which may be very large) to be represented as the span of a minimal set of codewords (known as a basis in linear algebra terms). These basis codewords are often collated in the rows of a matrix known as a generating matrix for the code ${\displaystyle C}$ .

The subspace definition also gives rise to the important property that the minimum Hamming distance between codewords is simply the minimum Hamming weight of all codewords since:

${\displaystyle d(c_{1},c_{2})=d(c_{1}+c_{2},0)\,}$ 

implying:

${\displaystyle \min _{c_{1},c_{2}\in C}d(c_{1},c_{2})=\min _{c_{1},c_{2}\in C}d(c_{1}+c_{2},0)=\min _{c_{1}\in C}d(c_{1},0).}$ 

The motivation behind creating linear codes is to allow for syndrome decoding.

Popular notation

Codes in general are often denoted by the letter ${\displaystyle C}$ . A linear code of length ${\displaystyle n}$ , rank ${\displaystyle k}$  (ie having ${\displaystyle k}$  codewords in its basis and ${\displaystyle k}$  rows in its generating matrix) and minimum Hamming weight ${\displaystyle d}$  is referred to as an ${\displaystyle (n,k,d)}$  code.

Remark. This is not to be confused with the notation ${\displaystyle [n,r,d]}$  to denote a non-linear code of length ${\displaystyle n}$ , size ${\displaystyle r}$  (ie having ${\displaystyle r}$  codewords) and minimum Hamming distance ${\displaystyle d}$ .

See also

• Code
• Syndrome decoding