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.

The dual code to the Hamming code 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