Linear code

Definition

A $(n,k,q)$-linear code is the following data:

• A $n$-dimensional vector space $V$ over $F_{q}$ equipped with a basis $X$
• A $k$-dimensional vector subspace $W$ of $V$

The purpose of a linear code is as follows. Given a message of length $k$ over the alphabet $F_{q}$, we want to convert this to a linear code-word of length $n$, via a suitable encoding isomorphism $C:F_{q}^{k}\to W$. We can recover the original message by applying the decoding map $D=C^{-1}$.

Terminology associated with linear codes

Message length

The message length for a linear code is the parameter $k$. This is the length of the initial message that is meant to be encoded.

Code length

The code length for a linear code is the parameter $n$. This is the length of the coded message, that is, the element of $C$ obtained after applying the isomorphism $C$.

Message rate

The rate of a linear code is defined as the value $k/n$. This in some sense measures the density of information sent through the code.

Weight

The weight of a linear code is defined in any of the following equivalent ways:

• The minimum over all nonzero code-words of the number of nonzero coordinates (code-words are the elements of $W$)
• The minimum over all pairs of distinct code-words of the Hamming distance between them.

It turns out that the theoretically best possible error-detecting radius is one less than the weight while the theoretically best possible error-correcting radius is half of one less than the weight.

These theoretical bounds may not be achievable through practical algorithms for a given linear code.

Related notions

• Error-detecting code
• Error-correcting code
• Binary linear code: This is the special case where $q=2$