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.[1] Linear codes allow for more efficient encoding and decoding algorithms than other codes (cf. syndrome decoding).[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. The codewords in a linear block code are blocks of symbols that are encoded using more symbols than the original value to be sent.[2] 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.[3] This code contains 24=16 codewords.




Contents






  • 1 Definition and parameters


  • 2 Generator and check matrices


  • 3 Example: Hamming codes


  • 4 Example: Hadamard codes


  • 5 Nearest neighbor algorithm


  • 6 Popular notation


  • 7 Singleton bound


  • 8 Examples


  • 9 Generalization


  • 10 See also


  • 11 References


  • 12 External links





Definition and parameters


A linear code of length n and rank k is a linear subspace C with dimension k of the vector space Fqn{displaystyle mathbb {F} _{q}^{n}}mathbb {F} _{q}^{n} where Fq{displaystyle mathbb {F} _{q}}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.


We want to give Fqn{displaystyle mathbb {F} _{q}^{n}}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 Fqn{displaystyle mathbb {F} _{q}^{n}}mathbb {F} _{q}^{n}, 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 G=[Ik|P]{displaystyle {boldsymbol {G}}=[I_{k}|P]}{displaystyle {boldsymbol {G}}=[I_{k}|P]}, where Ik{displaystyle I_{k}}I_{k} denotes the k×k{displaystyle ktimes k}ktimes k identity matrix and P is some k×(n−k){displaystyle ktimes (n-k)}ktimes (n-k) matrix, then we say G is in standard form.


A matrix H representing a linear function ϕ:Fqn→Fqn−k{displaystyle phi :mathbb {F} _{q}^{n}to mathbb {F} _{q}^{n-k}}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=[Ik|P]{displaystyle {boldsymbol {G}}=[I_{k}|P]}{displaystyle {boldsymbol {G}}=[I_{k}|P]}, then H=[−PT|In−k]{displaystyle {boldsymbol {H}}=[-P^{T}|I_{n-k}]}{displaystyle {boldsymbol {H}}=[-P^{T}|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 ktimes n}ktimes n matrix, while H is a (n−k)×n{displaystyle (n-k)times 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


minc∈C, c≠c0d(c,c0)=minc∈C,c≠c0d(c−c0,0)=minc∈C,c≠0d(c,0)=d.{displaystyle min _{cin C, cneq c_{0}}d(c,c_{0})=min _{cin C,cneq c_{0}}d(c-c_{0},0)=min _{cin C,cneq 0}d(c,0)=d.}min _{cin C, cneq c_{0}}d(c,c_{0})=min _{cin C,cneq c_{0}}d(c-c_{0},0)=min _{cin C,cneq 0}d(c,0)=d.

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 H⋅cT=0{displaystyle {boldsymbol {H}}cdot {boldsymbol {c}}^{T}={boldsymbol {0}}}{boldsymbol {H}}cdot {boldsymbol {c}}^{T}={boldsymbol {0}}, which is equivalent to ∑i=1n(ci⋅Hi)=0{displaystyle sum _{i=1}^{n}(c_{i}cdot {boldsymbol {H_{i}}})={boldsymbol {0}}}sum _{i=1}^{n}(c_{i}cdot {boldsymbol {H_{i}}})={boldsymbol {0}}, where Hi{displaystyle {boldsymbol {H_{i}}}}{boldsymbol {H_{i}}} is the ith{displaystyle i^{th}}i^{th} column of H{displaystyle {boldsymbol {H}}}{boldsymbol {H}}. Remove those items with ci=0{displaystyle c_{i}=0}c_{i}=0, those Hi{displaystyle {boldsymbol {H_{i}}}}{boldsymbol {H_{i}}} with ci≠0{displaystyle c_{i}neq 0}c_{i}neq 0 are linearly dependent. Therefore, d{displaystyle d}d is at least the minimum number of linearly dependent columns. On another hand, consider the minimum set of linearly dependent columns {Hj|j∈S}{displaystyle {{boldsymbol {H_{j}}}|jin S}}{{boldsymbol {H_{j}}}|jin S} where S{displaystyle S}S is the column index set. ∑i=1n(ci⋅Hi)=∑j∈S(cj⋅Hj)+∑j∉S(cj⋅Hj)=0{displaystyle sum _{i=1}^{n}(c_{i}cdot {boldsymbol {H_{i}}})=sum _{jin S}(c_{j}cdot {boldsymbol {H_{j}}})+sum _{jnotin S}(c_{j}cdot {boldsymbol {H_{j}}})={boldsymbol {0}}}sum _{i=1}^{n}(c_{i}cdot {boldsymbol {H_{i}}})=sum _{jin S}(c_{j}cdot {boldsymbol {H_{j}}})+sum _{jnotin S}(c_{j}cdot {boldsymbol {H_{j}}})={boldsymbol {0}}. Now consider the vector c′{displaystyle {boldsymbol {c'}}}{boldsymbol {c'}} such that cj′=0{displaystyle c_{j}^{'}=0}c_{j}^{'}=0 if j∉S{displaystyle jnotin S}jnotin S. Note c′∈C{displaystyle {boldsymbol {c'}}in C}{boldsymbol {c'}}in C because H⋅c′T=0{displaystyle {boldsymbol {H}}cdot {boldsymbol {c'}}^{T}={boldsymbol {0}}}{boldsymbol {H}}cdot {boldsymbol {c'}}^{T}={boldsymbol {0}} . Therefore, we have d≤wt(c′){displaystyle dleq wt({boldsymbol {c'}})}dleq wt({boldsymbol {c'}}), which is the minimum number of linearly dependent columns in H{displaystyle {boldsymbol {H}}}{boldsymbol {H}}. The claimed property is therefore proved.



Example: Hamming codes


Main article: Hamming code

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 r≥2{displaystyle rgeq 2}rgeq 2, there exists a [2r−1,2r−r−1,3]2{displaystyle [2^{r}-1,2^{r}-r-1,3]_{2}}[2^{r}-1,2^{r}-r-1,3]_{2} Hamming code. Since d=3{displaystyle d=3}d=3, 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 [7,4,3]2{displaystyle [7,4,3]_{2}}[7,4,3]_{2} Hamming code.



G=(1 0 0 0 1 1 00 1 0 0 0 1 10 0 1 0 1 1 10 0 0 1 1 0 1),{displaystyle {boldsymbol {G}}={begin{pmatrix}1 0 0 0 1 1 0\0 1 0 0 0 1 1\0 0 1 0 1 1 1\0 0 0 1 1 0 1end{pmatrix}},}{boldsymbol {G}}={begin{pmatrix}1 0 0 0 1 1 0\0 1 0 0 0 1 1\0 0 1 0 1 1 1\0 0 0 1 1 0 1end{pmatrix}}, H=(1 0 1 1 1 0 01 1 1 0 0 1 00 1 1 1 0 0 1){displaystyle {boldsymbol {H}}={begin{pmatrix}1 0 1 1 1 0 0\1 1 1 0 0 1 0\0 1 1 1 0 0 1end{pmatrix}}}{boldsymbol {H}}={begin{pmatrix}1 0 1 1 1 0 0\1 1 1 0 0 1 0\0 1 1 1 0 0 1end{pmatrix}}


Example: Hadamard codes


Main article: Hadamard code

Hadamard code is a [2r,r,2r−1]2{displaystyle [2^{r},r,2^{r-1}]_{2}}[2^{r},r,2^{r-1}]_{2} linear code and is capable of correcting many errors. Hadamard code could be constructed column by column : the ith{displaystyle i^{th}}i^{th} column is the bits of the binary representation of integer i{displaystyle i}i, as shown in the following example. Hadamard code has minimum distance 2r−1{displaystyle 2^{r-1}}2^{r-1} and therefore can correct 2r−2−1{displaystyle 2^{r-2}-1}2^{{r-2}}-1 errors.


Example: The linear block code with the following generator matrix is a [8,3,4]2{displaystyle [8,3,4]_{2}}[8,3,4]_{2} Hadamard code:
GHad=(0 0 0 0 1 1 1 10 0 1 1 0 0 1 10 1 0 1 0 1 0 1){displaystyle {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 1end{pmatrix}}}{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 1end{pmatrix}}.


Hadamard code is a special case of Reed–Muller code. If we take the first column (the all-zero column) out from GHad{displaystyle {boldsymbol {G}}_{Had}}{boldsymbol {G}}_{Had}, we get [7,3,4]2{displaystyle [7,3,4]_{2}}[7,3,4]_{2} 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 Fqn{displaystyle mathbb {F} _{q}^{n}}mathbb {F} _{q}^{n} .


Output: A codeword w in C closest to v if any.



  • Starting with t=0 repeat the following two steps.

  • 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!


  • Increment t. Fail when t > (d - 1)/2 so 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 Fqn{displaystyle mathbb {F} _{q}^{n}}mathbb {F} _{q}^{n}.



Popular notation


Main article: Block code § Popular notation

Codes 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.


(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 k+d≤n+1{displaystyle k+dleq n+1}k+dleq n+1.


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 n×n{displaystyle ntimes n}ntimes n monomial matrix M:Fqn→Fqn{displaystyle Mcolon mathbb {F} _{q}^{n}to mathbb {F} _{q}^{n}}Mcolon mathbb {F} _{q}^{n}to mathbb {F} _{q}^{n} 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.



Examples


Some examples of linear codes include:




  • Repetition codes

  • Parity codes

  • Cyclic codes

  • Hamming codes


  • Golay code, both the binary and ternary versions


  • Polynomial codes, of which BCH codes are an example

  • Reed–Solomon codes

  • Reed–Muller codes

  • Goppa codes

  • Low-density parity-check codes

  • Expander codes

  • Multidimensional parity-check codes




Generalization


Hamming spaces over non-field alphabets have also been considered, especially over finite rings (most notably over Z4) giving 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. There exist a Gray isometry between Z22m{displaystyle mathbb {Z} _{2}^{2m}}mathbb {Z} _{2}^{2m} (i.e. GF(22m)) with the Hamming distance and Z4m{displaystyle mathbb {Z} _{4}^{m}}mathbb {Z} _{4}^{m} (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 Z22m{displaystyle mathbb {Z} _{2}^{2m}}mathbb {Z} _{2}^{2m} as images of ring-linear codes from Z4m{displaystyle mathbb {Z} _{4}^{m}}mathbb {Z} _{4}^{m}.[4][5][6]


More recently,[when?] some authors have referred to such codes over rings simply as linear codes as well.[7]



See also


  • Decoding methods


References




  1. ^ William E. Ryan and Shu Lin (2009). Channel Codes: Classical and Modern. Cambridge University Press. p. 4. ISBN 978-0-521-84868-8..mw-parser-output cite.citation{font-style:inherit}.mw-parser-output .citation q{quotes:"""""""'""'"}.mw-parser-output .citation .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Wikisource-logo.svg/12px-Wikisource-logo.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-maint{display:none;color:#33aa33;margin-left:0.3em}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}


  2. ^ MacKay, David, J.C. (2003). Information Theory, Inference, and Learning Algorithms (PDF). Cambridge University Press. p. 9. ISBN 9780521642989. In a linear block code, the extra N−K{displaystyle N-K}{displaystyle N-K} bits are linear functions of the original K{displaystyle K}K bits; these extra bits are called parity-check bits


  3. ^ Thomas M. Cover and Joy A. Thomas (1991). Elements of Information Theory. John Wiley & Sons, Inc. pp. 210–211. ISBN 0-471-06259-6.


  4. ^ Marcus Greferath (2009). "An Introduction to Ring-Linear Coding Theory". In Massimiliano Sala, Teo Mora, Ludovic Perret, Shojiro Sakata, Carlo Traverso. Gröbner Bases, Coding, and Cryptography. Springer Science & Business Media. ISBN 978-3-540-93806-4.CS1 maint: Uses editors parameter (link)


  5. ^ http://www.encyclopediaofmath.org/index.php/Kerdock_and_Preparata_codes


  6. ^ J.H. van Lint (1999). Introduction to Coding Theory (3rd ed.). Springer. Chapter 8: Codes over ℤ4. ISBN 978-3-540-64133-9.


  7. ^ S.T. Dougherty, J.-L. Kim, P. Sole (2015). "Open Problems in Coding Theory". In Steven Dougherty, Alberto Facchini, Andre Gerard Leroy, Edmund Puczylowski, Patrick Sole. Noncommutative Rings and Their Applications. American Mathematical Soc. p. 80. ISBN 978-1-4704-1032-2.CS1 maint: Uses authors parameter (link) CS1 maint: Uses editors parameter (link)



  • J. F. Humphreys; M. Y. Prest (2004). Numbers, Groups and Codes (2nd ed.). Cambridge University Press. ISBN 978-0-511-19420-7. Chapter 5 contains a more gentle introduction (than this article) to the subject of linear codes.


External links




  • q-ary code generator program


  • 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.


  • The database of Z4 codes Online, up to date database of optimal Z4 codes.




-

Popular posts from this blog

Guess what letter conforming each word

Image
6 $begingroup$ This is an entry in the Fortnightly Topic Challenge #41: Short and Sweet. 1 letter only could be mean anything . With an additional letter in front , could be used as medicine component and something you definitely learn or at least heard once. Add another letter in front , you would possibly hear that many times . Add an additional letter in front , you would found an independent country . With an additional letter, in the end , you would found something related to apple . Add another letter in the end , you would found something bad . Hint: Each letter is unique . word knowledge letters chemistry share | improve this question ...
Read more

Port of Spain

Image
For ports in the country of Spain, see List of ports in Spain. City in City of Port of Spain, Trinidad and Tobago Port of Spain City City of Port of Spain Top to bottom (left to right): Skyline of Port of Spain from Gulf of Paria; National Academy for the Performing Arts, Independence Square, Eric Williams Plaza; MovieTowne, Port of Port of Spain Motto(s):  "We Gather Strength As We Go Along" Port of Spain Coordinates: 10°40′N 61°31′W  /  10.667°N 61.517°W  / 10.667; -61.517 Coordinates: 10°40′N 61°31′W  /  10.667°N 61.517°W  / 10.667; -61.517 Country   Trinidad and Tobago Jurisdiction City of Port of Spain Settled 1560 Incorporated (town) 1853 Incorporated (city) 1914 Government  • Mayor Joel Martinez  • Governing body City Corporation Area [1]  • City 12 km 2 (5 sq mi) Elevation [2] 66 m (217 ft) Population (2011) [1]  • City 37,074  • Rank 3rd  • Density 3,090/km 2 (8,000/sq mi)...
Read more

Run scheduled task as local user group (not BUILTIN)

Image
0 I am trying to run a scheduled task with User Group (not a single user). This is working fine when I in the field "when running a task, use the following user account:" insert BUILTIN User Group (for example: Administrators or Users). But when I try it with the created Local User Group (example: TestGroup) it is not working. The Users in the TestGroup are the same as in the Administrators group. What could be the problem? Are there some restrictions to the Created User Group compared to BUILTINUsers? scheduled-tasks taskscheduler windowstaskschedule share | improve this question asked Nov 15 '18 at 15:36 Far...
Read more