# Linear code

In coding theory, a **linear code** is an error-correcting code for which any linear combination of codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although turbo 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 in forward error correction and are applied in methods for transmitting symbols (e.g., bits) on a communications 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 length *n* transmits blocks containing *n* symbols. For example, the [7,4,3] Hamming code is a linear binary 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^{4}=16 codewords.

The **weight** of a codeword is the number of its elements that are nonzero and the **distance** between two codewords is the Hamming distance between them, that is, the number of elements in which they differ. The distance *d* of the linear code is the minimum weight of its nonzero codewords, or equivalently, the minimum distance between distinct codewords. A linear code of length *n*, dimension *k*, and distance *d* is called an [*n*,*k*,*d*] code.

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

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

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

Codes in general are often denoted by the letter *C*, and a code of length *n* and of rank *k* (i.e., having *k* 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*.)

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.

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

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*.^{[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 of dual Hamming codes.^{[5]}

More recently,^{[when?]} some authors have referred to such codes over rings simply as linear codes as well.^{[9]}