Linear code
Encyclopedia
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 code
s and convolutional code
s, although Turbo code
s can be seen as a hybrid of these two types. Linear codes allow for more efficient encoding and decoding algorithms than other codes (cf. syndrome decoding).
Linear codes are used in forward error correction
and are applied in methods for transmitting symbols (e.g., bit
s) 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 which 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 [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 and a single error can be corrected. This code contains 24=16 codewords.
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 a code is 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.
Remark: We want to give
the usual standard basis because each coordinate represents a "bit" which 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.
of
, the entire code C (which may be very large) may be represented as the span of a minimal set of codewords (known as a basis
in linear algebra
). 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 A 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 (or sometimes a parity check matrix). Equivalently, H is a matrix whose null space
is C. If C is a code with a generating matrix G in standard form, G = (Ik | A), then H = (−At | In − k) is a check matrix for C. The code generated by H is called the dual code of C.
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.
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.
has been widely used in digital communication systems. For any positive integer
, there exists a 
Hamming code. Since 
, this Hamming code can correct 1-bit error.
Example : The linear block code with the following generator matrix and parity check matrix is a
Hamming code.
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 (the all-zero column) out from
, we get 
simplex code, which is the dual code of Hamming code.
Input: A "received vector" v in
.
Output: A codeword w in C closest to v.
Note: "fail" is not returned unless t > (d − 1)/2. We say that a linear C is t-error correcting if there is at most one codeword in Bt(v), for each v in
.
s 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.
Remark. 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.
): 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. 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 (c1,...,cn) in C1 if and only if (cp(1),...,cp(n)) 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.
Coding theory
Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...
, a linear code is an error-correcting code for which any linear combination
Linear combination
In mathematics, a linear combination is an expression constructed from a set of terms by multiplying each term by a constant and adding the results...
of codewords is also a codeword. Linear codes are traditionally partitioned into block code
Block code
In coding theory, block codes refers to the large and important family of error-correcting codes that encode data in blocks.There is a vast number of examples for block codes, many of which have a wide range of practical applications...
s and convolutional code
Convolutional code
In telecommunication, a convolutional code is a type of error-correcting code in which* each m-bit information symbol to be encoded is transformed into an n-bit symbol, where m/n is the code rate and...
s, although Turbo code
Turbo code
In information theory, turbo codes are a class of high-performance forward error correction codes developed in 1993, which were the first practical codes to closely approach the channel capacity, a theoretical maximum for the code rate at which reliable communication is still possible given a...
s can be seen as a hybrid of these two types. Linear codes allow for more efficient encoding and decoding algorithms than other codes (cf. syndrome decoding).
Linear codes are used in forward error correction
Forward error correction
In telecommunication, information theory, and coding theory, forward error correction or channel coding is a technique used for controlling errors in data transmission over unreliable or noisy communication channels....
and are applied in methods for transmitting symbols (e.g., bit
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
s) 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 which 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 [7,4,3] Hamming code
Hamming code
In telecommunication, Hamming codes are a family of linear error-correcting codes that generalize the Hamming-code invented by Richard Hamming in 1950. Hamming codes can detect up to two and correct up to one bit errors. By contrast, the simple parity code cannot correct errors, and can detect only...
is a linear binary code
Binary code
A binary code is a way of representing text or computer processor instructions by the use of the binary number system's two-binary digits 0 and 1. This is accomplished by assigning a bit string to each particular symbol or instruction...
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 and 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 subspaceLinear subspace
The concept of a linear subspace is important in linear algebra and related fields of mathematics.A linear subspace is usually called simply a subspace when the context serves to distinguish it from other kinds of subspaces....
C with dimension k of the vector space
Vector space
A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...
where is the finite fieldFinite field
In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...
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
Hamming distance
In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different...
between them, that is, the number of elements in which they differ. The distance d of a code is 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.
Remark: We want to give
the usual standard basis because each coordinate represents a "bit" which is transmitted across a "noisy channel" with some small probability of transmission error (a binary symmetric channelBinary symmetric channel
A binary symmetric channel is a common communications channel model used in coding theory and information theory. In this model, a transmitter wishes to send a bit , and the receiver receives a bit. It is assumed that the bit is usually transmitted correctly, but that it will be "flipped" with a...
). 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.
Properties
As a linear subspaceLinear subspace
The concept of a linear subspace is important in linear algebra and related fields of mathematics.A linear subspace is usually called simply a subspace when the context serves to distinguish it from other kinds of subspaces....
of
, the entire code C (which may be very large) may be represented as the span of a minimal set of codewords (known as a basisBasis (linear algebra)
In linear algebra, a basis is a set of linearly independent vectors that, in a linear combination, can represent every vector in a given vector space or free module, or, more simply put, which define a "coordinate system"...
in linear algebra
Linear algebra
Linear algebra is a branch of mathematics that studies vector spaces, also called linear spaces, along with linear functions that input one vector and output another. Such functions are called linear maps and can be represented by matrices if a basis is given. Thus matrix theory is often...
). These basis codewords are often collated in the rows of a matrix G known as a generating matrix
Generator matrix
In coding theory, a generator matrix is a basis for a linear code, generating all its possible codewords.If the matrix is G and the linear code is C,where w is a codeword of the linear code C, c is a row vector, and a bijection exists between w and c. A generator matrix for an q-code has...
for the code C. When G has the block matrix form
, where denotes the identity matrix and A 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 (or sometimes a parity check matrix). Equivalently, H is a matrix whose null spaceNull space
In linear algebra, the kernel or null space of a matrix A is the set of all vectors x for which Ax = 0. The kernel of a matrix with n columns is a linear subspace of n-dimensional Euclidean space...
is C. If C is a code with a generating matrix G in standard form, G = (Ik | A), then H = (−At | In − k) is a check matrix for C. The code generated by H is called the dual code of C.
Linearity guarantees that the minimum Hamming distance
Hamming distance
In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different...
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.
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, the Hamming codesHamming code
In telecommunication, Hamming codes are a family of linear error-correcting codes that generalize the Hamming-code invented by Richard Hamming in 1950. Hamming codes can detect up to two and correct up to one bit errors. By contrast, the simple parity code cannot correct errors, and can detect only...
has been widely used in digital communication systems. For any positive integer
, there exists a Hamming code. Since , this Hamming code can correct 1-bit error.Example : The linear block code with the following generator matrix and parity check matrix is a
Hamming code.-
: 
Example: Hadamard codes
Hadamard codeHadamard code
The Hadamard code is an error-correcting code that is used for error detection and correction when transmitting messages over very noisy or unreliable channels....
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
Hadamard code
The Hadamard code is an error-correcting code that is used for error detection and correction when transmitting messages over very noisy or unreliable channels....
is a special case of
Reed-Muller code
Reed–Muller code
Reed–Muller codes are a family of linear error-correcting codes used in communications. Reed–Muller codes belong to the classes of locally testable codes and locally decodable codes, which is why they are useful in the design of probabilistically checkable proofs in computational complexity theory....
If we take the first column (the all-zero 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 (called the nearest neighbor decoding algorithm):Input: A "received vector" v in
.Output: A codeword w in C closest to v.
- Enumerate the elements of the ball of (Hamming) radius t around the received word v, denoted Bt(v).
- For each w in Bt(v), check if w in C. If so, return w as the solution!
- Fail when enumeration is complete and no solution has been found.
Note: "fail" is not returned unless t > (d − 1)/2. We say that a linear C is t-error correcting if there is at most one codeword in Bt(v), for each v in
.Popular notation
CodeCode
A code is a rule for converting a piece of information into another form or representation , not necessarily of the same type....
s 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.
Remark. 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.
Singleton bound
Lemma (Singleton boundSingleton bound
In coding theory, the Singleton bound, named after Richard Collom Singleton, is a relatively crude bound on the size of a block code C with block length n, size r and minimum distance d.-Statement of the 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. 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
Symmetric group
In mathematics, the symmetric group Sn on a finite set of n symbols is the group whose elements are all the permutations of the n symbols, and whose group operation is the composition of such permutations, which are treated as bijective functions from the set of symbols to itself...
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. 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.
External links
- q-ary code generator program
- Compute parameters of linear codes – an on-line interface for generating and computing parameters (e.g. minimum distanceMinimum distanceThe term minimum distance is used in several ways:* In geometry, the minimum distance of a collection of points P in a space is the smallest distance between any two points of the space....
, covering radius) of linear error-correcting codes. - 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.