Linear code

In mathematics and information theory, a linear code is an important type of block codes used in error correction and detection schemes. The linearity of the code means that the sum of any two codewords is a codeword. Linear codes allow for more efficient encoding and decoding algorithms (cf. syndrome decoding).

Formal definition

A linear code of length ${\displaystyle n}$  and rank ${\displaystyle k}$  is a linear subspace ${\displaystyle C}$  with dimension ${\displaystyle k}$  of the vector space ${\displaystyle {\mathbb {F} _{q}}^{n}}$  where ${\displaystyle \mathbb {F} _{q}}$  is the finite field with ${\displaystyle q}$  elements. The most important cases are when ${\displaystyle q}$  is 2 or 3, in which case the code is said to be binary or ternary, 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).}$ 

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
• Cyclic code
• Syndrome decoding