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 24=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 c0 and any of the other codewords c ≠ c0 is independent of c0. This follows from the property that the difference c − c0 of two codewords in C is also a codeword (i.e., an element of the subspace C), and the property that d(c, c0) = d(c − c0, 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 (nk) code. Linear block codes are frequently denoted as [nkd] codes, where d refers to the code's minimum Hamming distance between any two code words.

(The [nkd] notation should not be confused with the (nMd) 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]