Content deleted Content added
m →Bonisoli's theorem: Various citation & identifier cleanup, plus AWB genfixes (arxiv version pointless when published) |
Alter: isbn. Add: chapter-url, class, eprint, bibcode. Removed or converted URL. Removed parameters. | You can use this tool yourself. Report bugs here. |
||
Line 1:
In [[coding theory]], a '''linear code''' is an [[error-correcting code]] for which any [[linear combination]] of [[code word|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]]).{{citation needed|date=April 2018}}
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 that are encoded using more symbols than the original value to be sent.<ref name=DrMacKayECC>{{cite book| last=MacKay | first=David, J.C.| authorlink=David J.C. MacKay| title=Information Theory, Inference, and Learning Algorithms |year=2003 | pages=9|publisher=[[Cambridge University Press]]| isbn=9780521642989|url=http://www.inference.phy.cam.ac.uk/itprnn/book.pdf | quote="In a ''linear'' block code, the extra <math>N - K</math> bits are linear functions of the original <math>K</math> bits; these extra bits are called ''parity-check bits''"| bibcode=2003itil.book.....M}}</ref> 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.<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=978-0-471-06259-
==Definition and parameters==
Line 78:
==Bonisoli's theorem==
A code is defined to be '''equidistant''' if and only if there exists some constant ''d'' such that the distance between any two of the code's distinct codewords is equal to ''d''.<ref>{{cite arxiv|author=Etzion, Tuvi|author2=Raviv, Netanel|title=Equidistant codes in the Grassmannian|year=2013|
==Examples==
Line 102:
[[Hamming space]]s over non-field alphabets have also been considered, especially over [[finite ring]]s (most notably over [[modulo arithmetic|'''Z'''<sub>4</sub>]]) giving rise to [[module (mathematics)|module]]s instead of vector spaces and [[ring-linear code]]s (identified with [[submodule]]s) instead of linear codes. The typical metric used in this case the [[Lee distance]]. There exist a [[Gray isometry]] between <math>\mathbb{Z}_2^{2m}</math> (i.e. GF(2<sup>2m</sup>)) with the Hamming distance and <math>\mathbb{Z}_4^m</math> (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 <math>\mathbb{Z}_2^{2m}</math> as images of ring-linear codes from <math>\mathbb{Z}_4^m</math>.<ref name="Greferath2009">{{cite book|editors=Massimiliano Sala, Teo Mora, Ludovic Perret, Shojiro Sakata, Carlo Traverso|title=Gröbner Bases, Coding, and Cryptography|year=2009|publisher=Springer Science & Business Media|isbn=978-3-540-93806-4|chapter=An Introduction to Ring-Linear Coding Theory|author=Marcus Greferath}}</ref><ref>http://www.encyclopediaofmath.org/index.php/Kerdock_and_Preparata_codes</ref><ref name="Lint1999">{{cite book|author=J.H. van Lint|title=Introduction to Coding Theory|year=1999|publisher=Springer|isbn=978-3-540-64133-9|edition=3rd|at=Chapter 8: Codes over ℤ<sub>4</sub>}}</ref>
More recently,{{when|date=May 2015}} some authors have referred to such codes over rings simply as linear codes as well.<ref name="DoughertyFacchini2015">{{cite book|editors=Steven Dougherty, Alberto Facchini, Andre Gerard Leroy, Edmund Puczylowski, Patrick Sole|title=Noncommutative Rings and Their Applications|chapter-url=https://books.google.com/books?id=psrXBgAAQBAJ&pg=PA80|year=2015|publisher=American Mathematical Soc.|isbn=978-1-4704-1032-2|page=80|chapter=Open Problems in Coding Theory|authors=S.T. Dougherty, J.-L. Kim, P. Sole}}</ref>
== See also ==
| |||