User:ECCclass/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 ƒ over F of degree less than K and listing the values of ƒ 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}^{\ell }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 (5): 652–656. doi:10.1109/TIT.1972.1054893.
• F.J. MacWilliams (1977). The Theory of Error-Correcting Codes. North-Holland. pp. 306–316. ISBN 0-444-85193-3. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

Category:Error detection and correction Category:Finite fields Category:Coding theory