Preparata code explained

In coding theory, the Preparata codes form a class of non-linear double-error-correcting codes. They are named after Franco P. Preparata who first described them in 1968.

Although non-linear over GF(2) the Preparata codes are linear over Z₄ with the Lee distance.

Construction

Let m be an odd number, and

n = 2 ^{m-1} . We first describe the extended Preparata code of length 2 n +2 = 2 ^{m+1} : the Preparata code is then derived by deleting one position. The words of the extended code are regarded as pairs (X, Y) of 2^m-tuples, each corresponding to subsets of the finite field GF(2^m) in some fixed way.

The extended code contains the words (X, Y) satisfying three conditions

1. X, Y each have even weight;

\sum _{x} x = \sum _{y} y; \sum _{x} x ^{3} + \left(\sum _{x} x\right) ^{3} = \sum _{y} y ^{3.}

The Preparata code is obtained by deleting the position in X corresponding to 0 in GF(2^m).

Properties

The Preparata code is of length 2^m+1 - 1, size 2^k where k = 2^m + 1 - 2m - 2, and minimum distance 5.

When m = 3, the Preparata code of length 15 is also called the Nordstrom–Robinson code.

References

• F.P. Preparata . Franco P. Preparata . A class of optimum nonlinear double-error-correcting codes . Information and Control . 13 . 1968 . 4 . 378–400 . 10.1016/S0019-9958(68)90874-7 . free . 2142/74662 . free .
• Book: J.H. van Lint . Introduction to Coding Theory . 2nd . Springer-Verlag . . 86 . 1992 . 3-540-54894-7 . 111–113 .
• http://www.encyclopediaofmath.org/index.php/Preparata_code
• http://www.encyclopediaofmath.org/index.php/Kerdock_and_Preparata_codes