# 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

MSC 94B65

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 may be attained 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

MSC 94B15

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

MSC 94B15

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 derived from Reed-Solomon codes which 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 distance 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 distance 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

MSC 94B65

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

MSC 94B65

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.

# 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. Parts I, II" (3rd repr.) North-Holland Mathematical Library 16 Elsevier (1985) ISBN 0-444-85193-3 Zbl 0657.94010
• Vera Pless, William Cary Huffman (edd), "Handbook of coding theory" (3 vols) (Elsevier, 1998) Zbl 0907.94001

# Linear code

MSC 94B05

A code of fixed length $n$ over a finite field $F$ which forms a subspace of the vector space $F^n$.

A linear code of rank $r$ may be represented by a generator matrix, an $(r \times n)$ matrix whose rows form a set of linearly independent code words. A generator matrix can be put in the form $G = (I_r | G_1)$ by row operations, showing that a linear code is necessarily a systematic code. The components of the code word corresponding to the columns of $G_1$ may be referred to as check digits.

A linear code $C$ has a dual code $C^\perp$ consisting of all vectors in $F^n$ orthogonal to every element of $C$ with respect to the bilinear form $(x,y) = \sum_{i=1}^n x_i y_i$. This is a linear code of rank $(n-r)$, and a basis for $C^\perp$ is a set of parity check vectors: a generator matrix for $C^\perp$ is a parity check matrix.

The syndrome of a received word $r \in F^n$ is the sequence of $n-r$ inner products $(r, p_i)$ where $p_i$ runs over the rows of a parity check matrix. A word is a codeword if and only if it has syndrome zero.

## 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

# Hamming bound

sphere-packing bound

A bound on the size of a code with given error-control capability. Let $C$ be a block code of length $n$ over an alphabet of size $q$ with minimum distance $2e+1$. Then the spheres of radiius $e$ with respect to the Hamming metric are disjoint, and letting $$V_q(n,e) = \sum_{r=0}^e \binom{n}{r} (q-1)^r$$ denote the volume of such a sphere, the number $m$ of words in the code is bounded by $$m \le q^n / V_q(n,e) \ .$$

A perfect code is one for which this bound is met. The Hamming codes are example of perfect codes with $e=1$.

## 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

# Perfect code

A block code which meets the Hamming bound: that is, has minimum distance $2e+1$ and for which the balls of radius $e$ in the Hamming metric exactly fill out the space of all possible words.

The Hamming codes are perfect, as are the Golay codes $(23,12,7)_2$ and $(11,6,5)_3$, and the trivial codes. There are perfect nonlinear codes with the same parameters as the Hamming codes, which are linear: there are no further perfect 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

# Alternant code

MSC 94Bxx

A class of parameterised error-correcting codes which generalise the BCH codes.

An alternant code over $GF(q)$ of length $n$ is defined by a parity check matrix $H$ of alternant form $H_{i,j} = \alpha_j^i y_i$, where the $\alpha_j$ are distinct elements of the extension $GF(q^m)$, the $y_i$ are further non-zero parameters again in the extension $GF(q^m)$ and the indices range as $i$ from 0 to $\delta-1$, $j$ from 1 to $n$.

They may equivalently de defined as the class of subcodes of generalised Reed–Solomon codes over $\mathrm{GF}(q^m)$ by restricting to the alphabet $\mathfm{GF}(q)$.

The parameters of this alternant code are length $n$, dimension $\ge n - m\delta$ and minimum distance $\ge \delta+1$. There exist long alternant codes which meet the Gilbert-Varshamov bound.

The class of alternant codes includes BCH codes, Goppa codes and Srivastava codes.

## References

• 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, pp.332-338

# Systematic code

MSC 94Bxx

An error-correcting code with words of length $n$ in which the message is encoded on a specific set of $r$ positions within the word, and the remaining $n-r$ positions may be regarded as check digits. A linear code is necessarily systematic, since it has a generator matrix $G$ which may be put in the form $G = ( I_r | G_1 )$ by row operations and column permutations.

## 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
How to Cite This Entry:
Richard Pinch/sandbox-codes. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Richard_Pinch/sandbox-codes&oldid=45795