Linear code: Difference between revisions

Revision as of 23:35, 21 November 2019

Revision as of 08:11, 18 December 2019

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=[https://archive.org/details/elementsofinform0000cove/page/210 210–211]|year=1991|publisher=John Wiley & Sons, Inc|isbn=978-0-471-06259-2|url=https://archive.org/details/elementsofinform0000cove/page/210}}</ref> This code contains 2⁴=16 codewords.

==Definition and parameters==

Line 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>{{Cite web|url=https://www.encyclopediaofmath.org/index.php/Main_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|url=https://archive.org/details/introductiontoco0000lint_a3b9/page/|url-access=registration|year=1999|publisher=Springer|isbn=978-3-540-64133-9|edition=3rd|at=[https://archive.org/details/introductiontoco0000lint_a3b9/page/ 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>