coding theory Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are stud ...

, the Preparata codes form a class of non-linear double-

error-correcting codes In computing, telecommunication, information theory, and coding theory, an error correction code, sometimes error correcting code, (ECC) is used for controlling errors in data over unreliable or noisy communication channels. The central idea is ...

. They are named after Franco P. Preparata who first described them in 1968. Although non-linear over

GF(2) (also denoted \mathbb F_2, or \mathbb Z/2\mathbb Z) is the finite field of two elements (GF is the initialism of ''Galois field'', another name for finite fields). Notations and \mathbb Z_2 may be encountered although they can be confused with ...

the Preparata codes are linear over Z₄ with the

Lee distance In coding theory, the Lee distance is a distance between two strings x_1 x_2 \dots x_n and y_1 y_2 \dots y_n of equal length ''n'' over the ''q''-ary alphabet of size . It is a metric defined as \sum_^n \min(, x_i - y_i, ,\, q - , x_i - y_i, ) ...

Construction

Let ''m'' be an odd number, and

n = 2^m-1

. We first describe the extended Preparata code of length

2n+2 = 2^

: 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 In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subt ...

GF(2^''m'') in some fixed way. The extended code contains the words (''X'', ''Y'') satisfying three conditions # ''X'', ''Y'' each have even weight; #

\sum_ x = \sum_ y;

\sum_ x^3 + \left(\sum_ x\right)^3 = \sum_ 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 − 2''m'' − 2, and minimum distance 5. When ''m'' = 3, the Preparata code of length 15 is also called the Nordstrom–Robinson code.

References

* * {{cite book , author=J.H. van Lint , title=Introduction to Coding Theory , edition=2nd , publisher=Springer-Verlag , series= GTM , volume=86 , date=1992 , isbn=3-540-54894-7 , page
111–113
, url=https://archive.org/details/introductiontoco0000lint/page/111 * http://www.encyclopediaofmath.org/index.php/Preparata_code * http://www.encyclopediaofmath.org/index.php/Kerdock_and_Preparata_codes Error detection and correction Finite fields Coding theory