|
|
| Line 1: |
Line 1: |
| 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.<ref>{{cite book|title=Channel Codes: Classical and Modern|author=William E. Ryan and Shu Lin|page=4|year=2009|publisher=Cambridge University Press|isbn=978-0-521-84868-8}}</ref> Linear codes allow for more efficient encoding and decoding algorithms than other codes (cf. [[syndrome decoding]]).
| | My name is Jina and I am studying Education Science and International Relations at Elk Grove Village / United States.<br><br>Also visit my web page; [http://www.deeplinkengine.com/fifa15-coingenerator.com-7152.html fifa 15 coin Generator] |
| | |
| 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.<ref name="Cover_and_Thomas">{{cite book|title=Elements of Information Theory|author=Thomas M. Cover and Joy A. Thomas|pages=210–211|year=1991|publisher=John Wiley & Sons, Inc|isbn=0-471-06259-6}}</ref> This code contains 2<sup>4</sup>=16 codewords.
| |
| | |
| ==Definition and parameters==
| |
| A '''linear code''' of length ''n'' and rank ''k'' is a [[linear subspace]] ''C'' with [[dimension (linear algebra)|dimension]] ''k'' of the [[vector space]] <math>\mathbb{F}_q^n</math> where <math>\mathbb{F}_q</math> 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 ''q''<sup>''k''</sup>.
| |
| | |
| 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 linear 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 <math>\mathbb{F}_q^n</math> 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.''
| |
| | |
| ==Properties==
| |
| As a [[linear subspace]] of <math>\mathbb{F}_q^n</math>, the entire code ''C'' (which may be very large) may be represented as the [[span (linear algebra)|span]] of a minimal set of codewords (known as a [[basis (linear algebra)|basis]] in [[linear algebra]]). These basis codewords are often collated in the rows of a matrix G known as a '''[[Generator matrix|generating matrix]]''' for the code ''C''. When G has the block matrix form <math>G = (I_k | A)</math>, where <math>I_k</math> denotes the <math>k \times k</math> identity matrix and A is some <math>k \times (n-k)</math> matrix, then we say G is in '''standard form'''.
| |
| | |
| A matrix ''H'' representing a linear function <math>\phi : \mathbb{F}_q^n\to \mathbb{F}_q^{n-k}</math> whose [[Kernel (matrix)|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''<sub>''k''</sub> | ''A''), then ''H'' = (−''A''<sup>''t''</sup> | ''I''<sub>''n'' − ''k''</sub>) 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 ''c''<sub>0</sub> and any of the other codewords ''c'' ≠ ''c''<sub>0</sub> is independent of ''c''<sub>0</sub>. This follows from the property that the difference ''c'' − ''c''<sub>0</sub> of two codewords in ''C'' is also a codeword (i.e., an [[element (mathematics)|element]] of the subspace ''C''), and the property that ''d''(''c'', c<sub>0</sub>) = ''d''(''c'' − ''c''<sub>0</sub>, 0). These properties imply that
| |
| | |
| :<math>\min_{c \in C,\ c \neq c_0}d(c,c_0)=\min_{c \in C, c \neq c_0}d(c-c_0, 0)=\min_{c \in C, c \neq 0}d(c, 0)=d.</math>
| |
| | |
| 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 <math>\boldsymbol{H} \cdot \boldsymbol{c}^T = \boldsymbol{0}</math>, which is equivalent to <math>\sum_{i=1}^n (c_i \cdot \boldsymbol{H_i}) = \boldsymbol{0}</math>, where <math>\boldsymbol{H_i}</math> is the <math>i^{th}</math> column of <math>\boldsymbol{H}</math>. Remove those items with <math>c_i=0</math>, those <math>\boldsymbol{H_i}</math> with <math>c_i \neq 0</math> are linearly dependent. Therefore <math>d</math> is at least the minimum number of linearly dependent columns. On another hand, consider the minimum set of linearly dependent columns <math>\{ \boldsymbol{H_j} | j \in S \}</math> where <math>S</math> is the column index set. <math>\sum_{i=1}^n (c_i \cdot \boldsymbol{H_i}) = \sum_{j \in S} (c_j \cdot \boldsymbol{H_j}) + \sum_{j \notin S} (c_j \cdot \boldsymbol{H_j}) = \boldsymbol{0}</math>. Now consider the vector <math>\boldsymbol{c'}</math> such that <math>c_j^{'}=0</math> if <math>j \notin S</math>. Note <math>\boldsymbol{c'} \in C</math> because <math>\boldsymbol{H} \cdot \boldsymbol{c'}^T = \boldsymbol{0}</math> . Therefore we have <math>d \le wt(\boldsymbol{c'}) </math>, which is the minimum number of linearly dependent columns in <math>\boldsymbol{H}</math>. The claimed property is therefore proved.
| |
| | |
| == Example: Hamming codes ==
| |
| | |
| {{main|Hamming code}}
| |
| | |
| As the first class of linear codes developed for error correction purpose, the [[Hamming code|''Hamming codes'']] has been widely used in digital communication systems. For any positive integer <math>r \ge 2 </math>, there exists a <math> [2^r-1, 2^r-r-1,3]_2</math> Hamming code. Since <math>d=3</math>, this Hamming code can correct 1-bit error.
| |
| | |
| '''Example :''' The linear block code with the following generator matrix and parity check matrix is a <math> [7,4,3]_2</math> Hamming code.
| |
| | |
| : <math>\boldsymbol{G}=\begin{pmatrix} 1\ 1\ 0\ 1\ 0\ 0\ 0 \\ 0\ 1\ 1\ 0\ 1\ 0\ 0 \\ 1\ 1\ 1\ 0\ 0\ 1\ 0 \\ 1\ 0\ 1\ 0\ 0\ 0\ 1 \end{pmatrix} ,</math> : <math>\boldsymbol{H}=\begin{pmatrix} 1\ 0\ 0\ 1\ 0\ 1\ 1 \\ 0\ 1\ 0\ 1\ 1\ 1\ 0 \\ 0\ 0\ 1\ 0\ 1\ 1\ 1 \end{pmatrix}</math>
| |
| | |
| == Example: Hadamard codes ==
| |
| | |
| {{main|Hadamard code}}
| |
| | |
| [[Hadamard code]] is a <math>[2^r, r, 2^{r-1}]_2 </math> linear code and is capable of correcting many errors. Hadamard code could be constructed column by column : the <math>i^{th}</math> column is the bits of the binary representation of integer <math>i</math>, as shown in the following example. Hadamard code has minimum distance <math>2^{r-1}</math> and therefore can correct <math>2^{r-2}-1</math> errors.
| |
| | |
| '''Example :''' The linear block code with the following generator matrix is a <math> [8,3,4]_2</math> Hadamard code:
| |
| <math>\boldsymbol{G}_{Had}=\begin{pmatrix} 0\ 0\ 0\ 0\ 1\ 1\ 1\ 1\\ 0\ 0\ 1\ 1\ 0\ 0\ 1\ 1\\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\end{pmatrix}</math>.
| |
| | |
| [[Hadamard code]] is a special case of
| |
| [[Reed–Muller code|Reed-Muller code]] If we take the first column (the all-zero column) out from <math>\boldsymbol{G}_{Had}</math>, we get <math>[7,3,4]_2</math> ''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 <math>\mathbb{F}_q^n</math> .
| |
| | |
| 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 B<sub>t</sub>(v).
| |
| **For each w in B<sub>t</sub>(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 B<sub>t</sub>(v), for each v in <math>\mathbb{F}_q^n</math>.
| |
| | |
| ==Popular notation==
| |
| {{main|Block_code#Popular_notation}}
| |
| [[Code]]s in general are often denoted by the letter ''C'', and a code of length ''n'' and of [[dimension (linear algebra)|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 bound]]): Every linear [n,k,d] code C satisfies <math>k+d \leq n+1</math>.
| |
| | |
| 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 C<sub>1</sub> and C<sub>2</sub> are two codes of length n and if there is a permutation p in the [[symmetric group]] S<sub>n</sub> for which (c<sub>1</sub>,...,c<sub>n</sub>) in C<sub>1</sub> if and only if (c<sub>p(1)</sub>,...,c<sub>p(n)</sub>) in C<sub>2</sub>, then we say C<sub>1</sub> and C<sub>2</sub> are '''permutation equivalent'''. In more generality, if there is an <math>n\times n</math> [[monomial matrix]] <math>M\colon \mathbb{F}_q^n \to \mathbb{F}_q^n</math> which sends C<sub>1</sub> isomorphically to C<sub>2</sub> then we say C<sub>1</sub> and C<sub>2</sub> are '''equivalent'''.
| |
| | |
| ''Lemma'': Any linear code is permutation equivalent to a code which is in standard form.
| |
| | |
| ==Examples==
| |
| Some examples of linear codes include:
| |
| <div style="-moz-column-count:2; column-count:2;">
| |
| * [[Repetition code]]s
| |
| * [[Parity code]]s
| |
| * [[Cyclic code]]s
| |
| * [[Hamming code]]s
| |
| * [[Golay code]], both the [[binary Golay code|binary]] and [[ternary Golay code|ternary]] versions
| |
| * [[Polynomial code]]s, of which [[BCH code]]s are an example
| |
| * [[Reed–Solomon error correction|Reed–Solomon codes]]
| |
| * [[Reed–Muller code]]s
| |
| * [[Goppa code]]s
| |
| * [[Low-density parity-check codes]]
| |
| * [[Expander code]]s
| |
| * [[Multidimensional parity-check code]]s
| |
| </div>
| |
| | |
| == See also ==
| |
| * [[Decoding methods]]
| |
| | |
| ==Notes==
| |
| <references/>
| |
| | |
| ==External links==
| |
| * [http://jason.mchu.com/QCode/index.html ''q''-ary code generator program]
| |
| * [http://ipsit.bu.edu/comp.html Compute parameters of linear codes] – an on-line interface for generating and computing parameters (e.g. [[minimum distance]], [[covering radius]]) of linear error-correcting codes.
| |
| * [http://www.codetables.de/ 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.
| |
| | |
| {{DEFAULTSORT:Linear Code}}
| |
| [[Category:Coding theory]]
| |
| [[Category:Finite fields]]
| |