[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.
[2] A linear code of length n transmits blocks containing n symbols.
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.
the standard basis because each coordinate represents a "bit" that is transmitted across a "noisy channel" with some small probability of transmission error (a binary 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.
, the entire code C (which may be very large) may be represented as the span of a set of
codewords (known as a basis in linear algebra).
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
is at least the minimum number of linearly dependent columns.
On another hand, consider the minimum set of linearly dependent columns
, which is the minimum number of linearly dependent columns in
As the first class of linear codes developed for error correction purpose, Hamming codes have been widely used in digital communication systems.
, this Hamming code can correct a 1-bit error.
linear code and is capable of correcting many errors.
column is the bits of the binary representation of integer
Hadamard code has minimum distance
Example: The linear block code with the following generator matrix is a
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
(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.) Lemma (Singleton bound): Every linear [n,k,d] code C satisfies
A code C whose parameters satisfy k +d = n + 1 is called maximum distance separable or MDS.
If C1 and C2 are two codes of length n and if there is a permutation p in the symmetric group Sn for which (c1,...,cn) in C1 if and only if (cp(1),...,cp(n)) in C2, then we say C1 and C2 are permutation equivalent.
[5] Some examples of linear codes include: Hamming spaces over non-field alphabets have also been considered, especially over finite rings, most notably Galois rings over Z4.
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.
(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