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. Linear codes allow for more efficient encoding and decoding algorithms than other codes.
Linear codes are used in forward error correction and are applied in methods for transmitting symbols 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. A linear code of length n transmits blocks containing n symbols. For example, the 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. This code contains 24=16 codewords.

Definition and parameters

A linear code of length n and rank k is a linear subspace C with dimension k of the vector space where is the finite field with q elements. Such a code is called a q-ary code. If q = 2 or q = 3, the code is described as a binary code, or a ternary code respectively. The vectors in C are called codewords. The size of a code is the number of codewords and equals qk.
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 code.
We want to give the standard basis because each coordinate represents a "bit" that is transmitted across a "noisy channel" with some small probability of transmission error. 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.

Generator and check matrices

As a linear subspace of, the entire code C may be represented as the span of a set of codewords. 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, where denotes the identity matrix and P is some matrix, then we say G is in standard form.
A matrix H representing a linear function whose kernel is C is called a check matrix of C. Equivalently, H is a matrix whose null space is C. If C is a code with a generating matrix G in standard form,, then 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 matrix, while H is a matrix.
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, and the property that d = d. 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.
Proof: Because , which is equivalent to, where is the column of. Remove those items with, those with are linearly dependent. Therefore, is at least the minimum number of linearly dependent columns. On another hand, consider the minimum set of linearly dependent columns where is the column index set. . Now consider the vector such that if. Note because . Therefore, we have, which is the minimum number of linearly dependent columns in. The claimed property is therefore proved.

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, there exists a Hamming code. Since, 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 Hamming code.

Example: Hadamard codes

is a linear code and is capable of correcting many errors. Hadamard code could be constructed column by column : the column is the bits of the binary representation of integer, as shown in the following example. Hadamard code has minimum distance and therefore can correct errors.
Example: The linear block code with the following generator matrix is a Hadamard code:
Hadamard code is a special case of Reed–Muller code. If we take the first column out from, we get 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 :
Input: A received vector v in .
Output: A codeword in closest to, if any.
We say that a linear is -error correcting if there is at most one codeword in, for each in.

Popular notation

s in general are often denoted by the letter C, and a code of length n and of rank k is generally referred to as an code. Linear block codes are frequently denoted as codes, where d refers to the code's minimum Hamming distance between any two code words.
notation used to denote a non-linear code of length n, size M

Singleton bound

Lemma : Every linear code C satisfies.
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 C1 and C2 are two codes of length n and if there is a permutation p in the symmetric group Sn for which in C1 if and only if ,...,cp in C2, then we say C1 and C2 are permutation equivalent. In more generality, if there is an monomial matrix which sends C1 isomorphically to C2 then we say C1 and C2 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 Hamming codes.

Examples

Some examples of linear codes include:
s over non-field alphabets have also been considered, especially over finite rings giving rise to modules instead of vector spaces and ring-linear codes instead of linear codes. The typical metric used in this case the Lee distance. There exist a Gray isometry between with the Hamming distance and with the Lee distance; its main attraction is that it establishes a correspondence between some "good" codes that are not linear over as images of ring-linear codes from.
More recently, some authors have referred to such codes over rings simply as linear codes as well.