Preparata code[1] 

Description

A nonlinear binary \((2^{m+1}-1, 2^{m+1}-2m-2, 5)\) code where \(m\) is odd. The size of this code is twice the size of the largest possible linear code with the same length and distance.

Codewords of extended Preparata codes can be thought of as characteristic functions of the tuple \((X,Y)\), where \(X, Y\) belong to \(GF(2)^m\), along with the following properties: (i) \(|X| = |Y| = 2^{m}\), (ii) \(\sum_{x \in X} x = \sum_{y \in Y} y \), and (iii) \(\sum_{x \in X} x^{3} + (\sum_{x \in X} x)^{3} = \sum_{y \in Y} y^{3} \). Preparata codes are obtained by leaving out the coordinate in the zeroth positions in the first half.

Rate

The rate is \(\frac{2^{m+1}-2m-2}{2^{m+1}-1}\).

Decoding

Preparata Codes can be decoded using a syndrome calculation based algorithm to correct all error patterns of Lee weight atmost 2 and detect all/ some error patterns of Lee weight 3/ 4 [2,3].

Notes

See corresponding MinT database entry [4].

Parents

  • Hergert code — Preparata codes are equivalent to Hergert codes for \(r=2\) [5; Thm. 2].
  • Nearly perfect code — Preparata codes are uniformly packed and nearly perfect [6]. For any word \(u\) and Preparata codebook \(C\) with \(d(u, C) > 2\), we have that \(u\) has a distance 2 or 3 to exactly floor((2^m+1-1)/3) codewords.
  • Small-distance block code

Child

Cousins

  • Quasi-perfect code — Punctured Preparata codes are quasi-perfect [7; pg. 475].
  • Reed-Muller (RM) code — A Preparata code can be written as a union of a linear subcode \(\mathcal{C}\) of RM\((m-2,m)\) and the \(2^{m-1}-1\) representatives of coset formed by \(\mathcal{C}\) in RM\((m-2,m)\). The coset representatives are given by \(|1|x^j|0|x^{j}\theta_{1}|\), where \(1\leq j \leq 2^{m-1}-1\). \(\mathcal{C}\) comprises of codewords of the form \(|g(1)|g(x)(1+\theta_{1})|f(1)+g(1)|g(x)(1+\theta_{1})+f(x)(1+\theta_{1}+\theta_{3})|\), where \(f(x)\) and \(g(x)\) are arbitrary, and where \(\theta_{1}\) and \(\theta_{3}\) denote the primitive idempotents corresponding to cyclotomic cosets \(C_1\) and \(C_3\) respectively.
  • Binary BCH code — Preparata codes contain twice as many code words as the double-error-correcting BCH codes of the same length, which is the largest number of code words possible for given length and distance [1].
  • Hamming code — Preparata codes can be obtained by Hensel-lifting Hamming codes to \(\mathbb{Z}_4\) [2]. The union of the dual a Preparata code and some of its translates forms a Hamming code [7; pg. 475].
  • Combinatorial design code — Preparata codewords of each weight form a 3-design [7; pg. 471].
  • Kerdock code — Preparata codes are duals of Kerdock codes in that their distance distribution is equal to the MacWilliams transform of the distance distribution of Kerdock codes [8]. However, the two codes are images of a pair of mutually dual linear codes over \(\mathbb{Z}_4\) under the Gray map [9][10; Sec. 6.3].

References

[1]
F. P. Preparata, “A class of optimum nonlinear double-error-correcting codes”, Information and Control 13, 378 (1968) DOI
[2]
A. R. Hammons et al., “The Z/sub 4/-linearity of Kerdock, Preparata, Goethals, and related codes”, IEEE Transactions on Information Theory 40, 301 (1994) DOI
[3]
A. R. Hammons Jr. et al., “The Z_4-Linearity of Kerdock, Preparata, Goethals and Related Codes”, (2002) arXiv:math/0207208
[4]
Rudolf Schürer and Wolfgang Ch. Schmid. “Preparata Codes.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2015-09-03. http://mint.sbg.ac.at/desc_CPreparata.html
[5]
P. Delsarte and J. M. Goethals, “Alternating bilinear forms over GF(q)”, Journal of Combinatorial Theory, Series A 19, 26 (1975) DOI
[6]
J. M. Goethals and S. L. Snover, “Nearly perfect binary codes”, Discrete Mathematics 3, 65 (1972) DOI
[7]
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[8]
W. Kantor, “On the inequivalence of generalized Preparata codes”, IEEE Transactions on Information Theory 29, 345 (1983) DOI
[9]
A. R. Calderbank et al., “A linear construction for certain Kerdock and Preparata codes”, (1993) arXiv:math/9310227
[10]
W. C. Huffman, J.-L. Kim, and P. Solé, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: preparata

Cite as:
“Preparata code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/preparata
BibTeX:
@incollection{eczoo_preparata, title={Preparata code}, booktitle={The Error Correction Zoo}, year={2023}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/preparata} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/preparata

Cite as:

“Preparata code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/preparata

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/bits/nonlinear/gray_map/duals/preparata.yml.