Linear code

In coding theory, a linear code is a special block code in which the code words are elements of a finite-dimensional vector space over a finite field . A code is linear if and only if it is a subspace of . ${\displaystyle \mathbb {F} _{q}^{n}}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle \mathbb {F} _{q}^{n}}$

Linear codes have the advantage that methods of linear algebra can be used. They are therefore easy to encode and decode. Most of the important codes are linear: Hamming code , low density parity check code , Reed-Muller code , Hadamard code , all cyclic codes (including BCH , Reed-Solomon codes , Golay codes and Goppa Codes ).

Is the vector space dimension of the linear code is equal , it is called a code or a Hamming distance of even code . ${\displaystyle C}$ ${\displaystyle k}$ ${\displaystyle C}$ ${\displaystyle [n,k]}$ ${\displaystyle d}$ ${\displaystyle [n,k,d]}$

properties

Since is a subspace of , there is a basis of . If you summarize this basis in a matrix ${\displaystyle C}$ ${\displaystyle V}$ ${\displaystyle g_{1},\dots ,g_{k}}$ ${\displaystyle C}$

${\displaystyle G={\begin{pmatrix}g_{1}\\\vdots \\g_{k}\end{pmatrix}}}$

together, a producer matrix is ​​obtained . The code also has a control matrix . It applies to them if and only if is a code word. The rank of is , which is of . The Hamming distance of is the minimum number of linearly dependent columns in the control matrix. ${\displaystyle H}$ ${\displaystyle Hc^{T}=0}$ ${\displaystyle c}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle H}$ ${\displaystyle n-k}$ ${\displaystyle C}$

The Hamming weight of a code word is equal to the number of those that are different from zero. For example, the code word has a Hamming weight of 4. The Hamming distance of the code is equal to the smallest Hamming weight of all code words except for the zero word. ${\displaystyle c=(c_{1},\dots ,c_{n})}$ ${\displaystyle c_{i}}$ ${\displaystyle (430540)}$ ${\displaystyle \mathbb {F} _{7}^{6}}$

If the individual coordinates of the code words are permuted, a so-called equivalent code is obtained . With this and by means of linear algebra , one can find an equivalent for every linear code, which has a generator matrix of the form . Where is the - identity matrix , and is a - matrix. Then it is called producer matrix in a reduced form. The first coordinates can be interpreted as information symbols and the last as control symbols. Is a generator matrix in reduced form, a control matrix can be found immediately . A linear code is already determined by its generator matrix or its control matrix. ${\displaystyle G=(\mathbb {E} _{k}|P)}$ ${\displaystyle \mathbb {E} _{k}}$ ${\displaystyle (k\times k)}$ ${\displaystyle P}$ ${\displaystyle (k\times (n-k))}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle n-k}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle H=(-P^{T}|\mathbb {E} _{n-k})}$

example

The binary - Hamming code has the following generator matrix in reduced form and the associated control matrix: ${\displaystyle [7,4,3]}$

${\displaystyle G=(\mathbb {E} _{k}|P)}$		${\displaystyle H=(-P^{T}|\mathbb {E} _{n-k})}$
${\displaystyle G={\begin{pmatrix}{\color {Brown}1}&0&0&0&1&1&0\\0&{\color {Brown}1}&0&0&1&0&1\\0&0&\color {Brown}{1}&0&1&1&1\\0&0&0&{\color {Brown}1}&0&1&1\\\end{pmatrix}}\qquad }$		${\displaystyle H={\begin{pmatrix}1&1&1&0&{\color {Brown}1}&0&0\\1&0&1&1&0&{\color {Brown}1}&0\\0&1&1&1&0&0&{\color {Brown}1}\\\end{pmatrix}}}$

Coding

A word from space is encoded by forming the product . The encoding of the word with the - Hamming code illustrated example, the following statement. ${\displaystyle x=(x_{1},\dots ,x_{k})}$ ${\displaystyle \mathbb {F} _{q}^{k}}$ ${\displaystyle xG}$ ${\displaystyle (0,0,1,1)}$ ${\displaystyle [7,4,3]}$

${\displaystyle {\begin{aligned}x\cdot G&=c\\{\begin{pmatrix}0,0,1,1\end{pmatrix}}\cdot {\begin{pmatrix}1&0&0&0&1&1&0\\0&1&0&0&1&0&1\\0&0&1&0&1&1&1\\0&0&0&1&0&1&1\\\end{pmatrix}}&={\begin{pmatrix}0,0,1,1,1,0,0\end{pmatrix}}\end{aligned}}}$

Since the addition takes place in here, the following applies ${\displaystyle \mathbb {F} _{2}}$ ${\displaystyle 1+1=0}$

Decoding

With the decoding associating is called a received, possibly faulty input vector  to a code vector  . The decoding is not the reverse function of the coding, which assigns a vector to a code vector . ${\displaystyle x}$ ${\displaystyle c'}$ ${\displaystyle \mathbb {F} _{q}^{k}}$

As a decoding method which is in the coding theory most maximum-likelihood (English: maximum likelihood decoding ) is used. A received vector is decoded into the code vector which is most likely identical to the code  vector  actually sent  . Often the vector in which the fewest places (errors) need to be corrected is assumed to be the most likely. In mathematical terms, this means looking for the code  vector with the smallest Hamming distance to the vector received  . This case is also a method of nearest neighbors (English: nearest neighbor decoding ), respectively. By knowing the type of data being sent or the channel being used, other information may be used to determine the likelihood of certain code vectors. ${\displaystyle x}$ ${\displaystyle c'}$ ${\displaystyle c}$ ${\displaystyle c'}$ ${\displaystyle x}$

Let it be the actually sent (code) vector and the received vector. The decoding searches for the code vector or vectors that were most likely sent from all code vectors . ${\displaystyle c}$ ${\displaystyle x}$ ${\displaystyle q^{n}}$ ${\displaystyle c'}$

${\displaystyle c'=\operatorname {argmax} _{y\in C}\left\{\operatorname {P} \left[y=c\right]\right\}}$

With the nearest neighbor decoding :

${\displaystyle c'=\operatorname {argmin} _{y\in C}\left\{wt(x-y)\right\}}$

It should be noted that this assignment is not unique for most codes for all error vectors. There are then some error vectors that cannot be assigned because they have more than one nearest neighbor. If a unique decoding is possible for each error vector, the code is called perfect .

Syndrome decoding

A more efficient method for decoding is so-called syndrome decoding . The syndrome of a vector is obtained by multiplying the control matrix  with . ${\displaystyle s_{x}}$ ${\displaystyle x}$ ${\displaystyle H}$ ${\displaystyle x^{T}}$

${\displaystyle s_{x}^{T}=Hx^{T}}$

Let it be the error vector of . In are exactly the coordinates not equal to zero, for which errors occurred during the transfer. ${\displaystyle e=x-c}$ ${\displaystyle x}$ ${\displaystyle e}$

Because of the linearity of the code, the following applies to the syndrome of : ${\displaystyle x}$

${\displaystyle s_{x}^{T}=Hx^{T}=Hc^{T}+He^{T}}$

Since the syndrome of error-free code vectors is always zero, it follows:

${\displaystyle s_{x}^{T}=He^{T}=s_{e}^{T}}$

All (incorrect) words with the same error vector are in the same affine subspace , i.e. the syndrome is constant for such words . ${\displaystyle s_{e}^{T}=He^{T}}$

All vectors that have emerged from any fixed vector by subtracting any code vector form a subsidiary class of the subgroup of . The vector with minimal weight in this class is called the leader of the secondary class (English: coset leader ). This is why the term “coset leader decoding” is widely used. ${\displaystyle C}$ ${\displaystyle \mathbb {F} _{q}^{n}}$

In order to decode, one looks for the error vector  whose syndrome is identical to the syndrome of and whose Hamming weight is minimal. This error vector is used to calculate the closest code  vector . You can therefore set up a table with up to rows that contains the corresponding error vector with minimal Hamming weight for each syndrome of a received vector. If the syndrome is 0, then nothing needs to be corrected, otherwise decoding is limited to looking up the error vector in this table and correcting the errors detected in this way. ${\displaystyle x}$ ${\displaystyle c'}$ ${\displaystyle e'}$ ${\displaystyle x}$ ${\displaystyle c'=x-e'}$ ${\displaystyle c'}$ ${\displaystyle q^{n-k}}$

Interpreted differently, the secondary classes are precisely the equivalence classes of the equivalence relation. The leaders are representatives of the equivalence classes, one chooses one with a minimal Hamming weight. Perfect codes are characterized by the fact that the leaders are clearly established. ${\displaystyle x\equiv y\Leftrightarrow s_{x}^{T}=s_{y}^{T}}$

The decoding of linear codes is generally NP-complete , i.e. no algorithms with a polynomial running time are known. The known linear codes, for example Hamming codes, are distinguished by the fact that efficient decoding algorithms are known for them. The complexity of linear decoding is the basis for the McEliece cryptosystem , which is considered secure, but has so far rarely been used due to its comparatively long keys.

example

Will you to decode Hamming code (from above), we come out the assumption that only - Bit errors occur. The possible error vectors are then ${\displaystyle [7,4,3]}$ ${\displaystyle 1}$ ${\displaystyle e}$

${\displaystyle (1,0,0,0,0,0,0)}$

${\displaystyle (0,1,0,0,0,0,0)}$

${\displaystyle (0,0,1,0,0,0,0)}$

${\displaystyle (0,0,0,1,0,0,0)}$

${\displaystyle (0,0,0,0,1,0,0)}$

${\displaystyle (0,0,0,0,0,1,0)}$

${\displaystyle (0,0,0,0,0,0,1)}$

The syndrome is now calculated for each of these error vectors . This results in ${\displaystyle s^{T}=He^{T}}$

${\displaystyle e}$	${\displaystyle s}$
${\displaystyle (1,0,0,0,0,0,0)}$	${\displaystyle (1,1,0)}$
${\displaystyle (0,1,0,0,0,0,0)}$	${\displaystyle (1,0,1)}$
${\displaystyle (0,0,1,0,0,0,0)}$	${\displaystyle (1,1,1)}$
${\displaystyle (0,0,0,1,0,0,0)}$	${\displaystyle (0,1,1)}$
${\displaystyle (0,0,0,0,1,0,0)}$	${\displaystyle (1,0,0)}$
${\displaystyle (0,0,0,0,0,1,0)}$	${\displaystyle (0,1,0)}$
${\displaystyle (0,0,0,0,0,0,1)}$	${\displaystyle (0,0,1)}$

If the incorrect word is then received, then results . This results in the error vector and is thus decoded. The plaintext word is then . ${\displaystyle x=(0,1,1,1,1,0,0)}$ ${\displaystyle s^{T}=Hx^{T}=(1,0,1)^{T}}$ ${\displaystyle e=e((1,0,1))=(0,1,0,0,0,0,0)}$ ${\displaystyle x}$ ${\displaystyle c(x)=(0,1,1,1,1,0,0)-(0,1,0,0,0,0,0)=(0,0,1,1,1,0,0)}$ ${\displaystyle (0,0,1,1)}$

Example with incomplete decoding

The ternary ( ) repetition code of length 3 is given: ${\displaystyle q=3}$

${\displaystyle G={\begin{pmatrix}1&1&1\end{pmatrix}}\qquad }$

${\displaystyle H={\begin{pmatrix}2&1&0\\2&0&1\\\end{pmatrix}}}$

Every two columns of are linearly independent, whereas all three are linearly dependent. The minimum Hamming distance of the code is calculated as the minimum number of linearly dependent columns in 3. This means that at most one character error can be corrected. The syndrome table looks like this: ${\displaystyle H}$ ${\displaystyle H}$

${\displaystyle e}$	${\displaystyle s}$
${\displaystyle (1,0,0)}$	${\displaystyle (2,2)}$
${\displaystyle (2,0,0)}$	${\displaystyle (1,1)}$
${\displaystyle (0,1,0)}$	${\displaystyle (1,0)}$
${\displaystyle (0,2,0)}$	${\displaystyle (2,0)}$
${\displaystyle (0,0,1)}$	${\displaystyle (0,1)}$
${\displaystyle (0,0,2)}$	${\displaystyle (0,2)}$

By using linearities, the number of rows could be halved, but then you have to test whether there is a linearly dependent syndrome in the table.

Now consider , . When the syndrome is , the correction is: . The calculation of the syndrome of results: . This value is not in the syndrome table, so the word cannot be corrected. ${\displaystyle x=(1,1,0)}$ ${\displaystyle y=(1,2,0)}$ ${\displaystyle x}$ ${\displaystyle Hx^{t}=(0,2)^{t}}$ ${\displaystyle (1,1,0)-(0,0,2)=(1,1,1)}$ ${\displaystyle y}$ ${\displaystyle Hy^{t}=(1,2)^{t}}$

application

The coding and decoding, as described above, is relatively complex. During the coding, the generator matrix must be kept in memory, which is problematic in systems with limited resources (for example mobile devices or space probes). A large table is required for decoding, depending on the correction rate; the memory consumption is correspondingly large. For this reason, additional properties of the codes are usually used in order to encode and decode them efficiently. Binary cyclic codes can be implemented very easily using shift registers and exclusive-or gates , for example .

Dual code

For every (linear) code there is a dual code (or also dual code) , which is itself a linear code. The code words of the dual code are all words that are dual to the code words : ${\displaystyle C}$ ${\displaystyle C^{\perp }}$ ${\displaystyle \mathbb {F} _{q}^{n}}$ ${\displaystyle C}$

An inner product is defined for this:

${\displaystyle \langle \cdot ;\cdot \rangle \,:\;\mathbb {F} _{q}^{n}\times \mathbb {F} _{q}^{n}\to \mathbb {F} _{q}}$

which maps the vectors as follows: ${\displaystyle x=(x_{1},x_{2},\dots ,x_{n}),y=(y_{1},y_{2},\dots ,y_{n})}$

${\displaystyle \langle x;y\rangle =\sum _{i=1}^{n}x_{i}y_{i}}$

Despite the similar definition, this is not a scalar product because this bilinear form is not positive definite . Because of the properties of finite fields there are mostly vectors that are not equal to the zero vector and for which the inner product is 0. Think of the binary vector, for example . ${\displaystyle (1,1)}$

With the help of this definition, the dual code results as:

${\displaystyle C^{\perp }=\{x\in \mathbb {F} _{q}^{n}\mid \langle x,c\rangle =0\;\mathrm {f{\ddot {u}}r\;alle} \;c\in C\}}$

A generator matrix of the dual code is a control matrix of the source code and vice versa.

The dual code plays an important role in analyzing the properties of codes.

The so-called self-dual codes are a special case. These are codes that are identical to their dual code. For dimensional reasons, these always have the dimension . The most important example of a self-dual code is the extended Hamming code, in which the binary [7,4,3] Hamming code is extended by one parity bit to even parity: ${\displaystyle k=n/2}$

${\displaystyle G=H={\begin{pmatrix}1&0&0&0&1&1&0&1\\0&1&0&0&1&0&1&1\\0&0&1&0&1&1&1&0\\0&0&0&1&0&1&1&1\\\end{pmatrix}}}$

literature

• Werner Lütkebohmert : Coding Theory. Algebraic-geometric basics and algorithms. Vieweg Verlag, Braunschweig u. a. 2003, ISBN 3-528-03197-2 ( Vieweg course - advanced course in mathematics ).
• JH van Lint : Introduction to Coding Theory. 3rd revised and expanded edition. Springer Verlag, Heidelberg u. a. 1999, ISBN 3-540-64133-5 ( Graduate texts in mathematics 86).
• Florence J. MacWilliams , Neil J. Sloane : The Theory of Error-Correcting Codes. 2. Printing. North-Holland publishing company, Amsterdam 1978, ISBN 0-444-85009-0 ( North Holland mathematical library 16).

Individual evidence

1. ^ ER Berlekamp, ​​RJ McEliece, HCA von Tilburg: On the inherent intractability of certain coding problems . In: IEEE Transactions on Information Theory 24 . 1978.