User:Richard Pinch/sandbox-codes

Reed–Solomon code

A family of linear codes defined over finite fields. Let $F = \mathbf{F}_q$ and put $n = q-1$. Let $\beta$ be a primitive element of $F^*$. For an integer $k \le n$, let $L_k$ denote the vector space of polynomials over $F$ of degree $\le k-1$, and let $E$ be the evaluation map $e : L_k \rightarrow F^n$ given by $$ E : f \mapsto \left({ f(\beta), f(\beta^2), \ldots, f(\beta^n) }\right) \ . $$

The image $E[L_k]$ is a subspace of $F^n$ and constitutes the Reed–Solomon code $\mathrm{RS}(q,k)$. It is a primitive BCH code.

The map $E$ is injective, as a non-zero polynomial of degree $k<n$ cannot be zero at $n$ distinct values. The rank of the code is thus $k$. The minimum weight is $n-k+1$, corresponding to a polynomial with $k-1$ zeroes all in $F$. The Reed–Solomon code thus meets the singleton bound and is an MDS code.

More generally, we may prescribe a set of $n$ evaluation points, $k \le n \le q-1$, distinct elements $\mathbf{x} = (x_1,\ldots,x_n)$ of $F$, and non-zero weights $ \mathbf{y} = (y_i)$. The generalised Reed–Solomon code is defined by the evaluation map $$ E : f \mapsto \left({ y_1 f(x_1), \ldots, y_n f(x_n) }\right) \ . $$ The image is of rank $n$ and minimum weight $n-k+1$: it is denoted $\mathrm{GRS}_k(\mathbf{x}, \mathbf{y})$. The dual code is $\mathrm{GRS}_{n-k}(\mathbf{x}, \mathbf{y'})$ for some $ \mathbf{y'}$.

References

• C.M. Goldie, R.G.E. Pinch, Communication theory, London Mathematical Society Student Texts. 20 Cambridge University Press (1991) ISBN 0-521-40456-8 Zbl 0746.94001
• J.H. van Lint, "Introduction to coding theory" (2nd ed.) Graduate Texts in Mathematics 86 Springer (1992) ISBN 3-540-54894-7 Zbl 0747.94018
• F.J. MacWilliams, N.J.A. Sloane, "The Theory of Error Correcting Codes", (Elsevier, 1977). Zbl 0369.94008
• H. Stichtenoth, "Algebraic function fields and codes", Universitext, Springer (1993) ISBN 3-540-58469-6 Zbl 0816.14011

Singleton bound

A constraint on the parameters of a linear block code. If a code has length $n$, rank $k$ and minimum distance $d$, then $$ k+d \le n+1 \ . $$ The bound is obtained by repeatedly shortening a code $C$: selecting the subcode consisting of all words with the symbol $0$ in a specific position and then deleting that position from all words.

A code for which equality holds is a maximum distance separable or MDS code. Examples of MDS codes are the Reed–Solomon codes, which show that if $n \le q+1$ there are MDS codes over $\mathbf{F}_q$ of rank $k$ for all $k< n$. The dual code to a linear MDS code is again an MDS code.

The weight enumerator of an MDS code is determined by its parameters $(n,k,d)$. The number of codewords of Hamming weight $i$ is $$ A_i = \binom{n}{i} \sum_{j=0}^{i-d} (-1)^j \binom{i}{j} (q^{i+1-d-j} - 1) $$

The MDS conjecture states that an MDS code with rank $k$ over the field of $q$ elements has length $n \le q+1$, except in the case $q$ a power of 2 and $k = 3$ or $q-1$ when $n \le q+2$. These bounds are achieved by Reed--Solomon codes.

References

• C.M. Goldie, R.G.E. Pinch, Communication theory, London Mathematical Society Student Texts. 20 Cambridge University Press (1991) ISBN 0-521-40456-8 Zbl 0746.94001
• J.H. van Lint, "Introduction to coding theory" (2nd ed.) Graduate Texts in Mathematics 86 Springer (1992) ISBN 3-540-54894-7 Zbl 0747.94018
• F.J. MacWilliams, N.J.A. Sloane, "The theory of error-correcting codes. Parts I, II" (3rd repr.) North-Holland Mathematical Library 16 Elsevier (1985) ISBN 0-444-85193-3 Zbl 0657.94010
• H. Stichtenoth, "Algebraic function fields and codes", Universitext, Springer (1993) ISBN 3-540-58469-6 Zbl 0816.14011

BCH code

A cyclic code over a finite field. Fix length $n$ and ground field $\mathbf{F}_q$ and a design distance parameter $\delta$. Let $\beta$ be a primitive $n$-th root of unity in a suitable extension of $\mathbf{F}_q$. The generator of the cyclic code is the least common multiple $g$ of the minimal polynomials (over $\mathbf{F}_q$) of the elements $\beta^1, \beta^2, \ldots, \beta^{\delta-1}$.

The minimum distance of the BCH code generated by $g$ is at least $\delta$: this is the BCH bound.

As an example, let $q=2$ and $\beta$ be a primitive $7$-th root of unity in $\mathrm{F}_{8}$: we may take $\beta$ to satisfy the polynomial $x^3 + x + 1$. Choose $\delta = 3$. The minimal polynomial for $\beta^2$ is the same as that of $\beta$, so that the cyclic code is generated by the word $1101000$. This is in fact the Hamming [7,4] code.

References

• C.M. Goldie, R.G.E. Pinch, Communication theory, London Mathematical Society Student Texts. 20 Cambridge University Press (1991) ISBN 0-521-40456-8 Zbl 0746.94001

Hamming code

A binary block code capable of error correction: see Error-correcting code.

The Hamming $[7,4]$ code has generator matrix with first row $1101000$ and the others being its three right shifts. It is a cyclic code, and indeed a BCH code with design distance $3$. It is perfect, because the balls of radius $1$ about the codewords have eight elements and the 16 balls precisely fill out the 7-dimensional space.

More generally, the binary $[2^{r-1}-1,r,3]$ Hamming code may be described in terms of its parity check matrix, which has $r$ rows and $2^r-1$ columns containing the binary expansions of the numbers $1,\ldots,2^r-1$. The syndrome of a word with a single error thus spells out the number of the position in error.

The dual code to the Hamming code, having the partity check matrix as generator, is the simplex code.

References

• C.M. Goldie, R.G.E. Pinch, Communication theory, London Mathematical Society Student Texts. 20 Cambridge University Press (1991) ISBN 0-521-40456-8 Zbl 0746.94001

Cyclic code

A block code over a finite field for which the code words have cyclic symmetric: any cyclic permutation of a code word is again a code word. A linear code of length $n$ over the field $k$ may be identified with polynomials of degree $< n$ over $k$ in an indeterminate $X$: the cyclic symmetry condition states that the code is invariant under multiplication by $X$ modulo $X^n-1$, so that the code may be identified with an ideal of the quotient ring $k[X]/\langle X^n-1 \rangle$. Since the polynomial ring $k[X]$ is a principal ideal domain, the codes are all principal ideals, and hence are determined by their generator polynomials, which must be factors of $X^n-1$.

References

• C.M. Goldie, R.G.E. Pinch, Communication theory, London Mathematical Society Student Texts. 20 Cambridge University Press (1991) ISBN 0-521-40456-8 Zbl 0746.94001
• van Lint, J.H., "Introduction to coding theory" (2nd ed.) Graduate Texts in Mathematics 86 Springer (1992) ISBN 3-540-54894-7 Zbl 0747.94018

Justesen code

A class of error-correcting codes which are derived from Reed-Solomon codes and have good error-control properties.

Let $R$ be a Reed-Solomon code of length $N = 2^m-1$, rank $K$ and minimum weight $N-K+1$. The symbols of $R$ are elements of $F=GF(2^m)$ and the codewords are obtained by taking every polynomial $f$ over $F$ of degree less than $K$ and listing the values of $f$ on the non-zero elements of $F$ in some predetermined order. Let $\alpha$ be a primitive element of $F$. For a codeword $\mathbf{a} = (a_1,\ldots,a_N)$ from $R$, let $\mathbf{b}$ be the vector of length $2N$ over $F$ given by $$ \mathbf{b} = \left( a_1, a_1, a_2, \alpha^1 a_2, \ldots, a_N, \alpha^{N-1} a_N \right) $$ and let $\mathbf{c}$ be the vector of length $2Nm$ obtained from $\mathbf{b}$ by expressing each element of $F$ as a binary vector of length $m$. The Justesen code is the linear code containing all such $\mathbf{c}$.

The parameters of this code are length $2mN$, dimension $mK$ and minimum distance at least $$ \sum_{i=1}^l i \binom{2m}{i} \ . $$ The Justesen codes are examples of concatenated codes.

References

• J. Justesen; A class of constructive asymptotically good algebraic codes, IEEE Trans. Info. Theory, 18 (1972), pp. 652-656
• F.J. MacWilliams; N.J.A. Sloane; The Theory of Error-Correcting Codes, , pp. 306-316, North-Holland ISBN: 0-444-85193-3

Distance enumerator

The distribution of Hamming distances between elements of a code, expressed as a polynomial. Let $C$ be a code of length $n$ over an alphabet $F$ and let $A_k$ be the number of pairs $x,y$ of words of $C$ of at Hamming distance $d(x,y) = k$. The weight enumerator $$ W_C(z) = \sum_{k=0}^n A_k z^k = \sum_{x,y \in C} z^{d(x,y)} \ . $$ It is also common to express the weight enumerator as a homogeneous binary form $$ W_C(x,y) = \sum_{k=0}^n A_k x^k y^{n-k} \ . $$

We have $W_C(0) = |C|$ and $W_C(1) = |C|^2$, where $|C|$ is the number of words in $C$.

The weight enumerator similarly expresses the distribution of Hamming weights of elements of a code, expressed as a polynomial. Let $C$ be a code of length $n$ over an alphabet $F$ and let $A_k$ be the number of of words of $C$ of weight $k$. The weight enumerator $$ W_C(z) = \sum_{k=0}^n A_k z^k = \sum_{x \in C} z^{w(x)} $$ where $w(x)$ is the weight of the word $x$. It is also common to express the weight enumerator as a homogeneous binary form $$ W_C(x,y) = \sum_{k=0}^n A_k x^k y^{n-k} \ . $$

We have $W_C(0) = 1$ or $0$, depending on whether the zero word is in $C$ or not, and $W_C(1) = |C|$, the number of words in $C$.

The MacWilliams identities relate the weight enumerator of a linear code over a finite field $\mathbf{F}_q$ to the enumerator of the dual code $C^\perp$: $$ W_{C^\perp}(x,y) = \frac{1}{|C|} W_C(x + (q-1)y, x-y) \ . $$

References

• Goldie, Charles M.; Pinch, Richard G.E. Communication theory, London Mathematical Society Student Texts. 20 Cambridge University Press (1991) iSBN 0-521-40456-8 Zbl 0746.94001
• van Lint, J.H., "Introduction to coding theory" (2nd ed.) Graduate Texts in Mathematics 86 Springer (1992) ISBN 3-540-54894-7 Zbl 0747.94018

Equidistant code

A code in which all distinct words are at the same Hamming distance.

The ternary linear code of length 13 and rank 3 with generator matrix $$ \left[{ \begin{array}{ccccccccccccc} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 2 & 2 & 2 \\ 1 & 0 & 1 & 2 & 0 & 1 & 2 & 0 & 1 & 2 & 0 & 1 & 2 \\ \end{array} }\right] $$ is an equidistant code of distance $9$.

References

• van Lint, J.H., "Introduction to coding theory" (2nd ed.) Graduate Texts in Mathematics 86 Springer (1992) ISBN 3-540-54894-7 Zbl 0747.94018

Plotkin bound

A bound on the number of words in a code of length $n$ and minimum distance $d$ over an alphabet of $q$ letters. Put $t = 1-1/q$. Suppose that $d > tn$. The size of such a code is at most $$ \frac{d}{d - tn} $$ A code achieving this bound is necessarily an equidistant code.

References

• van Lint, J.H., "Introduction to coding theory" (2nd ed.) Graduate Texts in Mathematics 86 Springer (1992) ISBN 3-540-54894-7 Zbl 0747.94018

Griesmer bound

A bound on the length of a linear code with rank $k$ and minimum distance $d$ over an alphabet of $q$ letters. The length of such a code is at least $$ \sum_{i=0}^{k-1} \left\lceil{ \frac{d}{q^i} }\right\rceil $$

Examples of codes meeting the Griesmer bound are the simplex code and the $[11,6,5]$ ternary Golay code.

References

• van Lint, J.H., "Introduction to coding theory" (2nd ed.) Graduate Texts in Mathematics 86 Springer (1992) ISBN 3-540-54894-7 Zbl 0747.94018
• Tor Helleseth, "On codes meeting the Griesmer bound", Information and Control 50 (1981) 128–159 DOI 10.1016/S0019-9958(81)90184-4. Zbl 0491.94021

Simplex code

A binary linear code, dual to the Hamming code. It has rank $r$ and length $n = 2^r - 1$, with minimum distance $2^{r-1}$. It is an equidistant code, and meets the Griesmer bound.

It may be generated as the row space of the $r$-row matrix with $2^r-1$ columns containing the binary expansions of the numbers $1,\ldots,2^r-1$.

References

• van Lint, J.H., "Introduction to coding theory" (2nd ed.) Graduate Texts in Mathematics 86 Springer (1992) ISBN 3-540-54894-7 Zbl 0747.94018
• F.J. MacWilliams, N.J.A. Sloane, "The Theory of Error Correcting Codes", (Elsevier, 1977). Zbl 0369.94008
• Vera Pless, William Cary Huffman (edd), "Handbook of coding theory" (3 vols) (Elsevier, 1998) Zbl 0907.94001