Incoding theory, alinear code is anerror-correcting code for which anylinear combination ofcodewords is also a codeword. Linear codes are traditionally partitioned intoblock codes andconvolutional codes, althoughturbo codes can be seen as a hybrid of these two types.^[1] Linear codes allow for more efficient encoding and decoding algorithms than other codes (cf.syndrome decoding).^{[citation needed]}

Linear codes are used inforward error correction and are applied in methods for transmitting symbols (e.g.,bits) on acommunications channel so that, if errors occur in the communication, some errors can be corrected or detected by the recipient of a message block. The codewords in a linear block code are blocks of symbols that are encoded using more symbols than the original value to be sent.^[2] A linear code of lengthn transmits blocks containingn symbols. For example, the [7,4,3]Hamming code is a linearbinary code which represents 4-bit messages using 7-bit codewords. Two distinct codewords differ in at least three bits. As a consequence, up to two errors per codeword can be detected while a single error can be corrected.^[3] This code contains 2⁴ = 16 codewords.

Alinear code of lengthn and dimensionk is alinear subspaceC withdimensionk of thevector space${\displaystyle {\mathbb{F}}_q^n}$ where${\displaystyle {\mathbb{F}}_q}$ is thefinite field withq elements. Such a code is called aq-ary code. Ifq = 2 orq = 3, the code is described as abinary code, or aternary code respectively. The vectors inC are calledcodewords. Thesize of a code is the number of codewords and equalsq^k.

Theweight of a codeword is the number of its elements that are nonzero and thedistance between two codewords is theHamming distance between them, that is, the number of elements in which they differ. The distanced of the linear code is the minimum weight of its nonzero codewords, or equivalently, the minimum distance between distinct codewords. A linear code of lengthn, dimensionk, and distanced is called an [n,k,d] code (or, more precisely,${\displaystyle [n,k,d{]}_q}$ code).

We want to give${\displaystyle {\mathbb{F}}_q^n}$ the standard basis because each coordinate represents a "bit" that is transmitted across a "noisy channel" with some small probability of transmission error (abinary symmetric channel). If some other basis is used then this model cannot be used and the Hamming metric does not measure the number of errors in transmission, as we want it to.

As alinear subspace of${\displaystyle {\mathbb{F}}_q^n}$, the entire codeC (which may be very large) may be represented as thespan of a set of${\displaystyle k}$ codewords (known as abasis inlinear algebra). These basis codewords are often collated in the rows of a matrix G known as agenerating matrix for the codeC. 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 instandard form.

A matrixH representing a linear function${\displaystyle \varphi :{\mathbb{F}}_q^n\to {\mathbb{F}}_q^{n-k}}$ whosekernel isC is called acheck matrix ofC (or sometimes a parity check matrix). Equivalently,H is a matrix whosenull space isC. IfC is a code with a generating matrixG 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 byH is called thedual 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 minimumHamming distanced between a codewordc₀ and any of the other codewordsc ≠ c₀ is independent ofc₀. This follows from the property that the differencec − c₀ of two codewords inC is also a codeword (i.e., anelement of the subspaceC), and the property thatd(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 distanced of a linear codeC also equals the minimum number of linearly dependent columns of the check matrixH.

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.

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.

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:.

Hadamard code is a special case ofReed–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 thedual code of Hamming code.

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: Areceived 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}$.

Codes in general are often denoted by the letterC, and a code of lengthn and ofrankk (i.e., havingn code words in its basis andk rows in itsgenerating matrix) is generally referred to as an (n, k) code. Linear block codes are frequently denoted as [n, k, d] codes, whered 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 anon-linear code of lengthn, sizeM (i.e., havingM code words), and minimum Hamming distanced.)

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

A codeC whose parameters satisfyk +d = n + 1 is calledmaximum distance separable orMDS. Such codes, when they exist, are in some sense best possible.

IfC₁ andC₂ are two codes of lengthn and if there is a permutationp in thesymmetric groupS_n for which (c₁,...,c_n) inC₁ if and only if (c_p(1),...,c_p(n)) inC₂, then we sayC₁ andC₂ arepermutation 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 sendsC₁ isomorphically toC₂ then we sayC₁ andC₂ areequivalent.

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

A code is defined to beequidistant if and only if there exists some constantd such that the distance between any two of the code's distinct codewords is equal tod.^[4] 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 ofdualHamming codes.^[5]

Some examples of linear codes include:

Hamming spaces over non-field alphabets have also been considered, especially overfinite rings, most notablyGalois rings overZ₄. This gives rise tomodules instead of vector spaces andring-linear codes (identified withsubmodules) instead of linear codes. The typical metric used in this case theLee distance. There exist aGray 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}$.^[6][7][8]

Some authors have referred to such codes over rings simply as linear codes as well.^[9]

• Decoding methods

• J. F. Humphreys; M. Y. Prest (2004).Numbers, Groups and Codes (2nd ed.). Cambridge University Press.ISBN 978-0-511-19420-7. Chapter 5 contains a more gentle introduction (than this article) to the subject of linear codes.

• q-ary code generator program
• Code Tables: Bounds on the parameters of various types of codes,IAKS, Fakultät für Informatik, Universität Karlsruhe (TH)]. Online, up to date table of the optimal binary codes, includes non-binary codes.
• The database of Z4 codes Online, up to date database of optimal Z4 codes.

• Coding theory
• Finite fields

• CS1 maint: multiple names: authors list
• Articles with short description
• Short description is different from Wikidata
• All articles with unsourced statements
• Articles with unsourced statements from April 2018