Preparata code

2020 Mathematics Subject Classification: Primary: 94B [MSN][ZBL]

A class of non-linear binary double-error-correcting codes. They are named after Franco P. Preparata who first described them in 1968. Although non-linear over the finite field $\mathrm{GF}(2)$, it is known that the Kerdock and Preparata codes are linear over $\mathbb{Z}/4$.

Let $m$ be an odd number, and $n=2^m-1$. We first describe the extended Preparata code of length $2n+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 $\mathrm{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;
2. $\sum_{x \in X} x = \sum_{y \in Y} y$;
3. $\sum_{x \in x} x^3 + \left(\sum_{x \in X} x\right)^3 = \sum_{y \in Y} y^3$.

The Peparata code is obtained by deleting the position in $X$ corresponding to 0 in $\mathrm{GF}(2^m)$.

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, "A class of optimum nonlinear double-error-correcting codes", Information and Control 13 (1968) 378-400 DOI 0.1016/S0019-9958(68)90874-7
• J.H. van Lint, Introduction to Coding Theory (2nd ed), Springer-Verlag (1992) ISBN 3-540-54894-7 pp.111-113