Linear code: Difference between revisions

Revision as of 01:56, 30 August 2019

Revision as of 02:00, 30 August 2019

Line 1:

{{Cleanup bare URLs |bot=wp:tagbot |requester=User:MarnetteD |date=August 2019}}

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}}

Line 101 ⟶ 100:

==Generalization==

[[Hamming space]]s over non-field alphabets have also been considered, especially over [[finite ring]]s (most notably over [[modulo arithmetic|'''Z'''₄]]) 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^2m)) 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{{Cite web|url=https://www.encyclopediaofmath.org/index.php/Kerdock_and_Preparata_codesMain_Page|title=Encyclopedia of Mathematics|website=www.encyclopediaofmath.org}}</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 ℤ₄}}</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>

Line 110 ⟶ 109:

==References==

<references/>

===Bibliography===

* {{cite book|author1=J. F. Humphreys|author2=M. Y. Prest|title=Numbers, Groups and Codes|year=2004|publisher=Cambridge University Press|isbn=978-0-511-19420-7|edition=2nd}} Chapter 5 contains a more gentle introduction (than this article) to the subject of linear codes.