Linear code: Difference between revisions

Revision as of 04:05, 23 May 2019

Latest revision as of 03:34, 28 November 2024

(40 intermediate revisions by 26 users not shown)

Line 1:

{{Short description|Class of error-correcting code}}

In [[coding theory]], a '''linear code''' is an [[error-correcting code]] for which any [[linear combination]] of [[codeCode word (communication)|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|url=https://archive.org/details/channelcodesclas00ryan|url-access=limited|author=William E. Ryan and Shu Lin|page=[https://archive.org/details/channelcodesclas00ryan/page/n21 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-62|url=https://archive.org/details/elementsofinform0000cove/page/210}}</ref> This code contains 2⁴&nbsp;=&nbsp;16 codewords.

==Definition and parameters==

A '''linear code''' of length ''n'' and rankdimension ''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''&nbsp;=&nbsp;2 or ''q''&nbsp;=&nbsp;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''^''k''.

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 (or, more precisely, <math>[n,k,d]_q</math> code).

We want to give <math>\mathbb{F}_q^n</math> 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 <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 <math>k</math> 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>\boldsymbol{G} = [I_k |\mid P]</math>, where <math>I_k</math> denotes the <math>k \times k</math> identity matrix and P 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, <math>\boldsymbol{G} = [I_k |\mid P]</math>, then <math>\boldsymbol{H} = [-P^{T} |\mid I_{n-k} ]</math> 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 <math>k \times n</math> matrix, while H is a <math>(n-k) \times n</math> matrix.

Linearity guarantees that the minimum [[Hamming distance]] ''d'' between a codeword ''c''₀ and any of the other codewords ''c''&nbsp;≠&nbsp;''c''₀ is independent of ''c''₀. This follows from the property that the difference ''c''&nbsp;&minus;&nbsp;''c''₀ 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'',&nbsp;c₀)&nbsp;=&nbsp;''d''(''c''&nbsp;&minus;&nbsp;''c''₀,&nbsp;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.

Line 23 ⟶ 24:

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} |\mid 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 provedproven.

== Example: Hamming codes ==

Line 33 ⟶ 34:

'''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\& 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\& 1 \end{pmatrix} ,</math> <math>\boldsymbol{H}=\begin{pmatrix} 1\& 0\& 1\& 1\& 1\& 0\& 0 \\ 1\& 1&\ 1\& 0\& 0\& 1\& 0 \\ 0\& 1\& 1\& 1\& 0\& 0\& 1 \end{pmatrix}</math>

== Example: Hadamard codes ==

Line 42 ⟶ 43:

'''Example:''' The linear block code with the following generator matrix is a <math> [8,3,4]_2</math> Hadamard code:

<math>\boldsymbol{G}_\mathrm{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]]. If we take the first column (the all-zero column) out from <math>\boldsymbol{G}_\mathrm{Had}</math>, we get <math>[7,3,4]_2</math> ''simplex code'', which is the ''dual code '' of Hamming code.

==Nearest neighbor algorithm==

Line 50 ⟶ 51:

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 <math>w</math> in <math>C</math> closest to <math>v</math>, if any.

*Starting with <math>t=0</math>, repeat the following two steps.

*Enumerate the elements of the ball of (Hamming) radius <math>t</math> around the received word <math>v</math>, denoted B<sub>t</submath>B_t(v)</math>.

**For each <math>w</math> in B<sub>t</submath>B_t(v)</math>, check if <math>w</math> in <math>C</math>. If so, return <math>w</math> as the solution!.

*Increment <math>t</math>. Fail only when <math>t > (d - 1)/2 </math> so enumeration is complete and no solution has been found.

Note: "fail" is not returned unless ''t''&nbsp;>&nbsp;(''d''&nbsp;&minus;&nbsp;1)/2. We say that a linear ''<math>C''</math> is ''<math>t''</math>-error correcting if there is at most one codeword in B<sub>t</submath>B_t(v)</math>, for each <math>v</math> 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 ''kn'' code words in its basis and ''k'' rows in its ''generating matrix'') is generally referred to as an (''n'',&nbsp;''k'') code. Linear block codes are frequently denoted as [''n'',&nbsp;''k'',&nbsp;''d''] codes, where ''d'' refers to the code's minimum Hamming distance between any two code words.

(The [''n'',&nbsp;''k'',&nbsp;''d''] notation should not be confused with the (''n'',&nbsp;''M'',&nbsp;''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''.)

Line 69 ⟶ 70:

==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''&nbsp;+''d''&nbsp;=&nbsp;''n''&nbsp;+&nbsp;1 is called '''maximum distance separable''' or '''MDS'''. Such codes, when they exist, are in some sense best possible.

If ''C''₁ and ''C''₂ are two codes of length ''n'' and if there is a permutation ''p'' in the [[symmetric group]] ''S''_''n'' for which (''c''₁,...,''c''_''n'') in ''C''₁ if and only if (''c''_''p''(1),...,''c''_''p''(''n'')) in ''C''₂, then we say ''C''₁ and ''C''₂ 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''₁ isomorphically to ''C''₂ then we say ''C''₁ and ''C''₂ are '''equivalent'''.

''Lemma'': Any linear code is permutation equivalent to a code which is in standard form.

==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 journalarXiv|author=Etzion, Tuvi|author2=Raviv, Netanel|title=Equidistant codes in the Grassmannian|journal=arXiv preprint arXiv:1308.6231|year=2013|urleprint=https://arxiv.org/abs/1308.6231|class=math.CO}}</ref> In 1984 Arrigo Bonisoli determined the structure of linear one-weight codes over finite fields and proved that every equidistant linear code is a sequence of [[w:Dual code|dual]] [[Hamming code]]s.<ref>{{cite journal|author=Bonisoli, A.|year=1984|title=Every equidistant linear code is a sequence of dual Hamming codes|journal=Ars Combinatoria|volume=18|pages=181–186}}</ref>.

==Examples==

Some examples of linear codes include:

{{div col|colwidth=27em}}

* [[Repetition code]]s

* [[Parity code]]s

* [[Cyclic code]]s

* [[Hamming code]]s

* [[Golay code (disambiguation)|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

* [[GoppaAlgebraic geometry code]]s

* [[Binary Goppa code]]

* [[Low-density parity-check codes]]

* [[Expander code]]s

* [[Multidimensional parity-check code]]s

* [[Toric code]]s

* [[Turbo code]]s

* [[Locally recoverable code]]

{{div col end}}

==Generalization==

[[Hamming space]]s over non-field alphabets have also been considered, especially over [[finite ring]]s, (most notably [[Galois ring]]s over [[modulomodular arithmetic|'''Z'''₄]]). This givinggives 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^2m2''m'')) 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 |editorseditor=Massimiliano Sala, |editor2=Teo Mora, |editor3=Ludovic Perret, |editor4=Shojiro Sakata, |editor5=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|url=https://archive.org/details/introductiontoco0000lint_a3b9|url-access=registration|year=1999|publisher=Springer|isbn=978-3-540-64133-9|edition=3rd|at=Chapter 8: Codes over {{not a typo|ℤ}}₄}}</ref>

More recently,{{when|date=May 2015}} someSome authors have referred to such codes over rings simply as linear codes as well.<ref name="DoughertyFacchini2015">{{cite book |editorseditor=Steven Dougherty, |editor2=Alberto Facchini, |editor3=Andre Gerard Leroy, |editor4=Edmund Puczylowski, |editor5=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|authorsauthor=S.T. Dougherty, |author2=J.-L. Kim, |author3=P. Sole}}</ref>

== See also ==

Line 109 ⟶ 112:

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

==External links==

* [https://web.archive.org/web/20070927213247/http://jason.mchu.com/QCode/index.html ''q''-ary code generator program]

* [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.

* [http://z4codes.info/ The database of Z4 codes] Online, up to date database of optimal Z4 codes.