Linear code

Generator and check matrices

As a linear subspace of ${\displaystyle {\mathbb{F}}_q^n}$, the entire code C (which may be very large) may be represented as the span of a set of ${\displaystyle k}$ codewords (known as a basis in linear algebra). These basis codewords are often collated in the rows of a matrix G known as a generating matrix for the code C. When G has the block matrix form ${\displaystyle \mathit{G}=[I_k\mid P]}$, where ${\displaystyle I_k}$ denotes the ${\displaystyle k\times k}$ identity matrix and P is some ${\displaystyle k\times (n-k)}$ matrix, then we say G is in standard form.

A matrix H representing a linear function ${\displaystyle \varphi :{\mathbb{F}}_q^n\to {\mathbb{F}}_q^{n-k}}$ whose kernel is C is called a check matrix of C (or sometimes a parity check matrix). Equivalently, H is a matrix whose null space is C. If C is a code with a generating matrix G in standard form, ${\displaystyle \mathit{G}=[I_k\mid P]}$, then ${\displaystyle \mathit{H}=[-P^T\mid I_{n-k}]}$ is a check matrix for C. The code generated by H is called the dual code of C. It can be verified that G is a ${\displaystyle k\times n}$ matrix, while H is a ${\displaystyle (n-k)\times n}$ matrix.

Linearity guarantees that the minimum Hamming distance d between a codeword c₀ and any of the other codewords c ≠ c₀ is independent of c₀. This follows from the property that the difference c − c₀ of two codewords in C is also a codeword (i.e., an element of the subspace C), and the property that d(c, c₀) = d(c − c₀, 0). These properties imply that

${\displaystyle \underset{c\in C,c\ne c_0}{min}d(c,c_0)=\underset{c\in C,c\ne c_0}{min}d(c-c_0,0)=\underset{c\in C,c\ne 0}{min}d(c,0)=d.}$

In other words, in order to find out the minimum distance between the codewords of a linear code, one would only need to look at the non-zero codewords. The non-zero codeword with the smallest weight has then the minimum distance to the zero codeword, and hence determines the minimum distance of the code.

The distance d of a linear code C also equals the minimum number of linearly dependent columns of the check matrix H.

Proof: Because ${\displaystyle \mathit{H}\cdot {\mathit{c}}^T=\mathbf{0}}$, which is equivalent to ${\displaystyle \sum _{i=1}^n(c_i\cdot {\mathit{H}}_{\mathit{i}})=\mathbf{0}}$, where ${\displaystyle {\mathit{H}}_{\mathit{i}}}$ is the ${\displaystyle i^{th}}$ column of ${\displaystyle \mathit{H}}$. Remove those items with ${\displaystyle c_i=0}$, those ${\displaystyle {\mathit{H}}_{\mathit{i}}}$ with ${\displaystyle c_i\ne 0}$ are linearly dependent. Therefore, ${\displaystyle d}$ is at least the minimum number of linearly dependent columns. On another hand, consider the minimum set of linearly dependent columns ${\displaystyle \{{\mathit{H}}_{\mathit{j}}\mid j\in S\}}$ where ${\displaystyle S}$ is the column index set. ${\displaystyle \sum _{i=1}^n(c_i\cdot {\mathit{H}}_{\mathit{i}})=\sum _{j\in S}(c_j\cdot {\mathit{H}}_{\mathit{j}})+\sum _{j\notin S}(c_j\cdot {\mathit{H}}_{\mathit{j}})=\mathbf{0}}$. Now consider the vector ${\displaystyle {\mathit{c}}^{\mathbf{\prime }}}$ such that ${\displaystyle c_j^{\prime }=0}$ if ${\displaystyle j\notin S}$. Note ${\displaystyle {\mathit{c}}^{\mathbf{\prime }}\in C}$ because ${\displaystyle \mathit{H}\cdot {{\mathit{c}}^{\mathbf{\prime }}}^T=\mathbf{0}}$ . Therefore, we have ${\displaystyle d\le wt({\mathit{c}}^{\mathbf{\prime }})}$, which is the minimum number of linearly dependent columns in ${\displaystyle \mathit{H}}$. The claimed property is therefore proven.

Example: Hamming codes

As the first class of linear codes developed for error correction purpose, Hamming codes have been widely used in digital communication systems. For any positive integer ${\displaystyle r\ge 2}$, there exists a ${\displaystyle [2^r-1,2^r-r-1,3{]}_2}$ Hamming code. Since ${\displaystyle d=3}$, this Hamming code can correct a 1-bit error.

Example : The linear block code with the following generator matrix and parity check matrix is a ${\displaystyle [7,4,3{]}_2}$ Hamming code.

${\displaystyle \mathit{G}=\left(\begin{array}{ccccccc}1& 0& 0& 0& 1& 1& 0\\ 0& 1& 0& 0& 0& 1& 1\\ 0& 0& 1& 0& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 1\end{array}\right),}$ ${\displaystyle \mathit{H}=\left(\begin{array}{ccccccc}1& 0& 1& 1& 1& 0& 0\\ 1& 1& 1& 0& 0& 1& 0\\ 0& 1& 1& 1& 0& 0& 1\end{array}\right)}$

Example: Hadamard codes

Hadamard code is a ${\displaystyle [2^r,r,2^{r-1}{]}_2}$ linear code and is capable of correcting many errors. Hadamard code could be constructed column by column : the ${\displaystyle i^{th}}$ column is the bits of the binary representation of integer ${\displaystyle i}$, as shown in the following example. Hadamard code has minimum distance ${\displaystyle 2^{r-1}}$ and therefore can correct ${\displaystyle 2^{r-2}-1}$ errors.

Example: The linear block code with the following generator matrix is a ${\displaystyle [8,3,4{]}_2}$ Hadamard code: ${\displaystyle {\mathit{G}}_{\mathrm{H}\mathrm{a}\mathrm{d}}=\left(\begin{array}{cccccccc}0& 0& 0& 0& 1& 1& 1& 1\\ 0& 0& 1& 1& 0& 0& 1& 1\\ 0& 1& 0& 1& 0& 1& 0& 1\end{array}\right)}$.

Hadamard code is a special case of Reed–Muller code. If we take the first column (the all-zero column) out from ${\displaystyle {\mathit{G}}_{\mathrm{H}\mathrm{a}\mathrm{d}}}$, we get ${\displaystyle [7,3,4{]}_2}$ simplex code, which is the dual code of Hamming code.

Nearest neighbor algorithm

The parameter d is closely related to the error correcting ability of the code. The following construction/algorithm illustrates this (called the nearest neighbor decoding algorithm):

Input: A received vector v in ${\displaystyle {\mathbb{F}}_q^n.}$

Output: A codeword ${\displaystyle w}$ in ${\displaystyle C}$ closest to ${\displaystyle v}$, if any.

• Starting with ${\displaystyle t=0}$, repeat the following two steps.
• Enumerate the elements of the ball of (Hamming) radius ${\displaystyle t}$ around the received word ${\displaystyle v}$, denoted ${\displaystyle B_t(v)}$.
  • For each ${\displaystyle w}$ in ${\displaystyle B_t(v)}$, check if ${\displaystyle w}$ in ${\displaystyle C}$. If so, return ${\displaystyle w}$ as the solution.
• Increment ${\displaystyle t}$. Fail only when ${\displaystyle t>(d-1)/2}$ so enumeration is complete and no solution has been found.

We say that a linear ${\displaystyle C}$ is ${\displaystyle t}$-error correcting if there is at most one codeword in ${\displaystyle B_t(v)}$, for each ${\displaystyle v}$ in ${\displaystyle {\mathbb{F}}_q^n}$.

Popular notation

Codes in general are often denoted by the letter C, and a code of length n and of rank k (i.e., having n code words in its basis and k rows in its generating matrix) is generally referred to as an (n, k) code. Linear block codes are frequently denoted as [n, k, d] codes, where d refers to the code's minimum Hamming distance between any two code words.

(The [n, k, d] notation should not be confused with the (n, M, d) notation used to denote a non-linear code of length n, size M (i.e., having M code words), and minimum Hamming distance d.)

Singleton bound

Lemma (Singleton bound): Every linear [n,k,d] code C satisfies ${\displaystyle k+d\le n+1}$.

A code C whose parameters satisfy k +d = n + 1 is called maximum distance separable or MDS. Such codes, when they exist, are in some sense best possible.

If C₁ and C₂ are two codes of length n and if there is a permutation p in the symmetric group S_n for which (c₁,...,c_n) in C₁ if and only if (c_p(1),...,c_p(n)) in C₂, then we say C₁ and C₂ are permutation equivalent. In more generality, if there is an ${\displaystyle n\times n}$ monomial matrix ${\displaystyle M:{\mathbb{F}}_q^n\to {\mathbb{F}}_q^n}$ which sends C₁ isomorphically to C₂ then we say C₁ and C₂ are equivalent.

Lemma: Any linear code is permutation equivalent to a code which is in standard form.

Bonisoli's theorem

A code is defined to be equidistant if and only if there exists some constant d such that the distance between any two of the code's distinct codewords is equal to d. In 1984 Arrigo Bonisoli determined the structure of linear one-weight codes over finite fields and proved that every equidistant linear code is a sequence of dual Hamming codes.

Examples

Some examples of linear codes include:

• Repetition code
• Parity code
• Cyclic code
• Hamming code
• Golay code, both the binary and ternary versions
• Polynomial codes, of which BCH codes are an example
• Reed–Solomon codes
• Reed–Muller code
• Algebraic geometry code
• Binary Goppa code
• Low-density parity-check codes
• Expander code
• Multidimensional parity-check code
• Toric code
• Turbo code
• Locally recoverable code

Generalization

Hamming spaces over non-field alphabets have also been considered, especially over finite rings, most notably Galois rings over Z₄. This gives rise to modules instead of vector spaces and ring-linear codes (identified with submodules) instead of linear codes. The typical metric used in this case the Lee distance. There exist a Gray isometry between ${\displaystyle {\mathbb{Z}}_2^{2m}}$ (i.e. GF(2^2m)) with the Hamming distance and ${\displaystyle {\mathbb{Z}}_4^m}$ (also denoted as GR(4,m)) with the Lee distance; its main attraction is that it establishes a correspondence between some "good" codes that are not linear over ${\displaystyle {\mathbb{Z}}_2^{2m}}$ as images of ring-linear codes from ${\displaystyle {\mathbb{Z}}_4^m}$.

Some authors have referred to such codes over rings simply as linear codes as well.