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 (cf. syndrome decoding). 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. 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. This code contains 24 = 16 codewords.
Definition and parameters A linear code of length n and dimension k is a linear subspace C with dimension k of the vector space F q n {\displaystyle \mathbb {F} _{q}^{n}} where F q {\displaystyle \mathbb {F} _{q}} 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 [n,k,d] code (or, more precisely, [ n , k , d ] q {\displaystyle [n,k,d]_{q}} code). We want to give F q n {\displaystyle \mathbb {F} _{q}^{n}} 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.
Generator and check matrices As a linear subspace of F q n {\displaystyle \mathbb {F} _{q}^{n}} , the entire code C (which may be very large) may be represented as the span of a set of k {\displaystyle k} 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 G = [ I k ∣ P ] {\displaystyle {\boldsymbol {G}}=[I_{k}\mid P]} , where I k {\displaystyle I_{k}} denotes the k × k {\displaystyle k\times k} identity matrix and P is some k × ( n − k ) {\displaystyle k\times (n-k)} matrix, then we say G is in standard form. A matrix H representing a linear function ϕ : F q n → F q n − k {\displaystyle \phi :\mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{n-k}} 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 = [ I k ∣ P ] {\displaystyle {\boldsymbol {G}}=[I_{k}\mid P]} , then H = [ − P T ∣ I n − k ] {\displaystyle {\boldsymbol {H}}=[-P^{T}\mid I_{n-k}]} 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 k × n {\displaystyle k\times n} matrix, while H is a ( n − k ) × n {\displaystyle (n-k)\times n} 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 (i.e., an element of the subspace C), and the property that d(c, c0) = d(c − c0, 0). These properties imply that
… excerpt ends here. Continue reading the full article.
