Justesen code

In coding theory, Justesen codes form a class of error-correcting codes which are derived from Reed-Solomon codes and have good error-control properties.

Definition

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 α be a primitive element of F. For a codeword a = (a₁,...,a_N) from R, let 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 c be the vector of length 2N m obtained from b by expressing each element of F as a binary vector of length m. The Justesen code is the linear code containing all such c.

Properties

The parameters of this code are length 2m N, dimension m K and minimum distance at least

$\sum _{i=1}^{l}i{\binom {2m}{i}}.$

The Justesen codes are examples of concatenated codes.

References

• J. Justesen (1972). "A class of constructive asymptotically good algebraic codes". IEEE Trans. Info. Theory 18: 652-656.

• F.J. MacWilliams; N.J.A. Sloane (1977). The Theory of Error-Correcting Codes. North-Holland, 306-316. ISBN 0-444-85193-3.