Linear code

In mathematics, a (binary) linear code of length n > 0 and rank 0 < k < n + 1 is a linear subspace C with dimension k of the vector space

${\displaystyle F_{2}^{n}.}$

Aside: F₂ = {0,1} is the field with two elements and ${\displaystyle F_{2}^{n}}$ is the set of all n-tuples of length n over F₂. Occasionally some other finite field F_q containing 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 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 Fⁿ, the sum c₁ + c₂ of two codewords in C is also a codeword (ie an element of the subspace 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 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 C. A linear code of length n, rank k (ie having k codewords in its basis and k rows in its generating matrix) and minimum Hamming weight d is referred to as an (n.k,d) code.

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

See also

• Code
• Syndrome decoding